On due-date based valid cuts for the sequential ordering problem. (English) Zbl 0893.90088
Summary: The sequential ordering problem with precedence relationships was introduced by the first author [Eur. J. Oper. Res. 37, No. 2, 236-249 (1988; Zbl 0653.90036)] and extended to cover release and due dates in a paper of L. F. Escudero and A. Sciomachen [Ann. Oper. Res. 43, No. 1-4, 397-416 (1993; Zbl 0784.90035)]. The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and lower and upper bounds on the Hamiltonian subpaths. In this paper we introduce valid cuts derived from the due date constraints that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation algorithm to obtain those cuts.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C35 | Programming involving graphs or networks |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
| 90C30 | Nonlinear programming |
Keywords:
integer programming; Lagrangean relaxation; Hamiltonian path; valid cuts; tightening; sequential ordering problem; precedence relationships; minimum weight Hamiltonian path; directed graphReferences:
| [1] | N. Ascheuer, L.F. Escudero, M. Grötschel and M. Stoer (1993), A cutting Plane Approach to the Sequential Ordering Problem (With Applications to Job Scheduling in Manufacturing),SIAM J. on Optimization,3, pp. 25–42. · Zbl 0794.90039 · doi:10.1137/0803002 |
| [2] | E. Balas, M. Fischetti and W.R. Pulleyblank (1995), The Precedence-Constrained Asymmetric Traveling Salesman Polytope,Mathematical Programming,68, pp. 241–265. · Zbl 0835.90109 |
| [3] | L.F. Escudero (1988), An Inexact Algorithm for the Sequential Ordering Problem,European Journal of Operational Research,37, pp. 236–253. · Zbl 0653.90036 · doi:10.1016/0377-2217(88)90333-5 |
| [4] | L.F. Escudero, M. Guignard and K. Malik (1994), A Lagrangian relax-and-cut approach for Sequential Ordering Problem with Precedence Relationships,Annals of Operations Research,50, pp. 219–237. · Zbl 0833.90068 · doi:10.1007/BF02085641 |
| [5] | L.F. Escudero and A. Schiomachen (1993), Local Search Procedures for Improving Feasible Solutions to the Sequential ordering Problem,Annals of Operations Research,43, pp. 397–416. · Zbl 0784.90035 · doi:10.1007/BF02024937 |
| [6] | M.T. Ortuño (1995), Sobre cortes Lagrangianos Fuertes en la resolución del Problema del Ordenamiento Secuencial, Thesis Dissertation,Universidad Complutense de Madrid. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
