Search

'Sequential assignment match processes' is a term that refers to models where M random 'offers' arriving sequentially are paired with N waiting 'candidates.' Matching between a candidate and an offer is done one at a time, and an offer that has been accepted or declined is no longer available for future assignments. A sequential matching problem is considered in which each of the waiting candidates, as well as each of the arriving offers, is distinguished by a fixed-length vector of random attribute obtained from a known, discrete-value, joint probability distribution function. The greater the compatibility between the assignment and the offer, the bigger the reward realized by the matching. Several cases are analyzed, including the general case where M is greater than or equal to N, special cases where M is equal to N and where M is greater than N, and the case where not all candidates must be assigned.

Markov decision processes (MDPs) are used to describe and control large and complicated stochastic systems. MDPs require efficient computational procedures such as the value iteration algorithm. Two innovations to this procedure for solving discounted MDPs, based on one-step lookahead analysis, are proposed. The approach involves tha application of two criteria that yield good adaptive relaxation factors: minimum difference and minimum variance. These considerably speed up algorithmic convergence. The proposed procedure is tested using several sample problems, including Howard's automobile replacement problem. The results indicate that the procedure yields savings in computation times compared to those associated with existing value iteration procedures. The proposed method has been demonstrated using real-life problems in cellular telephony.

Optimal scheduling policies for minimizing the anticipated completion time and the variance of completion time are presented for the sequential processing of a number of jobs on a single machine. Jobs can deteriorate while they are waiting to be processed, which causes processing time to increase. The completion time, as well as the processing time, is a function of the scheduling policy.

Analyzes the optimal storage allocation for serial files. Concept of serial files; Need for simple allocation rules to close the gap between theory and application; Introduction of model and various optimization criteria.

We consider a two-server service system in which idle servers produce and store preliminary services for reducing the sojourn time of incoming customers and increasing customers arrival rate. We model the system as a Markovian process and provide a method, based on matrix geometric (MG) analysis, to obtain closed-form solutions to the steady state probabilities and relevant performance measures. We show the relation of the elements in the rate matrix of the MG to Catalan numbers, and prove that the stability condition remains as is in the traditional M/M/2 queue, although the expected sojourn time of customers has been reduced. We provide an economic analysis for a system in which the PS capacity and the investment to increase customers’ arrival rate are decision variables.

A time-dependent mathematical stopping problem is stated such that it applies to decisions of whether to accept kidneys offered for transplantation. The value of kidney offerings are modeled as a sequence of variables that are independent, randomly distributed and positive. The problem ends (or stops) each time a decision is made to accept a kidney offered. In addition, a first-order differential equation is devised to calculate control-limit functions associated with non-homogeneous Poisson arrivals of kidney offers to the system. The models and equations developed by the research are applied to cases of actual kidney offerings, acceptance, and transplantation.

Systems whose arrival or service rates fluctuate over time are very common, but are still not well understood analytically. Stationary formulas are poor predictors of systems with fluctuating load. When the arrival and service processes fluctuate in a Markovian manner, computational methods, such as Matrix-analytic and spectral analysis, have been instrumental in the numerical evaluation of quantities like mean response time. However, such computational tools provide only limited insight into the functional behavior of the system with respect to its primitive input parameters: the arrival rates, service rates, and rate of fluctuation.For example, the shape of the function that maps rate of fluctuation to mean response time is not well understood, even for an M/M/1 system. Is this function increasing, decreasing, monotonic? How is its shape affected by the primitive input parameters? Is there a simple closed-form approximation for the shape of this curve? Turning to user experience: How is the performance experienced by a user arriving into a "high load" period different from that of a user arriving into a "low load" period, or simply a random user. Are there stochastic relations between these? In this paper, we provide the first answers to these fundamental questions.

Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absenteeof servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/cqueue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline.Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absenteeof servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/cqueue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline.

