Models And Algorithms For Three Scheduling Problems In Health Care Operations Management

Suffering from high health care cost and facing more demand in the future,it is increasingly important to efficiently allocate the healthcare resources and improve the efficiency of the health care operations.In this thesis,based on operation research techniques,we study three decision-making problems in health care operations management,i.e.,surgery scheduling problem with post-anesthesia care unit(PACU)capacity for hospitals,home health care routing and appointment scheduling problem with single and multiple caregivers,respectively.Surgical patients that complete in an operating room(OR)must quickly move to the PACU to recover from anesthesia.When the PACU capacity is limited,without effective planning and scheduling,some patients may have to wait in the ORs after the surgery due to the unavailability of PACU beds,which can cause delays for subsequent OR procedures and possible overtime work for staff.To minimize the cost of opening ORs and overtime cost,in this thesis,we develop a novel two-stage stochastic programming model to solve the surgery scheduling problem with PACU capacity.In the two-stage stochastic programming model,the recourse cost and uncertainties of surgery and recovery durations are captured by a discrete-event simulation model in the second-stage problem after the first-stage problem determines the assignment and sequencing decisions.Practical-size problem instances of our model are difficult to be solved by standard stochastic programming techniques(e.g.,L-shaped method).Therefore,we exploit several structural properties of the model to achieve computational advantages and also describe a set of lower bounding inequalities to speed up the convergence of the algorithm.Our computational experiment based on real data shows that our algorithm can solve practicalsize problem instances close to optimality in a reasonable time and the set of lower bounding inequalities can significantly improve the computational efficiency of the algorithm.We also show that by considering the PACU capacity constraint,the cost can be decreased by 20% on average and the ORs and PACU can be used more efficiently.Home health care,as an alternative to hospital services,is an essential sector of health care system.Motivated by the practices of home health care,we consider an integrated routing and appointment scheduling(RAS)problem with stochastic service times.Given a set of customers with known locations and random service times,the caregiver has to visit each customer location exactly once to provide the services.The objective of the problem is to determine the visit route and the appointment times for the customers so as to minimize the total costs of idling of the caregiver,waiting of the customers and traveling.Given that the distributions of service times are known,we develop a two-stage stochastic programming model using sample average approximation and propose an integer L-shaped method to solve the problem.We also propose an easy-to-implement heuristic algorithm that allows solving large-size problem efficiently.For the case that only the means and variances are known for the service times,we propose a method based on a mixedinteger second-order cone program to deal with the problem.The effectiveness and efficiency of these methods are demonstrated through computational experiment on randomly generated problem instances.Finally,we consider the routing and appointment scheduling problem with caregiver assignment,where there are multiple caregivers and we need to assign them to the customers.This problem is more complex because of the assignment decision.To efficiently solve it,we build a scenario-based mixed-integer program and develop an algorithm based on Tabu Search(TS)method.Our computational experiment show that the TS-based algorithm works quite well.Specifically,compared with known optimal solutions on small-size problem instances,the algorithm efficiently produces optimal solutions for 38 out of 40 instances and near-optimal solutions for the other 2 instances(optimality gaps are less than 2%).Moreover,the algorithm significantly outperforms the approach that separately optimizes assignment,routing,and appointment scheduling.