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
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
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) Track citations by RSS feed
Downloads: (external link)
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 [301 Moved Permanently]--> https://www.fep.up.pt/investigacao/workingpapers/wp129.pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
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 ().