On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates

Antonio Alonso-Ayuso, Paolo Detti, Laureano Escudero and M. Ortuño ()

Annals of Operations Research, 2003, vol. 124, issue 1, 131 pages

Abstract: 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. Copyright Kluwer Academic Publishers 2003

Keywords: Hamiltonian path; sequential ordering problem; precedences; due dates; minimum arborescence; Lagrangian relaxation; permutation path (search for similar items in EconPapers)
Date: 2003
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000004765.69773.41 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:124:y:2003:i:1:p:111-131:10.1023/b:anor.0000004765.69773.41

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000004765.69773.41

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().