G-88-29
Production Scheduling: Complexity and Approximate Algorithms
BibTeX reference
This research review presents very recent results in the theory of deterministic scheduling in production systems. The deterministic models dealt with include: openshop, jobshop, flowshop and flowshop with parallel machines. The objective functions considered are: minimization of job finish time, known also as makespan and minimization of the sum of the completion times of all jobs, known also as mean flowtime. The processing of a job by a machine is nonpreemptive. A few of the more significant NP-Completeness results are highlighted. The approximate algorithms for production scheduling problems are presented and the performance of these algorithms is discussed.
Published June 1988 , 31 pages
This cahier was revised in January 1989