Probabilistic analysis and practical algorithms for the flow shop weighted completion time problem

Probabilistic analysis and practical algorithms for the flow shop weighted completion time problem

0.00 Avg rating0 Votes
Article ID: iaor2000770
Country: United States
Volume: 46
Issue: 6
Start Page Number: 872
End Page Number: 882
Publication Date: Nov 1998
Journal: Operations Research
Authors: ,
Abstract:

In the flow shop weighted 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 weighted completion times of all jobs on the final machine. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of the job processing times and weights. In particular, we show that the optimal objective value of this problem is asymptotically equivalent to certain single and parallel machine scheduling problems. This characterization leads to a better understanding of the effectiveness of the celebrated weighted shortest processing time (WSPT) algorithm, as well as to the development of an effective algorithm closely related to the profile fitting heuristic, which was previously utilized for flow shop makespan problems. Computational results show the effectiveness of WSPT and this modified profile fitting heuristic on a set of random test problems.

Reviews

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