Skip to Main content Skip to Navigation

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

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:37:39 AM
Last modification on : Thursday, February 11, 2021 - 2:48:12 PM
Long-term archiving on: : Thursday, March 24, 2011 - 12:04:17 PM


  • HAL Id : inria-00072699, version 1



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⟩



Record views


Files downloads