日前，北理工管理与经济学院李金林教授及其博士研究生王珊珊与美国西北大学工业工程与管理科学系Sanjay Mehrotra教授合作的研究成果“Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning”近期在《INFORMS Journal on Computing》期刊在线发表。该项成果是在国家自然科学基金重点项目（71432002）支持下完成的。

经典的装箱问题(bin-packing problem)要求把一定数量的物品(item)放入具有一定容量(capacity)的一些箱子(bin)中，使得每个箱子中的物品大小(size)之和不超过箱子容量并使所花费的箱子的总成本最小。装箱问题及其变型被广泛应用到资源调度分配，交通物流和云计算等领域。经典的装箱问题是一个复杂的离散组合优化(combinational optimization)问题，也被证明为NP-Hard问题。该论文研究一类随机环境下的机会约束装箱问题(chance-constrained multiple bin-packing problem), 物品的大小服从有限离散的概率分布，并要求每个箱子中的物品大小之和不超过箱子容量的概率不低于某一分位数（例如95%）。针对该问题，论文首先分析二元线性(bi-linear)等价模型的结构，提出了三类有效不等式(valid inequalities)，然后设计一个改进的下界启发式算法和精确的分支切割(branch-and-cut)算法求解。最后，以医疗健康运作管理中的手术室调度分配问题为例进行算例分析，考虑手术时间不确定，机会约束刻画了每个手术室完成分配的手术不需要加班的概率，并于文献中的算法和方法（如CVaR估计）进行比较，验证了所提出的算法的高效性，并取得较好的样本外(out-of-sample)加班概率。

《INFORMS Journal on Computing》(简称IJOC)为美国运筹学和管理学研究协会（INFORMS）季刊，每年约发表论文50篇。该刊是UT-Dallas 24期刊（国际商学院研究能力评估参考的24本顶级期刊）之一。UT-Dallas 24 是由美国德克萨斯大学达拉斯分校界定的24本权威、顶级期刊目录，用于国际商学院研究能力评估，是商学院排名的重要参考依据，在国际上认可度极高。同时，该目录也是国家自然科学基金委管理科学部、教育部管理学科等重要人才计划项目评选的重要参考条件。

论文信息 Shanshan Wang, Jinlin Li, and Sanjay Mehrotra. Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning. INFORMS Journal on Computing, 2021, https://doi.org/10.1287/ijoc.2020.1010

论文链接：https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2020.1010