Professor Li Jinlin and his doctoral graduate student Wang Shanshan collaborated with Professor Sanjay Mehrotra of the Department of Industrial Engineering and Management Sciences of Northwestern University in the United States, published recently“Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning” online in INFORMS Journal on Computing. The research was supported by the National Natural Science Foundation of China (71432002) key project.

The classic bin -packing problem requires that a certain number of items be placed in bins with a certain capacity so that the sum of the items in each bin does not exceed the bin capacity and minimizes the total cost of the bins.Packing problem and its variant are widely used in resource scheduling and distribution, Transportation logistics and cloud computing and other fields. Classic packing problem is a complex discrete combinational optimization problem, and a chance-constrained multiple bin-packing problem. The size of the object follows a finite discrete probability distribution, and requires that the sum of the items in each box does not exceed the probability of box capacity not less than a certain quartile (e.g .95%). In response, Firstly, the structure of bi-linear equivalent model is analyzed, Having proposed three kinds of valid inequalities, we designed an improved lower bound heuristic algorithm and an accurate branch-and-cut algorithm. Finally, Taking the problem of operating room dispatch and distribution in medical and health operation management as an example, we verified the efficiency of the proposed algorithm, and obtain better out-of-sample overtime probability.

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

Link：https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2020.1010