A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times

Edward Sewell (), Jason Sauppe (), David Morrison (), Sheldon Jacobson () and Gio Kao ()

Journal of Global Optimization, 2012, vol. 54, issue 4, 812 pages

Abstract: This paper presents a Branch, Bound, and Remember (BB&R) exact algorithm using the Cyclic Best First Search (CBFS) exploration strategy for solving the $${1|ST_{sd}|\sum T_{i}}$$ scheduling problem, a single machine scheduling problem with sequence dependent setup times where the objective is to find a schedule with minimum total tardiness. The BB&R algorithm incorporates memory-based dominance rules to reduce the solution search space. The algorithm creates schedules in the reverse direction for problems where fewer than half the jobs are expected to be tardy. In addition, a branch and bound algorithm is used to efficiently compute tighter lower bounds for the problem. This paper also presents a counterexample for a previously reported exact algorithm in Luo and Chu (Appl Math Comput 183(1):575–588, 2006 ) and Luo et al. (Int J Prod Res 44(17):3367–3378, 2006 ). Computational experiments demonstrate that the algorithm is two orders of magnitude faster than the fastest exact algorithm that has appeared in the literature. Computational experiments on two sets of benchmark problems demonstrate that the CBFS search exploration strategy can be used as an effective heuristic on problems that are too large to solve to optimality. Copyright Springer Science+Business Media, LLC. 2012

Keywords: Branch and bound algorithms; Scheduling theory and algorithms; Dynamic programming; Dominance rules (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-011-9793-z (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:jglopt:v:54:y:2012:i:4:p:791-812

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-011-9793-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().