MINIMIZING MAKESPAN IN THE 2-MACHINE FLOWSHOP WITH RELEASE TIMES

This paper considers the two-machine flow-shop problem with the object ive of minimising the makespan subject to different release times. In view of the strongly NP-hard nature of this problem, five lower bounds and two new dominance criteria are proposed together with a decomposi tion procedure that reduces the problem size by setting jobs at the be ginning of the sequence. Several branch and bound procedures are descr ibed by applying different lower bounds and branching schemes. A detai led computational campaign has been performed on different kinds of in stances testing problems with size up to 200 jobs.