期刊
INFORMS JOURNAL ON COMPUTING
卷 34, 期 6, 页码 3059-3079出版社
INFORMS
DOI: 10.1287/ijoc.2022.1229
关键词
parallel machine scheduling; optimization under uncertainty; bin packing; branch and price
资金
- National Natural Science Foundation of China [72101264, 71801218]
- Science and Technology Innovation Team in Higher Educational Institutions of Hunan Province [2020RC4046]
This study investigates parallel machine scheduling with uncertain job processing times and adopts three different modeling paradigms to handle uncertainty. Generic solution methods are proposed and compared, and general lessons are learned regarding the choice between different frameworks for planning under uncertainty.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据