Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms

Guopeng Song () and Roel Leus ()
Additional contact information
Guopeng Song: College of Systems Engineering, National University of Defense Technology, 410073 Changsha, China
Roel Leus: Research Centre for Operations Research and Statistics (ORSTAT), Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 3059-3079

Abstract: We study parallel machine scheduling for makespan minimization with uncertain job processing times. To incorporate uncertainty and generate solutions that are, in some way, insensitive to unfolding information, three different modeling paradigms are adopted: a robust model, a chance-constrained model, and a distributionally robust chance-constrained model. We focus on devising generic solution methods that can efficiently handle these different models. We develop two general solution procedures: a cutting-plane method that leverages the submodularity in the models and a customized dichotomic search procedure with a decision version of a bin packing variant under uncertainty solved in each iteration. A branch-and-price algorithm is designed to solve the bin packing problems. The efficiency of our methods is shown through extensive computational tests. We compare the solutions from the different models and report the general lessons learned regarding the choice between different frameworks for planning under uncertainty.

Keywords: parallel machine scheduling; optimization under uncertainty; bin packing; branch and price (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1229 (application/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:inm:orijoc:v:34:y:2022:i:6:p:3059-3079

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().