We explore visit-order policies in nonsymmetric polling systems with switch-in and switch-out times, where service is in batches of unlimited size. We concentrate on so-called “Hamiltonian tour” policies in which, in order to give a fair treatment to the various users, the server attends every nonempty queue exactly once during each round of visits (cycle). The server dynamically generates a new visit schedule at the start of each round, depending on the current state of the system (number of jobs in each queue) and on the various nonhomogeneous system parameters. We consider three service regimes, globally gated, (locally) gated, and exhaustive, and study three different performance measures: (1) minimizing the expected weighted sum of all sojourn times of jobs within a cycle; (2) minimizing the expected length of the next cycle, and (3) maximizing the expected weighted throughput in a cycle. For each combination of performance measure and service regime, we derive characteristics of the optimal Hamiltonian tour. Some of the resulting optimal policies are shown to be elegant index-type rules. Others are the solutions of deterministic NP-hard problems. Special cases are reduced to assignment problems with specific cost matrices. The index-type rules can further be used to construct fixed-order, cyclic-type polling tables in cases where dynamic control is not applicable.

We compare two routing-control strategies in a high-speed communication network with cparallel channels (routes), where information on service completions in down-stream servers is randomly delayed. The controller can either hold arriving messages in a common buffer, dispatching them to servers only when the delayed information becomes available (Wait option), or route jobs to the various channels, in a round-robin fashion, immediately upon their arrival. Interpreting the delays as servers's vacations and considering overall queue sizes as a measure of performance, we show that the Wait strategy is superior as long as the mean information delay is below a threshold. We calculate threshold values for various combinations of load and cand show that, for a given load, the threshold increases with cand, for fixed c, the threshold decreases with an increasing load. If information is delayed on arrival instants, rather than on service completions, we show that the system can be viewed as a tandem queue and derive a generalization of a queue-decomposition result obtained by Altman, Kofman and Yechiali.

Two random traffic streams are competing for the service time of a single server (multiplexer). The streams form two queues, primary (queue 1) and secondary (queue 0). The primary queue is served exhaustively, after which the server switches over to queue 0. The duration of time the server resides in the secondary queue is determined by the dynamic evolution in queue 1. If there is an arrival to queue 1 while the server is still working in queue 0, the latter is immediately gated, and the server completes service there only to the gated jobs, upon which it switches back to the primary queue. We formulate this system as a two-queue polling model with a single alternating server and with randomly-timed gated (RTG) service discipline in queue 0, where the timer there depends on the arrival stream to the primary queue. We derive Laplace–Stieltjes transforms and generating functions for various key variables and calculate numerous performance measures such as mean queue sizes at polling instants and at an arbitrary moment, mean busy period duration and mean cycle time length, expected number of messages transmitted during a busy period and mean waiting times. Finally, we present graphs of numerical results comparing the mean waiting times in the two queues as functions of the relative loads, showing the effect of the RTG regime.

Closed polling systems with station breakdowns, under the gated, exhaustive or globally gated services regimes, are studied and analyzed. Multi-dimensional sets of probability generating functions of the system's state are derived. They are further utilized to obtain an approximate solution for the mean number of jobs residing in the system's various queues at polling instants. The analysis is then concentrated on the case of cyclic Bernoulli polling. Explicit formulae for the mean number of jobs, as well as for the expected cycle duration and system utilization, are derived. Comparison of the throughputs of the three regimes concludes the paper.

