Next: Miscellaneous Up: Shop Scheduling Previous: MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING Index

### MINIMUM JOB SHOP SCHEDULING

- 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