No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates

Abstract

In this paper, we consider the two-machine no-wait flow-shop scheduling problem, when every machine is subject to one non-availability constraint and jobs have different release dates. The non-availability intervals of the machines overlap and they are known in advance. We aim to find a non-resumable schedule that minimises the makespan. We propose several lower bounds and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method.

Keywords:

• scheduling
• flow-shop
• no-wait, non-availability
• branch-and-bound algorithm

Acknowledgements

We thank the referees for their constructive comments which significantly improved the paper.