Even though many computational methods (recursive formulae) for blocking probabilities in finite-capacity M/D/1 queues have already been produced, these are forms of transforms or are limited to single-node queues. Using a distinctly different approach from the usual queueing theory, this study introduces explicit (transformfree) formulae for a blocking probability, a stationary probability, and mean sojourn time under either production or communication blocking policy. Additionally, the smallest buffer capacity subject to a given blocking probability can be determined numerically from these formulae. With proper selection of the overall offered load ρ, the approach described herein can be applicable to more general queues from a computational point of view if the explicit expressions of random vector D n are available. Keywords: Blocking probability, finite-capacity queues, max-plus algebra, max-plus linear system, stationary probability, system sojourn time. Manuscript received Aug. 19, 2013; revised Nov. 1, 2013; accepted Nov. 8, 2013. This research was supported by grant from Kyung Hee University in 2011 (KHU-20110900  An M/D/1 queue, the simplest queue with deterministic service time, has been studied extensively and has a variety of applications in the performance evaluation of production management, telecommunications networks, and other areas. However, because blocking phenomena caused by finite capacity raise many difficulties and introduce complexity into evaluations of various performance measures, results regarding finite-capacity queues are small in number. With the exception of some special cases, such as Markovian queues (M/M/1/K), Erlang's loss queues (no waiting room at all, M/G/c/c), M/G/1/1 and M/G/1/2 queues, and so on, it is very difficult to obtain explicit expressions for a blocking probability or a stationary distribution in finitecapacity queues (for example, see Gross and Harris [1] and Takagi [2] ). On the one hand, the recursive formula for stationary distributions (or blocking probabilities) in M/G/c/K queues was first provided by Tijms [3] . Brun and Garcia [4] showed analytical (transform-free) solutions of steady-state probability distributions in finite-capacity M/D/1 queues via the use of the generating function (z-transform). Alouf and others [5] analytically derived the stationary distribution of the M/D/1/K queue using Cohen's results -which were based on the Laplace-Stieltjes transform (LST) -of the M/G/1/K queue of the service time distribution (see Cohen [6] constructed an approximation formula for the overflow probability for GI/GI/c/N queues in terms of a queue-length distribution for the corresponding GI/GI/c/∞ queues. The blocking probability plays an important role in the analysis of finite-capacity queues. Once a blocking probability is obtained, we are able to compute various performance measures of interest, including carried load, stationary probabilities, (higher) moments of stationary waiting time and sojourn time, and so forth. However, normal queueing theory has limitations in applications to general queues with multinode, multi-server, or generally structured queues. In an effort to overcome these shortcomings we adopt a different method from the usual queueing theory -namely, max-plus algebra. Many types of networks belonging to a class of queueing networks, the so-called max-plus linear system, can be modeled properly by timed event graphs, a special case of the Petri net. They can be analysed using maxplus algebra, which involves the use of only two operators: "max" and "+." In brief, a max-plus linear system is a choicefree network of single-server queues with first-in first-out service discipline. Because it is clear that an M/G/1/K queue belongs to a max-plus linear system, a max-plus algebra is useful in analysing this finite-capacity queue. Additionally, constant service times render the series expressions (see section II) simple and tractable such that we focused solely on deterministic service times. The principal objective of this study is to demonstrate a closed-form (transform-free) expression of a blocking probability for an M/D/1/K queue under either communication or production blocking policy. In the case of communication blocking policy we can obtain the same expression as the one of Brun and Garcia [4] and Alouf and others [5] , whereas in the case of production blocking policy we obtain a new formula. Moreover, other related expressions for stationary probability, mean system sojourn time, and an optimal buffer capacity are also provided. Similar to Sakasegawa and others [9] , these expressions are written in terms of the blocking probability and the queuelength distribution of the corresponding M/D/1/∞ queue. This paper is organized as follows. Brief preliminaries on max-plus algebra and on waiting times in a max-plus linear system are provided in section II. Section III includes our principal results on the explicit expression of blocking probability in finite-capacity M/D/1 queues. We show other related expressions in section IV and end with some concluding remarks in section V.
Especially the M/D/1/K model is of particular interest for TDMA networks, describing Poisson distributed arrival, deterministic service time, a single transmitter and a queue of length K. In REF closed-form expressions are given for the blocking probability and other properties.
Explicit Formulae for Characteristics of Finite-Capacity M/D/1 Queues
Etri Journal
Mathematics