Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-19T06:14:40.604Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  14 July 2016

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.

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.

MSC classification

Information

Type
Research Papers
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.)

Article purchase

Temporarily unavailable