Article ID: | iaor20083747 |
Country: | Netherlands |
Volume: | 175 |
Issue: | 2 |
Start Page Number: | 751 |
End Page Number: | 768 |
Publication Date: | Dec 2006 |
Journal: | European Journal of Operational Research |
Authors: | Kovalyov Mikhail Y., Shakhlevich Natalia V., Cheng T.C. Edwin |
The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(