Scheduling and Controlling Work-in-Process : An on Line Study for Shop Problems

Fabrice Chauvet , Jean-Marie Proth (1)

1 SAGEP - Simulation, analyse et gestion des systèmes de production

In this paper, we address the problem of production systems having two characteristics. First, the manufacturing times can be chosen between given bounds. Such a production system is said to have controllable processing times. Second, an operation must start as soon as the previous operation on the same part (if any) is completed. A production system having this characteristic is said to be no-wait. Several on-line schedules are considered to minimize the makespan in flow shop and job shop situations. We prove that in the worst case, the makespan provided by these schedules is m times longer than the optimal one (for different flow shops and job shops), m being the number of machines. We give several related results on competitive ratio.

Mots clés: on-line scheduling; no-wait problems; controllable processing times

Domaines: Autre [cs.OH]

Fabrice Chauvet, Jean-Marie Proth. Scheduling and Controlling Work-in-Process : An on Line Study for Shop Problems. [Research Report] RR-3950, INRIA. 2000, pp.15. ⟨inria-00072699⟩