Back

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.

, 31 pages

This cahier was revised in January 1989