News Source: School of Management and Economics

Editor: New Agency of BIT

Beijing Institute of Technology, May 24th 2021: Recently, Professor Li Jinlin from the School of Management and Economics of Beijing Institute of Technology(BIT), his Ph.D. student Wang Shanshan and Professor Sanjay Mehrotra from the Department of Industrial Engineering and Management Sciences of Northwestern University in the US collaborated on the research result "Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning" which was published on INFORMS Journal on Computing online. This achievement was completed with the support of the key project of the National Natural Science Foundation of China (71432002).

The classic bin-packing problem requires putting a certain number of items into some bins with a certain capacity, so that the sum of the size of the items in each box does not exceed the box capacity while minimizing the total cost of the box spent. The packing problem and its variants are widely used in the fields of resource scheduling and distribution, transportation logistics and cloud computing. The classic bin-pack problem is a complex discrete combinatorial optimization problem, which has also been proven to be an NP-Hard problem. This paper studies a kind of chance-constrained multiple bin-packing problem in a random environment. The size of items obeys a finite discrete probability distribution, and requires the probability that the sum of the sizes of items in each box does not exceed the box capacity is not lower than a certain quantile (for example, 95%). In response to this problem, the thesis analyzes the structure of the bi-linear equivalent model initially, and proposes three types of valid inequalities, and then designs a lower-bound improvement heuristic which combined with precise branch-and-cut algorithm to solve. Finally, take the application in hospital operating room planning as an example to analyze. Considering the uncertainty of the operation time, the opportunity constraint describes the probability that each operating room completes the assigned operation without overtime, and it is reported in the literature. The algorithm is compared with the method (such as CVaR estimation) to verify the efficiency of the proposed algorithm and obtain a better out-of-sample overtime probability.

INFORMS Journal on Computing (IJOC for short) is a quarterly journal of the Institute for Operations Research and the Management Sciences (INFORMS), which publishes 50 papers every year approximately. The journal is one of UT-Dallas 24 journals (24 top journals referenced in the research ability assessment of international business schools). UT-Dallas 24 is a catalog of 24 authoritative and top journals defined by the University of Texas at Dallas. It is used for the assessment of research capabilities of international business schools which is a significant reference for business school rankings and is highly recognized internationally. Meanwhile, the catalog is also an important reference condition for the selection of important talent program projects such as the Ministry of Management Science of the NSFC and the Management Discipline of the Ministry of Education.

Paper information: 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

Paper link: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2020.1010