The expected steady-state waiting time, Wq(s), in a GI/M/ssystem with interarrival-time distribution H(·) is compared with the mean waiting time, Wq, in an "equivalent" system comprised of sseparate GI/M/1 queues each fed by an interarrival-time distribution G(·) with mean arrival rate equal to 1/s times that of H(·). For H(·) assumed to be Exponential, Gamma or Deterministic three possible relationships between H(·) and G(·) are considered: G(·) can be of the "same type" as H(·); G(·) can be derived from H(·) by assigning new arrivals to the individual channels in a cyclic order; and G(·) may be obtained from H(·) by assigning customers probabilistically to the different queues. The limiting behaviour of the ratio R = Wq/Wq(s) is studied for the extreme values (1 and 0) of the common traffic intensity, ρ. Closed form results, which depend on the forms of H(·) and G(·) and on the relationships between them, are derived. It is shown that Wqis greater than Wq(s) by a factor of at least (s+ 1)/2 when ρ approaches one, and that Ris at least s(s!) when ρ tends to zero. In the latter case, however, Rgoes to infinity (!) in most cases treated. The results may be used to evaluate the effect on the waiting times when, for certain (non-queueing) reasons, it is needed to partition a group of sservers into several small groups.

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to ‘move’ from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilitypi, or moves on to the next queue (w.p. 1 —pi) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all “parameterized” cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thepi's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {pi}iN=1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalpi's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp1=1 is the best strategy, and derive conditions under which it is optimal to havep1 < 1.

We consider a polling system consisting ofN queues and a single server where polling is performed according to anElevator (scan) scheme. The server first serves queues in the “up” direction, i.e. in the order 1, 2,...,N - 1,N, and then serves these queues in the opposite (“down”) direction, i.e. visiting them in the orderN,N-1,...,2,1. The server then changes direction again, and so on. A globally gating regime is used each time the server changes direction. We show that, for this Elevator scheme,the expected waiting times in all channels are equal. This is the only known non-symmetric polling system that exhibits such afairness phenomenon. We then discuss the problem of optimally ordering the queues so as to minimize some measure of variability of the waiting times.

We study the behavior of a single-server discrete-time queue with batch arrivals, where the information on the queue length and possibly on service completions is delayed. Such a model describes situations arising in high speed telecommunication systems, where information arrives in messages, each comprising a variable number of fixed-length packets, and it takes one unit of time (a slot) to transmit a packet. Since it is not desirable to attempt service when the system may be empty, we study a model where we assume that service is attempted only if, given the information available to the server, it is certain that there are messages in the queue. We characterize the probability distribution of the number of messages in the queue under some general stationarity assumptions on the arrival process, when information on the queue size is delayedK slots, and derive explicit expressions of the PGF of the queue length for the case of i.i.d. batch arrivals and general independent service times. We further derive the PGF of the queue size when information onboth the queue length and service completion is delayedK=1 units of time. Finally, we extend the results to priority queues and show that when all messages are of unit length, thecµ rule remains optimal even in the case of delayed information.

A polling system comprising n queues and a single server is considered. Service is performed according to an elevator scheme under the globally gated regime. The problem of arranging the channels to minimize a measure of the variability of the waiting times is addressed. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 605–611, 1997

A cyclic service system is composed of Kchannels (queues) and a single cyclically roving server who typically takes a positive amount of time to switch between channels. Research has previously focused on evaluating and computing performance measures (notably, waiting times) of fixed template routing schemes under three main service disciplines, the exhaustive, gatedand limited serviceregimes.In this paper, probabilistic results are derived that allow control strategies and optimal policies to be considered for the first time. By concentrating on a new objective function, we are able to derive rules of index form amenable for direct implementation to dynamically control the system at suitably defined decision epochs. These rules utilize current system information, are of an adaptive nature, and are shown to emanate from a general physical principle.

By using a probabilistic equivalence between the M/G/1 queue with multiple server ' vacations and the M/M/c system, we derive the Laplace-Stieltjes transform of the waiting time Wk, of a class-k customer in the non-preemptive priority M/M/c queue where all customers have the same mean service time. We also calculate the first two moments of Wk.

The well known birthday problem asks for the probability of at least one match out of a group of n people. Also of interest are the number of matches and the number of matched people. In this paper the means and variances of the number of matches and matched people are obtained. A generalization of the use of these methods to computer storage analysis is discussed.

