Article ID Journal Published Year Pages File Type
1142938 Operations Research Letters 2012 5 Pages PDF
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
, , , , , ,