Scheduling with target start times
We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The objective is to minimize a bicriteria objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in O(n4) time if preemption is allowed or if total completion time outweighs maximum promptness.
|Keywords||Bicriteria scheduling, maximum promptness, single-machine scheduling, target start times, total completion time|
|Persistent URL||dx.doi.org/10.1016/S0377-2217(99)00426-9, hdl.handle.net/1765/12333|
Hoogeveen, J.A., & van de Velde, S.L.. (2000). Scheduling with target start times. European Journal of Operational Research, 129(1), 87–94. doi:10.1016/S0377-2217(99)00426-9