Article ID: | iaor20083748 |
Country: | Netherlands |
Volume: | 175 |
Issue: | 2 |
Start Page Number: | 769 |
End Page Number: | 781 |
Publication Date: | Dec 2006 |
Journal: | European Journal of Operational Research |
Authors: | Kovalyov Mikhail Y., Shakhlevich Natalia V., Cheng T.C. Edwin |
The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(