- 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.,
.

*Good News:*Approximable within 2 [347].*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].*Garey and Johnson:*SS14