Research On Branch-and-Price For Surgery Planning And Scheduling

With the improvement of the income level and the enhancement of health care consciousness of residents,their demands for healthcare service are increasing rapidly.Operating room is the place to provide patients with surgeries and rescues,with the most expensive equipment,the highest revenue,the most extensive human resources for assignment,and the most upstream and downstream sectors involved in the hospital.As there exist many uncertainties in the operating room,to establish scientific and reasonable surgery planning has become a problem troubling operating theater managers for many years.A hospital operating theater generally admits two categories of patients: emergency patients and elective patients.Emergency patients arrive at random requiring surgeries as soon as possible;elective patients wait in the hospital,and they can be planned in advance.Emergency patients arriving randomly will cause a negative impact on the surgery plan of elective patients,such as operation delay or cancelling.In reality,refusing or delaying surgeries for emergency patients often results in their deteriorations and dissatisfactions and other bad influences.Therefore,the manager of the operating operating reserve part of the operation abilities to deal with the randomly arriving emergency patients;deficiency in reserved surgery abilities will lead to emergency patients waiting for a long time,while the surplus will certainly lead to the waste of operating room resources.In order to improve the situation,under the premise of sharing operating rooms for emergency patients and elective patients,the paper studied the surgery planning problem with random surgery demand of emergency patients,and determined a plan that specifies the set of elective patients that would be operated on in each operating room in each period over a planning horizon to minimize the expected overtime cost and expected idle cost of the operating rooms.First of all,the mathematical description of the problem was conducted to construct a 0-1 integer-programming model.Considering that the problem was a NP-hard problem,it was solved through the precise branch-and-price.Then by applying the Dantzing-Wolfe decomposition principle,the original 0-1 integer-programming model was decomposed into the set covering master problem model and sub-problem model.Against the similarity between the sub-problem model and the knapsack problem,the sub-problem model was decomposed,to propose an efficient dynamic programming algorithm,and work out the optimal linear relaxation solution of the master problem through the column generation.When the relaxation solution was a fraction,the optimal integer solution to the problem was worked out through the branch-and-price.The outer layer of the algorithm is branch and bound method,which chooses the most infeasible branching as the branch strategy,combined with the mixed strategy between the depth first search and the best bound search as the node selection strategy,through the comparison of several commonly used strategies,thus to thoroughly search the solution space so as to obtain the optimal integer solution.Numerical experiments show that the proposed branch-and-price can be used to work out the optimal solution of the case size problem.The research work is of great significance,both in theory and in practice.On the one hand,this paper will give a certain reference for surgery planning and schdeuling model construction with emergency patients.On the other hand,it can offers effective schemes to operating theater managers,so as to guide practice.