On the optimal control problem of a single-server queueing system

For a single-server queueing system (with a finite waiting room) with phase type arrivals and exponential service times, an optimal control for the service rate is derived. This generalizes the result of Scott and Jefferson for theM/M/1/1 queueing model.     

On the optimal control of a single-server queueing system: Reply

This comment replies to a criticism due to Klein and Gruver (Ref. 1) of our earlier paper (Ref. 2) on the application of control theory to a queueing system. The criticism concerns the state-space diagram and the table which we inadvertently gave for the terminal-reward problem, albeit incorrectly labeled, rather than for the free-endpoint problem considered in our paper. We show that the solution given by Klein and Gruver is itself incorrect and nonoptimal.     

On the optimal control of a single-server queueing system: Comment

In a recent paper by Scott and Jefferson, the optimal control of the service rate for a single-server queue with limited waiting space is treated by the maximum principle. We show that their control policies are necessarily suboptimal. Characterizations for optimal control are derived and used to obtain corresponding optimal trajectories in both nonsingular and singular regions.     

Dynamic scheduling of a single-server two-class queue with constant retrial policy

We analyze the non-preemptive assignment of a single server to two infinite-capacity retrial queues. Customers arrive at both queues according to Poisson processes. They are served on first-come-first-served basis following a cost-optimal routing policy. The customer at the head of a queue generates a Poisson stream of repeated requests for service, that is, we have a constant retrial policy. All service times are exponential, with rates depending on the queues. The costs to be minimized consist of costs per unit time that a customer spends in the system. In case of a scheduling problem that arise when no new customers arrive an explicit condition for server allocation to the first or the second queue is given. The condition presented covers all possible parameter choices. For scheduling that also considers new arrivals, we present the conditions under which server assignment to either queue 1 or queue 2 is cost-optimal.     

On the optimal control of a single-server queueing system: Further remarks

This comment is in response to a reply by Scott and Jefferson (Ref. 3) concerning the application of control theory to a queueing problem.     

A multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

Dynamic multi-priority,multi-class patient scheduling with stochastic service times

Efficient patient scheduling has significant operational, clinical and economical benefits on health care systems by not only increasing the timely access of patients to care but also reducing costs. However, patient scheduling is complex due to, among other aspects, the existence of multiple priority levels, the presence of multiple service requirements, and its stochastic nature. Patient appointment (allocation) scheduling refers to the assignment of specific appointment start times to a set of patients scheduled for a particular day while advance patient scheduling refers to the assignment of future appointment days to patients. These two problems have generally been addressed separately despite each being highly dependent on the form of the other. This paper develops a framework that incorporates stochastic service times into the advance scheduling problem as a first step towards bridging these two problems. In this way, we not only take into account the waiting time until the day of service but also the idle time/overtime of medical resources on the day of service. We first extend the current literature by providing theoretical and numerical results for the case with multi-class, multi-priority patients and deterministic service times. We then adapt the model to incorporate stochastic service times and perform a comprehensive numerical analysis on a number of scenarios, including a practical application. Results suggest that the advance scheduling policies based on deterministic service times cannot be easily improved upon by incorporating stochastic service times, a finding that has important implications for practice and future research on the combined problem.     

Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

A queueing model for a nonreliable multiterminal system with polling scheduling

This paper deals with a nonhomogeneous finite-source queueing model to describe the performance of a multiterminal system subject to random breakdowns under the polling service discipline. The model studied here is a closed queueing network which has three service stations. a CPU (single server), terminals (infinite server), a repairman (single server), and a finite number of customers (jobs) that have distinct service rates at the service stations. The CPU's repair has preemptive priority over the terminal repairs, and failure of the CPU stops the service of the other stations, thus the nodes are not independent. It can be viewed as a continuation of papers by the authors (see references), which discussed a FIFO (first-in, first-out) and a PPS (priority processor sharing) serviced queueing model subject to random breakdowns. All random variables are assumed to be independent and exponentially distributed. The system behavior can be described by a Markov chain, but the number of states is very large. The purpose of this paper is to give a recursive computational approach to solve steady-state equations and to illustrate the problem in question using some numerical results. Supported by the Hungarian National Foundation for Scientific Research (grant Nos. OTKA T014974/95 and T016933/95) Proceedings of the Seminar on Stability Problems for Stochastic Models. Hajdúszoboszló, Hungary, 1997, Part, II.     

Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies

