Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods

Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods

0.00 Avg rating0 Votes
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: ,
Keywords: approximation, job shop, parallel machines
Abstract:

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

Reviews

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