Control limit type policies are widely discussed in the literature, particularly regarding the maintenance of deteriorating systems. Previous studies deal mainly with stationary deterioration processes, where costs and transition probabilities depend only on the state of the system, regardless of its cumulative age. In this paper, we consider a nonstationary deterioration process, in which operation and maintenance costs, as well as transition probabilities “deteriorate” with both the system's state and its cumulative age. We discuss conditions under which control limit policies are optimal for such processes and compare them with those used in the analysis of stationary models. Two maintenance models are examined: in the first (as in the majority of classic studies), the only maintenance action allowed is the replacement of the system by a new one. In this case, we show that the nonstationary results are direct generalizations of their counterparts in stationary models. We propose an efficient algorithm for finding the optimal policy, utilizing its control limit form. In the second model we also allow for repairs to better states (without changing the age). In this case, the optimal policy is shown to have the form of a 3-way control limit rule. However, conditions analogous to those used in the stationary problem do not suffice, so additional, more restrictive ones are suggested and discussed.

AnN-node tandem queueing network with Bernoulli feedback to the end of the queue of thefirst node is considered. We first revisit the single-nodeM/G/1 queue with Bernoulli feedback, and derive a formula forEL(n), the expected queue length seen by a customer at his nth feedback. We show that, asn becomes large,EL(n) tends to ?/(l ?), ? being the effective traffic intensity. We then treat the entire queueing network and calculate the mean value ofS, the total sojourn time of a customer in theN-node system. Based on these results we study the problem ofoptimally ordering the nodes so as to minimize ES. We show that this is a special case of a general sequencing problem and derive sufficient conditions for an optimal ordering. A few extensions of the serial queueing model are also analyzed. We conclude with an appendix in which we derive an explicit formula for the correlation coefficient between the number of customers seen by an arbitrary arrival to anM/G/1 queue, and the number of customers he leaves behind him upon departure. For theM/M/1 queue this coefficient simply equals the traffic intensity ?.

