A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships |
| |
Authors: | L F Escudero Monique Guignard Kavindra Malik |
| |
Institution: | (1) Mathematical Sciences School, University of Madrid, 28040 Madrid, Spain;(2) The Wharton School, University of Pennsylvania, 19104-6366 Philadelphia, PA, USA;(3) Johnson Graduate School of Management, Cornell University, 14853 Ithaca, NY, USA |
| |
Abstract: | The sequential ordering problem with precedence relationships was introduced in Escudero 7]. It has a broad range of applications, mainly in production planning for manufacturing systems. The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the arcs, subject to precedence relationships among nodes. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, and the weights are sums of processing and setup times. We introduce a formulation for the constrained minimum weight Hamiltonian path problem. We also define Lagrangian relaxation for obtaining strong lower bounds on the makespan, and valid cuts for further tightening of the lower bounds. Computational experience is given for real-life cases already reported in the literature. |
| |
Keywords: | Hamiltonian path minimum arborescence Lagrangian multipliers 0– 1 model precedence cutting planes makespan sequencing |
本文献已被 SpringerLink 等数据库收录! |
|