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.
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 HeadofLine (HOL) discipline, that consists in: if m is the class number, the iclass customer have serving priority versus those of jclass, 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
_{}
_{}
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 bidimensional vector _{} holds the number of the j priority class of i station, at a given time; obviously _{} is true.
The tridimensional 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 pseudocode 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)*(timpevLtime)
endfor;
endfor;
for i=i,n do
if Ctime (i)= then Tlen(i) Tlen(i)+timpevLtime
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 endofservice 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
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.
Sim. station 
An.app. 

MTw  
CLen 


MTs  
MQL 
Table 1. The results for case 1
1^{st} Sim.st. 
2^{nd} Sim.st. 

MTs  
CLen  
MQL  
MTw  
MTw(0 class )  
MTw (1 class) 
Table 2.The results for case 2
1^{st} Simulated station 
2^{nd} Simulated station 

MTs  
CLen  
MQL  
MTw  
MTw( 0 class)  
MTw (1 class) 
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.
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.2230, 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. McGrawHill 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.
Politica de confidentialitate 
.com  Copyright ©
2024  Toate drepturile rezervate. Toate documentele au caracter informativ cu scop educational. 
Personaje din literatura 
Baltagul – caracterizarea personajelor 
Caracterizare Alexandru Lapusneanul 
Caracterizarea lui Gavilescu 
Caracterizarea personajelor negative din basmul 
Tehnica si mecanica 
Cuplaje  definitii. notatii. exemple. repere istorice. 
Actionare macara 
Reprezentarea si cotarea filetelor 
Geografie 
Turismul pe terra 
Vulcanii Și mediul 
Padurile pe terra si industrializarea lemnului 
Termeni si conditii 
Contact 
Creeaza si tu 