Parallel Machine Scheduling Under Uncertainty: Models and Exact Algorithms
研究了加工时间不确定的并行机调度问题，以最小化最大完工时间为目标，提出了鲁棒、机会约束和分布鲁棒三种模型，并设计了切割平面法和二分搜索法两种通用求解方法，通过计算实验验证了效率。
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 .