Math Meth Oper Res (2003) 57 : 367–376
Control policy of a hysteretic queueing system Lotfi Tadj*, Jau-Chuan Key * Department of Statistics and Operations Research, College of Science, King Saud University, P.O. Box 2455, Riyadh 11451, Saudi Arabia (e-mail:
[email protected]) y Department of Statistics, National Taichung Institute of Technology, No. 129, Sec. 3, Sanmin Rd., Taichung 404, Taiwan, R.O.C. (e-mail:
[email protected]) Manuscript received: June 2002/Final version received: October 2002
Abstract. This paper is concerned with the optimal control of a bulk service queueing system under N-policy. If the number of customers in the system at a service completion is larger than some integer r, then the server starts processing a group of r customers. If, on the other hand, it is smaller than r, then the server goes through an idle period and waits for the line to grow up to some integer N, ðN b rÞ. We present some system characteristics by means of the embedded Markov chains and semi-regenerative techniques. We also construct the expected total cost for this model and develop a procedure to determine the optimal thresholds r and N that yield the minimum cost. AMS Subject Classification: Primary 60K10, 60K25, secondary 90B22, 90B25. Key words: Queue, hysteresis, embedded Markov chain, semi-regenerative process, control policy 1 Introduction The optimal control of queues under N-policy, launched by Yadin and Naor (1963), has been the subject of numerous research papers. This is because it is a very important problem that finds applications in various systems, such as production, inventory, transportation, telecommunication, and computer systems. The researchers working in this area have looked at the problem from di¤erent angles, depending on the application on hand. This has given rise to a vast and rich literature, from which we list below some of the features considered. All the references cited below deal with a queueing system under Npolicy. (a) Linear vs non-linear cost structure. A cost function is usually designed and optimal system parameters that yield minimum cost are sought. Hey-
368
(b)
(c)
(d)
(e) (f )
(g)
(h)
(i)
L. Tadj, J.-C. Ke
man (1968) showed the optimality of N-policies within the class of all policies for problems dealing with average costs per unit time. Bell (1971) and Okamura et al. (1996) and (2000) investigated an expected total discounted cost which is discounted continuously by a positive discount rate. Specific vs general service time distribution. The original model considered by Yadin and Naor (1963) was an M/M/1 queueing system. The M/G/1 queueing system was first investigated by Heyman (1968) and was studied by several other authors such as Sobel (1969), Bell (1971), Levy and Yechiali (1975), and Hersh and Brosh (1980). Analytic closed-form solutions were developed by Wang and Huang (1995) for the M/Ek /1 and by Wang et al. (1999) for the M/H2 /1 queueing system. Some authors, such as Kimura (1981), Okamura et al. (1996) and (2000), assumed incomplete information on the service distribution function and used a di¤usion approximation model to determine the optimal N-policy. Set-up vs no set-up. Combination of N-policy and set-up in a queueing system was first considered Borthakur et al. (1987). Others to consider this combination include Lee and Park (1997), Hur and Paik (1999), and Ke (2001). Reliable vs non-reliable server. Closed-form solutions of the M/M/1 under N-policy with non-reliable server were first obtained by Wang (1995). Wang et al. (1999) studied the M/H2 /1 with a non-reliable server while the N-policy Markovian system with finite capacity and a non-reliable server was proposed by Wang and Hsieh (1995). Finite vs infinite queueing system. Finite capacity queueing systems have been studied by Hersh and Brosh (1980), Teghem (1987), Wang and Huang (1995), Wang and Hsieh (1995), and Wang et al. (1999). Single vs batch arrivals. Procedures to find the optimal stationary policy in a bulk arrival queueing process have been developed by Lee and Srinivasan (1989), and Lee et al. (1994) and (1995). Optimality of N-policies for problems dealing with average costs per unit time has been shown by Federgruen and So (1991) for systems with batch arrivals. Vacationing vs non-vacationing server. A vacationing server has been considered by Kella (1989) who describes, for the special case of linear holding costs and unit Poisson demands, a simple algorithm for the determination of the optimal threshold level. Lee and Srinivasan (1989) achieved the same for the more general case of a compound Poisson demand process (but linear holding costs). Ke (2001) considered a bulk arrival system with two vacation types. Single vs bicriterion optimization. Teghem (1987) investigated the M/G/1 ðv; NÞ-policy queueing system. Bicriterion optimization has also been adopted by Feinberg and Kim (1996): one criterion is the average number of customers in the system, and the other is the average operating cost per unit time. Also, ðN; TÞ-policy was considered by Okamura et al. (1996) and (2000). Single vs bulk service. All the queueing models cited above assume a server that serves customers singly. To the best of the authors’ knowledge, the optimal control of a bulk service queueing system under N-policy has not been considered.
The goal of this paper is to design an optimal control policy for a bulk service queueing system under N-policy. The analysis of this system is carried
Control policy of a hysteretic queueing system
369
out using the method of embedded Markov chains and semi-regenerative techniques. These techniques have recently been applied to bulk service queues, see for example Tadj (1993). As the analysis follows well-beaten paths, we derive steady-state probabilities of the discrete and continuous time parameter processes. We also present some important system characteristics such as mean system size, mean busy period, mean idle period and mean busy cycle. Using the notation of Kendall, the model considered is an M/G r /1 N-policy. It is briefly described and analyzed below. Steady-state results are given Section 2. Section 3 discusses the control problem. Our interest is in the numerical results of Section 4 in which the hysteretic model is studied in detail and some important operating characteristics are revealed. Conclusions are given in Section 5. 2 Model description and steady-state results Consider a queueing system of M/G/1-type. The arrival process is Poisson with rate l. The service time is general with finite first and second moments, b and b2 , respectively. The waiting room is unlimited. The service discipline is FIFO. The process of interest is the number QðtÞ of customers in the system at time t. Let Tn denote the nth service completion instant. Then, Q n ¼ QðTn þÞ is the embedded process and represents the number of customers in the system at a service completion epoch. The service discipline is as follows. If at a service completion there are more than r customers in the queue, then the server takes a batch of customers of size r to process in a single batch. On the other hand, if at a service completion there are less than r customers in the queue, then the server starts an idle period and when the queue size reaches the value N, ðN b rÞ, then he takes a batch of customers of size r to process in a single batch. Let Vn denote the number of customer arrivals during the service time of the nth batch. Since Q nþ1 ¼
N þ Vnþ1 r; Q n < r; Q n þ Vnþ1 r; Q n b r;
then, the process fQ n g is a Markov chain. Denote by pi ¼ lim PfQ n ¼ ig; n!y
ð1Þ
the steady-state probability of state i, by Pn ðzÞ ¼ E½z Q n the probability generating function of Q n . Also, let F ðzÞ ¼ E½z Vn ¼ B ðl lzÞ, where B ðsÞ is the Laplace-Stieltjes transform of the service time distribution B, let U ¼ f1; . . . ; r 1g and let IU ðÞ denote the indicator function of set U. Theorem 1. The Markov chain fQ n g is ergodic if and only if r :¼
lb < 1: r
ð2Þ
370
L. Tadj, J.-C. Ke
Its probability generating function PðzÞ ¼ lim n!y Pn ðzÞ is given by PðzÞ ¼
F ðzÞ
P
N i
