×

On dynamic scheduling of a parallel server system with complete resource pooling. (English) Zbl 0982.90024

McDonald, David R. (ed.) et al., Analysis of communication networks: call centres, traffic and performance. Proceedings of the workshop on analysis and simulation of communication networks, Toronto, Ontario, Canada, November 1998. Providence, RI: AMS, American Mathematical Society. Fields Inst. Commun. 28, 49-71 (2000).
Summary: We consider a dynamic scheduling problem for a parallel server queueing system. This system might be viewed as a model for a manufacturing or computer system, consisting of a bank of buffers for holding incoming jobs and a bank of servers for processing these jobs. Incoming jobs are classified into one of several different classes (or buffers). Jobs within a class are served on a first-in-first-out basis by one of a bank of parallel servers. Servers may have differing but overlapping capabilities and so may be able to service more than one class. The system manager seeks to minimize holding costs by dynamically allocating waiting jobs to available servers.
This paper is organized as follows. In Section 2, we describe the model of a parallel server system considered here. In Section 3, we review the notion of heavy traffic defined in [J. M. Harrison, Ann. Appl. Probab. 10, 75-103 (2000; Zbl 1131.60306)] and [J. M. Harrison and M. J. López, Queueing Systems 33, 339-368 (1999; Zbl 0997.60108)] using a linear program, and we interpret this in terms of the behavior of an associated fluid model. In Section 4, we describe the Brownian control problem. The cost function used there is an average discounted holding cost function. Following Harrison and López [loc. cit.], in Section 5 we present the solution of a reduced form of this problem called the equivalent workload formulation [J. M. Harrison and J. A. Van Mieghem, Ann. Appl. Probab. 7, 747-771 (1997; Zbl 0885.60080), Harrison, loc. cit.], under the complete resource pooling condition of Harrison and López [loc. cit.]. This condition ensures that the Brownian model workload process is one-dimensional and form Harrison and López [loc. cit.] we know this condition is equivalent to uniqueness of a solution to the dual to the heavy traffic linear program described in Section 3. In Section 6, we describe the dynamic threshold-type scheduling policy that we propose for the original parallel server problem.
For the entire collection see [Zbl 0951.00043].

MSC:

90B35 Deterministic scheduling theory in operations research
60K25 Queueing theory (aspects of probability theory)
60J70 Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
PDFBibTeX XMLCite