The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem
- 1 April 2001
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 49 (2) , 293-304
Abstract
In the flow shop mean completion time problem, a set of jobs has to be processed on m-machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize the sum of the completion times of all jobs on the final machine. In this paper, we prove the asymptotic optimality of the Shortest Processing Time algorithm for any continuous, independent, and identically distributed job processing times.Keywords
This publication has 9 references indexed in Scilit:
- Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time ProblemOperations Research, 1998
- A Probabilistic Analysis of Two-Machine FlowshopsOperations Research, 1996
- Probabilistic analysis of the minimum weighted flowtime scheduling problemOperations Research Letters, 1992
- The Asymptotic Optimality of the LPT RuleMathematics of Operations Research, 1987
- Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor SchedulingMathematics of Operations Research, 1984
- Probabilistic Analysis of the LPT Processor Scheduling Heuristic1982
- The Complexity of Flowshop and Jobshop SchedulingMathematics of Operations Research, 1976
- Exact, Approximate, and Guaranteed Accuracy Algorithms for the Flow-Shop Problem n / 2 / F / F¯Journal of the ACM, 1975
- Heuristic-Programming Solution of a Flowshop-Scheduling ProblemOperations Research, 1974