This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r _k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Scheduling control for Markov-modulated single-server multiclass queueing systems in heavy traffic

This paper studies a scheduling control problem for a single-server multiclass queueing network in heavy traffic, operating in a changing environment. The changing environment is modeled as a finite-state Markov process that modulates the arrival and service rates in the system. Various cases are considered: fast changing environment, fixed environment, and slowly changing environment. In all cases, the arrival rates are environment dependent, whereas the service rates are environment dependent when the environment Markov process is changing fast, and are assumed to be constant in the other two cases. In each of the cases, using weak convergence analysis, in particular functional limit theorems for Poisson processes and ergodic Markov processes, it is shown that an appropriate “averaged” version of the classical \(c\mu \) -policy (the priority policy that favors classes with higher values of the product of holding cost \(c\) and service rate \(\mu \) ) is asymptotically optimal for an infinite horizon discounted cost criterion.     

Order statistics applications to queueing and scheduling problems

We prove several basic combinatorial identities and use them in two applications: the queue inference engine (QIE) and earliest due date rule (EDD) scheduling. Larson (1990) introduced the QIE. His objective was to deduce the behavior of a multiserver queueing system without observing the queue. With only a Poisson arrival assumption, he analyzed the performance during a busy period. Such a period starts once all servers are busy with the queue empty, and it ends as soon as a server becomes idle. We generalize the standard order statistics result for Poisson processes, and show how to sample a busy period in the M/M/c system. We derive simple expressions for the variance of the total waiting time in the M/M/c and M/D/1 queues given that n Poisson arrivals and departures occur during a busy period. We also perform a probabilistic analysis of the EDD for a one-machine scheduling problem with earliness and tardiness penalties. The schedule is without preemption and with no inserted idle time. The jobs are independent and each may have a different due date. For large n, we show that the variance of the total penalty costs of the EDD is linear in n. The mean of the total penalty costs of the EDD is known to be proportional to the square root of n (see Harel (1993)). This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal server scheduling in nonpreemptive finite-population queueing systems

We consider a finite-population queueing system with heterogeneous classes of customers and a single server. For the case of nonpreemptive service, we fully characterize the structure of the server's optimal service policy that minimizes the total average customer waiting costs. We show that the optimal service policy may never serve some classes of customers. For those classes that are served, we show that the optimal service policy is a simple static priority policy. We also derive sufficient conditions that determine the optimal priority sequence.     

Control and scheduling in a two-station queueing network: Optimal policies and heuristics

Consider a two-station queueing network with two types of jobs: type 1 jobs visit station 1 only, while type 2 jobs visit both stations in sequence. Each station has a single server. Arrival and service processes are modeled as counting processes with controllable stochastic intensities. The problem is to control the arrival and service processes, and in particular to schedule the server in station 1 among the two job types, in order to minimize a discounted cost function over an infinite time horizon. Using a stochastic intensity control approach, we establish the optimality of a specific stationary policy, and show that its value function satisfies certain properties, which lead to a switching-curve structure. We further classify the problem into six parametric cases. Based on the structural properties of the stationary policy, we establish the optimality of some simple priority rules for three of the six cases, and develop heuristic policies for the other three cases.     

Waiting time approximation in multi-class queueing systems with multiple types of class-dependent interruptions

We consider a single-server queue subject to class-dependent interruptions motivated by vessel queueing at entrances of waterways. Two classes of customers and k types of possibly simultaneous and class-dependent service interruptions are considered. We have employed service completion time analysis and proposed approximations to obtain the expected waiting time of a customer (vessel) in the queue.     

Chaos in a simple deterministic queueing system

We present a simple discrete-time deterministic queueing model, with one server and two queueing lines. The input rates of both queues are constant and their sum equals the server-capacity. In each time period the server has to decide how much time to spend on each of the two queues. The servers decision rule is a nonlinear, but increasing function of the difference between the two queue-lengths. We investigate how the dynamical behaviour of the queue-lengths and the service process depend on the steepness of the decision function and the ratio of the input rates of the two queues. We show that if the decision function is steep, then for many input-ratios chaotic dynamics occurs.