Simultaneity in discrete-time single server queues with Bernoulli inputs. (English) Zbl 0752.60079

The work considers the scheduling of arrivals and departures in discrete- time queues with Bernoulli arrivals and general independent service times with both infinite and finite waiting rooms. The number of customers varies only at equally spaced epochs: during any slot — a slot is an interval of time whose boundaries are two successive epochs — no customer enters or leaves the system, so the probability that two or more arrivals or departures occur simultaneously can be positive. The waiting- room management policy is qualified as AF (arrivals first) or DF (departures first) depending on one’s precedence over another. There are significant discrepancies between the system’s state distributions for AF and DF queues. The paper determines the departing and arriving customers’ distributions in both cases and besides the outside observer’s distribution, i.e. the number of customers \(X_ i\) in the system at time \(\theta(i-{1\over 2})\), where \(\theta\) is the length of a slot. It is shown if the probability of customer’s arrival in an elementary slot is low, the behaviours of AF and DF queues differ slightly, if it is larger, the discrepancies between them are more important. Lastly, the paper states that the discrete-time analog of the \(M/G/1\) queue is the \(Geo/G/1\) one for which arrivals are scheduled prior to departures in case of their simultaneity. For this policy the arriving customer’s and the outside observer’s distributions of the number of customers in the system are identical.


60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
Full Text: DOI