Improved Lower Bounds for the Early/Tardy Scheduling Problem with No Idle Time

Jorge M. S. Valente () and Rui A. F. S. Alves ()
Additional contact information
Jorge M. S. Valente: Faculdade de Economia da Universidade do Porto
Rui A. F. S. Alves: Faculdade de Economia da Universidade do Porto

FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto

Abstract: In this paper we consider the single machine earliness/tardiness scheduling problem with no idle time. Two of the lower bounds previously developed for this problem are based on lagrangean relaxation and the multiplier adjustment method, and require an initial sequence. We investigate the sensitivity of the lower bounds to the initial sequence, and experiment with di?erent dispatch rules and some dominance conditions. The computational results show that it is possible to obtain improved lower bounds by using a better initial sequence. The lower bounds are also incorporated in a branch-and-bound algorithm, and the computational tests show that one of the new lower bounds has the best performance for larger instances.

Keywords: scheduling; early/tardy; lower bound (search for similar items in EconPapers)
Pages: 23 pages
Date: 2003-04
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/wp125.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://www.fep.up.pt/investigacao/workingpapers/wp125.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/wp125.pdf)

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:por:fepwps:125

Access Statistics for this paper

More papers in FEP Working Papers from Universidade do Porto, Faculdade de Economia do Porto Contact information at EDIRC.
Bibliographic data for series maintained by ().