Algorithms for two-machine flow-shop sequencing with precedence constraints

This paper considers the problem of minimizing the maximum completion time in a two-machine flow-shop for which precedence constraints on the jobs are specified. If one job has precedence over another, then the second of these jobs cannot be processed on a machine until the first of them is completed on that machine. A powerful new lower bounding rule which uses Lagrangean relaxation is developed. Then several dominance theorems are presented which are used to eliminate some jobs from the problem. The lower bound is used in three branch and bound algorithms, two of which employ well-known branching rules while the third uses a new branching rule. The algorithms are compared and tested on problems with up to 80 jobs.