- 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