Maximum entropy analysis of the M[x]/M/1 queueing system with multiple vacations and server breakdowns

We consider a single unreliable sever in an M^[x]/M/1 queueing system with multiple vacations. As soon as the system becomes empty, the server leaves the system for a vacation of exponential length. When he returns from the vacation, if there are customers waiting in the queue, he begins to serve the customers; otherwise, another vacation is taken. Breakdown times and repair times of the server are assumed to obey a negative exponential distribution. Arrival rate varies according to the server’s status: vacation, busy, or breakdown. Using the maximum entropy principle, we develop the approximate formulae for the probability distributions of the number of customers in the system which is used to obtain various system performance measures. We perform a comparative analysis between the exact results and the maximum entropy results. We demonstrate, through the maximum entropy results, that the maximum entropy principle approach is accurate enough for practical purposes.     

Analysis of the resequencing buffer in a homogeneous M/M/2 queue

The resequencing problem is encountered in many practical information systems such as distributed database and communication networks. In these systems customers, such as messages in a computer network, have to be delivered to users in their original order. Therefore, those customers which become out of order due to the randomness of the system are forced to wait in a resequencing buffer so that their delivered order can be guaranteed. The previous work on the resequencing problem mainly concentrated on the delay aspect. From both theoretical and practical viewpoints, however, the queue length characteristics of the resequencing buffer are also significant. We consider the queue length distribution of the resequencing buffer fed by a homogeneous M/M/2 queue. The exact analysis is carried out for the probability mass functions of the queue length in equilibrium and the maximal occupancy which corresponds to the queue length just before the departure instants of customers from the resequencing buffer.     

Note on the article: Maximum entropy analysis of the M/M/1 queueing system with multiple vacations and server breakdowns

Wang et al. [Wang, K. H., Chan, M. C., & Ke, J. C. (2007). Maximum entropy analysis of the M^[x]/M/1 queueing system with multiple vacations and server breakdowns. Computers & Industrial Engineering, 52, 192–202] elaborate on an interesting approach to estimate the equilibrium distribution for the number of customers in the M^[x]/M/1 queueing model with multiple vacations and server breakdowns. Their approach consists of maximizing an entropy function subject to constraints, where the constraints are formed by some known exact results. By a comparison between the exact expression for the expected delay time and an approximate expected delay time based on the maximum entropy estimate, they argue that their maximum entropy estimate is sufficiently accurate for practical purposes. In this note, we show that their maximum entropy estimate is easily rejected by simulation. We propose a minor modification of their maximum entropy method that significantly improves the quality of the estimate.     

A multi-server perishable inventory system with negative customer

In this paper, we consider a continuous review perishable inventory system with multi-server service facility. In such systems the demanded item is delivered to the customer only after performing some service, such as assembly of parts or installation, etc. Compared to many inventory models in which the inventory is depleted at the demand rate, however in this model, it is depleted, at the rate at which the service is completed. We assume that the arrivals of customers are according to a Markovian arrival process (MAP) and that the service time has exponential distribution. The ordering policy is based on (s, S) policy. The lead time is assumed to have exponential distribution. The customer who finds either all servers are busy or no item (excluding those in service) is in the stock, enters into an orbit of infinite size. These orbiting customers send requests at random time points for possible selection of their demands for service. The interval time between two successive request-time points is assumed to have exponential distribution. In addition to the regular customers, a second flow of negative customers following an independent MAP is also considered so that a negative customer will remove one of the customers from the orbit. The joint probability distribution of the number of busy servers, the inventory level and the number of customers in the orbit is obtained in the steady state. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.     

Optimal NT policies for M/G/1 system with a startup and unreliable server

This paper studies the control policies of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers are served in the queue exhaustively, the server immediately takes a vacation and operates two different policies: (i) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the completion period. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. Furthermore, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We analyze the system characteristics for each scheme. The total expected cost function per unit time is developed to determine the optimal thresholds of N and T at a minimum cost.     

Comparative analysis of a randomized N-policy queue: An improved maximum entropy method

We analyze a single removable and unreliable server in an M/G/1 queueing system operating under the 〈p, N〉-policy. As soon as the system size is greater than N, turn the server on with probability p and leave the server off with probability (1 ? p). All arriving customers demand the first essential service, where only some of them demand the second optional service. He needs a startup time before providing first essential service until there are no customers in the system. The server is subject to break down according to a Poisson process and his repair time obeys a general distribution. In this queueing system, the steady-state probabilities cannot be derived explicitly. Thus, we employ an improved maximum entropy method with several well-known constraints to estimate the probability distributions of system size and the expected waiting time in the system. By a comparative analysis between the exact and approximate results, we may demonstrate that the improved maximum entropy method is accurate enough for practical purpose, and it is a useful method for solving complex queueing systems.     

