Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem

Philip Kaminsky and David Simchi-Levi
Additional contact information
Philip Kaminsky: University of California, Berkeley, California
David Simchi-Levi: Northwestern University, Chicago, Illinois

Operations Research, 1998, vol. 46, issue 6, 872-882

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

Keywords: Production/scheduling; multiple machine sequencing; flow shop weighted completion time problem; Analysis of algorithm; probabilistic analysis (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.6.872 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:6:p:872-882

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().