Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty

Marco Silva, Michael Poss and Nelson Maculan

European Journal of Operational Research, 2020, vol. 283, issue 1, 70-82

Abstract: We investigate algorithms that solve exactly the robust single machine scheduling problem that minimizes the total tardiness. We model the processing times as uncertain and let them take any value in a budgeted uncertainty set. Therefore, the objective seeks to minimize the worst-case tardiness over all possible values. We compare, through computational experiments, two types of solution algorithms. The first combines classical MILP formulations with row-and-column generation algorithms. The second generalizes the classical branch-and-bound algorithms to the robust context, extending state-of-the-art concepts used for the deterministic version of the problem. By generalizing the classical branch-and-bound algorithm we are able to assemble and discuss good algorithmic decisions steps that once put together make our robust branch-and-bound case attractive. For example, we extend and adapt dominance rules to our uncertain problem, making them an important component of our robust algorithms. We assess our algorithms on instances inspired by the scientific literature and identify under what conditions an algorithm has better performance than others. We introduce a new classifying parameter to group our instances, also extending existing methods for the deterministic problem case.

Keywords: Robust optimization; Scheduling problem; Row-and-column generation; Integer programming; Branch-and-bound (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719308720
Full text for ScienceDirect subscribers only

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:eee:ejores:v:283:y:2020:i:1:p:70-82

DOI: 10.1016/j.ejor.2019.10.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().