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 nj operations oi,j 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
fp(oi,j) >
fp(oi',j') implies
and such
that
.
- MEASURE:
The completion time of the schedule, i.e.,
.
- Good News:
Approximable within
,
where
and
[188].
- Bad News:
Not approximable within 5/4
for any
[443].
- Comment:
Transformation from 3-PARTITION.
Approximable within
if each job must be processed on each machine at most once
[417].
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
[417].
- Garey and Johnson: SS18
Next: Miscellaneous
Up: Shop Scheduling
Previous: MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING
  Index
Viggo Kann
1999-04-22