A SIMULATION ALGORITHM FOR QUEUING SYSTEMS WITH PARALLEL WORKING STATIONS HAVING ONE'S OWN QUEUE FOR EVERY STATION WITH HOL SERVING DISCIPLINE

A SIMULATION ALGORITHM FOR QUEUING SYSTEMS WITH PARALLEL WORKING STATIONS HAVING ONE'S OWN QUEUE FOR EVERY STATION WITH HOL SERVING DISCIPLINE

Abstract We can think the queuing system as having only one queue to all stations, where the client joins in order to be served when a free station exists or every station has its own queue where the arrived clients joins. Also, the queued clients are served based on serving discipline, FIFO or based on dividing in priority classes of the customers. This paper presents a simulation algorithm for the queuing system, where very station has own queue and serving discipline is of Head of Line type. One proves the polynomial complexity of the proposed algorithm. Also, we present the object oriented approach of the system.

Key words: Queuing system, Simulation, Algorithm, HOL discipline.

Introduction

The queuing models deal with systems that have agglomerations. Such models assume a random generation mechanism for the arrivals in the system, for the clients serving and the same serving discipline. In the traditional approach, where the stations topology is parallel and there is only one queue to all stations, the arrived client is immediately served, if there is a station in laziness otherwise it joins to the queue. Also, based on a serving discipline (FIFO, HOL etc.), when a station finishes a service and own queue is not empty, a new client is selected in order to be served.

If there are no clients in the queue, the station becomes lazy. In the following we assume that every station has its own queue. So, when a client arrives in system, it chooses a station based on a random mechanism, described in [3]. Also, when one server finishes serving a customer, if the queue is not empty, a client is selected for serving based one the Head-of-Line (HOL) discipline, that consists in: if m is the class number, the i-class customer have serving priority versus those of j-class, if ; inside the same class, the clients are served in FIFO order; when a customer arrives and there is a an idle server, the client is immediately served, otherwise it is last queued inside his class and when a station finish a service the first client of the high class is selected to be served

There are a lot of real systems that can be abstracted in this mode. The CPU of a computer divides the processes in priority class; also, a printing server in a network divides the file in the same mode. As a general rule, a computing system has resources which the clients (processes) try to access. These resources can have the same type. In this case, we assume that there is only one queue to all resources or every resource has its own queue. In [2] one queuing system simulation algorithm is presented for the case with only one queue for all stations and HOL discipline and in [3] it is proposed such studying method for the queuing systems, with parallel stations having own queue and FIFO discipline. In this paper we will consider the same topology of station but the HOL discipline, which is a generalization of the FIFO discipline.

2. The model entities and the simulation mechanism

In the following we denote by n the number of station and every station is identified by a number i, i=1,..,n. Atime represents the event time of the next arrival (innitial with value 0 and incremented at every arrival by the value IntAriv representing the time between two arrivals). Also, we generate Stime, the service time of the arrived client and the priority class.A client that arrives in the system chooses his working station on a random basis. If we denote p_i the probability that it chooses the station i, choosing the station is equivalent to generating a discrete variable X given by

where p_i is

In this formula, nc(i) denotes the number of clients queued at the station i.

Remark 1

i) If then by a simple calculus we can proof .

ii) Also we have and .

iii) When all stations are free, i.e. nc(i)=0, for all i, , i=1,..,n we can consider one of the two possibilities:

iii.1)

iii.2)

Also, every station is characterized by the following variables:

For i station, we denote the end of the serving event time, that is, the station clock. If the station is free and there aren't clients queued for the station, the variable is .

The bi-dimensional vector holds the number of the j priority class of i station, at a given time; obviously is true.

The tri-dimensional vector holds the serving time values needed for the corresponding clients queued at the station i. Here the value represents the amount of time needed to serve the client k queued client of j priority class at the station i ..

We define the index ip as being

The algorithm that we are going to present follows the "next event"("minimum time") rule. If the moment of a serving end, in every moment it's possible to have one of the two events:

Handling of an arrival (arrival event); this event arrises when; a new arrival is generated.

Handling of an end of service event (Cevent), if .

Remark 2 If we define a simulation cycle as the handling of an arrival or of an event of type end of service, then we can say that the simulation consists of these cycles. Considering the hypothesis that the number of arrivals is smaller than the number of servings, the number of servings is less than Tnra. Also, if we consider the Tnra of a sufficiently great value, we can say that the great majority of clients are served. This leads to the conclusion that the number of cycles executed, in the case of the FIFO discipline, is smaller than 2Tnra.

