We consider the queueing system denoted by M/MN/1/N where customers are served in batches of maximum size N. The model is motivated by a traffic application. The time-dependent probability distribution for the number of customers in the system is obtained in closed form. The solution is used to predict the optimal service rates during a finite time horizon.

We prove a monotonicity result for the problem of optimal service rate control in certain queueing networks. Consider, as an illustrative example, a number of ·/M/1 queues which are arranged in a cycle with some number of customers moving around the cycle. A holding cost hi(xi) is charged for each unit of time that queue i contains xi customers, with hi being convex. As a function of the queue lengths the service rate at each queue i is to be chosen in the interval , where cost ci(μ) is charged for each unit of time that the service rate μis in effect at queue i. It is shown that the policy which minimizes the expected total discounted cost has a monotone structure: namely, that by moving one customer from queue i to the following queue, the optimal service rate in queue i is not increased and the optimal service rates elsewhere are not decreased. We prove a similar result for problems of optimal arrival rate and service rate control in general queueing networks. The results are extended to an average-cost measure, and an example is included to show that in general the assumption of convex holding costs may not be relaxed. A further example shows that the optimal policy may not be monotone unless the choice of possible service rates at each queue includes 0.

Jobs arrive at a buffer from which there are several parallel routes to a destination. A socially optimal policy is one which minimizes the average delay of all jobs, whereas an individually optimal policy is one which, for each job, minimizes its own delay, with route preference given to jobs at the head of the buffer. If there is a socially optimal policy for a system with no arrivals, which can be implemented by each job following a policy γ in such a way that no job ever utilizes a previously declined route, then we show that such a γ is an individually optimal policy for each job. Moreover γ continues to be individually optimal even if the system has an arbitrary arrival process, subject only to the restriction that past arrivals are independent of future route-traversal times. Thus, γ is an individually optimal policy which is insensitive to the nature of the arrival process. In the particular case where the times to traverse the routes are exponentially distributed with a possibly different mean time for each of the parallel routes, then such an insensitive individually optimal policy does in fact exist and is moreover trivially determined by certain threshold numbers. A conjecture is also made about more general situations where such individually optimal policies exist.

A new approach to the optimal control of the service rate in M/G/1 queues is introduced using the method of phases. Each customer's work requirement is approximated by a random number of exponential phases with (possibly) different parameters (a generalized hyper-Erlang distribution). Using a semi-Markov decision-process formulation, we establish monotonicity properties of optimal policies for the finite-horizon problem, by induction on the horizon length. The analysis is then extended to the discounted infinite-horizon and the long-run average-return problems. In contrast to the models in previous papers, our model is appropriate for situations where the system controller has partial information about the work requirement of a customer, specifically the number of phases (tasks) to be performed. Because it requires a multidimensional state description, the analysis of the phase-type control model may be viewed as a first step toward the solution of control models for networks of queues.

The problem of controlling input to a stochastic input-output system by accepting or rejecting arriving customers is analyzed as a semi-Markov decision process. Included as special cases are a GI/G/1 model and models with compound input and/or output processes, as well as several previously studied queueing-control models. We establish monotonicity of socially and individually optimal acceptance policies and the more restrictive nature of the former, with random rewards for acceptance and both customer-oriented and system-oriented non-linear waiting costs. Distinctive features of our analysis are (i) that it allows dependent interarrival times and (ii) that the monotonicity proofs do not rely on the standard concavity-preservation arguments.

Some properties of the number of up- and downcrossings over level u, in a special case of regenerative processes are discussed. Two basic relations between the density functions and the expected number of upcrossings of this process are derived. Using these reults, two examples of controlled M/G/1 queueing systems are solved. Simple relations are derived for the waiting time distribution conditioned on the phase of control encountered by an arriving customer. The Laplace-Stieltjes transform of the distribution function of the waiting time of an arbitrary customer is also derived for each of these two examples.