A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships (Q1339126)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships |
scientific article; zbMATH DE number 698910
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships |
scientific article; zbMATH DE number 698910 |
Statements
A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships (English)
0 references
15 February 1996
0 references
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.
0 references
sequential ordering problem
0 references
precedence relation
0 references
minimum weight Hamilton path
0 references
directed graph
0 references
Lagrangian relax-and-cut approach
0 references
strong lower bounds
0 references
makespan
0 references
0 references
