Tandem queue with group arrivals and no intermediate buffer

We study a system with two single-server stations in series. There is an infinite buffer in front of the first station and no buffer between the two stations. The customers come in groups; the groups contain random numbers of customers and arrive according to a Poisson process. Assuming general service time distributions at the two stations, we derive the Laplace transform and the recursive formula for the moments of the total time spent in the tandem system (waiting time in the system) by an arbitrary customer. From the Laplace transform, we conclude that the optimal order of the servers for minimizing the waiting time in the system does not depend on the group size.     

A simple load balancing problem with decentralized information

The following load balancing problem is investigated in discrete time: A service system consists of two service stations and two controllers, one in front of each station. The service stations provide the same service with identical service time distributions and identical waiting costs. Customers requiring service arrive at a controller's site and are routed to one of the two stations by the controller. The processes describing the two arrival streams are identical. Each controller has perfect knowledge of the workload in its own station and receives information about the other station's workload with one unit of delay. The controllers' routing strategies that minimize the customers' total flowtime are determined for a certain range of the parameters that describe the arrival process and the service distribution. Specifically, we prove that optimal routing strategies are characterized by thresholds that are either precisely specified or take one of two possible values.     

Single machine scheduling with two competing agents,arbitrary release dates and unit processing times

Rapid transit systems timetables are commonly designed to accommodate passenger demand in sections with the highest passenger load. However, disruptions frequently arise due to an increase in the demand, infrastructure incidences or as a consequence of fleet size reductions. All these circumstances give rise to unsupplied demand at certain stations, which generates passenger overloads in the available vehicles. The design of strategies that guarantee reasonable user waiting time with small increases of operation costs is now an important research topic. This paper proposes a tactical approach to determine optimal policies for dealing with such situations. Concretely, a short-turning strategy is analysed, where some vehicles perform short cycles in order to increase the frequency among certain stations of the lines and to equilibrate the train occupancy level. Turn-back points should be located and service offset should be determined with the objective of diminishing the passenger waiting time while preserving certain level of quality of service. Computational results and analysis for a real case study are provided.     

On Markov?CKrein characterization of the mean waiting time in M/G/K and other queueing systems

We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems??via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov?CKrein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.     

Optimizing acyclic traffic signal switching sequences through an Extended Linear Complementarity Problem formulation

In this paper we first show how the Extended Linear Complementarity Problem, which is a mathematical programming problem, can be used to design optimal switching schemes for a class of switched systems with linear dynamics subject to saturation. More specifically, we consider the determination of the optimal switching time instants (the switching sequences are acyclic, but the phase sequence is pre-fixed). Although this method yields globally optimal switching time sequences, it is not feasible in practice due to its computational complexity. Therefore, we also discuss some approximations that lead to suboptimal switching time sequences that can be computed very efficiently and for which the value of the objective function is close to the global optimum. Finally we use these results to design optimal switching time sequences for a traffic signal controlled intersection so as to minimize criteria such as average queue length, worst case queue length, average waiting time, and so on.     

Optimal control of a single server in a finite-population queueing network

We study the optimal dynamic assignment of a single server to multiple stations in a finite-population queueing network. The objective is to maximize the long-run average reward/throughput. We use sample-path comparisons to identify conditions on the network structure and service time distributions under which the optimal policy is an index policy. This index policy assigns the server to the non-empty station where it takes the shortest amount of time (in some stochastic sense) to complete a job. For example, in a network of multiple parallel stations, the optimal policy assigns the highest priority to the fastest station if service times can be ordered in likelihood ratios. Finally, by means of a numerical study, we test the shortest-expected-remaining-service-time policy on parallel-series networks with three stations and find that this index policy either coincides with the optimal policy or provides a near-optimal performance.     

Approximating queue size and waiting time distributions in general polling systems

