INSTANCE:
Number
of processors, set J of jobs, each
consisting
of m operations
with
(with
to be
executed by processor i), and for each operation a length .
SOLUTION:
An open-shop schedule for J, i.e., a collection of one-processor schedules
,
,
such that
implies
,
such that for each
the
intervals
are all disjoint.
MEASURE:
The completion time of the schedule, i.e.,
.
Bad News:
Not approximable within 5/4
for any
[466].
Comment:
Approximable within 3/2 if m=3 [106].
Variation in which m=2, but the two processors are replaced by
respectively
and
identical parallel processors, is
approximable within 3/2 if
,
5/3 if
and
otherwise [107].