Optimal policies for M/M/m queue with two different kinds of (N,T)‐policies

In this paper, two different kinds of (N, T)‐policies for an M/M/m queueing system are studied. The system operates only intermittently and is shut down when no customers are present any more. A fixed setup cost of K > 0 is incurred each time the system is reopened. Also, a holding cost of h > 0 per unit time is incurred for each customer present. The two (N, T)‐policies studied for this queueing system with cost structures are as follows: (1) The system is reactivated as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T, and (2) the system is reactivated as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. The equations satisfied by the optimal policy (N*, T*) for minimizing the long‐run average cost per unit time in both cases are obtained. Particularly, we obtain the explicit optimal joint policy (N*, T*) and optimal objective value for the case of a single server, the explicit optimal policy N* and optimal objective value for the case of multiple servers when only predefined customers number N is measured, and the explicit optimal policy T* and optimal objective value for the case of multiple servers when only predefined time units T is measured, respectively. These results partly extend (1) the classic N or T policy to a more practical (N, T)‐policy and (2) the conclusions obtained for single server system to a system consisting of m (m ≥ 1) servers. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 240–258, 2000     

An M/M/1 queue with a general bulk service rule

A model of an M/M/1, bulk queue with service rates dependent on the batch size is developed. The operational policy is to commence service when at least L customers are available with a maximum batch size of K. Arriving customers are not allowed to join in-process service. The solution procedure utilizes the matrix geometric methodology and reduces to obtaining the inverse of a square matrix of dimension K + 1 - L. For the case where the service rates are not batch size dependent, the limiting probabilities can be written in closed form. A numerical example illustrates the variability of the system cost as a function of the minimum batch service size L.     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

Optimal control of entry to an M/Ek/1 queue serving several classes of customers

The individual and social optimum control policies for entry to an M/M//1 queue serving several classes of customers have been shown to be control-limit policies. The technique of policy iteration provides the social optimum policy for such a queue in a straightforward manner. In this article, the problem of finding the optimal control policy for the M/E_k/1 system is solved, thereby expanding the potential applicability of the solutions developed. The Markovian nature of the queueing system is preserved by considering the service as having k sequential phases, each with independent, identically distributed, exponential service times, through which a customer must pass to be serviced. The optimal policy derived by policy iteration for such a system is likely to be difficult to use because it requires knowledge of the number of phases rather than customers in the system when an arrival occurs. To circumvent this difficulty, a heuristic is used to find a good usable (implementable) solution. In addition, a mixed-integer program is developed which yields the optimal implementable solution when solved.     

Optimal admission pricing and service rate control of an M[x]/M/s queue with reneging

In this article we consider the optimal control of an M^[X]/M/s queue, s ≧ 1. In addition to Poisson bulk arrivals we incorporate a reneging function. Subject to control are an admission price p and the service rate μ. Thus, through p, balking response is induced. When i customers are present a cost h(i,μ,p) per unit time is incurred, discounted continuously. Formulated as a continuous time Markov decision process, conditions are given under which the optimal admission price and optimal service rate are each nondecreasing functions of i. In Section 4 we indicate how the infinite state space may be truncated to a finite state space for computational purposes.     

A queueing system with vacations after N services

This article is devoted to the study of an M/G/1 queue with a particular vacation discipline. The server is due to take a vacation as soon as it has served exactly N customers since the end of the previous vacation. N may be either a constant or a random variable. If the system becomes empty before the server has served N customers, then it stays idle until the next customer arrival. Such a vacation discipline arises, for example, in production systems and in order picking in warehouses. We determine the joint transform of the length of a visit period and the number of customers in the system at the end of that period. We also derive the generating function of the number of customers at a random instant, and the Laplace–Stieltjes transform of the delay of a customer. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 646–658, 2015     

Computational analysis of MMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline

This paper studies a queueing system with a Markov arrival process with marked arrivals and PH‐distribution service times for each type of customer. Customers (regardless of their types) are served on a mixed first‐come‐first‐served (FCFS) and last‐come‐first‐served (LCFS) nonpreemptive basis. That is, when the queue length is N (a positive integer) or less, customers are served on an FCFS basis; otherwise, customers are served on an LCFS basis. The focus is on the stationary distribution of queue strings, busy periods, and waiting times of individual types of customers. A computational approach is developed for computing the stationary distribution of queue strings, the mean of busy period, and the means and variances of waiting times. The relationship between these performance measures and the threshold number N is analyzed in depth numerically. It is found that the variance of the virtual (actual) waiting time of an arbitrary customer can be reduced by increasing N. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 399–421, 2000     

Vehicle routing problems with regular objective functions on a path

We investigate the problem of scheduling a fleet of vehicles to visit the customers located on a path to minimize some regular function of the visiting times of the customers. For the single‐vehicle problem, we prove that it is pseudopolynomially solvable for any minsum objective and polynomially solvable for any minmax objective. Also, we establish the NP‐hardness of minimizing the weighted number of tardy customers and the total weighted tardiness, and present polynomial algorithms for their special cases with a common due date. For the multivehicle problem involving n customers, we show that an optimal solution can be found by solving or O(n) single‐vehicle problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 34–43, 2014     

On the busy period of the M/G/1 retrial queue

