Title
Scheduling Unit Jobs with Compatible Release Dates on
Parallel Machines with Nonstationary Speeds
Authors
-
Publication
Springer, Lecture Notes in Computer Science 920, Integer Programming and Combinatorial Optimization, ed. Egon Balas and Jens Clausen, 1995, pp. 307-320
Source
-
Classification
-
not available
Keywords
-
not available
-
-
We consider the problem of nonpreemptively scheduling
a set of jobs with identical processing requirements
( unit jobs) on parallel machines with
nonstationary speeds. In addition to the case of
uniform machines, this allows for such predictable
effects as operator learning and tool wear and tear, as
well as such planned activities as machine upgrades,
maintenance and the preassignment of other operations,
all of which may affect the available processing speed
of the machine at different points in time. We also
allow release dates that satisfy a certain
compatibility property. We show that the convex hull
of feasible completion time vectors is a supermodular
polyhedron. For nonidentical but compatible release
dates, the supermodular function defining this
polyhedron is the Dilworth truncation of a (non
supermodular) function defined in a natural way from
the release dates. This supermodularity result implies
that the total weighted flow time can be minimized by a
greedy algorithm. Supermodular polyhedra thus provide a
general framework for several unit job, parallel
machine scheduling problems and for their solution
methods.
