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 (see MINIMUM OPEN-SHOP SCHEDULING) such that,
for each
and ,
.
MEASURE:
The completion time of the schedule, i.e.,
.
Good News:
Approximable within m/2 if m is even and within m/2 + 1/6 if
m is odd [104].
Bad News:
Not approximable within 5/4
for any
[466].
Comment:
Approximable within 5/3 if m=3 [104].
Variation in which m=2, but the two processors are replaced by
respectively
and
identical parallel processors, is
approximable within
[103].