北理工在UT-Dallas 24期刊《INFORMS Journal on Computing》發(fā)表最新研究成果
發(fā)布日期：2021-03-24 供稿：管理與經(jīng)濟(jì)學(xué)院 王笑竹
編輯：趙強 審核：顏志軍 閱讀次數(shù)：
日前，北理工管理與經(jīng)濟(jì)學(xué)院李金林教授及其博士研究生王珊珊與美國西北大學(xué)工業(yè)工程與管理科學(xué)系Sanjay Mehrotra教授合作的研究成果“Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning”近期在《INFORMS Journal on Computing》期刊在線發(fā)表。該項成果是在國家自然科學(xué)基金重點項目（71432002）支持下完成的。
經(jīng)典的裝箱問題(bin-packing problem)要求把一定數(shù)量的物品(item)放入具有一定容量(capacity)的一些箱子(bin)中，使得每個箱子中的物品大小(size)之和不超過箱子容量并使所花費的箱子的總成本最小。裝箱問題及其變型被廣泛應(yīng)用到資源調(diào)度分配，交通物流和云計算等領(lǐng)域。經(jīng)典的裝箱問題是一個復(fù)雜的離散組合優(yōu)化(combinational optimization)問題，也被證明為NP-Hard問題。該論文研究一類隨機環(huán)境下的機會約束裝箱問題(chance-constrained multiple bin-packing problem), 物品的大小服從有限離散的概率分布，并要求每個箱子中的物品大小之和不超過箱子容量的概率不低于某一分位數(shù)（例如95%）。針對該問題，論文首先分析二元線性(bi-linear)等價模型的結(jié)構(gòu)，提出了三類有效不等式(valid inequalities)，然后設(shè)計一個改進(jìn)的下界啟發(fā)式算法和精確的分支切割(branch-and-cut)算法求解。最后，以醫(yī)療健康運作管理中的手術(shù)室調(diào)度分配問題為例進(jìn)行算例分析，考慮手術(shù)時間不確定，機會約束刻畫了每個手術(shù)室完成分配的手術(shù)不需要加班的概率，并于文獻(xiàn)中的算法和方法（如CVaR估計）進(jìn)行比較，驗證了所提出的算法的高效性，并取得較好的樣本外(out-of-sample)加班概率。
《INFORMS Journal on Computing》(簡稱IJOC)為美國運籌學(xué)和管理學(xué)研究協(xié)會（INFORMS）季刊，每年約發(fā)表論文50篇。該刊是UT-Dallas 24期刊（國際商學(xué)院研究能力評估參考的24本頂級期刊）之一。UT-Dallas 24 是由美國德克薩斯大學(xué)達(dá)拉斯分校界定的24本權(quán)威、頂級期刊目錄，用于國際商學(xué)院研究能力評估，是商學(xué)院排名的重要參考依據(jù)，在國際上認(rèn)可度極高。同時，該目錄也是國家自然科學(xué)基金委管理科學(xué)部、教育部管理學(xué)科等重要人才計劃項目評選的重要參考條件。
論文信息 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
分享到：