In this chapter, the authors study some optimal dynamic policies of assignment to control the entrance of a system. This system is formed of two waiting lines (queues) in parallel. Every line is composed of a server and a waiting room (buffer). Upon arrival to this system, the authors suppose the existence of an assignment policy. The role of the policy is to assign dynamically the customers (the customers here may represent a physical customer in the entrance of a cinema or bank, packets in a computer networks, calls in a telephone system…etc.) to the one or to the other of two lines or it may reject (or assigned to other system). This assignment is done according to policies in order to achieve some performance criterion.
TopMathematical Background Of The Queue
We start by defining Markov’s chain, before formulate a waiting line (queue) mathematically. After that, we will model a network formed by several connected waiting lines (queues) in parallel. We consider a system that can take different states E = {Ei, i=1, 2,..}. The states change occur in the Markov chain in different time that we note t1,t2,…,tk,… We call Pn(tK) the probability that in the instant tK, the system is in the En state. We suppose the transition of the Ei state to the Ej state depends only of these two states. We note pij the transition probability from the state i to the state j. The initial time t0 and the initial probabilities pn(t0) are known.
The set {pij, pn(t0) and Ei, i=1,2..} forms Markov chain. If the set E is continuous, the Markov chain is continuous. If the change of the time is continuous, we can define a process of Markov in continuous time.
Waiting Line (Queue)
The diagram shows a waiting line (Figure 1).
A customer arrives according to a certain process A. If the ticket window of the service is free, the customers enter and it is served with a process S, if he is not alone in the waiting line (queue) during his arrival, a queue discipline (QD) is applied. The most classic are:
A waiting line can have several servers and can only receive a finite number of customers (line with finite capacity). If a customer presents alone when the line is full, he is refused or send it to other system. The queue discipline that we will use in this chapter is FIFO.
There are several ways to symbolize a waiting line; one of these notations is for example: (QD/K/N) where:
An M/M/1 queue is therefore a line, with a Markov process, in arrival and in service, only one server and an infinite capacity.
Thereafter, we will use the following terminology: A/B/s: d/e
Where:
- •
A: the process of arrival.
- •
B: describes the process of service.
- •
s: the number of servers.
- •
d: capacity of the system.
- •
e: queue discipline.
(According to the terminology of Kendall [TOHME, 97]).
In the modeling of complex systems, a simple waiting line is not sufficient; it is necessary to use networks of waiting lines.