Two-machine flowshop scheduling with availability constraints

✍ Scribed by Chung-Yee Lee

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 143 KB
• Volume: 114
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00452-9

✦ Synopsis

The majority of the scheduling literature carries a common assumption that machines are available all the time. However, this availability assumption may not be true in real industry settings, since a machine may become unavailable during certain periods of time when, for instance, a machine breakdown or a preventive maintenance activity is scheduled. Although the problem is realistic and important, it is relatively new and unstudied. In this paper, we study the two-machine ¯owshop problem under the assumption that the unavailable time is known in advance. We assume that if a job cannot be ®nished before the next down period of a machine then the job will have to partially restart when the machine has become available again. We call our model semiresumable. Our model contains two important special cases: resumable where the job can be continued without any penalty and nonresumable where the job needs to totally restart. We study the problem where an availability constraint is imposed only on one machine as well as on both machines. We provide complexity analysis, develop a pseudo-polynomial dynamic programming algorithm to solve the problem optimally and also propose heuristic algorithms with an error bound analysis.