Algorithms for two-machine flow-shop sequencing with precedence constraints (Q800822)

This paper studies a scheduling problem of minimizing the maximum completion time in a two-machine flow-shop for which precedence constraints on jobs are specified, implying if one job has precedence over another, then the former must be completed on a machine before the latter begins processing on that machine. For this problem a branch-and-bound algorithm is proposed, including a new lower bounding rule based on Lagrangean relaxation and a new branching rule. This algorithm is compared to two existing branch-and- bound methods and tested up to 80 jobs, but it does not appear to be significantly superior to the others.