Article ID: | iaor20108910 |
Volume: | 181 |
Issue: | 1 |
Start Page Number: | 359 |
End Page Number: | 375 |
Publication Date: | Dec 2010 |
Journal: | Annals of Operations Research |
Authors: | Chu Chengbin, Nessah Rabia |
Keywords: | approximation, job shop, parallel machines |
This paper addresses an identical parallel machine scheduling problem with job release dates and unavailability periods to minimize total weighted completion time. This problem is known to be NP-hard in the strong sense. We propose a new lower bound that can be computed in polynomial time. The test on more than 8400 randomly generated instances shows a very significant improvement with respect to existing results for previously studied special cases: without unavailability constraints, unweighted version, or identical job release dates. For instance, the average improvement for the unweighted problem is as much as 20.43% for 2 machines, 53.03% for 7 machines and 66.70% for 15 machines. For some instances, the improvement can be even as much as 93%.