计算机科学
装箱问题
调度(生产过程)
作业车间调度
剖切面法
数学优化
箱子
算法
运筹学
整数规划
数学
地铁列车时刻表
操作系统
作者
Guopeng Song,Roel Leus
出处
期刊:Informs Journal on Computing
日期:2022-11-01
卷期号:34 (6): 3059-3079
被引量:3
标识
DOI:10.1287/ijoc.2022.1229
摘要
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. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72101264 and 71801218] and the Science and Technology Innovation Team in Higher Educational Institutions of Hunan Province [Grant 2020RC4046]. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.1229 .
科研通智能强力驱动
Strongly Powered by AbleSci AI