An Exact Approach to Early/Tardy Scheduling with Release Dates

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 di?erent release dates and no unforced idle time. The problem is decomposed into a weighted earliness subproblem and a weighted tardiness subproblem. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is then simply the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.

Keywords: scheduling; early/tardy; release dates; lower bounds; branch-and-bound (search for similar items in EconPapers)
Pages: 17 pages
Date: 2003-05
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 (10)

Downloads: (external link)
http://www.fep.up.pt/investigacao/workingpapers/wp129.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/wp129.pdf [302 Found]--> https://fep.up.pt/investigacao/workingpapers/wp129.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:129

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 ().