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.

Bicriteria scheduling, maximum promptness, single-machine scheduling, target start times, total completion time
dx.doi.org/10.1016/S0377-2217(99)00426-9, hdl.handle.net/1765/12333
ERIM Top-Core Articles
European Journal of Operational Research
Erasmus Research Institute of Management

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