An M/G/C/C state-dependent network simulation model

A discrete-event digital simulation model is developed to study traffic flows in M/G/C/C state-dependent queueing networks. Several performance measures are evaluated, namely (i) the blocking probability, (ii) throughput, (iii) the expected number of the customers in the system, and (iv) expected travel (service) time. Series, merge, and split topologies are examined with special application to pedestrian planning evacuation problems in buildings. Extensive computational experiments are presented showing that the simulation model is an effective and insightful tool to validate analytical expressions and also to analyze general accessibility in network evacuation problems especially in high-rise buildings.     

The effect of workers with different capabilities on customer delay

Many service facilities operate seven days per week. The operations managers of these facilities face the problem of allocating personnel of varying skills and work speed to satisfy the demand for services. Furthermore, for practical reasons, periodic staffing schedule is implemented regularly. We introduce a novel approach for modeling periodic staffing schedule and analyzing the impact of employee variability on customer delay. The problem is formulated as a multiple server vacation queueing system with Bernoulli feedback of customers. At any point in time, at most one server can serve the customers. Each server incur a durations of set-up time before they can serve the customers. The customer service time and server set-up time may depend on the server. The service process is unreliable in the sense that it is possible for the customer at service completion to rejoin the queue and request for more service. The customer arrival process is assumed to satisfy a linear–quadratic model of uncertainty. We will present transient and steady-state analysis on the queueing model. The transient analysis provides a stability condition for the system to reach steady state. The steady-state analysis provides explicit expressions for several performance measures of the system. For the special case of M^X/G/1 vacation queue with a gated or exhaustive service policy and Bernoulli feedback, our result reduces to a previously known result. Lastly, we show that a variant of our periodic staffing schedule model can be used to analyze queues with permanent customers. For the special case of M/G/1 queue with permanent customers and Bernoulli feedback of ordinary customers, we obtain results previously given by Boxma and Cohen (IEEE J. Select. Areas Commun. 9 (1991) 179) and van den Berg (Sojourn Times in Feedback and Processor Sharing Queues, CWI Tracts, vol. 97, Amsterdam, Netherlands, 1993).Scope and purposeWorkforce scheduling is a classical problem and has been studied by many researchers. The problem is usually formulated with homogeneous workforce as part of the assumption. Clearly, non-homogeneous workforce is a fact of life for many organizations. Operations manager would prefer to have skills and experience worker as it would improve the quality of the services provided. Ignoring the effect of employees with varying skills and work speed would seriously undermine the effectiveness of the services provided and lead to significant undesirable outcomes for the organization. This paper aims as a first step to fill the gap of past research. We present a novel approach to analyze the issue of non-homogeneous workforce on stability of work flows and the effect of workers with different capabilities on customers’ waiting time. We believe that the results are useful for operations manager dealing with non-homogeneous workforce.     

Cost analysis of a finite capacity queue with server breakdowns and threshold-based recovery policy

This paper analyzes a repairable M/M/1/N queueing system under a threshold-based recovery policy. The threshold-based recovery policy means that the server breaks down only if there is at least one customer in the system, and the recovery can be performed when q (1 ≤ q ≤ N) or more customers are present. For this queueing system, a recursive method is applied to obtain steady-state solutions in neat closed-form expressions. We then develop some important system characteristics, such as the number of customers in the system, the probability that the server is busy, the effective arrival rate and the expected waiting time in the system, etc. A cost model is constructed to determine the optimal threshold value, the optimal system capacity and the optimal service rate at a minimum cost. In order to solve this optimization problem, the direct search method and Newton's method are employed. Sensitivity analysis is also conducted with various system parameters. Finally, we present some managerial insights through an application example.     

On the number of customers served in the M/G/1 retrial queue: first moments and maximum entropy approach

