Methods and algorithms for job scheduling in systems with parallel service: a survey

The review of research papers devoted to the analysis of the dispatching problem in queueing systems is presented. The analysis is restricted to the class of systems with independent, operating in parallel, fully reliable servers, stochastic incoming flows of customers without any preceding constraints. The general goal of the analysis carried out in most of the papers is the solution of an optimization problem, which specification heavily depends on additional assumptions made. The models considered in the review are classified into several classes depending on the amount of a priori information and observability at decision times and performance criteria. The description of the dispatching algorithms most commonly found in literature and their properties is given. The main methods used for the analysis of the systems under these dispatching algorithms are reviewed. This review is intended to draw attention of the research community to one of the important problems in the field of information processing.