The asymptotic optimality of the shortest processing time rule for the flow shop mean completion time problem

The asymptotic optimality of the shortest processing time rule for the flow shop mean completion time problem

0.00 Avg rating0 Votes
Article ID: iaor20021659
Country: United States
Volume: 49
Issue: 2
Start Page Number: 293
End Page Number: 304
Publication Date: Mar 2001
Journal: Operations Research
Authors: ,
Keywords: scheduling
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.

Reviews

Required fields are marked *. Your email address will not be published.