In this paper we present general results on the number of customers, I, served during the busy period in an M/G/1 retrial system. Its analysis in terms of Laplace transforms has been previously discussed in the literature. However, this solution presents important limitations in practice; in particular, the moments of I cannot be obtained by direct differentiation. We propose a direct method of computation for the second moment of I and also for the probability of k,k⩽4, customers being served in a busy period. Then, the maximum entropy principle approach is used to estimate the true distribution of I according to the available information.Scope and purposeWe consider an M/G/1 queue with retrials. Retrial queueing systems are characterized by the fact that, an arriving customer who finds the server busy is obliged to leave the service area and return later to repeat his request after some random time. We deal with I, the number of customers served during the busy period of a retrial queue, and obtain closed expressions for its main characteristics, which will be employed in order to estimate the true distribution of this random variable.     

MMAP|M|N queueing system with impatient heterogeneous customers as a model of a contact center

A multi-server queueing system with infinite buffer and impatient heterogeneous customers as a model of a contact center that processes incoming calls (priority customers) and e-mail requests (non-priority customers) is investigated. The arrival flow is described by a Marked Markovian Arrival Process (MMAP). The service time of priority and non-priority customers by a server has an exponential distribution with different parameters. The steady state distribution of the system is analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transforms of the sojourn and waiting time distribution are derived. The problem of optimal choice of the number of contact center agents under the constraint that the average waiting time of e-mail requests does not exceed a predefined value is numerically solved.     

A finite source multi-server inventory system with service facility

In this article, we study a continuous review retrial inventory system with a finite source of customers and identical multiple servers in parallel. The customers arrive according a quasi-random process. The customers demand unit item and the demanded items are delivered after performing some service the duration of which is distributed as exponential. The ordering policy is according to (s, S) policy. The lead times for the orders are assumed to have independent and identical exponential distributions. The arriving customer who finds all servers are busy or all items are in service, joins an orbit. These orbiting customer competes for service by sending out signals at random times until she finds a free server and at least one item is not in the service. The inter-retrial times are exponentially distributed with parameter depending on the number of customers in the orbit. The joint probability distribution of the number of customer in the orbit, the number of busy servers and the inventory level is obtained in the steady state case. The Laplace–Stieltjes transform of the waiting time distribution and the moments of the waiting time distribution are calculated. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.     

A finite source multi-server inventory system with service facility

In this article, we study a continuous review retrial inventory system with a finite source of customers and identical multiple servers in parallel. The customers arrive according a quasi-random process. The customers demand unit item and the demanded items are delivered after performing some service the duration of which is distributed as exponential. The ordering policy is according to (s, S) policy. The lead times for the orders are assumed to have independent and identical exponential distributions. The arriving customer who finds all servers are busy or all items are in service, joins an orbit. These orbiting customer competes for service by sending out signals at random times until she finds a free server and at least one item is not in the service. The inter-retrial times are exponentially distributed with parameter depending on the number of customers in the orbit. The joint probability distribution of the number of customer in the orbit, the number of busy servers and the inventory level is obtained in the steady state case. The Laplace–Stieltjes transform of the waiting time distribution and the moments of the waiting time distribution are calculated. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.     

Three m-failure group maintenance models for M/M/N unreliable queuing service systems

This paper considers group maintenance problems for an unreliable service system with N independent operating servers and a Markovian queue. A specific class of group maintenance policies is developed where the repair is started as soon as the number of failed servers reaches a predetermined threshold. This is actually a Quasi Birth-and-Death Process with two dimensions, the level for the arrival/service process and the phase for the failure/repair process. Two models with positive repair time and another with instantaneous repair are considered. The matrix geometric approach is applied to calculate the steady state distribution and the expected average cost for all three models. For the theoretical analysis, this paper proves that there exists an optimal group maintenance parameter m^*, which can find the minimal average cost for all three models. Additionally, some mathematical properties and sensitivity analyses are numerically demonstrated based on various parameters. Finally, the comparisons of these three proposed models in many aspects are also discussed.     

Reducing congestion in bulk-service finite-buffer queueing system using batch-size-dependent service

In the design and analysis of any queueing system, one of the main objectives is to reduce congestion which can be achieved by controlling either arrival-rates or service-rates. This paper adopts the latter approach and analyzes a single-server finite-buffer queue where customers arrive according to the Poisson process and are served in batches of minimum size a with a maximum threshold limit b. The service times of the batches are arbitrarily distributed and depends on the size of the batches undergoing service. We obtain the joint distribution of the number of customers in the queue and the number with the server, and distributions of the number of customers in the queue, in the system, and the number with the server. Various performance measures such as the average number of customers in the queue (system) and with the server etc. are obtained. Several numerical results are presented in the form of tables and graphs and it is observed that batch-size-dependent service rule is more effective in reducing the congestion as compared to the one when service rates of the batches remain same irrespective of the size of the batch. This model has potential application in manufacturing, computer-communication network, telecommunication systems and group testing.     

