Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T18:34:40.991Z Has data issue: false hasContentIssue false
  • English
  • Français

On the optimality of LEPT and cµ rules for machines in parallel

Part of: Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Cheng-Shang Chang ,
Xiuli Chao ,
Michael Pinedo  and
Richard Weber
Cheng-Shang Chang*
Affiliation:
T. J. Watson Research Center
Xiuli Chao*
Affiliation:
New Jersey Institute of Technology
Michael Pinedo*
Affiliation:
Columbia University
Richard Weber*
Affiliation:
University of Cambridge
*
∗Postal address: IBM Research Division, T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA.
∗∗Postal address: Division of Industrial and Management Engineering, New Jersey Institute of Technology, Newark, NJ 07102, USA.
∗∗∗Postal address: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027, USA.
∗∗∗∗Postal address: Cambridge University Engineering Department, Mill Lane, Cambridge, CB2 1RX, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider scheduling problems with m machines in parallel and n jobs. The machines are subject to breakdown and repair. Jobs have exponentially distributed processing times and possibly random release dates. For cost functions that only depend on the set of uncompleted jobs at time t we provide necessary and sufficient conditions for the LEPT rule to minimize the expected cost at all t within the class of preemptive policies. This encompasses results that are known for makespan, and provides new results for the work remaining at time t. An application is that if the cµ rule has the same priority assignment as the LEPT rule then it minimizes the expected weighted number of jobs in the system for all t. Given appropriate conditions, we also show that the cµ rule minimizes the expected value of other objective functions, such as weighted sum of job completion times, weighted number of late jobs, or weighted sum of job tardinesses, when jobs have a common random due date.

Keywords

EXPONENTIAL DISTRIBUTIONMAKESPANPRIORITY POLICIESSTOCHASTIC SCHEDULINGWEIGHTED FLOWTIME

MSC classification

Primary: 90B35: Scheduling theory, deterministic
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 3 , September 1992 , pp. 667 - 681
Copyright
Copyright © Applied Probability Trust 1992 

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.)

Footnotes

The research of this author was partially supported by the NSF under grant ECS 86–14689.

References

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.Google Scholar
Buyukkoc, C., Varaiya, P. and Walrand, J. (1985) The cµ rule revisited. Adv. Appl. Prob. 17, 237–238.Google Scholar
Chang, C. S. (1992) Ordering for stochastic majorization: theory and applications. Adv. Appl. Prob. 24(3).Google Scholar
Chang, C. S. and Yao, D. D. (1990) Rearrangement, majorization and stochastic scheduling.Google Scholar
Frederickson, G. N., Bruno, J. and Downey, P. (1981) Sequencing tasks with exponential service times to minimize the expected flow time or makespan. J. Assoc. Comput. Mach. 28, 100–113.Google Scholar
Kämpke, T. (1987) On the optimality of static priority policies in stochastic scheduling on parallel machines. J. Appl. Prob. 24, 430–448.Google Scholar
Kämpke, T. (1989) Optimal scheduling of jobs with exponential service times on identical parallel processors. Operat. Res. 37, 126–133.CrossRefGoogle Scholar
Keilson, T. (1979) Markov Chain Models - Rarity and Exponentiality. Springer-Verlag, New York.CrossRefGoogle Scholar
Marshall, A. W. and Olkin, I. (1979) Inequalities: Theory of Majorization and its Applications. Academic Press, New York.Google Scholar
Muirhead, R. F. (1903) Some methods applicable to identities and inequalities of symmetric algebraic functions with n letters. Proc. Edinburgh Math. Soc. 21, 144–157.Google Scholar
Pinedo, M. (1983) Stochastic scheduling with release dates and due dates. Operat. Res. 31, 559–572.CrossRefGoogle Scholar
Pinedo, M. and Rammouz, E. (1988) A note on stochastic scheduling on a single machine subject to breakdown and repair. Prob. Eng. Inf. Sci. 2, 41–49.CrossRefGoogle Scholar
Pinedo, M. and Weiss, G. (1979) Scheduling stochastic tasks on two parallel processors. Naval Res. Log. Quart. 26, 527–535.Google Scholar
Ross, S. M. (1983) Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
Shanthikumar, J. G. and Yao, D. D. W. (1991) Multiclass queueing systems: polymatroidal structure and optimal scheduling control. Operat. Res. Google Scholar
Van Der Heyden, L. (1981) Scheduling jobs with exponential processing and arrival times on identical processors so as to minimize expected makespan. Math. Operat. Res. 6, 305–312.CrossRefGoogle Scholar
Walrand, J. (1988) An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Weber, R. R. (1982) Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime. J. Appl. Prob. 19, 167–182.CrossRefGoogle Scholar
Weber, R. R. (1983) Scheduling stochastic jobs on parallel machines to minimize makespan or flowtime. In Applied Probability - Computer Science: The Interface , ed. Disney, R. and Ott, T., pp. 327–338. Birkhauser, Boston, MA.Google Scholar
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., pp. 601–609. Springer-Verlag, New York.Google Scholar
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., pp. 157–179. Reidel, Dordrecht.Google Scholar
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