HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:37:39 AM
Last modification on : Friday, February 4, 2022 - 3:23:40 AM
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