Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T20:28:11.323Z Has data issue: false hasContentIssue false
  • English
  • Français

On the optimality of LEPT and μc rules for parallel processors and dependent arrival processes

Part of: Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Arie Hordijk  and
Ger Koole
Arie Hordijk*
Affiliation:
University of Leiden
Ger Koole
Affiliation:
University of Leiden
*
* Postal address: Dept. of Mathematics and Computer Science, University of Leiden P.O. Box 9512, 2300 RA Leiden, The Netherlands.
Get access Rights & Permissions [Opens in a new window]

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

STOCHASTIC SCHEDULINGDYNAMIC PROGRAMMINGDEPENDENT ARRIVALS

MSC classification

Primary: 90B22: Queues and service
Secondary: 90C40: Markov and semi-Markov decision processes

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 25 , Issue 4 , December 1993 , pp. 979 - 996
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

**

Present address: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.

References

[1] Asmussen, S. and Koole, G. (1993) Marked point processes as limits of Markovian arrival streams. J. Appl. Prob. 30, 365–372.Google Scholar
[2] Baras, J. S., Dorsey, A. J. and Makowski, A. M. (1985) Two competing queues with linear costs and geometric service requirements: the µc-rule is often optimal. Adv. Appl. Prob. 17, 186–209.CrossRefGoogle Scholar
[3] Baras, J. S., Ma, D.-J. and Makowski, A. M. (1985) K competing queues with geometric service requirements and linear costs: the µc-rule is always optimal. Syst. Control Lett. 6, 173–180.Google Scholar
[4] Bruno, J., Downey, P. and Frederickson, G. N. (1981) Sequencing tasks with exponential service times to minimize the expected flow time or makespan. J. Assoc. Comput. Mach. 28, 100–113.Google Scholar
[5] Buyukkoc, C., Varaiya, P. and Walrand, J. (1985) The cp rule revisited. Adv. Appl. Prob. 17, 237–238.Google Scholar
[6] Chang, C. S., Chao, X., Pinedo, M. and Weber, R. R. (1992) On the optimality of LEPT and cµ-rules for machines in parallel. J. Appl. Prob. 29, 667–681.Google Scholar
[7] Hordijk, A. and Koole, G. (1992) The µc-rule is not optimal in the second node of the tandem queue: a counterexample. Adv. Appl. Prob. 24, 234–237.Google Scholar
[8] Hordijk, A. and Koole, G. (1992) On the assignment of customers to parallel queues. Prob. Eng. Inf. Sci. 6, 495–511.Google Scholar
[9] Kämpke, T. (1989) Optimal scheduling of jobs with exponential service times on parallel processors. Operat. Res. 37, 126–133.Google Scholar
[10] Koole, G. (1992) Stochastic scheduling and dynamic programming. Ph.D. thesis, University of Leiden. (Available from the author on request.) Google Scholar
[11] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Johns Hopkins University Press, Baltimore.Google Scholar
[12] Pinedo, M. (1983) Stochastic scheduling with stochastic release dates and due dates. Operat. Res. 31, 559–572.Google Scholar
[13] Pinedo, M. and Weiss, G. (1971) Scheduling of stochastic tasks on two parallel processors. Naval Res. Logist. Quart. 26, 527–535.Google Scholar
[14] Righter, R. and Shanthikumar, J. G. (1989) Scheduling multiclass single server queueing systems to stochastically maximize the number of successful departures. Prob. Eng. Inf. Sci., 3, 323–333.Google Scholar
[15] Righter, R. and Shanthikumar, J. G. (1992) Extension of the bivariate characterization for stochastic orders. Adv. Appl. Prob. 24, 506–508.CrossRefGoogle Scholar
[16] Ross, S. M. (1983) Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
[17] Shanthikumar, J. G. and Yao, D. D. W. (1992) Multiclass queueing systems: polymatroidal structure and optimal scheduling control. Operat. Res. 40, S293–S299.CrossRefGoogle Scholar
[18] Van Der Heyden, L. (1981) Scheduling jobs with exponential service times on non-identical processors so as to minimize expected makespan. Math. Operat. Res. 6, 305–312.Google Scholar
[19] Walrand, J. (1988) An Introduction to Queueing Networks. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
[20] Weber, R. R. (1982) Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime. J. App. Prob. 19, 167–182.Google Scholar
[21] Weber, R. R. (1983) Scheduling stochatic jobs on parallel machines to minimize makespan or flowtime. In Applied Probability-Computer Science: The Interface, ed. Disney, R. and Ott, T. Birkhauser, Boston.Google Scholar
[22] Weber, R. R. (1988) Stochastic scheduling on parallel processors and minimization of concave functions of completion times. In Stochastic Differential Systems, Stochastic Control Theory and Applications 10, ed. Fleming, W. and Lions, P.-L. Springer-Verlag, New York.Google Scholar
[23] Weiss, G. (1982) Multiserver stochastic scheduling. In Deterministic and Stochastic Scheduling, ed. Dempster, M. A. H., Lenstra, J. K. and Rinnooy Kan, A. H. G. Reidel, Dordrecht.Google Scholar
[24] Weiss, G. and Pinedo, M. (1980) Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Prob. 17, 187–202.Google Scholar