RT Journal Article
T1 On dual based lower bounds for the sequential ordering problem with precedences and due dates
A1 Ortuño Sánchez, María Teresa
A1 Alonso Ayuso, Antonio
A1 Detti, Paolo
A1 Escudero Bueno, Laureano Fernando
AB The Sequential Ordering Problem ( herewith, SOP) with precedence relationships was introduced in Escudero (1988), and extended to cover release and due dates in Escudero and Sciomachen (1993). 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 nodes and the arcs, satisfying precedence relationships among the nodes and given lower and upper bounds on the weights of the Hamiltonian subpaths. In this paper we present a model for the constrained minimum weight Hamiltonian path problem with precedences and due dates forcing constraints, and introduce related valid cuts that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation procedure to obtain those cuts, so-called the Lagrangian Relax-and-Cut (LRC) scheme. Computational experience is given for variations of some SOP cases already reported in the literature.
PB Springer
SN 0254-5330
YR 2003
FD 2003-11
LK https://hdl.handle.net/20.500.14352/50247
UL https://hdl.handle.net/20.500.14352/50247
LA eng
NO Alonso-Ayuso, Antonio, Paolo Detti, Laureano F. Escudero, y M. Teresa Ortuño. «On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates». Annals of Operations Research 124, n.o 1-4 (noviembre de 2003): 111-31. https://doi.org/10.1023/B:ANOR.0000004765.69773.41.
NO Dirección General de Coordinación y Estudios (España)
NO Comisión Interministerial de Ciencia y Tecnología (España)
NO Comunidad de Madrid
DS Docta Complutense
RD 17 abr 2025