Every handled event ends with an update of the following

, where represents the total waiting time for the queued clients of the j priority class at the working station i;

, where represents the total laziness amount of time for the working station i .

In addition, after every end of service event the following are updated:

, where represents the total amount of time spent to serve client of j class, by the working station i;

 , where represents the total number of clients from j class served by the working station i.

At the end of the simulation we determine the following global efficiency factors:

is the average amount of time spent by the queued clients waiting to be served by the working station i and it is given by the formula:

is the average amount of time spent by the queued clients of j class waiting to be served by all working stations and it is given by the formula:

represents the average amount of time spent by the working station i to serve clients. This value is given by the formula:

If Ltime is the number of time units of the entire simulation, represents the i working station laziness coefficient . This value is given by the formula:

(4)

We denote the average length of the queue for the working station i, and is given by :

(5)

3. Algorithm description and the complexity study

The following pseudo-code procedure describes "the main function" of the simulation algorithm of this queuing system type.

Procedure SistAstnStatiiFIFO(n,,m,Tnra);

Read(Random generation parameters);

ltime

for i=1 to n do

Ctime(i)

for j=1 to m do

ncq(i,j) 0; Tts(i,i) 0;Nrs(i,j) 0;;Tw(i,j)

endfor;

endfor;

GenArrival(Atime,Stime,NrSt,Nra,NrClass);

While Nra Tnra do

MinCtime(ip)

if Atime Ctime(ip) then

tipev Aev;timpev Atime;

PrelVectEfFact(tipev,timpev,Tw,timpev,Ltime,nc,Tlen);

JoinStation(Stime,NrSt);

Ltime Atime;

GenArrival(Atime,Stime,NrSt,Nra,NrClass);

else

tipev Cev;timpev Ctime(ip);

PrelVectEfFact(tipev,timpev,Tw,timpev,Ltime,nc,Tlen);

if nc(ip)>1 then FinServ(ip, Ctime, Ts, Tss, nc)

else Ctime(ip)

endif

endif

endwhile;

EfFactComp(MTw,MTwc,Mqueue,Mclen,Mts);

write(MTw,MTwc,Mqueue,Mclen,Mts)

end.

MinCtime determines the index of station that firstly will finish the service and it was described in [3]. Depending on the type of the event, the next procedure will update the previous mentioned arrays:

Procedure FactAtr(tipev,timpev,Tw,timpev,Ltime,nc,Tlen,ip,ic);

for i= to n do

for j=1 to m do

Tw(i,j) Tw(i,j)+ncq(i)*(timpev-Ltime)

endfor;

endfor;

for i=i,n do

if Ctime (i)= then Tlen(i) Tlen(i)+timpev-Ltime

endif;

endfor;

Ltime timpev;

if tipev="Cev" then

Nrs(ip,ic) Nrs(ip,ic)+1;Tts(ip,ic) Tts(ip)+Tss(ip)

Endif;

end;

Besides the amounts generated in the algorithm presented in [3], the GenArriv procedure will generate the priority client class.

Procedure GenArriv(nc,Stime,Atime,cp,NrSt);

Gen(Stime);Gen(IntAriv);cp Random(m);

Atime Atime+IntAriv;Nra Nra+1;Discr(nc,X,NrSt)

end;

The JoinStation procedure will join the arrived client to a generated station; if the station is free, it will be immediately served otherwise it will be introduced in the queue.

Procedure JoinStation(Stime,NrSt,NrClass);

ifCtime(NrSt)= then

Ctime(NrSt) Atime+Stime;Tss(NrSt) Stime

else

ncq(NrSt,NrClass) nc(NrSt,NrClass)+1;