This paper considers a single-server queue with Poisson arrivals and multiple customer feedbacks. If the first service attempt of a newly arriving customer is not successful, he returns to the end of the queue for another service attempt, with a different service time distribution. He keeps trying in this manner (as an ‘old' customer) until his service is successful. The server operates according to the ‘gated vacation' strategy; when it returns from a vacation to find K(new and old) customers, it renders a single service attempt to each of them and takes another vacation, etc. We study the joint queue length process of new and old customers, as well as the waiting time distribution of customers. Some extensions are also discussed.

The problem considered here is the adjustment of cross-tabulated sampled data which fit known marginal totals but retain their original relationships to each other as measured by a statistical criterion (e.g., the minimization of Neyman's modified chi-square, the maximization of the likelihood function, the minimization of the discrimination information number). In this paper a mathematical model and algorithm are presented from which the adjusted cell counts are computed so that they satisfy exactly any of the proposed statistical criteria subject to the marginal constraints. These integer valued estimates are obtained in a finite number of iterations using readily available computer programs.

Almost all polling models studied in the literature deal with ‘open’ systems where all jobs are transient, i.e., they arrive to, are served by, and leave the system. Recently Altman & Yechiali [1994] introduced and analyzed models for ‘closed’ polling networks in which a fixednumber of permanentjobs always reside in the system, such that each job, after being served in one station, is immediately (and randomly) routed to another station where it waits to be served again by the rotating server. Boxma and Cohen [1991] analyzed a single-node M/G/1 configuration with regular (transient) Poisson jobs and with a fixed number of permanent jobs who immediately return to the end of the queue each time they receive a service.In this work we study hybridmulti-node polling systems with bothtransient and permanent jobs, operated under the Gated, Exhaustive, or Globally-Gated service regime. We define the laws of motion governing the evolution of such systems and derive the multi-dimensional generating functions of the number of jobs at the various queues at polling instants, and at arbitrary points in time. For each regime we investigate the interaction between the two populations of jobs and derive formulae for the means, as well as expressions for calculating the second moments, of the number of jobs at the various queues. Waiting times and throughput rates are calculated and the systems are compared with each other

We consider models of polling systems where switching times between channels are composed of two parts:walking times required to move from one channel (station) to another, and switch-in times that are incurred only when the server enters a station to render service.We analyze three Gated-type systems:(i) Cyclic polling with Gated regime, (ii) Cyclic polling with Globally-Gated regime, and (iii) Elevator-type polling with Globally-Gated regime. In all systems, the server visits station i if and only if the number of customers (jobs) present there at the gating instant is greater than or equal to given threshold K>0.For all schemes we derive formulae for the multi-dimensional generating functions of the number of jobs in the various queues at polling instants, and derive bounds on mean waiting times, mean cycle times and mean number of jobs present in the system. For the Elevator scheme we further show that if switch-in times, as well as arrival rates, are equal among channels, then jobs' mean waiting times in all stations are equal

A deteriorating system is inspected at equally spaced points in time. After each inspection a repair to a better state or a full replacement are possible. We introduce a generalized control limit policy and show that, under reasonable conditions on the system's law of evolution and on the operating, repair and replacement costs, this policy is optimal for the expected total discounted cost, as well as for the (long-run) average cost criteria. Furthermore, we allow for uncertain repair actions (that may even end up in a worse state), and show that the generalized control limit rule is still optimal. The work extends, generalizes and unifies many models in the area of optimal control of repairable systems

The problem considered hers is the adjustment of cross-tabulated sampled data which tit known marginal totals but retain their original relationships to each other as measured by a statistical criterion (e.g., the minimisation of Neyman's modified chi-squars, the maximisation of the Likelihood function, the minimisation or the discrimination information number). In this paper a mathematical model and algorithm are presented from which the adjusted cell counts are computed so that they satisfy exactly any of the proposed statistical criteria subject to the marginal constraints. These integer valued estimates are obtained in a finite number of iterations using readily available computer programs.

We study the relative effectiveness of two multi-unit forces, A and B, fighting a successive series of duels between randomly selected pairs of opposing units. A duel consists of a series of games - each of at most s units of time - and the duel terminates as soon as one of the two duelists is hit. A new independent duel then starts, and so on.Each force is characterized by a common probability distribution function representing the time required by a single unit of the force to hit a non-firing unit of the other force in a game of unbounded duration. The relative effectiveness of force A with respect to force B is expressed by the exchange rateR(s), defined as the expected number of units of force B hit by a single unit of force A until unit A itself is hit.We derive a general characterization of R{s) and develop analytic results for several choices of pairs of families of time-to-hit distributions. We show that the shape of the distributions can strongly affect the outcome of the duels and that this effect changes with the duration of the duel. We further show that duels are not necessarily transitive. Some Numerical results are presented.

Polling systems under the Randomly Timed Gated (RTG) regime are studied and analyzed, and various performance measures are derived. The RTG protocol operates as follows: whenever the server enters a station, a Timer is activated. If the server empties the queue before the Timer‘s expiration, it moves on to the next node. Otherwise (i.e., if there is still work in the station when the Timer expires), the server obeys one of the following rules, each leading to a different model: (1) The server completes all the work accumulated up to the Timer‘s expiration and then moves on to the next node. (2) The server completes only the service of the job currentlybeing served, and moves on. (3) The server stops working immediatelyand moves on. The RTG protocol defines a wide class of time-based control mechanisms: under rule (1) it spans an entire spectrum of regimes lying between the Gated and the Exhaustive, while under rule (2) it spans an entire spectrum between the 1-Limited and the Exhaustive protocols

Offers become available from time to time. The offers constitute a sequence of i.i.d. positive random variables. Upon arrival of an offer a decision is taken whether to accept it or not. When an offer is accepted the process terminates. Otherwise, the offer is lost and the process continues until the next arrival or until a moment where it terminates by itself. The probability of self-termination depends on the age of the underlying process.