Minimizing makespan on a two-machine re-entrant flowshop

Abstract

This paper focuses on a two-machine re-entrant flowshop scheduling problem with the objective of minimizing makespan. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. We develop dominance properties, lower bounds and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.

Keywords:

• scheduling
• re-entrant flowshop
• branch and bound
• heuristics