Polling system models are extensively used to model a large variety of computer and communication networks as well as production and service systems in which multiple customer classes or a number of distinct items compete for the capacity of a common server or production facility. In this paper we describe an efficient approximation method for the steady state distributions of the queue sizes and waiting times. This method is highly accurate as demonstrated by an extensive numerical study. In addition, it is highly adaptable to a variety of arrival patterns and switching protocols, including exhaustive and gated regimes, simple cyclical systems as well as general polling tables. For a system withN stations, one finds the firstK probability density function values of the steady state queue size in any given station inO(max(N, K ²) time only. When executed on an IBM system RS/6000, we have observed an average CPU time of less than 1 second for systems with as many as 50 stations over a large variety of parameter settings.     

Response times in gated M/G/1 queues: The processor-sharing case

A class of single server queues with Poisson arrivals and a gated server is considered. Whenever the server becomes idle the gate separating it from the waiting line opens, admitting all the waiting customers into service, and then closes again. The batch admitted into service may be served according to some arbitrary scheme. The equilibrium waiting time distribution is provided for the subclass of conservative schemes with arbitrary service times and the processor-sharing case is treated in some detail to produce the equilibrium time-in-service and response time distributions, conditional on the length of required service. The LIFO and random order of service schemes and the case of compound Poisson arrivals are treated briefly as examples of the effectiveness of the proposed method of analysis. All distributions are provided in terms of their Laplace transforms except for the case of exponential service times where the L.T. of the waiting time distribution is inverted. The first two moments of the equilibrium waiting and response times are provided for most treated cases and in the exponential service times case the batch size distribution is also presented.     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

Waiting times in a two-queue model with exhaustive and Bernoulli service

This paper deals with waiting times in a two-queue polling system in which one queue is served according to the Bernoulli service discipline and the other one attains exhaustive service. Exact results are derived for the LST's of the waiting time distributions via an iteration scheme. Based on those results the mean waiting times are expressed in the system parameters.     

Efficiency and welfare implications of managed public sector hospital waiting lists

A queuing model for public health service waiting lists is developed, and the implications for patient welfare of different systems for managing the waiting list are analysed. If patients are admitted to hospital on a first-come-first-served basis, a welfare gain is achieved by moving from a system of implicit to one of explicit rationing of access to the waiting list. If individual waiting times and hospital admissions are dependent on clinical priority, a further welfare gain is achievable without the use of explicit rationing, by reallocating the total waiting time from the more towards the less seriously ill. On efficiency and welfare criteria, a maximum waiting time guarantee does not appear to be a desirable development.     

Queues with waiting time dependent service

Motivated by service levels in terms of the waiting-time distribution seen, for instance, in call centers, we consider two models for systems with a service discipline that depends on the waiting time. The first model deals with a single server that continuously adapts its service rate based on the waiting time of the first customer in line. In the second model, one queue is served by a primary server which is supplemented by a secondary server when the waiting of the first customer in line exceeds a threshold. Using level crossings for the waiting-time process of the first customer in line, we derive steady-state waiting-time distributions for both models. The results are illustrated with numerical examples.     

Optimal control of polling models for transportation applications

We formulate and analyze a dynamic scheduling problem for a class of transportation systems in a Markov Decision Process (MDP) framework. A transportation system is represented by a polling model consisting of a number of stations and a server with switch-over costs and constraints on its movement (the model we have analyzed is intended to emulate key features of an elevator system). Customers request service in order to be transported by the server from various arrival stations to a common destination station. The objective is to minimize a cost criterion that incorporates waiting costs at the arrival stations. Two versions of the basic problem are considered and structural properties of the optimal policy in each case are derived. It is shown that optimal scheduling policies are characterized by switching functions dependent on state information consisting of queue lengths formed at the arrival stations.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

Single-machine scheduling with convex resource dependent processing times and deteriorating jobs

In this study, we consider scheduling problems with convex resource dependent processing times and deteriorating jobs, in which the processing time of a job is a function of its starting time and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately. This paper focus on the single-machine problems with objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. It shows that the problems remain polynomially solvable under the proposed model.     

Optimal scheduling policies in time sharing service systems

We consider optimal scheduling problems in a TSSS (Time Sharing Service System), i.e., a tandem queueing network consisting of multiple service stations, all of which are served by a single server. In each station, a customer can receive service time up to the prescribed station dependent upper bound, but he must proceed to the next station in order to receive further service. After the total amount of the received services reaches his service requirement, he departs from the network. The optimal policy for this system minimizes the long-run average expected waiting cost per unit of time over the infinite planning horizon. It is first shown that, if the distribution of customer's service requirement is DMRL (Decreasing Mean Residual Life), the policy of giving the highest priority to the customer with the most attained service time is optimal under a set of some appropriate conditions. This implies that any policy without interruptions and preemptions of services is optimal. If the service requirement is DFR (Decreasing Failure Rate), on the other hand, it is shown that the policy of giving the highest priority to the customer with the least attained service time, i.e., the so-called LAST (Least Attained Service Time first) is optimal under another set of some appropriate conditions. These results can be generalized to the case in which there exist multiple classes of customers, but each class satisfies one of the above sets of conditions.     

服务系统中位相型分布的随机比较

本文运用应用概率中的随机占优研究位相型(PH)分布的随机比较问题,具体给出在一阶、二阶随机占优下比较两个离散PH分布或两个连续PH分布的充分条件及充分必要条件。研究表明,比较两个离散PH分布可变性的条件与比较两个连续PH分布可变性的条件不同,在二阶随机占优意义下比较两个连续PH分布的条件与均值无关,而比较两个离散PH分布的条件与均值有关。本文的结果可用于研究PH分布的最小变异系数问题和可变性问题,也可用于研究带有PH到达间隔或PH服务的排队系统中到达过程或服务时间可变性对系统队长或等待时间的影响。     

Insensitivity of multiclass systems with general dynamic preemptive resume queueing disciplines

We are concerned with the insensitivity of the stationary distributions of the system states inM/G/s/m queues with multiclass customers and with LIFO preemptive resume service disciplines. We introduce general entrance and exit rules into and from waiting positions, respectively, for the behaviour of waiting customers whose service is interrupted. These rules may, roughly speaking, depend on the number of customers in the system. It is shown that the stationary distribution of the system state is insensitive not only with respect to the service time distributions but also with respect to the general entrance and exit rules. As well as the insensitivity of the service scheme, our results are obtained for a special form of state and customer type dependent arrival and service rates. Some further results are concluded related to insensitivity like the formula for the conditional mean sojourn time and the property of transformation of a Poisson input into a Poisson output by the systems.     

Modelling complex assemblies as a queueing network for lead time control

In this paper we develop an open queueing network for optimal design of multi-stage assemblies, in which each service station represents a manufacturing or assembly operation. The arrival processes of the individual parts of the product are independent Poisson processes with equal rates. In each service station, there is a server with exponential distribution of processing time, in which the service rate is controllable. The transport times between the service stations are independent random variables with exponential distributions. By applying the longest path analysis in queueing networks, we obtain the distribution function of time spend by a product in the system or the manufacturing lead time. Then, we develop a multi-objective optimal control problem, in which the average lead time, the variance of the lead time and the total operating costs of the system per period are minimized. Finally, we use the goal attainment method to obtain the optimal service rates or the control vector of the problem.