Composite Dispatching Rules For Three Scheduling Problems,With Applications In Health Care Operations Management

With increased demand of healthcare due to life quality improvement,more aged people,and environmental problems,there is huge pressure for China to improve its healthcare system at both policy level as well as operational level.The resources in a healthcare system,especially in hospitals,are normally very limited.In particular,operating rooms(ORs),surgeons,anesthesiologists,nurses and expensive surgical equipment(ESE)are among those expensive and bottleneck resources in hospitals.Improving the utilization of these resources is always a critical issue in hospital resource management and better management of these resources may increase the benefits(both tangible and intangible)for hospitals as well as patients significantly.Surgical operations have long been a major treatment for various diseases,and these operations require many key resources in hospitals,such as ORs,surgeons,anesthesiologists,nurses and ESE.In such a customer-contact service,patient waiting times and operating room congestion are critical elements in service quality.Both patients and hospital are concerned with long waiting times and high cost of cares.An obvious way to reduce the waiting times is to use more processing resources(e.g.,personnel and/or equipment).However,adding expensive resources may increase service costs significantly.As a solution,well-designed operating theater scheduling systems may help to increase the utilization of these expensive resources as well as reduce waiting times for patients,hence improve the performance of hospitals and reduce healthcare cost.However,it is not an easy task to find a good way to manage the operating theater due to the complexities and various physical or logical constraints.For example,the equipment in operating rooms is different from each other,and the types of surgeries that an operating room can accommodate is different,which implies that there are eligibility constraints when we consider the operating room scheduling.How to cope with this problem? Besides the eligibility constraints,there are resource constraints as well.In practice,a surgery is usually performed by the surgeon who handles this patient before the surgery,with support of the anesthetists,nurses and assistants.Thus a surgeon may take care only a specific set of patients.This is another critical constraint in OR scheduling.How to cope with this problem? Furthermore,after the patients receive surgical operations in operating rooms,they are transferred immediately to the ICUs or recovery room.How to model and solve this problem?These three problems are important from both theoretical and practical perspectives but are less studied.Motivated by these operating room scheduling problems,we construct three scheduling models,and propose dispatching rule type of heuristic algorithms for solving the problems.We not only conduct the numerical experiments to show the performance of our algorithms,but also test them by real data sets obtained from a large hospital in China.Although the studies are motivated by health care operations,the models and algorithms can be applied to general scheduling problems with eligibility constraints under different machines environments.The main contributions of this research can be summarized as follows.1.We study a parallel machine scheduling problem,where a job j can only be processed on a specific subset of machines,and the subsets of the n jobs are nested.We develop a two-phase heuristic for minimizing the total weighted tardiness subject to the machine eligibility constraints.In the first phase,we compute the factors and statistics that characterize a problem instance.In the second phase,we propose a new composite dispatching rule,the ATCF rule,which is governed by several scaling parameters of which the values are determined by the factors obtained in the first phase.The ATCF rule is a generalization of the well-known ATC rule which is very widely used in practice.We further discuss how to improve the dispatching rule using some simple but powerful properties without requiring additional computation time,and the improvement is quite satisfactory.We apply the Sequential Uniform Design Method to design our experiments and conduct an extensive computational study,and we perform tests on the performance of the ATCF rule using a real data set from a large hospital in China.We further compare its performance with that of the classical ATC rule.We also compare the schedules improved by the the ATCF rule with what we believe are Near Optimal schedules generated by a general search procedure.The computational results show that especially with a low due date tightness,the ATCF rule performs significantly better than the well-known ATC rule generating much improved schedules that are close to the Near Optimal schedules.2.We model the OR scheduling problem as a parallel machine scheduling problem with the machine(i.e.,OR)eligibility and resource(e.g.,surgeons,nurses,and equipment)constraints to minimize the makespan of the schedule,and develop a two-phase heuristic(a dispatching rule)to solve the problem.We empirically evaluate the performance of the heuristic by comparing the schedules with the optimal schedules for small-sized problems and show that the Average Relative Deviation(ARD)between the two types of schedules is less than 10%.By using the real data set from a large hospital in China,we compare the schedules generated by the heuristic with the real schedules,as well as the schedules generated by Simulated Annealing(SA)algorithm.The results show that the heuristic significantly improves the real schedules,and the performance of the heuristic is quite near those by the SA algorithm,although the SA algorithm takes much more computational time.Furthermore,the heuristic can be easily modified to deal with more complicated problems thus is applicable in practical settings.3.We study a makespan minimization problem in a two-stage no-wait hybrid flow shop with eligibility constraints.We develop a MIP(Mixed Integer Programming)model and a heuristic algorithm based on the composite dispatching rule for the research problem.An extensive computational study is conducted on the performance of our heuristic algorithm against a comprehensive benchmark provided by the approximate solver,CPLEX,for the MIP model.Overall,the results show that this paper brings the gap between theory and practice of scheduling and the performance of the proposed algorithm is quite satisfied.The novelty of this research mainly lies in the following aspects.1.We study three practical schedluing problems motivated by applications in healthcare operations management,by considering eligibility and resource constraints,and more practical objective.Three new dispatching rules are developed for solving these three complicated scheduling problems.These dispatching rules are easy to understand and implement in practices.Through extensive computational experiments with randomly generated as well as real data sets,we demonstrate the efficiency and effectiveness of the heuristic algorithms.2.We innovatively apply Sequential Uniform Design(also known as the Sequential Number-Theoretic Optimization(SNTO))to quickly find the best pair of scaling parameters for the composite dispatching rules.One major advantage of the uniform design is that it can explore relationships between the responses and the factors in a reasonable number of runs and it is robust with regard to the underlying model specifications.3.We propose dominance rules and identify special cases for the three scheduling problems.In this way,not only can we shed light on the essential characteristics of the problems,but also show that those rules can help improve the solutions obtained from the heuristic algorithms as seed solutions.