Article ID: | iaor20063358 |
Country: | United States |
Volume: | 52 |
Issue: | 3 |
Start Page Number: | 232 |
End Page Number: | 242 |
Publication Date: | Apr 2005 |
Journal: | Naval Research Logistics |
Authors: | Simchi-Levi David, Queyranne Maurice, Liu Hui |
Keywords: | heuristics |
We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP-hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal.