Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-03T02:10:05.040Z Has data issue: false hasContentIssue false
  • English
  • Français

The Stochastic Optimality of SEPT in Parallel Machine Scheduling

Published online by Cambridge University Press:  27 July 2009

Cheng-Shang Chang ,
Arie Hordijk ,
Rhonda Righter  and
Gideon Weiss
Cheng-Shang Chang
Affiliation:
IBM Research Division, T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, New York 10598
Arie Hordijk
Affiliation:
Institute of Applied Mathematics and Computer Science, University of Leiden, P.O. Box 9512, 2333 CA Leiden, The Netherlands
Rhonda Righter
Affiliation:
Department of Decision and Information Sciences, Santa Clara University, Santa Clara, California 95053
Gideon Weiss
Affiliation:
Faculty of Industrial Engineering and Management, The Technion, Technion City, Haifa 32000, Israel
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider preemptive scheduling on parallel machines where processing times of jobs are i.i.d. but jobs may already have received distinct amounts of service. We show that when processing times are increasing in likelihood ratio, SEPT (shortest expected [remaining] processing time first) stochastically minimizes any increasing and Schur-concave function of the job completion times. The same result holds when processing times are exponential with possibly different means.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 8 , Issue 2 , April 1994 , pp. 179 - 188
Copyright
Copyright © Cambridge University Press 1994

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

References

1.Chang, C.-S. & Yao, D.D. (1993). Rearrangement, majorization and stochastic scheduling. Mathematics of Operations Research 18: 658–684.CrossRefGoogle Scholar
2.Glazebrook, K.D. (1979). Scheduling tasks with exponential service times on parallel processors. Journal of Applied Probability 16: 685–689.CrossRefGoogle Scholar
3.Marshall, A.W. & Olkin, I. (1979). Inequalities: Theory of majorization and its applications. New York: Academic Press.Google Scholar
4.Pinedo, M. (1983). Stochastic scheduling with release dates and due dates. Operations Research 31:559–572.CrossRefGoogle Scholar
5.Righter, R.L. & Shanthikumar, J.G. (1992). Extremal properties of the FIFO discipline in queue-ing networks. Journal of Applied Probability 29: 967–978.CrossRefGoogle Scholar
6.Ross, S.M. (1983). Stochastic processes. New York: Wiley.Google Scholar
7.Weber, R.R. (1982). Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime. Journal of Applied Probability 19: 167–182.CrossRefGoogle Scholar
8.Weber, R.R., Varaiya, P., & Walrand, J. (1986). Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. Journal of Applied Probability 23: 841–847.CrossRefGoogle Scholar