Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142938 | Operations Research Letters | 2012 | 5 Pages |
Abstract
We consider preemptive machine scheduling problems on identical parallel machines. It is shown that every such problem with chain-like precedence constraints, release dates and a regular unit-concave objective function (e.g. total weighted tardiness and total weighted number of late jobs) has the following integer preemption property: for any problem instance with integral input data there exists an optimal schedule where all interruptions (as well as starting and completion times of jobs) occur at integer time points.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ph. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov, M. Sviridenko,