Ts(NrSt,NrClass,nc(NrSt,NrClass) Stime

endif;

end;

When the queue of the station is not empty, the FinServ procedure will select the first client of high class, in order to be served.

Procedure FinServ(ip,Ctime,Ts,Tss,ncq);

ic

while ncq(ip,ic)=0 do ic ic+1;

Ctime(ip) Ctime(ip)+Ts(ip,ic,1); Tss(ip) Ts(ip,,ic,1);

for i=1 to ncq(ip,ic)-1 do Ts(ip,ic,i) Ts(ip,ic,i+1);

ncq(ip,ic) ncq(ip,ic)-1

end;

Algorithm complexity. We assume that the time needed to resolve a comparison and the time needed to assign a value to a variable is O(1). With these assumptions the complexity needed to run the algorithm is: initialization phase - n steps; the simulation algorithm will execute at most 2*Tnra cycles that handle either an arrival in the system or an end of service. The numbers of arrivals is greater but approximately equal to the number of end-of-service cycles

If we have an Aevent event: Execution of MinCtime - O(n) but can be considered O(1) since n is small; Execution of PrelVectEfFact- O(m*n) but can be considered O(1) since n,m have small values; Execution of JoinStation - O(1); Execution GenArrival- known polynomial complexity- we consider it O(1).

If we have a Cevent event: Execution of PrelVectEfFact- O(m*n) but can be considered O(1) since n,m have small values; Execution of FinServ- O(1)

Summing the complexities identified above we can conclude that the complexity of the algorithm is O(2*Tnra).

4. The OOP approach

The use of object in programming is a way of shortening the distance between the real life and the way it has to be modeled for the computer world. In order to generate the simulation needed we use model presented in [3], with slightly modifications. Inserting the priority classes modifies the client generation and handling and the efficiency information gathering. The HOL discipline had to be implemented. We had to implement also means to retain information, such as: the number of clients belonging to certain priority class, served by a station; the total time of wait for the clients belonging to a certain priority class.

4. Models Validity and practical considerations

In the following we consider 10,000 arrivals simulated.

i) Case 1. n=1, m=1. This model is the same with FCFS and one station model, with only one queue. We will consider the model exp(l)/exp(m ,FIFO), that is analytically studied [4]. If we take l m , we obtain the results given in table 1. As we can see from the above table, our simulation tends to equal the values obtained using the analytical approach. This validates our simulation model.

ii) Case 2.n=2, m=2. This model implements HOL having two serving stations and two priority classes. We shall consider l m The obtained results are presented in the table 2. As we can see the values are approximately equal for the two simulated stations and we can observe a slightly difference in matter of time of wait between the two priority classes. The class with a bigger priority (the "0" class) has a smaller time of wait value. To increase this gap we increase the frequency of arrivals as in:

iii) Case 3 n=2, m=2. This model implements HOL having two serving stations and two priority classes. We shall consider l m .The obtained results are presented in the table 3.

Table 1. The results for case 1

Table 2.The results for case 2

Table 3.The results for case 2

As we can see, the gap between the time of wait for the clients with different priority is bigger and more easy to observe. The privileged clients must wait a smaller amount of time until they are served.

Conclusions. We remark that in both case 2 and 3 we obtain results approximately similar. We constructed the first case simulation to verify the analytical model. For the next two simulations we obtained the results as expected. If the probability of choosing a station is equal in the case of zero client's number, the efficiency factors calculated in for the two stations are similar. The difference can be observed between the time of wait of a client with bigger priority and a client with a smaller priority.

References

Cormen, T.H., Leirson, C.E, Rivest R.L.: Introductions to Algorithms. MIT Press, Cambridge, 1992.

Florea, I.: One Algorithmic Approach of the Parallel Multi Server Queuing System of Head of Line Type, Bulletin of the Transilvania University of Brasov, vol. 8(43), p.22-30, 2002

Florea, I., Carstea A.: A Simulation Algorithm for Queuing Systems with Parallel Working Stations Having one's Own Queue for Every Station, Bulletin of the Transilvania University of Brasov, vol. 11(46),(to appear),2005

Gross, D., Harris C.: Foundamentals of Queuing Theory, John Wiley & Sons, NewYork,1998.

Tanner, M. : Practical Queuing Analysis. McGraw-Hill Book Company, 1995.

Vaduva, I.: Computer Simulation Model., Technical Publishing House, Bucharest, 1977

Vaduva, I., Stoica, M., Odagescu, I.: Economy Processes Simulation. Technical, Publishing House, Bucharest, 1983.

Algoritm de simulare pentru sistemele de asteptare cu statii de servire paralele, cu coada la fiecare statie si disciplina de servire HOL

Rezumat Putem considera un sistem de asteptare ca avand o coada unica pentru toate statiile, unde sunt introdusi clientii care asteapta sa fie serviti cind o statie devine libera sau fiecare statie are propria sa coada unde sunt introdusi clientii sositi. De asemenea, clientii din coada sunt serviti pe baza unei discipline de server, FIFO sau bazata pe impartirea clientilor in clase de prioritati . Aceasta lucrare, prezinta un algoritm de simulare pentru sistemele de asteptare, unde fiecare statie are propria coada,iar disciplina de servire este HOL. Se demonstreaza complexitatea polinomiala a algoritmului propus. De asemenea, prezentam abordarea orientata pe obiecte a sistemului.

Cuvinte cheie Sistem de asteptare Simulare, Algoritm, Disciplina HOL