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 goal is to minimize an 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 0( n4 ) time if preemption is allowed or if total completion time outweighs maximum promptness.
|Title of host publication||Ten years LNMB|
|Subtitle of host publication||Ph.D. research and graduate courses of the Dutch Network of Operations Research|
|Editors||W.K. W.K. Klein Haneveld, O.J. Vrieze, L.C.M. Kallenberg|
|Place of Publication||Amsterdam|
|Publisher||Centrum voor Wiskunde en Informatica|
|ISBN (Print)||90 6196 475X|
|Publication status||Published - 1997|