Minimising maximum lateness in a two-machine flowshop

Abstract

The objective of this paper is to develop a branch and bound algorithm for the problem of minimising maximum lateness in a two-machine flowshop, subject to release dates and time lag constraints. The importance of this NP-hard problem is twofold, it arises as a strong relaxation of the classical permutation flowshop problem, and it generalises several well studied two-machine flowshop problems. Computational experiments performed on a large set of randomly generated problems show that our algorithm can solve to optimality large size instances.

Keywords:

• scheduling
• permutation flowshop
• lateness
• branch and bound