The M/G/1 queue with repeated attempts is considered. A customer who finds the server busy, leaves the service area and joins a pool of unsatisfied customers. Each customer in the pool repeats his demand after a random amount of time until he finds the server free. We focus on the busy period L of the M/G/1$ retrial queue. The structure of the busy period and its analysis in terms of Laplace transforms have been discussed by several authors. However, this solution has serious limitations in practice. For instance, we cannot compute the first moments of L by direct differentiation. This paper complements the existing work and provides a direct method of calculation for the second moment of L. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 115–127, 2000     

The queue G/M/m/N: Busy period and cycle,waiting time under reverse and random order service

The busy period, busy cycle, and the numbers of customers served and lost therein, of the G/M/m queue with balking is studied via the embedded Markov chain approach. It is shown that the expectations of the two discrete variables give the loss probability. For the special case G/M/1/N a closed expression in terms of contour integrals is obtained for the Laplace transform of these four variables. This yields as a byproduct the LIFO waiting time distribution for the G/M/m/N queue. The waiting time under random order service for this queue is also studied.     

Optimal control for entry of many classes of customers to an M/M/1 queue

A method is developed for determining the optimal policy for entry of customers from many independent classes of Poisson arrivals to a first-come, first-serve (for customers admitted to the queue) single-server queue with exponential service times. The solution technique utilizes a semi-Markov formulation or the decision problem.     

A queueing system with multiple service time distributions

This paper explores a modification of the output discipline for the Poisson input, exponential output, single channel, first-come, first-served queueing system. Instead, the service time distribution of customers beginning service when alone in the system is considered different from that governing service times of all other customers. More specifically, the service times of lone customers are governed by a one parameter gamma distribution, while the service times of all other customers are exponentially ajstributed. The generating function for the steady-state probsbilities, n_j = Pr { j customers in system at an arbitrary point of departure}, of the imbedded chain, {X_n/X_n = number in system after nth customer is serviced}, is obtained, and the steady-state probabilities, themselves, are found in closed form.     

Optimal pricing and scheduling control of product shipping

In this article, we seek to understand how a capacity‐constrained seller optimally prices and schedules product shipping to customers who are heterogeneous on willingness to pay (WTP) and willingness to wait (WTW). The capacity‐constrained seller does not observe each customer's WTP and WTW and knows only the aggregate distributions of WTP and WTW. The seller's problem is modeled as an M/M/N_s queueing model with multiclass customers and multidimensional information screening. We contribute to the literature by providing an optimal and efficient algorithm. Furthermore, we numerically find that customers with a larger waiting cost enjoys a higher scheduling priority, but customers with higher valuation do not necessarily get a higher scheduling priority. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 215–227, 2015     

Quantifying the performance effects of idle time utilization in multiserver systems

In many practical multiserver queueing systems, servers not only serve randomly arriving customers but also work on the secondary jobs with infinite backlog during their idle time. In this paper, we propose a c‐server model with a two‐threshold policy, denoted by (e d), to evaluate the performance of this class of systems. With such a policy, when the number of idle servers has reached d (<c), then e (<d) idle agents will process secondary jobs. These e servers keep working on the secondary jobs until they find waiting customers exist in the system at a secondary job completion instant. Using the matrix analytic method, we obtain the stationary performance measures for evaluating different (e, d) policies. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

有限服务能力的损失制排队系统M/M/1分析

提出了随机服务系统的服务能力问题,给出有限服务能力的损失制M／M／1模型的描述和其稳态解,并求出了评价系统运行的几个主要数量指标。     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

An M/M/1 queue with delayed feedback

We present some results for M/M/1 queues with finite capacities with delayed feedback. The delay in the feedback to an M/M/1 queue is modelled as another M-server queue with a finite capacity. The steady state probabilities for the two dimensional Markov process {N(t), M(t)} are solved when N(t) = queue length at server 1 at t and M(t) = queue length at server 2 at t. It is shown that a matrix operation can be performed to obtain the steady state probabilities. The eigenvalues of the operator and its eigenvectors are found. The problem is solved by fitting boundary conditions to the general solution and by normalizing. A sample problem is run to show that the solution methods can be programmed and meaningful results obtained numerically.     

Optimal dynamic rules for assigning customers to servers in a heterogeneous queuing system

We consider a queuing system in which both customers and servers may be of several types. The distribution of a customer's service time is assumed to depend on both the customer's type and the type of server to which he is assigned. For a model with two servers and two customer types, conditions are presented which ensure that the discounted number of service completions is maximized by assigning customers with longer service times to faster servers. Generalizations to more complex models are discussed.     

Probabilistic priorities in the M/G/1 queue

A simple method is presented for deriving the mean and variance of the queueing time distribution in an M/G/1 queue when the priorities assigned to customers have an assignment probability distribution. Several examples illustrate the results. The mean and variance of the queueing time distribution for the longest service time discipline are derived, and its disadvantages are discussed.     

Control of entry to a nonstationary queuing system

In this article the control of entry of customers to a queuing system with s servers is considered. It is assumed that the arrivals form a nonstationary Poisson process with a periodic rate. The service times are assumed to be exponentially distributed with a parameter independent of time. The cost structure considered is the same as that of Naor. It is demonstrated numerically that, like the stationary cases, the average expected benefit of customers per unit of time is a unimodal function of the critical point. And, also, the social critical point is smaller than the individual critical point. These suggest the use of a search technique for finding the social critical point. The results show successful application of the discrete version of the Fibonacci search.