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