Analysis of GI/M/s/c queues using uniformisation

We combine uniformisation, a powerful numerical technique for the analysis of continuous time Markov chains, with the Markov chain embedding technique to analyze GI/M/s/c queues. The main steps of the proposed approach are the computation of

• (1)the mixed-Poisson probabilities associated to the number of arrival epochs in the uniformising Poisson process between consecutive customer arrivals to the system; and
• (2)the conditional embedded uniformised transition probabilities of the number of customers in the queueing system immediately before customer arrivals to the system.

To show the performance of the approach, we analyze queues with Pareto interarrival times using a stable recursion for the associated mixed-Poisson probabilities whose computation time is linear in the number of computed coefficients. The results for queues with Pareto interarrival times are compared with those obtained for queues with other interarrival time distributions, including exponential, Erlang, uniform and deterministic interarrival times. The obtained results show that much higher loss probabilities and mean waiting times in queue may be obtained for queues with Pareto interarrival times than for queues with the other mentioned interarrival time distributions, specially for small traffic intensities.     

Robustness of inventory replenishment and customer selection policies for the dynamic and stochastic inventory-routing problem

When inventory management, distribution and routing decisions are determined simultaneously, implementing a vendor-managed inventory strategy, a difficult combinatorial optimization problem must be solved to determine which customers to visit, how much to replenish, and how to route the vehicles around them. This is known as the inventory-routing problem. We analyze a distribution system with one depot, one vehicle and many customers under the most commonly used inventory policy, namely the (s,S), for different values of s. In this paper we propose three different customer selection methods: big orders first, lowest storage first, and equal quantity discount. Each of these policies will select a different subset of customers to be replenished in each period. The selected customers must then be visited by a vehicle in order to deliver a commodity to satisfy the customers' demands. The system was analyzed using public benchmark instances of different sizes regarding the number of customers involved. We compare the quality and the robustness of our algorithms and detailed computational experiments show that our methods can significantly improve upon existing solutions from the literature.     

A perishable inventory system with service facilities and retrial customers

In this article, we present a continuous review perishable (s, S) inventory system with a service facility consisting of finite waiting room and a single server. The customers arrive according to a Markovian arrival process (MAP). The individual customer’s unit demand is satisfied after a random time of service which is assumed to have phase-type distribution. The life time of each item and the lead time of reorders are assumed to have independent exponential distributions. Any arriving customer, who finds the waiting room is full, enters into the orbit of infinite space. These orbiting customers compete for service by sending out signals the duration between two successive attempts are exponentially distributed. The joint probability distribution of the number of customers in the waiting room, number of customers in the orbit and the inventory level is obtained in the steady-state case. Various stationary system performance measures are computed and total expected cost rate is calculated.     

The passport control problem or how to keep a dynamic service system load balanced?

In many real life situations (such as department stores, or passport control booths in airports) parallel queues are formed in front of control stations. Typically, some of the stations are manned while others are not. Classical queuing theory considers the configuration constant, and concentrates on the arrival process. This work explores a new line of research—the case in which the configuration is dynamic, and the customers can plan to cope with anticipated changes. Specifically, as the queues build up, management assigns additional officers to the unmanned stations. When this happens—some people move to the newly manned queues from nearby busy queues. In anticipation, people may prefer to line up in busy queues next to unmanned ones.Mathematically we discuss the problem of dynamic arrangement of the queues in a service system where at any time each server can be in either an active or an inactive mode. A balancing strategy determines how customers will be reallocated when a station becomes active. Given a balancing strategy, we seek a partition of customers to queues that minimizes the maximum wait time of a customer in each of the active stations, thereby keeping the system balanced at all times. We study two balancing strategies that we call Split and Trim. For the Split strategy we discuss a special case (the stations are ordered on a line and a single unmanned station is at one end). We show how an optimal partition can be calculated recursively. We then give partitions that approximate the minimal expected wait time within a factor of 1+O(1/N), under each of these strategies, where N is the number of stations. We obtain similar bounds (to within factor 2) for the case, where the number of active servers can be any 1⩽n⩽N−1, and the balancing strategy is Trim.