Next: Miscellaneous
Up: Shop Scheduling
Previous: MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING
  Index
- INSTANCE:
Number
of processors, set J of jobs, each
consisting
of a sequence of
operations
with
,
for each such operation a processor
and a length
.
- SOLUTION:
A job shop schedule for J, i.e., a collection of one-processor schedules
such that
implies
and such
that
.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within
,
where
and
[200].
- Bad News:
Not approximable within 5/4
for any
[466].
- Comment:
Transformation from 3-PARTITION.
Approximable within
if each job must be processed on each machine at most once
[440].
The variation in which the operations must be processed in an order
consistent to a particular partial order, and the variation in
which there are different types of machines, for each type, there are
a specified number of identical processors, and each operation may be
processed on any processor of the appropriate type,
are approximable within
[440].
- Garey and Johnson: SS18
Next: Miscellaneous
Up: Shop Scheduling
Previous: MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING
  Index
Viggo Kann
2000-03-20