On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates |
| |
Authors: | Antonio Alonso-Ayuso Paolo Detti Laureano F Escudero M Teresa Ortuño |
| |
Institution: | 1. Departamento de Ciencias Experimentales y Tecnología, Universidad Rey Juan Carlos, 28933, Móstoles, Madrid, Spain 2. Dipartimento di Ingegneria dell'Informazione, Università di Siena, Via Roma 56, 53100, Siena, Italy 3. Centro de Investigación Operativa, Universidad Miguel Hernández, Avda. del Ferrocarril s/n, 03202, Elche (Alicante), Spain 4. Departamento de Estadística e Investigación Operativa I, Facultad de Matemáticas, Universidad Complutense de Madrid, Avda. Complutense s/n, 28040, Madrid, Spain
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|