A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships (Q1339126)

This paper discusses the sequential ordering problem with precedence relation (SOP). The SOP consists of finding a minimum weight Hamilton path on a directed graph with weights on the arcs, subject to given precedence constraints. This paper presents a 0-1 model for the SOP and develops a Lagrangian relax-and-cut approach to obtain strong lower bounds on the makespan and valid cuts for further tightening of the bounds. Computational experience for real life cases shows better results than those in literatures.