On the optimality of LEPT and μc rules for parallel processors and dependent arrival processes
- 1 December 1993
- journal article
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 25 (4) , 979-996
- https://doi.org/10.2307/1427802
Abstract
In this paper we study scheduling problems of multiclass customers on identical parallel processors. A new type of arrival process, called a Markov decision arrival process, is introduced. This arrival process can be controlled and allows for an indirect dependence on the numbers of customers in the queues. As a special case we show the optimality of LEPT and the µc-rule in the last node of a controlled tandem network for various cost structures. A unifying proof using dynamic programming is given.Keywords
This publication has 17 references indexed in Scilit:
- On the optimality of LEPT and cµ rules for machines in parallelJournal of Applied Probability, 1992
- On the Assignment of Customers to Parallel QueuesProbability in the Engineering and Informational Sciences, 1992
- Extension of the bivariate characterization for stochastic ordersAdvances in Applied Probability, 1992
- Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling ControlOperations Research, 1992
- The µc-rule is not optimal in the second node of the tandem queue: a counterexampleAdvances in Applied Probability, 1992
- Optimal Scheduling of Jobs with Exponential Service Times on Identical Parallel ProcessorsOperations Research, 1989
- Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful DeparturesProbability in the Engineering and Informational Sciences, 1989
- Stochastic Scheduling with Release Dates and Due DatesOperations Research, 1983
- Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtimeJournal of Applied Probability, 1982
- Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or MakespanJournal of the ACM, 1981