An Algorithm for Simulation of Waiting Systems with Different Types and Variable Number of Parallel Working Stations Each Having its Own Queue

Ion Florea
Transilvania University of Brasov, Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science
Iuliu Maniu 50, Braşov, 500091, Romania

Lucian Sasu
Transilvania University of Brasov, Department of Mathematics and Computer Science, Faculty of Mathematics and Computer Science
Iuliu Maniu 50, Braşov, 500091, Romania

Abstract: This paper presents waiting systems with parallel working stations, for which both the clients and the working stations are grouped in classes. The working stations from the same class are identical and have their own waiting queues. The clients’ arrivals, the choice of a class to whom the client belongs to and furthermore the choice of the serving station relies on a random process. Also, this approach considers a variable number of stations, influenced by the number of clients in the system. For this kind of problems there is no suitable analytical method and the support offered by specialized languages is quite poor. The paper presents a study approach for this kind of systems, based on discrete event simulation. It is shown that the given algorithm has a polynomial complexity. Also, the object-oriented design we used for implementation is sketched.

Keywords: Queuing System, Waiting Queue, Simulation Algorithm, Polynomial Complexity, Different Classes of Stations, Variable Number of Active Stations.

>>Full text
CITE THIS PAPER AS:
Ion FLOREA, Lucian SASU, An Algorithm for Simulation of Waiting Systems with Different Types and Variable Number of Parallel Working Stations Each Having its Own Queue, Studies in Informatics and Control, ISSN 1220-1766, vol. 21 (3), pp. 333-340, 2012. https://doi.org/10.24846/v21i3y201212

1. Introduction

In this paper we approach the queuing system having a waiting queue to each station. When a new client arrives in the system, it chooses a random station based on a random process which takes into account the burden of the stations. Furthermore, we can consider that the clients themselves can be partitioned into classes and that for each class of clients there is a corresponding fixed set of deserving stations. A station from the clients’ class is randomly selected to serve this client. The client’s class and the station which will serve it are also randomly chosen. Inside a class, we will allow a client to migrate from a queue to another one that became empty. Here we suppose that there are two classes of clients, denoted as “privileged” and “regular”, respectively. From now on we will suppose that the number of stations in each class varies, according to the agglomeration degree of the stations in that class.

In [3] we presented a simulation algorithm for waiting systems with a variable number of stations and with a single waiting queue, while in [4] we studied systems for which every working station has it own waiting queue and the probability of choosing a specific station is based on a random process. In [5] we considered the case for which the stations are clustered in two different classes, each station being devoted to a specific category and with a constant number of stations in each class.

According to the status of each station, they are partitioned in three groups: busy, inactive and in laziness. Busy stations are those currently serving clients. Inactive stations are the ones removed from the system, due to a low number of clients. Finally, for every class of working stations there is at most a station in laziness, when no client is in the waiting queue.

The essential difference between the model with a fixed number of parallel stations and the one that allows for a variable number is the approach of determining the laziness time of the stations.

In the first case, all stations that are not currently working are in laziness while for the latter model, there is at most a single station in laziness when no other client is present in the same class and a potential arrival is expected.

Motivation: In real world there are plenty of systems that can be abstracted as described above. For example in super-markets, the pay desks set can be seen as such a waiting system.

This type of simulation is potentially useful for analyzing and predicting the behavior of client-server based applications, when “organizations or resourceful individuals provide services via a set of loosely-coupled workstation nodes” [9]. We consider that simulation results are a starting point to perform load balancing for a set of resources that are accessed concurrently. Moreover, simulating different scenarios can assure decision support for making a choice between the two main types of scalability [6]: vertical scalability – adding more hardware to the machine, which in our case is lowering the service time for a client – and horizontal scalability – which refers to adding more servers and in our case this is equivalent to adding more working stations. The main target is in this case middleware platforms that use clustered deployment not only for scalability but also for efficiently supporting multiple concurrent applications. From the same area of enterprise applications we also mention the load sensitivity which is an expression of how the response time varies with system’s load [6]. The concept of different classes of clients is encountered in marketing, for which successful strategy is a classification of the firm’s target markets. For example, in [10] a three tier classification system of potential and present clients is discussed. Thus our study based on different types of clients in the simulation mechanism has a strong connection with real-world applications.

REFERENCES:

CORMEN, T. H., C. E. LEIRSON, R. L. RIVEST, Introductions to Algorithms, MIT Press, Cambridge, 2001.
DEVROYE, L., Non-Uniform Random Variate Generation, New York, Springer Verlag, 1986.
FLOREA, I., One Algorithmic Approach of First-Come-First-Served Queuing Systems, Bucharest University Annals, Informatics, ANO XLIX, 2000, pp. 41-58.
FLOREA, I., A. CARSTEA, 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. 12(47), 2005, pp. 115-123.
FLOREA, I., A. CARSTEA, An Alghoritmic Approach of the Queuing Systems with Different Station Classes, Studies in Informatics and Control, vol. 15(4), March 2006, pp. 391-402.
FOWLER, M., Patterns of Enterprise Application Architecture, Addison-Wesley, 2002.
GAMMA, E, R. HELM, R. JOHNSON, J. VLISSIDES, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1994.
GROSS, D., C. HARRIS, Fundamentals of Queuing Theory, John Wiley & Sons, New York, 1998.
PETROU, D., K. AMIR, G. RANGER, G. GIBSON, Easing the Management of Data-parallel Systems Via Adaptation, Proceedings of the 9th ACM SIGOPS European Workshop, Denmark, September 17-20, 2000.
RADER, C., R. COMISH, D. BURCKEL, L. TURPIN, Adapting Marketing Strategies to Customer Buying Processes in the Context of Customer Importance to the Firm, Proceedings of American Society for Business and Behavioral Sciences, Volume 16, no 1, February 2009.
TANNER, M., Practical Queuing Analysis, McGraw-Hill Book Company, 1995.