Please note that Internet Explorer version 8.x is not supported as of January 1, 2016. Please refer to this support page for more information.
- Purchase PDF
Article preview
Introduction, section snippets.
- References (18)
Cited by (116)
Recommended articles (6).
International Journal of Production Economics
Solving surgical cases assignment problem by a branch-and-price approach ☆.
In this paper, we study a surgical cases assignment problem (SCAP) of assigning a set of surgical cases to several multifunctional operating rooms with an objective of minimizing total operating cost. Firstly, we formulate this problem as an integer problem and then reformulate the integer program by using Dantzig–Wolf decomposition as a set partitioning problem. Based on this set partitioning formulation, a so-called branch-and-price exact solution algorithm , combining Branch-and-Bound procedure with column generation (CG) method, is designed for the proposed problem where each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a CG approach in which each column represents a plan for one operating room and is generated by solving a sub-problem (SP) of single operating room planning problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems.
Operating theatre, consisting of operating rooms and recovery rooms, is the kernel in a hospital. With almost 10–15% of the intended budget (Clergue, 1999 and Macario et al., 1995), costs of the operating theatre are the most significant portion of those of hospital sectors. As a result of centrally constrained budgets, resource-allocation problems, in which such limited resources as surgeons, nurses and beds should be allocated appropriately to services by minimizing the operating cost and maximizing operating theatre's utilization, are known as the common issues in health-care planning problems.
In an industrial system, normally the production process is pre-determined while in a hospital system, all services offered to a patient might vary according to his health situation and preference. What's more, more urgent cases occur in a hospital system than those of an industrial one.
In an industrial system, one machine is normally occupied by one technician while the surgical team is composed of different specialists (such as a surgeon, nurses and an anaethesist), so it is much harder to coordinate the activities concerned.
Considering the objective of those two management problems, we can also find the difference: the operating theatre management problem normally aims at minimizing the operating cost while the objective of production management problem is normally to maximize the factory's profit.
By comparing the main constraints of both systems, we find that the requests of the patients (for example, the operating deadline) should be absolutely satisfied, and it is much more difficult for a manager to assign human resources in a hospital because the surgical team consists various roles and their capacity and requests should also be met while these are not necessarily done in the factory.
Another difference between these two systems is based on the difficulty of estimating the operating time. In fact, it is extremely difficult to determine the operating time of a surgical case because it depends on many parameters (patient's age, surgeon's experience, etc.) while normally the operating time of a product can be well evaluated according to the previous experience.
In an industrial system, normally the semi-finished products can be temporarily stored when there is no machine available in the precedent stage and working process of the current stage will not be interrupted; however, if there is no recovery bed available in the recovery room of the hospital when the operation of a patient is finished, this patient has to remain in the operating room where he is treated and begin to regain consciousness.
In conclusion, the operating theatre management problem is much more complex than a typical production planning one though there are also many things in common.
In this paper, we will focus on the surgical cases assignment problems (SCAP), one part of the operating theatre planning problem, which belongs to a primary category of operating theatre planning problem. This kind of problem aims at assigning a set of surgical cases to operating theatres during one planning period (1 day, 1 week or 1 month) by minimizing total operating cost with given resources’ constraints. As a popular issue, it is absolutely attractive to researchers, such as Ozkarahan (1995), Vissers (1998), Lovejoy and Li (2002), Jebali et al.(2003), Dexter et al.(1999), Blake and Donald (2002), Chaabane et al.(2003), Guinet and Chaabane (2003), and Weinbroum et al.(2003).
We assume, in this paper, that the operating time of a surgical case is estimated in advance and used as a determined data in the mathematical model.
We aim to assign N case surgical cases to several multifunctional operating rooms during 1 week (5 days). Each surgical case is identified by its operating time and deadline. A surgical case can be assigned to an operating room for a day whenever the total operating time of assigned surgical cases is less than or equal to this operating room's maximal opening duration in this day (ordinary opening time plus its maximal additional time). The operation date has to be fixed before its deadline. Each operating room can have different opening periods. The objective is to minimize total operating cost (unexploited time's cost or overtime cost).
As for this assignment problem, some precedent work has been done by Fei et al. (2004). In that paper, we constructed a heuristic procedure, based on column generation (CG) and dynamic programming, to get the solution to this problem. We obtained approximate solutions, so in this paper we will try to solve this problem for the exact solution by a so-called branch-and-price procedure here. Furthermore, in this paper we will loosen the hypothesis that all operating rooms are identical.
This paper is organized as follows. Firstly, a general integer programming (GIP) formulation is described for the problem concerned. Then, framework of applied branch-and-price procedure is described. After that the decomposition approach is given, and the CG method assisted with dynamic program method is presented to solve linear relaxation of the set partitioning problem. In Section 4, we will present the CG procedure and its key points, and in Section 5 the detail of the branch-and-price procedure are presented for the exact optimal solution of the general integer problem. Afterwards we will show the experimental results and finally give out conclusions and perspectives.
General integer programming
All the operating rooms are multifunctional; i.e., each operating room can operated any assigned surgical case.
Human and instruments resources are always
Framework of branch-and-price procedure
As presented in Barnhart et al. (1998), the successful solution of large-scale mixed integer programming, such as SCAP, requires formulations whose linear programming (LP) relaxations make a good approximation of feasible solutions. Based on this idea, a great deal of attention has been paid to the Branch-and-Cut and Branch-and-Price approaches. The philosophies of Branch-and-Cut and branch-and-price are similar: both of them are generations of Branch-and-Bound approach, where pricing and
Set partitioning general problem (GP) corresponding to general integer problem (GIP)
Utilizing Dantzig and Wolfe (1960), we decompose this GIP problem into a set partitioning master problem (MP) consisting of constraints (1), (2) and a set of SPs with feasible region defined by (3) with C j defined by (5). All decision variables in the MP and SPs are binary integers defined by (4).
1 if surgical case i is assigned to plan j ; 0 otherwise;
1 if plan j is scheduled on day d ; 0 otherwise;
1 if operating room k is used by plan j ; 0 otherwise.
one possible assignment
Framework of heuristic procedure based on column generation
As mentioned in Section 4, in the proposed branch-and-price procedure, the linear relaxation of each node is solved by a CG procedure. In addition, the first node is solved by an HPBCG for an approximate solution, which is set as the first UB in the branch-and-price procedure. In this section, we will describe the framework of the heuristic procedure HPBCG where CG procedure is one of its parts.
Selection strategy of node and branching variable
In this section, we will give the details of the branch-and-price procedure, whose framework was already described in Section 3, in order to solve the proposed SCAP, especially its branching criteria.
As is known, usually two classes of decision need to be made throughout a Branch-and-Bound procedure. One, called node selection, is to select an active node in the Branch-and- Bound tree (node list) to be explored; the other, called branching variable selection, is to select a fractional variable
Experimental results
Hardware for running the algorithm : IBM ThinkPad T23 (CPU: PM 1.6 GHz, Memory: 256 MB).
Software development environment : Microsoft VC++ 6.0
Software support : COIN, a LP solver, downloadable at IBM's website ( http://www.coin-or.org/index.html ).
Conclusion and perspective
In this paper, we have developed a decomposition-based branch-and-price algorithm to optimally solve a SCAP with an objective of minimizing total unexploited and overtime operating cost. At the end of this paper, we tested problems with a size up to 160 surgical cases. The results show our algorithm works quite well for tested problems.
However, it is the fact that our proposed problem has taken into account too many strict hypotheses that make our results far from practical application. Thus,
Reference (18)
Efficiency of the operating room suite, the american journal of surgery, patient flow-based allocation of inpatient resources: a case study, european journal of operation research, a recursive exact algorithm for weighted two-dimensional cutting, european journal of operational research, operating theatre planning, a column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem, the industrial management and the management of surgical units, annales françaises d’anethésie et de réanimation, branch-and-price: column generation for solving huge integer programs, operations research, mount sinai hospital uses integer programming to allocate operating room time, solving parallel machine scheduling problems by column generation, informs: journal of computing, application of a risk-averse objective function for scheduling surgeries.
Traditional objective functions for scheduling surgeries, such as maximising utilisation of operating rooms, maximising throughput of surgeries, or minimising cost, can lead to inequitable outcomes for patients in terms of the time waiting for their operation. Using a simple mixed integer program and historical data from a surgical centre we compare two objective functions (a risk neutral and a risk averse objective) intended to reduce the lateness of the latest-performed operations. Further, the effects of other model parameters on the surgical schedules are compared. By applying the model to a case study at a surgical centre, it is demonstrated that, with the appropriate values of the other model parameters, the risk neutral objective can achieve similar schedules to the risk averse objective, and results in problems that are easier to solve.
A data-driven approach to include availability of ICU beds in the planning of the operating room
In this paper, we propose a novel approach to deal with the integration of the cancellation probability due to congestion in the intensive care unit in the (long term) surgical case assignment problem. This problem consists of selecting patients from the wait list to be on the operating list of surgeons for a selected horizon, and assigning a day, an operating room, and a time block to each surgeon. We propose an approach that computes the probability of canceling cases on each day through the graph of possible states and actions derived from the schedule in the OR. This graph is then integrated into a Mixed Integer Programming model to optimize the monthly case assignment schedule. We evaluated the method on the practical case of the teaching hospital Sainte-Justine (CHUSJ) in Montreal and performed and extensive sensitivity analysis on the parameters. We show that prioritizing patients during this process only increases the quality of the schedule without decreasing the occupancy rate of the operating room. We also use probabilities that need to be discussed with senior management to decide on the acceptable risk to cancel an elective case.
A discrete squirrel search algorithm for the surgical cases assignment problem
Surgical cases assignment problem (SCAP) is among the most investigated parts in healthcare scheduling and assignment problems, in which a set of surgical cases are assigned to operating rooms within a specified planning horizon. Several methods have been developed to provide approximate solutions for SCAP. Nevertheless, existing methods underperform at the large-scale instances. In this paper, a discrete squirrel search algorithm (DSSA) is proposed for SCAP with the objective of minimizing total operating cost. First, four heuristics are presented to improve quality and diversity of initial population. Second, a surgical case sequence vector is employed to encode individuals, and a corresponding decoding scheme is designed to construct feasible schedules. Third, several efficient heuristics are embedded into DSSA to enhance the search capacity. Moreover, the Taguchi method of design-of-experiment (DOE) is adopted to explore the influence of parameter settings. To the best of our knowledge, it is the first application of the squirrel search algorithm for SCAP. The effectiveness of DSSA is conducted on a typical benchmark dataset. Computational results and comparisons demonstrate the superiority of the proposed scheme over the existing methods in solution accuracy and consuming time for solving SCAP.
A robust multiobjective integrated master surgery schedule and surgical case assignment model at a publicly funded hospital
This paper considers an integrated operating room (OR) planning and advanced scheduling problem in a surgery department comprising several specialties that share a fixed number of ORs and post-surgery beds. It jointly considers the allocation of surgical specialties to OR blocks together with the assignment of the subsets of patients from each specialty’s waiting list to the OR blocks over a one-week planning horizon. By integrating the master surgical schedule problem (MSSP) and surgical case assignment problem (SCAP), we extend the stability of the scheduling process. We consider both uncertain surgery durations and emergency arrivals. The aim of this study is to maximize both patient service levels and hospital efficiency. A multi-objective integer linear programming (MOILP) model is developed to minimize patient waiting times as well as to maximize the OR utilization rates. An Lp-metric methodology is applied to solve the final integrated objective function. The MOILP is transformed into a robust optimization model using a transformation framework. In addition, we develop a two-stage stochastic integer linear programming model. The effectiveness of three models is compared and demonstrated through an extensive numerical experiment carried out on a large set of instances based on real data.
An approximate dynamic programming approach to the admission control of elective patients
In this paper, we propose an approximate dynamic programming (ADP) algorithm to solve a Markov decision process (MDP) formulation for the admission control of elective patients. To manage the elective patients from multiple specialties equitably and efficiently, we establish a waiting list and assign each patient a time-dependent dynamic priority score. Then, taking the random arrivals of patients into account, sequential decisions are made on a weekly basis. At the end of each week, we select the patients to be treated in the following week from the waiting list. By minimizing the cost function of the MDP over an infinite horizon, we seek to achieve the best trade-off between the patients’ waiting times and the over-utilization of surgical resources. Considering the curses of dimensionality resulting from the large scale of realistically sized problems, we first analyze the structural properties of the MDP and propose an algorithm that facilitates the search for best actions. We then develop a novel reinforcement-learning-based ADP algorithm as the solution technique. Experimental results reveal that the proposed algorithms consume much less computation time in comparison with that required by conventional dynamic programming methods. Additionally, the algorithms are shown to be capable of computing high-quality near-optimal policies for realistically sized problems.
Surgery scheduling in outpatient procedure centre with re-entrant patient flow and fuzzy service times
To meet the increase in demand for outpatient surgical services, surgery scheduling for outpatient procedure centres (OPCs) has recently attracted considerable attention in both the healthcare industry and the academic community. This paper considers a novel OPC daily surgery scheduling problem (ODSSP) to minimise the average recovery completion time of all patients. To satisfy the OPC surgical practice, patient intake and recovery are applied in the same area for more resource flexibility, and uncertain service times for intake, surgical procedures and recovery are considered. Owing to the similarities shared between healthcare delivery systems and production systems, ODSSP is formulated as a two-stage no-wait re-entrant hybrid flow shop scheduling problem with fuzzy service times. Considering the NP-hardness of such scheduling problem, a new hybrid meta-heuristic (GA-BAVNS) is employed to obtain detailed daily OPC surgery schedules. To achieve greater balance between exploration and exploitation in the search space, GA-BAVNS hybridises a genetic algorithm (GA) and a variable neighbourhood search (VNS) to schedule outpatients for surgical services. To improve the local search performance of the VNS, six novel block-based neighbourhood structures are employed to generate neighbourhood solutions. Moreover, an adaptive neighbourhood change procedure (ANCP) is employed to systematically change the search order of neighbourhood structures for better solutions. Computational results on a set of test problems indicate the superiority of the proposed GA-BAVNS.
A two level metaheuristic for the operating room scheduling and assignment problem
Given a surgery department comprising several specialties that share a fixed number of operating rooms and post-surgery beds, we study the joint operating room (OR) planning and advanced scheduling problem. More specifically, we consider the problem of determining, over a one week planning horizon, the allocation of OR time blocks to specialties together with the subsets of patients to be scheduled within each time block. The aim of this paper is to extend and generalize existing approaches for the joint OR planning and scheduling problem. First, by allowing schedules that include patients requiring weekend stay beds which was not the case previously. Second, by tackling simultaneously both the OR planning and patient scheduling decision levels, instead of taking them into account in successive phases. To achieve this, we exploit the inherent hierarchy between the two decision levels, i.e., the fact that the assignment decisions of OR time blocks to surgical specialties directly affect those regarding the scheduling of patients, but not the reverse. The objective function used in this study is an extension of an existing one. It seeks to optimize both patient utility (by reducing waiting time costs) and hospital utility (by reducing production costs measured in terms of the number of weekend stay beds required by the surgery planning). 0–1 linear programming formulations exploiting the stated hierarchy are proposed and used to derive a formal proof that the problem is NP-hard. A two level metaheuristic is then developed for solving the problem and its effectiveness is demonstrated through extensive numerical experiments carried out on a large set of instances based on real data.
Local search heuristics for a surgical case assignment problem
This work is part of an ongoing project with a Portuguese public hospital, where the elective surgeries scheduling problem is studied. The administration of the hospital aims to achieve the targets set by the Portuguese Ministry of Health for surgical production and to ensure a surgical service with a high level of efficiency. However, hospitals do not have an elective surgeries scheduling system, so the surgeries are unsystematically scheduled and without respecting equity criteria, thus disregarding the Ministry’s goals.
Three versions of the problem are considered and local search heuristics are developed in order to quickly find good solutions for each version of the problem. The heuristics select patients from a long waiting list for surgery to be scheduled in each week, and define a room, a day and a shift for each selected surgery according to one of three different perspectives of the problem.
The heuristics developed are tested in real instances and the values of the solutions are compared with the values of the solutions obtained using mixed integer linear programming models. The solutions obtained by the heuristics are of very good quality and the computational time required is generally quite low, even considering the instances with more surgeries in the waiting list.
In addition, a user-friendly interface is created for the hospital, which reads all the relevant data and proposes a weekly surgical schedule in a systematic manner.
A simulation based approximate dynamic programming approach to multi-class, multi-resource surgical scheduling
This paper presents a model and solution methodology for scheduling patients in a multi-class, multi-resource surgical system. Specifically, given a master schedule that provides a cyclic breakdown of total OR availability into specific daily allocations to each surgical specialty, the model provides a scheduling policy for all surgeries that minimizes a combination of the lead time between patient request and surgery date, overtime in the operating room and congestion in the wards. To the best of our knowledge, this paper is the first to determine a surgical schedule based on making efficient use of both the operating rooms and the recovery beds. Such a problem can be formulated as Markov Decision Process model but the size of any realistic problem makes traditional solution methods intractable. We develop a version of the Least Squares Approximate Policy Iteration algorithm and test our model on data from a local hospital to demonstrate the success of the resulting policy.
Scheduling elective surgeries with sequence-dependent setup times to multiple operating rooms using constraint programming
The problem studied in this paper is to schedule elective surgeries (in contrast to urgent surgeries) to multiple operating rooms (ORs) in ambulatory surgical settings. We focus on three aspects of the daily scheduling decisions, including the number of ORs to open, the allocation of surgery-to-OR, and the sequence of surgeries in each OR. All the surgeries to be scheduled are known in advance, which is a common assumption for elective surgery scheduling problems. The surgeries belong to different types, and each OR can only allow certain types of surgeries to be performed. Before a surgery starts, some setup work needs to be done, such as sterilization and preparing required equipment. The setup times are assumed sequence-dependent, and both setup times and surgery durations are deterministic. The fixed costs of running the ORs are high; while sometimes overtime costs, which are even higher than the fixed costs, may occur when the surgeries cannot be done within the normal operating period of the ORs. We build a Mixed Integer Nonlinear Programming (MINLP) model and a Constraint Programming (CP) model to solve this problem. The performance of these two models is tested on numerical examples, and the results show that the CP model is more efficient than the MINLP model in terms of the computational time and solution quality. We also examine the sensitivity of the solutions to the variation of surgery durations, and the analysis shows that the total costs do not change much when the variations of surgery durations are small.
Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations
There is evidence in the literature that most surgeries in hospitals are performed by a team composed of two surgeons, and that their experience largely influences the surgery duration. However, to the best our knowledge, only one contribution has addressed the operating room planning and scheduling problem with surgical teams, but in such case surgery durations did not depend on the experience of surgeons. In this paper we address an integrated operating room planning and scheduling problem with surgical teams composed by one or two surgeons where surgery durations depend on their experience and skills. We propose a mixed integer linear programming (MILP) model to optimally solve this problem. Given the high computation requirements of our MILP model, we also propose an iterative constructive method. In order to evaluate the performance of both exact and approximate methods, an extensive test bed is generated. The computational experience shows that the proposed algorithm is able to find feasible solution for all problems requiring shorter CPU time and average relative percentage deviation than the MILP model. Finally, the robustness of the so-obtained surgical schedules is analyzed using simulation.
A hybrid optimization algorithm for surgeries scheduling
This paper deals with the Operating Room (OR) planning problem at an operational planning level. The problem addressed consists of two interrelated sub-problems usually referred to as “advance scheduling” and “allocation scheduling”. In the first sub-problem, the decisions considered are the assignment of a surgery date and an OR block to a set of patients to be operated on over a given planning horizon. The second aims at determining the sequence of selected patients in each OR and day. We assume that the duration of surgeries are random variables with known probability distributions. For each sub-problem an integer linear stochastic formulation is given. A hybrid two-phase optimization algorithm which exploits the potentiality of neighborhood search techniques combined with Monte Carlo simulation is developed to solve the overall problem. The approach developed searches for a feasible and robust solution designed to balance the trade-off arising between the hospital and patient perspectives, i.e. maximizing the OR utilization and minimizing the number of patient cancellations. The contribution of this paper is twofold. The former, more methodological, is to provide an efficient algorithmic framework to solve the joint advance and allocation scheduling problem taking into account the inherent uncertainty of surgery durations. The latter, more practical, is to provide a tool to develop robust offline OR schedules which consider the trade-off between reducing surgery cancellations and postponements while maximizing the operating theater utilization. To evaluate the efficiency of the proposed algorithmic approach, in terms of quality of solutions and solution time, we provide a computational analysis on a set of instances based on real data.
This research is funded by “Inter-university Attraction Poles Programme – Belgian State – Belgian Science Policy”.
Information
- Author Services
Initiatives
You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.
All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .
Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.
Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.
Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.
- Active Journals
- Find a Journal
- Proceedings Series
- For Authors
- For Reviewers
- For Editors
- For Librarians
- For Publishers
- For Societies
- For Conference Organizers
- Open Access Policy
- Institutional Open Access Program
- Special Issues Guidelines
- Editorial Process
- Research and Publication Ethics
- Article Processing Charges
- Testimonials
- SciProfiles
- Encyclopedia
Article Menu
- Subscribe SciFeed
- Recommended Articles
- Google Scholar
- on Google Scholar
- Table of Contents
Find support for a specific problem in the support section of our website.
Please let us know what you think of our products and services.
Visit our dedicated information section to learn more about MDPI.
JSmol Viewer
Solving a special case of the generalized assignment problem using the modified differential evolution algorithms: a case study in sugarcane harvesting.
1. Introduction
2. problem definition and mathematical model for special case of the generalized assignment problem, 2.1. problem definition, 2.2. mathematical model.
- X jk = { 1 i f c u t t i n g s e t j i s a s s i g n e d t o s u g a r c a n e f i e l d k 0 o t h e r w i s e
- Y ij = { 1 i f w o r k e r i i s a s s i g n e d t o c u t t i n g s e t j 0 o t h e r w i s e
- Wi = { 1 i f w o r k e r i i s i n u s e d 0 o t h e r w i s e
- Z k = { 1 i f s u g a r c a n e f i e l d i s a s s i g n e d b y a t l e a s t o n e c u t t i n g s e t 0 o t h e r w i s e
- H jk = Hours required to cut sugarcane in field k using harvester j
- Q jk = Hours required to travel from j to k
- M j = Real fuel consumption rate of harvester j (baht/hours)
- N j = Real cutting speed of harvester j (rai/hours)
3. Proposed Heuristic
3.1. generating the initial solution and decoding method, 3.1.1. initial solution, 3.1.2. decoding method, 3.2. mutation process, 3.3. recombination process, 3.4. selection process, 3.5. local search, 4. computational framework and results, 5. conclusions and outlook, author contributions, acknowledgment, conflicts of interest.
- Shim, S.-O.; Park, K.; Choi, S. Innovative Production Scheduling with Customer Satisfaction Based Measurement for the Sustainability of Manufacturing Firms. Sustainability 2017 , 9 , 2249. [ Google Scholar ] [ CrossRef ]
- Shim, S.-O.; Park, K. Technology for Production Scheduling of Jobs for Open Innovation and Sustainability with Fixed Processing Property on Parallel Machines. Sustainability 2016 , 8 , 904. [ Google Scholar ] [ CrossRef ]
- Jeong, B.J.; Kim, Y.-D.; Shim, S.-O. Algorithms for a two-machine flow shop problem with jobs of two classes. Int. Trans. Oper. Res. 2018 . [ Google Scholar ] [ CrossRef ]
- Joo, B.J.; Shim, S.-O.; Chua, T.J.; Cai, T.X. Multi-level job scheduling under processing time uncertainty. Comput. Ind. Eng. 2018 , 120 , 480–487. [ Google Scholar ] [ CrossRef ]
- Jeong, B.J.; Shim, S.-O. Heuristic algorithms for two-machine re-entrant flow shop scheduling problem with jobs of two classes. J. Adv. Mech. Des. Syst. Manuf. 2017 , 11 , 1–14. [ Google Scholar ] [ CrossRef ]
- Ross, G.T.; Soland, R.M. A branch and bound algorithm for the generalized Assignment problem. Math. Program. 1975 , 8 , 91–103. [ Google Scholar ] [ CrossRef ]
- Fisher, M.L.; Jaikumar, R. A generalized assignment heuristic for vehicle routing. Networks 1981 , 11 , 109–124. [ Google Scholar ] [ CrossRef ]
- Chu, P.C.; Beasley, J.E. A genetic algorithm for the generalized assignment problem. Comput. Oper. Res. 1997 , 24 , 17–23. [ Google Scholar ] [ CrossRef ]
- Osorio, M.A.; Laguna, M. Logic cuts for multi-level generalized assignment problems. Eur. J. Oper. Res. 2003 , 151 , 238–246. [ Google Scholar ] [ CrossRef ]
- Alfares, H.K. Optimum work force scheduling under the (14,21) days-off timetable. Adv. Decis. Sci. 2002 , 6 , 191–199. [ Google Scholar ]
- Elshafei, M.; Alfares, H.K. A dynamic programming algorithm for days-off scheduling with sequence dependent labor costs. J. Sched. 2008 , 11 , 85–93. [ Google Scholar ] [ CrossRef ]
- Ghoniem, A.; Flamand, T.; Haouari, M. Exact solution methods for a generalized assignment problem with location/allocation considerations. INFORMS J. Comput. 2016 , 28 , 589–602. [ Google Scholar ] [ CrossRef ]
- Laguna, M.; Kelly, J.P.; Gonzalez Velarde, J.L.; Glover, F. Tabu search for the multilevel generalized assignment problem. Eur. J. Oper. Res. 1995 , 82 , 176–189. [ Google Scholar ] [ CrossRef ]
- Kaewman, S.; Srivarapongse, T.; Theeraviriya, T.; Jirasirilerd, G. Differential Evolution Algorithm for Multilevel Assignment Problem: A Case Study in Chicken Transportation. Math. Comp. Appl. 2018 , 23 , 55. [ Google Scholar ] [ CrossRef ]
- Woźniak, M.; Połap, D. Bio-inspired methods modeled for respiratory disease detection from medical images. Swarm Evolut. Comp. 2018 , 41 , 69–96. [ Google Scholar ] [ CrossRef ]
- Woźniak, M.; Połap, D. Adaptive neuro-heuristic hybrid model for fruit peel defects detection. Neural Netw. 2018 , 98 , 16–33. [ Google Scholar ] [ CrossRef ] [ PubMed ]
- Woźniak, M.; Połap, D. Hybrid neuro-heuristic methodology for simulation and control of dynamic systems over time interval. Neural Netw. 2017 , 93 , 45–56. [ Google Scholar ] [ CrossRef ] [ PubMed ]
- Thongkham, M.; Kaewman, S. Methodology to Solve the Combination of the Generalized Assignment Problem and the Vehicle Routing Problem: A Case Study in Drug and Medical Instrument Sales and Service. Adm. Sci. 2019 , 9 , 3. [ Google Scholar ] [ CrossRef ]
- Savelsbergh, M. A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 1997 , 45 , 831–841. [ Google Scholar ] [ CrossRef ]
- Cohen, R.; Katzir, L.; Raz, D. An efficient approximation for the generalized assignment problem. Inf. Process. Lett. 2006 , 100 , 162–166. [ Google Scholar ] [ CrossRef ]
- López Cruz, I.L.; van Willigenburg, L.G.; van Straten, G. Optimal control of nitrate in lettuce by a hybrid approach: Differential evolution and adjustable control weight gradient algorithms. Comput. Electron. Agric. 2003 , 40 , 179–197. [ Google Scholar ] [ CrossRef ]
- Woodcock, A.J.; Wilson, J.M. A hybrid tabu search/branch and bound approach to solving the generalized assignment problem. Eur. J. Oper. Res. 2010 , 207 , 566–578. [ Google Scholar ] [ CrossRef ]
- Osman, I.H. Heuristics for the generalized assignment problem: Simulated annealing and tabu search approaches. Oper. Res. Spektrum 1995 , 17 , 211–225. [ Google Scholar ] [ CrossRef ]
- Diaz, J.A.; Fernandez, E. A Tabu search heuristic for the generalized assignment problem. Eur. J. Oper. Res. 2001 , 132 , 22–38. [ Google Scholar ] [ CrossRef ]
- McKendall, A.; Li, C. A tabu search heuristic for a generalized quadratic assignment problem. J. Ind. Prod. Eng. 2017 , 34 , 221–231. [ Google Scholar ] [ CrossRef ]
- Ghoniem, A.; Flamand, T.; Haouari, M. Optimization based very large-scale neighborhood search for generalized assignment problems with location/allocation considerations. INFORMS J. Comp. 2016 , 28 , 575–588. [ Google Scholar ] [ CrossRef ]
- Özbakir, L.; Baykasoglu, A.; Tapkan, P. Bees algorithm for generalized assignment problem. Appl. Math. Comput. 2010 , 215 , 3782–3795. [ Google Scholar ] [ CrossRef ]
- Tasgetiren, M.F.; Suganthan, P.N.; Chua, T.J.; Al-Hajri, A. Differential evolution algorithms for the generalized assignment problem. In Proceedings of the 2009 IEEE Congress on Evolutionary Computation, Trondheim, Norway, 18–21 May 2009. [ Google Scholar ]
- Sethanan, K.; Pitakaso, R. Improved differential evolution algorithms for solving generalized assignment problem. Expert Syst. Appl. 2016 , 45 , 450–459. [ Google Scholar ] [ CrossRef ]
- Pitakaso, R. Differential evolution algorithm for simple assembly line balancing type 1 (SALBP-1). J. Ind. Prod. Eng. 2015 , 32 , 104–114. [ Google Scholar ] [ CrossRef ]
- Sethanan, K.; Pitakaso, R. Differenevolution algorithm for simple assembly line balancing with a limit on the number of machine types. Eng. Optim. 2015 , 48 , 253–271. [ Google Scholar ] [ CrossRef ]
- Dechampai, D.; Tanwanichkul, L.; Sethanan, K.; Pitakaso, R. A differential evolution algorithm for the capacitated VRP with flexibility of mixing pickup and delivery services and the maximum duration of a route in poultry industry. J. Intell. Manuf. 2015 , 28 , 1357–1376. [ Google Scholar ] [ CrossRef ]
- Akararungruangkul, R.; Kaewman, S. Modified Differential Evolution Algorithm Solving the Special Case of Location Routing Problem. Math. Comput. Appl. 2018 , 23 , 34. [ Google Scholar ] [ CrossRef ]
- Sethanan, K.; Pitakaso, R. Differential evolution algorithms for scheduling raw milk transportation. Comput. Electron. Agric. 2016 , 121 , 245–259. [ Google Scholar ] [ CrossRef ]
- Boon, E.T.; Ponnambalam, S.G.; Kanagara, G. Differential evolution algorithm with local search for capacitated vehicle routing problem. Int. J. Bio-Inspired Comput. 2013 , 7 , 321–342. [ Google Scholar ]
- Połap, D.; Woz’niak, M. Polar Bear Optimization Algorithm: Meta-Heuristic with Fast Population Movement and Dynamic Birth and Death Mechanism. Symmetry 2017 , 9 , 203. [ Google Scholar ] [ CrossRef ]
- Mirjalili, S. Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems. Neural Comput. Appl. 2016 , 27 , 1053. [ Google Scholar ] [ CrossRef ]
- Sun, W.-Z.; Wang, J.-S.; Wei, X. An Improved Whale Optimization Algorithm Based on Different Searching Paths and Perceptual Disturbance. Symmetry 2018 , 10 , 210. [ Google Scholar ] [ CrossRef ]
- Yun, J.J.; Jeong, E.; Lee, Y.; Kim, K. The Effect of Open Innovation on Technology Value and Technology Transfer: A Comparative Analysis of the Automotive, Robotics, and Aviation Industries of Korea. Sustainability 2018 , 10 , 2459. [ Google Scholar ] [ CrossRef ]
- Yun, J.J.; Won, D.; Park, K. Dynamics from open innovation to evolutionary change. J. Open Innov. Technol. Mark. Complex. 2016 , 2 , 1–22. [ Google Scholar ] [ CrossRef ]
Share and Cite
Srivarapongse, T.; Pijitbanjong, P. Solving a Special Case of the Generalized Assignment Problem Using the Modified Differential Evolution Algorithms: A Case Study in Sugarcane Harvesting. J. Open Innov. Technol. Mark. Complex. 2019 , 5 , 5. https://doi.org/10.3390/joitmc5010005
Srivarapongse T, Pijitbanjong P. Solving a Special Case of the Generalized Assignment Problem Using the Modified Differential Evolution Algorithms: A Case Study in Sugarcane Harvesting. Journal of Open Innovation: Technology, Market, and Complexity . 2019; 5(1):5. https://doi.org/10.3390/joitmc5010005
Srivarapongse, Tassin, and Phajongjit Pijitbanjong. 2019. "Solving a Special Case of the Generalized Assignment Problem Using the Modified Differential Evolution Algorithms: A Case Study in Sugarcane Harvesting" Journal of Open Innovation: Technology, Market, and Complexity 5, no. 1: 5. https://doi.org/10.3390/joitmc5010005
Article Metrics
Article access statistics, further information, mdpi initiatives, follow mdpi.
Subscribe to receive issue release notifications and newsletters from MDPI journals
Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
Sequencing surgical cases in a day-care environment: An exact branch-and-price approach
2009, Computers & Operations Research
Related Papers
Workshop on Mixed Integer Nonlinear …
Claudia D'Ambrosio
Matin Bagherpour
In this paper, a case is considered where a distribution center (warehouse of an auto spare parts company) receives orders regularly. Warehouse management is interested in assigning available vehicles to picked orders in such a way that lead time remains lower than a threshold, and transportation cost per unit (money) of received orders is minimized. Since the company receives orders dynamically and arrival of new orders can provide it with the opportunity to improve existing decided distribution paths, the problem better be solved several times a day in a dynamic manner.
Journal of Applied Sciences
Latifa Dekhici
We present in this study some manufacturing systems scheduling constraints that we adapt to the operating theatre scheduling. The scheduling that should comply with all operating constraints, related to quality, to patients and numerous resources information can be considered as a two-stage hybrid flow shop problem without buffer. We confirmed the existence of the constraints after a large study with operating theatre managers at several hospitals. For resolution, we use two methods: Local search for constraint satisfaction in the initial feasible solution and Tabu search with restricted neighborhood system for Makespan Optimization. In one hand, we use yearly data from an existing multidisciplinary which has 3 operating rooms and 9 beds and releases 10 surgeries per day. In the other hand, we schedule others examples with different variables. The amelioration rates of both makespan and constraints conflict were interessting according to program execution time.
Computational Optimization and Applications
Miguel Fragoso Constantino
Logistics consists of the planning and controlling of the transportation and storage activities in a system that produces and distributes goods and/or services. It is one of the most important functions of many companies. The design of a distribution system begins with the questions of where to locate the facilities and how to allocate customers to the selected facilities.
Abstract Branch-and-price algorithms based on Dantzig-Wolfe decomposition have shown great success in solving mixed integer linear optimization problems (MILPs) with specific identifiable structure, such as vehicle routing and crew scheduling problems. For unstructured MILPs, the most frequently used methodology is branch-and-cut, which depends on generation of “generic” classes of valid inequalities to strengthen bounds.
Within the field of mathematical programming, discrete optimization has become the focus of a vast body of research and development due to the increasing number of industries now employing it to model the decision analysis for their most complex systems. Mixed integer linear programming problems involve minimizing (or maximizing) the value of some linear function over a polyhedral feasible region subject to integrality restrictions on some of the variables.
Mariagrazia Dotoli
We present a novel hierarchical and iterative procedure for lean manufacturing [1][2]. The technique effectively integrates the Value Stream Mapping (VSM) tool [3], the Analytic Hierarchy Process (AHP) technique [4] and discrete event simulation, in order to continuously improve the internal logistics of discrete manufacturing systems.
Peter G Higgins
Diego Klabjan
Loading Preview
Sorry, preview is currently unavailable. You can download the paper by clicking the button above.
RELATED PAPERS
Anand Umapathy
D. Conforti , maria elena bruni
Public Transport
Marta Mesquita
International Conference on Reasoning and Optimisation in Information Systems (ROIS2013)
Ouajdi Korbaa , F. Maaroufi , Herve Camus
erik purnomo
E.W. Hans , Nikky Kortbeek
New Journal of Physics
Nikky Kortbeek
Jacques Desrosiers
BMC health services research
Adrian Aguirre
Gilles Pesant
Johann Hurink , Erwin W Hans
Health Care Management Science
Johann Hurink , Erwin W Hans , Johann Hurinka
OR Spectrum
Johann Hurink
Optimization Letters
Josef Kallrath
Computers & Operations Research
Discrete Optimization
Christophe Duhamel
kosii spade
Jennie Gallimore , Pratik Parikh
Andrea Lodi
David Bredström
Computers & Industrial Engineering
Chengbin Chu
Airline crew scheduling: models, algorithms, and data sets
Mohammed Saddoune , Atoosa Kasirzadeh , François Soumis
Serpil Erol , Bulent Soykan
European Journal of Operational Research
Jesper Larsen
2007 IEEE International Conference on Automation Science and Engineering
Xiaolan Xie
Annals of Operations Research
Sridhar Tayur
Jeroen Beliën
International Journal of Production Economics
SSRN Electronic Journal
Rosemary Berger
Alain Martel
Maria Di Mascolo
Gloria Pérez Sainz de Rozas
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2023
Similar articles being viewed by others
Slider with three articles shown per slide. Use the Previous and Next buttons to navigate the slides or the slide controller buttons at the end to navigate through each slide.
Multi-objective admission planning problem: a two-stage stochastic approach
15 January 2019
Ana Batista, Jorge Vera & David Pozo
Operating room planning and surgical case scheduling: a review of literature
06 July 2018
Shuwan Zhu, Wenjuan Fan, … Panos M. Pardalos
A two-stage robust optimization approach for the master surgical schedule problem under uncertainty considering downstream resources
21 August 2021
Salma Makboul, Said Kharraja, … Ahmed El Hilali Alaoui
A data-driven hierarchical MILP approach for scheduling clinical pathways: a real-world case study from a German university hospital
19 September 2019
Karsten Schwarz, Michael Römer & Taïeb Mellouli
A two-step stochastic approach for operating rooms scheduling in multi-resource environment
08 November 2019
Arezoo Atighehchian, Mohammad Mehdi Sepehri, … Kamran Kianfar
Home health care routing and scheduling problems: a literature review
08 June 2022
Jalel Euchi, Malek Masmoudi & Patrick Siarry
An integrated rolling horizon approach to increase operating theatre efficiency
23 May 2020
Belinda Spratt & Erhan Kozan
Surgery scheduling heuristic considering OR downstream and upstream facilities and resources
23 July 2020
Rafael Calegari, Flavio S. Fogliatto, … Beatriz D. Schaan
Operating room scheduling with surgical team: a new approach with constraint programming and goal programming
14 December 2022
Şeyda Gür, Mehmet Pınarbaşı, … Tamer Eren
- Review Paper
- Published: 10 April 2021
Healthcare scheduling in optimization context: a review
- Zahraa A. Abdalkareem ORCID: orcid.org/0000-0003-0326-2519 1 , 5 ,
- Amiza Amir 1 ,
- Mohammed Azmi Al-Betar 2 , 3 ,
- Phaklen Ekhan 1 &
- Abdelaziz I. Hammouri 4
Health and Technology volume 11 , pages 445–469 ( 2021 ) Cite this article
10k Accesses
22 Citations
1 Altmetric
Metrics details
This paper offers a summary of the latest studies on healthcare scheduling problems including patients’ admission scheduling problem, nurse scheduling problem, operation room scheduling problem, surgery scheduling problem and other healthcare scheduling problems. The paper provides a comprehensive survey on healthcare scheduling focuses on the recent literature. The development of healthcare scheduling research plays a critical role in optimizing costs and improving the patient flow, providing prompt administration of treatment, and the optimal use of the resources provided and accessible in the hospitals. In the last decades, the healthcare scheduling methods that aim to automate the search for optimal resource management in hospitals by using metaheuristics methods have proliferated. However, the reported results are disintegrated since they solved every specific problem independently, given that there are many versions of problem definition and various data sets available for each of these problems. Therefore, this paper integrates the existing results by performing a comprehensive review and analyzing 190 articles based on four essential components in solving optimization problems: problem definition, formulations, data sets, and methods. This paper summarizes the latest healthcare scheduling problems focusing on patients’ admission scheduling problems, nurse scheduling problems, and operation room scheduling problems considering these are the most common issues found in the literature. Furthermore, this review aims to help researchers to highlight some development from the most recent papers and grasp the new trends for future directions.
Working on a manuscript?
1 introduction.
Nowadays, healthcare optimization problems have received significant attention in order to provide more appropriate services at a lower cost [ 1 , 2 ]. Moreover, it is imperative and attracts many researchers’ attention due to the high cost and limitation of resources (e.g. medical supplies, equipment, doctors, and staff) in the hospital. Without a doubt, healthcare scheduling is a challenge due to high constraints and preferences, such as personnel requirements, resources limitation. Unlike any other institution, healthcare sectors are working around the clock. However, the lack of staffing and irregular working shifts leads to job dissatisfaction and might influence patient satisfaction. Moreover, increasing population longevity will lead to a rising in demand for medical services [ 2 , 3 ]. However, increasing in demand for medical care, and the absence or shortage of it may cause patients threatened lives, overworking manpower, patients infection rates, and patients flow overcrowding [ 4 ].
A scheduling system could decrease patients waiting time, ease access to medical services and impact the quality of healthcare operations [ 1 , 5 ]. In order to get feasible scheduling for any healthcare system, the hard and soft constraints have to be determined. Hard constraints could not be violated whilst, the soft constraints integrated as a part of the cost function and should be minimized.
Hence, enhancing, planning and scheduling procedures of hospital resources play a vital role in the improvement of the hospital’s benefit and service quality delivered to patients. An improved scheduling system is essential because it is a crucial role in reducing costs revenue, and for enhanced accessibility to the healthcare system as well [ 6 ].
In recent years, many reviews have been conducted in healthcare scheduling considering the different scopes. for instance, healthcare scheduling based data mining is discussed in [ 7 ]. The author provides a systematic review of the literature that reflects an industrial engineering approach to healthcare scheduling with an emphasis on the behaviour of the patients’ role in scheduling. An integrated hospital scheduling issue has been reviewed in [ 8 ]. The review has been done based on collects scientific papers related to integrated hospital scheduling problems published between 1995 and 2016. In addition, operational research applicable to healthcare was surveyed in [ 2 ]. One of the major contributions of this work is to cover recent improvement issues in this area. In addition, there are several review papers dealing with healthcare scheduling that include part of scheduling issues such as [ 9 ], resource scheduling, operating room scheduling [ 10 , 11 ], and outpatient appointment scheduling [ 12 ].
Our contribution in this review paper is to compare and analyze all scientific work between 2010 -2020 in optimization-based healthcare scheduling, focusing on metaheuristic approaches. We investigate several versions of problem definitions in the research of patient admission scheduling. Furthermore, we also review the works available in solving other healthcare scheduling, including nurse scheduling problems and operating room scheduling/surgical scheduling. Our review work centered around patient admission scheduling research, nurse scheduling problems, and operating room scheduling/surgical scheduling, considering these problems are the most studied healthcare scheduling problems as described in Fig. 1 and 2 .
We cover several articles written in English and published in peer reviewed journals, searched the databases covering several disciplines such as, Scopus, Google scholar for relevant papers using combinations of relevant keywords such as “nurse scheduling”, “nurse rostering”, “patient admission scheduling”, “patient to bed assignment”, “operating room scheduling”, “operating theater”, “surgery scheduling”, “surgical scheduling”, “physician scheduling”, and healthcare scheduling with “heurstic” or “metaheurstics” “meta-heurstics”. For each article found, we performed a forward and backward search to find additional manuscripts. We limited the review to papers that are written in English and are published from 2010 to 2020 (see Fig. 1 ). The search procedure resulted in a set of 190 articles (see Fig. 2 ), we included papers that described the scheduling technique in healthcare, an overview of healthcare scheduling process which covers in this survey. We also included all papers that described the effects of metaheuristics in scheduling healthcare decision-making in an optimization context.
Number of covered article
Healthcare scheduling papers between 2010-2020
The organization of this survey is based on recent research papers which provide optimization-based for the most common healthcare scheduling problems including definition and formulations, data sets, methods. The major part of the paper discussed the patient admission scheduling, considering the recent problem found in the literature. We also reviewed the problems in allocating nurse to shift; and scheduling of operating room and surgery.
The importance and growth in using these optimization methods revealed very effective results when used for healthcare scheduling problem. However, it is still possible to improve the outcomes generated by present studies. Thus the research trends can be directed to investigate the applicability of other optimization methods for healthcare scheduling problems. This review has been analyzed based on optimization technique which especially based on heuristics, metaheuristic, hybrid metaheuristic to address any healthcare scheduling problem such as patient admission, nurse scheduling/rostering, operating room scheduling/surgery scheduling, etc (see Table 1 ).
Thereby, we achieve a better understanding of this spectrum, point out some development from the most recent papers, summarise some of the existing methods and grasp the new trends for future directions in this field. The organization of the paper is as the following. Section 2 discusses patient admission scheduling problems, definition, versions, formulation, and data sets. Then, it is followed by Section 3 , which describes the nurse rostering problem. Section 4 presents an operating room scheduling problem, and Section 5 briefly discusses other different healthcare optimization problems and solutions. Finally, Section 6 comprises the the conclusion and future work directions.
2 Patient admission scheduling problem (PASP)
The Patient Admission Scheduling (PASP) is referred to assign patients to room in the hospital over a time horizons [ 13 ]. Patient admission scheduling is combinatorial optimisation problem that is gaining a researchers concern in the healthcare career. PASP support a decision makers at various level such as long term (strategic level), med-term (tactical level), and short-term (operational level) in the healthcare institutes [ 14 ], which determine whether the hospital’s resources is ready for accepting patients through satisfactory services.
2.1 Definition of patient admission scheduling problem (PASP)
The Patient Admission Scheduling (PASP) is a problem of scheduling patients within certain time slots in the hospital to maximize both management competency, and patient comfort and safety, in addition to enhancing medical care in the hospital. Patient admission scheduling problem is a complex combinatorial problem [ 15 ]. Since the problem is first formulated in [ 16 ], its solution enables the scheduling of patients allocated to specific beds in particular relevant departments, fulfilling in an optimal way to the needs of the patients and ensures all the required medical restrictions. Usually, the assignment of patients to beds is executed by a centralized admission office, by contacting the departments several days prior for efficient patient admission. Some hospitals control the admission of their patients without a central admission office, leaving the admission responsibility to the various respective departments. As in the second case, an absence of the overall knowledge and information of the departments may cause in not being occupied optimally. There could be shortage of beds available for patients in some departments, but extra beds in other departments.
2.2 PASP Formulation
First, the Patient Admission Scheduling version (1) also called (original problem) has been introduced by [ 17 ], which entails the supposition that the dates for admission and discharge are prior knowledge. In addition, each patient should occupy at least one bed for a certain duration of time. The basic terminology of the problem can be described in the following:
Nigh: The variables representing time horizon for individual patient located in the hospital
Admitted patients are patients that are effectively admitted to the hospital and are assigned to a room and a bed.
Patient: A person requiring healthcare in a hospital and must be allocated a bedroom with a determined date of admission and discharge.
Room: Every department possesses its specific room, where each room possesses its specific capacity dependent upon the number of beds in it, which may be in the form of single/twin/ward beds.
Specialism: Every individual department in the hospital is determined by a single or additional treatment. Furthermore, individual rooms belonging to a specific department possesses its own specific level of treatment ranging from (1-3) dependent upon specific patient case.
Transfer: Moving admitted patient from room to another during her/his stay.
The problems faced in the original version of PASP are the adherence to some of the constraints, which is to break them up into hard and soft constraints categories, depending on the level of impact on the patients. The patient admission scheduling problem constraints (original PASP) is as follwing:
HC1: The availability of the room ( \(R_j\) ).
HC2: Admission \(AD_i\) , discharge date \(DD_i\) , and time horizon for the elective patient should be fixed, and unchangeable.
HC3: Time horizon should be continuous.
HC4: Two patients ( \(P_{i1},P_{i2}\) ) cannot be allocated in the same bed at the same time horizons.
HC5: Gender schema should be carried out.
HC6: The patient should be allocated to a department which is is acceptable to his/her age.
HC7: Mandatory room properties should be available in the assignment rooms.
HC8: Quarantine policy for some patients who need to be isolated, according to their illness requirement.
Furthermore, the soft constraints for this problem could be summarized as follow:
SC1:Room preference, which indicates the patient preference regarding room capacity such as(single, double, ward, etc). These constraints might be considered, otherwise they should be penalized (Table 3 ) for the weight penalty.
SC2: Preferred room properties, which represented some medical equipment in the department, and staff such as nurses.
SC3: Degree of specialism, in some cases, patients preferred to get medical treatment in departments that have highest degree of specialism.
SC4: Needed properties, some patients should assigned to a room with special equipment’s. This constraints is related to HC7.
SC5: Transfer, the unplanned transfers should be minimised.
All soft constraints should be satisfied as much as possible, and sometimes impossible to satisfy all the soft constraints. Otherwise, could be penalized the solution, the weight for each those constraints is as the following Table 2 .
The objective function of Patient Admission Scheduling (PASP) is to minimize all soft constraints, while satisfying the patients preferences, and respecting all the hard constraints to the problem, in order to obtain feasible solutions.
2.2.1 Patient admission scheduling problem under uncertainty (PASU) version 2
The PASU version involve in allocating room for each patient upon a number of days equal to her/his stay period, starting in a day, not before the planned admission. The extended version from PASP was proposed and formulated by [ 13 ], However, it included several real-world features, such as the presence of emergency patients, uncertainty in stay lengths; and the possibility of delaying admissions. The problem formulation considered many attributes in order to develop medical service in the hospital. It takes into consideration the possibility that a patient’s stay can be extended. The patient’s extended stay might affect the room scheduling, and this may lead to overcrowding. The PASU problem have several basic concepts [ 13 ]:
Day (planning horizon) : This entails the measurement of time and is to denote the duration of the determined stay of individual patient in the hospital; the set of sequential days taken into account in the problem is termed as the planning horizon.
Patient: A patient is the person who needs specific treatments in the hospital and is required to stay in the hospital, the duration of the stay should be continuous. In addition, two kinds of patients have been used in this version, inpatients who are already admitted to the hospital, and a new patients, new patient refers to a patient who will be admitted.
Room/Department: Each room in the hospital belongs to specific department depending on the patient’s needs. Every room in the hospital can be a single, twin room, or a ward. The capacity of a room depends on the number of beds available. A patient may want to occupy a specific room capacity, but might need to pay extra.
Specialism: Every patient in the hospital needs a specific treatment. Thus, the management office in the hospital should distribute the patients according to their diseases. However, a specific departments may be considered as fully, partially qualified, or not qualified for the patients. It is considered as unreasonable to schedule a patient to a non-qualified department for the treatment of the patient’s disease; whereas, allocating a patient to a partially qualified department is acceptable. However this might maximize the cost function.
Room Feature: The quality in the room is depends on its feature. Some of room have additional features such as oxygen, telemetry, nitrogen, and television. Some patients need/prefer certain specific features which are case-dependent. Assigning a patient to a room without considering the needs is deemed to be an unfeasible solution, whereas missing the desired features will maximize the objective function depending on the weight value of this element.
Room Gender Policy: Every individual room has a gender policy. There are four policies (SG, Fe, Ma, All). Fe: is for female patients only; Ma: is for male patients only; SG: both genders can be accepted. But in the same day should be from the same gender. All: the same gender can be accepted at the same time, for example (intensive care).
Age Policy: Certain departments have age limits. For example; the pediatrics department accepts patients ranging from 0 to 12. PASU involved hard and soft constraints and have to be met. In this problem Department Specialism (DS) , Room Features (RF) , they are hard for the missing qualification, or needed features, but soft for partial qualification and the desired feature. The hard constraints are:
HC1: Room capacity (RC), allocating two patients at the same bed simultaneously make the solution infeasible.
HC2: Patient Age (PA), patients should be assigned to a department that accept his/her age.
The soft constraints are:
SC1: Room Gender (RG), gender policy room should be fulfilled.
SC2: Room Preference (RP), patient prefer to be allocated room with special preference.
SC3: Transfer (Tr), transfer inpatient from room to another during her stay is undesirable.
Delay (De): delay patients admission.
Overcrowd Risk (OR): calculated a number of patients who have been allocated for each room and take the certain, potential attend overstay length of some patients, and capacity of the room.
All soft constraints have been correlated with weights, based on its importance to the patients. The highest weight is associated with SC3, transfer patients are adding (100) to the objective function, the second-highest weight is for SC1, which is related to the gender policy for the patients, it is weighted (50) adding to the cost. The rest are Department specialism, Room feature is weighted (20), while Room Preference is (20). Finally, Delay (De) is (2), and Overstay Risk is weighted (1).
2.3 PASU formulation in mathematics
The mathematical formulation for PASU is described and formulated by [ 13 ], and for self- integration for this paper, we introduce the mathematical formulation here.
P : is a set of all patients.
\(P_{F}\) is a set of female. \(P_{M}\) is a set of male patients. Where \(P_{F}\) \(\bigcup\) \(P_{M}\) \(=\) P .
\(P_{H}\) is a set of in-patients and \(r_{p}\) is the room occupied by in-patient where \(p \in P_{H}\)
D : is a set of days.
R : the set of rooms and \(c_{r}\) is the capacity of room \(r\in R\) .
\(R_{SG}\) : the subset of rooms with policy SG . Additionally we have
\(D_{p}\) : is a set of days in which a patient \(p\in P\) is present in the hospital.
\(P_{d}\) : is a set of patients present in day d (i.e., set of patients p such that \(d\in D_{p}\) ). The main decision variables are the following:
\(x_{p,r}\) : 1 if patient p is assigned to room r , And 0 if not. The constraints on the x variables are:
The equations describes how the constraints are defined in PASU, equation (1) explains how the patient is assigned to the specified room, while equation (2) ensure the capacity of the room does not exceed the limits ( RC ). Finally, equation (3) provides against infeasible assignments for patient-room unsuitability (PRS). The variable x represents the search space of the problem. There are other variables to describe the components of the objective function F . The variables for the Room Preference ( RP ) management component is shown in the mathematical expression below:
\(f_{r,d}\) , \(m_{r,d}\) :1 if there is one female at least (resp.male) patient in room r in day d ,0 otherwise.
\(b_{r,d}\) :1 if there is both male and female patients in room r in day d ,0 otherwise. These new variables are related to the x and to each other by the following constraints:
As well as the equation (4), and (5) establishing relation between the auxiliary variables f and m to x , stating that when there is a female (resp.male) patient in room, then all the f (resp.male) variables corresponding to the days \(d\in\) \(D_{p}\) must be set to 1, whereas, constraints ( d ) relate both m and f to b , in the way that if m and f are \(=\) \(1\) then b must be 1. For the constraint (OR) overcrowd risk components the modeling is as follow:
\(y_{r,d}\) :1 if room r risks to be overcrowded in day d , 0 otherwise. So as to define the constraints that have relating y variables to x , the following definition will complete the mathematical expression. \(\overset{+}{p}_{d}\) : is a set of patients that are possible to attend to hospital in day d , which are the patients that existing in day d plus those present in day \(d-1\) with the risk of overstay. \(\left| Z\right|\) :the cardinally of a set Z . and \(\bar{z}\) :the complement of variable z . The constraints relating y to x are the following:
It’s worth noting when \(y_{r,d}=1\) the variables \(x_{p,r}\) can be any value. On the contrary, when \(y_{r,d}=0\) then at least \(\big (\left| P^{+}_{d}\right| -c_{r}\) of the x include should take the value 0. Additionally the objective function can computed as follow:
The components of the objective function PRC , RG ,and OR is defined as follow:
The equation (9) calculates the cost for patient-room assignment, while equation (10) calculates the number of rooms occupied by both male and female patients. The last equation (11) assesses the overcrowd risk. The PASU problem is modeled as Integer Linear Programming (ILP). In addition, it can be implemented in any general purpose Integer Programming IP solver. In general the problem is modeled as three dimensional matrix of decision variables z , \(z_{p,r,d}=0\) if and only if patient p is in room r in day d . It is worth mentioning that the \(1's\) in the matrix z are consecutive, and its equal to patients stay length.
2.4 Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delay (version 3)
This version of patient admission scheduling problem engaged with operating room scheduling [ 18 ], it is presented into two phases, patients admission constraints phase, and operating room constraints phase.
The basic concept of the first phase is as following [ 18 ]:
Patients : Is the main component in this problem, and the patient should have an admission and discharge date, the duration between the admission and discharge date is termed as the length of stay (LoS) . Some patients may need to extend their stay in the hospital, because of their situation, and these extension is termed as overstay risk .
Day : A day is a unit specifying the time spent by the patients in the hospital, where each patient should spent a few continuous days. These days are termed as a planning horizon.
Room : A room belongs to a department, the quantity of beds that can occupy a room is termed as capacity (typically one, two, four rooms, or a ward). The room may have properties such as oxygen, nitrogen, telemetry, and TV). These properties may become preferences or patients’ requirements.
Specialty/Specialism : Ordinarily, patients usually need to get one type of treatment, whereas there are some patients who might need more than one treatment and those with special cases. In fact, each department in the hospital is responsible for treating a specific disease that needs different types of specialization but at diverse levels of expertise. Three levels of specialists sets in the department, complete treatment (no penalty), partial treatment with a penalty, last level none , which mean that the patient can not be treated in this department. Beside the features mentioned above, there are two polices, age and gender, some departments which specialized in treatment for one type of patients such as pediatrics and geriatrics, only host patients from a certain range of age, with minimum and maximum age terms and conditions. While (Gender policy), refer to four types of rooms in the hospital which are: D,F,M, and N. The room from type D can accept patients from both genders, but in the same day the patient should be from the same gender. Type F only accepts female patients, whereas type M only accepts male patients. Finally, room type N, accepts both genders, for instance, recovery rooms and the intensive care rooms. Dynamic Patient Admission Scheduling with Operating Room Constraints, Flexible Horizon, and Patient delays are to assign a patient to a room in a department, and the patient is currently present at the hospital, making the admission realistic, and the discharge of a patient from a room could be done later, depending on the patient’s situation. The solution to this problem should satisfy all of the hard constraints and categorized in this problem as:
HC1: Room capacity (RC), each room has a limited number of beds, thus, the number of patients cannot exceed the number of the rooms.
HC2: Patient-Room Suitability (PRS), the assignment of individual patient to a room must be a match and appropriate to the patient’s needs and condition.
Hence, the cost function could be calculated based on the violation of the following four soft constraints related to the patient’s admission problem. Patient-room cost (PRC) , [ 18 ] generated a matrix that consists of an integer value termed as Patient-Room Matrix. It explains the penalty of patient-to-room allocations. If the value in the matrix is 1, that signifies that the room is not suitable for the patient. Meanwhile, if it has a positive value, it means that the room accepts the patient with penalty. Additionally, if it is 0, that signifies that it is matches the requirements, and it is a suitable fit. The second constraints is Room gender (RG) , based on the room types mentioned above, the room type N is the result of no cost, whilst the room type D denotes that it can be occupied by both genders concurrently. However, there is a penalty imposed that is proportionate to the size of the smaller of the two patients. The cost for rooms of type F and M are inclusive in the patients room matrix. The third constraints is Delay (De) , the delay results with cost incurred depending on the length of the delay. The delay is usually undesirable if the admission date is nearer, then the delay expense is multiplied by priority that is reciprocally proportionate to the nearness of the admission day. Finally, Overcrowding risk (Ri) , additional penalty added for the cost function, if the patient is to be discharged and needs to stay, and his/her room is fully occupied.
The basic concept of the second phase (operating room notions) is as follow:
Operating room scheduling is assigned specialities to the Master Surgical Schedule (MSS). Master surgical schedule regularly repeated schedule [ 19 ], in which assigning one specialist for the operating room for the duration of time (typically each week). Patient admission scheduling problem (version 3) has been bounded with operating room scheduling, and the basic notation for operating in this problem is as follow:
Operating Room Slot: It is the smallest amount of time, in which the operating room could be reserved for one specialty in that day. In any day in the scheduling planning for Master Surgical Schedule(MSS) an integer number of operating room slots will be assigned a specialty. In the same day/the operating room could be occupied by different surgeon in the same specialty.
Surgery Treatment: Each patient in the hospital is subject to a special treatment. Some of them need to get surgery of corresponding specialty. In this situation the day of the surgery (may be in the same day of admission or the next day after admission), so the expected length of the surgery should be fixed with the specialty. The assignment is as long as subject to all the constraints that are presented previously (RC,PRS,PRC,RG,De,Ri) and for the operating room there are additional constraints: Operating Room Utilization(ORU): In each day and specialty, there is a limited time specified by the (MSS) , where the total length for each surgery belonging to the specialty should not exceed the limit. This condition is considered as a hard constraint, and its effect on the search space of the problem. Meanwhile, [ 18 ] is only covered the admission day of a patient; the problem of sequencing operating room slots in diverse operating rooms and surgeries within each OR slot is not included in this problem. In addition, the length of emergencies for patient is not take in consideration in the computation of the utilization for the ORU constraint. Further more the total occupation should be lower than the capacity. So there is another constraint, should take in consideration that deals specifically with this issue, which is Operating Room Total Utilization (ORTU): In each day the total length of all surgeries including urgent cases and belong to the same specialty should not exceed the capacity of the operating rooms. The ORU and ORTU constraints cover only the total length of slots. In reality, this length is divided into normal time and overtime. Normal time can be used freely, whilst overtime is allowed but should be minimized. To model this situation, the problem includes a cost component soft for the overtime work. Operating Room Overtime (ORO): for each day and specialty, the total length of surgeries with the same specialty must not exceed the limitation of normal time that giving to it. In some cases specialty goes overtime, this will lead to cost related to dedicated personnel, but not for all staff in the operating room. In contrast, other specialty may not use the operating room full time, so this will balance the occupancy. Also the total overtime of the rooms could be calculated by adding the next component called an operating room total overtime in order to count the costs. Operating Room Total Overtime (ORTO): For any day, the cost for the overall length surgeries in all specialties including (urgent cases) should not exceed the total normal time of the operating rooms.
2.5 Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delay (version 3) formulation in mathematics
Mathematical formulation for this problem is extension for (PASU) problem version 2. However, The cost function for this problem could be calculated according to various weight based on the importance of the constraint for the patients. Tables 3 and 4 reports the weight of the cost components.
2.6 PASP Data sets versions
The original data set which belong to the first version of the problem Footnote 1 is firstly reported by [ 17 ]. The data set consists of 13 instances as shown in Table 3 . The instances 1 to 6 have equal time slots of 14 days. While, the instances 7 to 12 have the time slots between 14 to 91 days. All the patients in these instances are in need of only one specific treatment, but in instance 13, the patients need multiple treatments during the patients’ stay. This signifies that the instance 13 is more complex than others. In addition, this data set which reported by [ 15 , 17 ] describes the original data set features including all present patients, even those whose admission and discharge dates are the same day. Figure 3 give an example description of the data set. The data set involved two-stage, first stage describes the rooms in the hospital, including room name, capacity, type (mean type of patients gender, which occupied the room), specialist for each room, finally the room properties. Second stage represented the patients needed/preference feature. Starting with patient id, age, gender, duration of stay. Then the department and specialist need for each patient, room capacity preferred by the patient, finally the needed and preferred properties.
Example for PASP original version data set
The second data set type is generated by [ 13 ], the author created and designed a data generator that is able to generate realistic data for a huge set of varying sizes. The generator accepts parameters such as: the number of patients , departments , days , rooms , and features . Randomized instances generated according to preset dissemination related to varying features like the duration of the stay, the room capacity, the number of specialism, and others. Meanwhile, the generator is not designed for single-day-cases to give opportunity for a complex to be solved. The data set consists of 9 families of 50 instances each. The data set entities is divided into three varying sizes in terms of the number of patients and the planning horizons. By observing this data set, on the doubling of number of days, the number of patients is equally doubled in order to keep the average occupancy balanced. Tables 5 and 6 reports the data set features.
2.7 PASP-based optimization methods
The ways that are presented by the researchers to optimize the patient admission scheduling can be classified into two types of search methodologies and solution technique. There are many scheduling techniques available for solving patient admission scheduling problem (PASP). The work done by [ 17 ], local search called tabu search hybrid engaged with token ring and a variable neighborhood descent approach, has been applied to assign a patient to bed in the hospital. Randomly generated data set have been used to evaluate the proposed method. The method needs more be investigated due to the complexity of this problem and could also be expanded further in terms of considered emergency admissions, and intensive care department. Moreover, another local search have been applied by [ 20 ] to tackle PASP, simulated annealing hybrid with local search and get the best known results. The method was tested on data set 1; the author excluded one constraint, which is transfer patients form one room to another.
A hyper heuristic approach has been used to tackle two combinatorial optimization problem, the patient admission scheduling problem and the nurse rostering problem [ 15 ]. Applying hyper heuristic is not appropriate, if the occupancy bed rate is increased in the hospital, which is due to the fix admission date. Moreover, the method has not considered the intensive care patients, patients who need isolation, patients on waiting lists. On another hand, theses two problems could be integrated together and come up with new version of PASP. The method was tested on a new benchmark data set introduced by the author.
Two Integer linear programming models (ILP) has been developed for tackling a day- to- day planning process for (PASP) problem [ 21 ]. This work is an extension of the work done by [ 20 ], and similar to [ 13 ]. The main contribution is by adding random registration date and predicted leaving date. The first model calculate for determining the optimal assignment for patients who have just arrived, while the second model calculate for forthcoming, but planned, arrivals. Hence, the performances of these models are compared with each other. The result shows that the second model is superior to the first in all conditions. In this method the over-crowed risk and the delayed in admission are not considered.
In addition, [ 22 ] introduced meta-heuristics algorithm for tackling appointment scheduling problem in an imaging clinic. A discrete-event simulation model bound with an optimization technique in order to minimize the patients’ waiting time. To evaluated this approach data is collected from 966 medical test for specific duration (4 month). This method has been focused on one aspect of the patient’s admission, which is imagine clinic.
Certain methods were developed using various types of metaheurstics such as in [ 23 ] the author introduced a Biogeography (BBO) algorithm which is population based meta-heuristic to address PASP problem. The proposed method evaluated its performance through the utilization instances from dataset 1. The result of BBO needs to be investigated further because it has reached a stagnation state earlier and could utilize all instances instead of only (1-6). In addition, an exact method was used by [ 24 ], the proposed method utilized column generation based heurstic incorporated with dynamic constraint aggregation, and new mathematical formulation for PASP problem was introduced. In this method, six instances were used from data set 1 to evaluate the method. The proposed method obtained good result in term of accuracy for small instances (1-5 instances). An exact method could be used to solve small instances, for large instances, the approach needs further investigation. Another metaheurstic was proposed by [ 25 ] known as an adaptive non-linear deluge algorithm to address patient admission scheduling PASP. The result of this approach was compared with other algorithms in literature, and was found to obtain superior results through the utilization of the six instances out of 13 from data set 1.
Furthermore, [ 14 ] proposed a metaheurstic approach using large neighborhood search by utilizing simulated annealing for solving dynamic patient admission scheduling problem. This method is based on [ 13 ], and tested using 450 instances from data set 2. The result demonstrated an improvement for the small and medium instances and much faster than the work done by [ 13 ], while for large instances there is a need for further improvement.
In similar context, [ 26 ] studied a dynamic patient-to-room assignment planning by expanded the PASP proposed by [ 17 ]. In this method, two outline Integer linear programming ILP models for solving this problem. The developed method engaged in certain testing using benchmark data set with some extension on its parameters, such as registration date and expected departure and also explicit the emergency patients. The result of these two models showed a more superior performance by the second model under all circumstances. Two methods known as Fix-and-Relax (FR) and Fix- and-Optimize (FO) has been conducted by [ 27 ] to solve (PASP). These two methods are based on heurstic using mixed integer programming. The problem is divided into two sub-problem based on time frame, and then the sub-problem are optimized. It entails the decomposition with the consideration of LoS, preference. The solution that was generated by the first method (FR) was used as input to the second method (FO). The proposed method that used (12) instances out of (13) from the data set 1 obtained promising feasible result at a faster rate of less than 3 minutes comparable with the state-of-arts. Recently [ 28 ] introduced an offline patient admissions scheduling problem under uncertainty with new suggestion on how to set the weight for the constraints. The method was tested on small short families from data set. This method was developed based on previous work of the same author [ 29 ] which proposed three optimization models based matheuristic called (FiNeMat) for solving patient to bed assignment which considered it as a sub-task from PASP [ 17 ]. In this work the author gives a guideline on how to set up the penalty values for the soft constraints. Moreover, [ 30 ] presented a newly metaheurstic approach known as Late Acceptance Hill Climbing Algorithm (LAHC) to address PASP problem. LAHC type of meta-heurstic and considered as a one-point solution technique. The proposed method involves two steps: the first step includes the generation of the initial feasible solution utilizing the room oriented-based approach whilst, the second step entailed the embedment of three neighbourhood structures inside the LAHC-based PASP component for the extended enhancement of the initial resolution generated at the beginning step. The suggested algorithm was assessed utilising the dataset 1. The result showed that the technique outperformed numerous other existing techniques from the literature using 1-6 instances out of 13. The main purpose behind the scheduling method is in the reduction of the patient waiting time, and in the hospital resource utilization enhancement. Moreover, [ 31 ] tackled PASP using a population-based metaheurstic called harmony search algorithm. The method has been tested on 6 instances of data set 1 and compare with other metaheurstic approaches. The proposed method needs more enhancement and should be tested on the rest of the data set.
In the work done by [ 32 ] the author proposed an exact method to address PASP. A new mathematical formulation bulit up, and mixed integer programming has been utilized with parameter free, and without pre- processing phase. The proposed approach tested on (1-13) instances from data set 1, and proof an optimal results for 2 of the instances and 9 new best result have been reported. Recently [ 33 ] revisited and extend biogeography-based optimization algorithm (BBO) to tackle PASP. The author introduced a selection technique called guided bed selection to enhance the ability of BBO and increased the diversity. Modified BBO yield better results than simple BBO using 6 instances from the original data set. On the other hand, [ 34 ] have studied the effect of compatible between short term and long term (strategic) in context dynamic patient admission scheduling problem which proposed by [ 18 ]. The results of this method using Dantzig-Wolfe decomposition and column generation get better results for 26 instances out of 30.
2.8 Discussion
The problem of optimizing patients admission scheduling has received attention recently. Patients scheduling in optimization can be considered from different side of aspects, (short,med,long) term scheduling, patients group, and methods which can be used to tackle such problem. Patient admission scheduling problem has been aroused at all levels of hospital planning and scheduling. Generally, most studies have focused on the operational level more than the tactical and strategical level. The operational level is also called the decision support level by assigning one task to resources in the hospital. There is fewer scheduling system that uses multiple level of decisions. The compatibility between all decision level very challenging problem and the studies on it is not rather vast and need to be further investigation.
Moreover, the patients have been classified into groups, elective patients and non-elective patients, elective patients have been widely studied in the literature which used a historical data from the hospital and scheduling the patients according to fixed data (statically). Non-elective patients refer to the patients whose the admission and discharge dates are unknown, such as emergency patients or uncertainty patients (dynamically). However, scheduling uncertainty is a complex task and there are few studies on scheduling the uncertainty patients. It should be noted that most studies on elective patients and neglect the problems arose in non-elective patients. Static PASP optimality are open challenges and still most of the researchers focusing on the short data set (1-6), due to the complexity of the rest. However, instance 13 only addressed in three articles because the patients need to be treated in multi departments. Dynamic version of this problem get less attention, and also many researchers focused on the small families and medium data sets. Patient admission scheduling problem integrated with other healthcare resources such as nurse, physician, and operating room could be improved the services in the hospital for future challenge work.
From an algorithmic point of view, patient admission scheduling problem versions were handled using different heuristics, metaheuristic, or exact method. The researchers have to develop new algorithms for handling this problem. The Table 7 summarizes the patient admission scheduling problem versions, approaches, and data sets.
3 Nurse rostering problem
Nurse rostering problem is a type of staff scheduling issues [ 37 ]. It is defined as a procedure to organize a time table that satisfies the demand of each person without conflict [ 37 ]. Nurse rostering have adjudged to be particularly complex and difficult optimization problem. Many researchers attempt to solve this problem using a different optimization model. Nurse rostering is N/P hard problem which involves two steps; the first step is to determine the number of staff to be scheduled, and second step is to allocate them in the time horizon for the schedule. The following section will give further details about this particular problem including its definition, mathematical formulation, versions, and finally the data set types for each version.
3.1 Nurse scheduling problem definition
The problem in nurse scheduling is so entrenched in the healthcare system, which is considered as under resource scheduling in healthcare, entailing the scheduling of a personnel [ 38 ] or staff in the hospital, by balancing the workload and preferences. The nurse scheduling problem entails NP hard optimization problem which is set through the allocation of a group of differing skilled nurses to various kinds of shifts as shown in Table 8 , over a predefined scheduling time [ 39 ]. To obtain the feasible scheduling, the hard constraint should be achieved, while the soft constraints are allowed, however will be penalized. Nurse scheduling preference should be maximized, and the overall cost should be minimized.
3.2 Nurse rostering problem versions
Nurse rostering problem has been widely studied in the last decades. The first version has been run in 2002, and then in 2007 an extension model was developed in order to provide the researchers with various models and increase the real world constraints. Recently in 2010, (INRC-I) has been expanded and later (INRC-II). The next section will illustrated (INRC-I) and (INRC-II) in details.
3.2.1 NRP version1 (INRC-I)
The first international competition (INRC-I) [ 41 ] was established in 2010, based on two influential competition ITC2002, ITC2007 [ 42 ]. The generic model in this problem is how to allocate a nurse in a shift subject to several numbers of constraints. The objective function of this problem is to minimize all the soft constraints and this will lead to reduced penalties. The NRP description is [ 41 ]:
Roster: List which is made for several days for each ward in the healthcare institution.
Shift/rotation types: Appointed a nurse with specific skill based on period of time.
The number of nurses required for each day and for each type of shift is provided.
A series of arrangements reflecting the nurses ’ work regulation. Every nurse performs precisely according to a contract. A contract should provide a rules of the work as shown in Table 9 :
3.3 NRP Datasets versions
There are several data set type publicly available for NRP. However, most of them are real world data, first of them KAHO data sets https://people.cs.kuleuven.be/pieter.smet/nursero , represented instances of six wards in two different Belgian hospitals. These wards include three different scenario’s: normal, overload and absence. The first scenario represents a usual working case with average working conditions. The second scenario offers unexpected condition, for example when there is a disaster or an unexpected absence case. On the other hand, the second data set type belongs to the First International Nurse Rostering Competition (INRC-2010) prepared by the research group at the University of Udine in Italy and the Second International Nurse Rostering Competition (INRC-II), all instances and data set could be find https://mobiz.vives.be/inrc2/?paged=20 . NSPLib http://www.projectmanagement.ugent.be/research/data/realdata is another data but it is not derived from real data,but its constructed with that problem generator. Nottingham datasets [ 43 ] which has been provided by Nottingham university which, established a website consist of a wide range of data sets from world wide hospitals. Additionally, the UK data set [ 43 ] which is the earlier one that is obtained from the UK hospital and consists of 411 preprocessed valid shift patterns.
3.4 NRP-based Optimization Methods
NRP typically considers staff scheduling problem [ 44 ] Numerous researchers give special attention to nurse scheduling and attempts to optimize it in order to achieve a workable roster that has positive scheduling quality. Recently, [ 45 ] proposed directed Bee Colony algorithm which is used to address NRP. The researchers utilized a multi-objective mathematical programming model and adapted a Multi-Objective Directed Bee Colony Optimization (MODBCO). The performance of this algorithm is evaluated using INRC2010. A set of 69 different cases of various sized data sets are chosen, and 34 out of 69 instances obtained the best results. Furthermore, [ 46 ] proposed a hybrid harmony search algorithm with hill climbing as a resolution in addressing the greatly limited nurse rostering problem (NRP). This method utilizes hill climbing to empower its exploitation in the search space. Moreover, the harmony memory consideration in the harmony search algorithm is through replacement by random selection scheme along side the global best concept of particle swarm optimization, in order to accelerate the convergence rate. The result of this technique demonstrated that the proposed method obtained five new best outcomes in relations to the quality of the solution, and time necessities. In addition, [ 39 ] offered another method to address NRP. The author introduced harmony search algorithm with a modification in its operators, replacing random selection with the global-best selection of Particle Swarm Optimization in memory consideration operator to enhance convergence speed. In order to develop a local utilization in this method, multi-pitch adjustment procedures were added. The result of this method proved that harmony search algorithm have the ability to solve the NRP using INRC2010 data set. Furthermore [ 47 ] proposed hybrid Artificial Bee Colony algorithm to address NRP. The author replaced the bee phase by hill climbing method in order to rise up the exploitation. The performance of this algorithm is evaluated using INRC-I. For two instances the proposed method has had good results.
In the work done by [ 48 ], the author proposed an integer programming techniques to solve NRP. On the other hand, [ 49 ] solved a dynamic version of NRP which was formulated for the second nurse rostering competition (INRC-II). In this proposed method two solvers were created, which were dependent on Mixed Integer Linear Programming (MILP) and Simulated Annealing respectively. The first solver was based on the exact method using the MILP solver CPLEX (v. 12.5), Meanwhile the second solver was implemented using EasyLocal++ (v.3). In addition [ 50 ] had also solved the dynamic version for NRP. The researchers have added a new expansion to the problem in the version of additional constraints to address incomplete data, and have used an integer programming model to solve the problem. The experimental result using this approach had shown an improvement on the basic model outcome, and had attained competitive outcome in comparison to the contest finalists competition. The work done by [ 51 ], branch-and-price procedure engaged with large-neighborhood-search framework has been used to solve INRC-II. The results in large instances has been achieved. In addition, [ 52 ] tackled NRP by utilized local search method (SA) based on a large neighborhood. The proposed method tested on INRC-II and getting better results in small instances (4-8) weeks whilst, for large instance are worst in comparing with [ 51 ]. Moreover, [ 53 ] developing two heuristic algorithms to solve NRP in a radio logical technologist rosters in the research hospital. Decision tree method and greedy search algorithm has been integrated with bat algorithm and particle swarm in order to generate a feasible solution. This method has a limitation in considering a scheduling for long period. Fix-and-Relax (F and R) and Fix-and-Optimize based simulated annealing, are two methods has been utilized by [ 54 ] to tackle NRP. The method has been tested on 24 available data set, and has been reported seven new best-known results. In Table 10 summaries of NRP and various version with its method, datasets, and categories
3.5 Discussion
The problem of optimization Nurse rostering (NRP) has become a major topic for scholar among the personnel scheduling problems. It become an attractive problem for many optimization researchers. Nursing shortages are a significant and multifaceted problem in healthcare systems and in optimization field is crucial. Many researchers have tackled the problems with different techniques such as exact methods, heuristic procedures and metaheuristics. Nurse rostering problem is an open research challenge in operational level using various metaheuristics approaches. Hybridization of metaheuristics with local search show the ability to solve NRP [ 47 ], Due to the ability to balance the exploration and exploitation.
Nurse rostering problem has been studied with a different type of constraints, features and evaluated in various countries [ 43 ] using different real hospital data sets. Most studies have focused on the data sets (INRC-I), and INRC2010. There is a limitation of creating real data sets from hospitals from different countries, this belongs to the privacy for the hospitals. INRC-II dynamic version has limited studies due to its complexity and the multi-stage scenario. Most studies for INRC-II focused on the small instances (4-8) weeks for this problem. Nurse scheduling problem could be developed further by taking in consideration, each country conditions. Integrating between nurse scheduling and other healthcare problem such as patients scheduling, physician scheduling could enhance the performance of the medical institution.
4 Operating room scheduling
Operating room theatre plays a significant part in the health care sector, because of its major impact on hospital performance. Operating room requires a special combination of personnel and equipment. In addition, each surgery requires preparation, before and after the surgery. So, the operating room theatre consists of two parts, namely the preoperative and the postoperative [ 70 ]. Managing/scheduling the operating room theatre is extremely difficult due to its constraints, and the preferences of the stakeholders. Moreover, the resources limitations, and the increase in demand for surgical services have to lead to improved approaches to room scheduling, by applying different approaches to manage the operating room theatre. The next sections will explicate the operating room scheduling extensively.
4.1 Operating room scheduling problem definition
The operating theatre scheduling also called surgery scheduling consists of two parts; the operating room and the recovery room [ 71 ]. The Operating Theater (OT) involves the required resources for surgeries. These include personnel such as nurses, surgeons, anaesthetists and others, meanwhile, others involve facilities such as equipment, pre-operative holding units, multiple ORs, post-anaesthesia care units, and intensive care. There are varying operating room scheduling definitions, [ 72 ] has been described the operating room scheduling as “sequence of job/activities to allocate in the operating room”. The operating room is the ultimate important part of the hospital; it represents the source of income and expense for hospitals. The operating room has an immense significance with other hospital resources, and represent approximately \(40\%\) from the hospital income [ 73 ]. “The OR schedule is a patient flow management tool, and it assists the flow of other hospital resources, such as equipment, instrumentation, and ancillary hospital staffing resources” [ 74 ]. In addition [ 74 ] defined the operating room scheduling as a central system where the operating room is run by operation room leadership team, functioning as an efficient instrument, for the transmission of real-time patients flow and resources data of all departments, including the care of surgical patients. Hence operating room scheduling allows the coordination of resources in the hospital such as surgeons, anesthesiologists, nurses, technicians, and ancillary staff to be allocated in the appropriate technicians, and ancillary staff to be allocated in the appropriate way. On the other hand [ 75 ] defined the Operating Room Surgical Schedule in his article as the assignment of a surgical operation to an operating room, according to a different type of factors such as room availability, weekly working hours, doctor’s preferences, and operating room capabilities.
The main goal for each hospital is the high-quality service deliverance for patients, therefore there is an essential requirement for the boosting of operating room/department achievement through optimal resources usage. The operating room surgery scheduling is to distribute the operation start time and allocate the resources for scheduled surgeries, taking into consideration the multiple constraints in order to obtain the entire surgery flow, the existence and accessibility of resources, and the specializations and credentials of the staff [ 76 ].
Operating room theatre could be classified into different levels, according to patients type (elective, emergency), upon decision level such as (short, mid, long) term, or according to management procedures (block scheduling, open scheduling, or modified block scheduling) [ 77 ]. In this study, the primary emphasis is on the short term of the operating room scheduling which is split up to advance scheduling and allocation scheduling.
4.2 Operating room scheduling versions
Operating room scheduling at operational decision level is called surgical case scheduling problem (SCSP). There are mainly two scheduling versions of Operating Room Scheduling, namely: Advanced scheduling and Allocation scheduling. Advance scheduling is the procedure of establishing a patient’s (elective) surgery date and aim to get patients satisfaction (minimize patients waiting time), while allocation scheduling involves the setting of the operating room and the process initiation time on the particular surgery day. This literature focused on the operating room planning, in which the scheduling of the patients needs two essential procedures to be carried out; firstly, the assignment of patients to the operation room as (advanced scheduling), and secondly, the determination of the sequence of surgeries in each operating room block by the allocation schedule. Generally, each hospital has determined one of the following strategies which have been classified by Fei et al to establish a surgery scheduling procedure. The first group of strategy encompasses an open scheduling strategy, block scheduling strategy, and modified block scheduling strategy [ 1 ].
Open scheduling strategy
or “any workday” model of scheduling on OR scheduling entails no reservation in the time slot for a specific surgeon, and any workday option for surgeons. Additionally, this model is constraint-free [ 78 ]and follow the prioritization of chronology sequencing, starting from the earliest patient time-in strategy.
Block scheduling strategy
surgeons or the appointment of a collective of surgeons assigned to a grouped time blocks, where the organization of surgical patients (usually half-day or full-day length) are made. Block scheduling is a particular open scheduling matter.
Modified block scheduling strategy
This model is modified to obtain two types of scheduling: Firstly, by reserving some operating rooms opening hours while others are left open, and secondly, by freeing unused time blocks determined previously.
Practically the block scheduling and modified block scheduling has been widely applied in hospitals [ 1 ]. Moreover, this model is more flexible and provides an opportunity to re-use free time slots of operating room scheduling [ 78 ].
4.3 OR Advanced scheduling (version 1)
Advanced scheduling entails the surgery date establishment process for scheduling elective patients, which implicates a future event occurrence [ 79 ]. Advanced scheduling also has been diverse to dynamic and static scheduling based on the surgery settings [ 80 ]. However, the dynamic type refers to the patients who given a surgery date at consultation time. Whereas, the static type based on the patients waiting list. Advanced scheduling of the operating room is segregated into two categories, dependent on the type of constraints. The first constraints which are the total available operating room, while the rest of the constraints are determined by the available resources such as staff, and equipment.
4.4 Allocation scheduling (version 2)
Allocation scheduling also has other name called intervention scheduling, and surgical case scheduling. Allocation scheduling is to set the starting time of the operation and the resources are required for utilization. Allocation scheduling generates feasible scheduling for the operating room for each surgery per day with the assumption is that all patients in the hospital and ready for surgery [ 79 ].
4.5 Operating room scheduling mathematical formulation
The mathematical formulation of operating room planing and scheduling are presented in the huge majority of papers presented by [ 1 , 81 , 82 ]. This review will consider the mathematical formulation as it is modelled by [ 82 ] as advanced scheduling formulation. Lets ( R ) is the operating rooms, and \((r=1,...,R)\) . Q be a set of patients, ( \(q=1,...,Q\) ), and patients are scheduled in a set of time blocks, \(b=1,...,B\) , in a set of days, \(d=1,...,D\) in a set of weeks, \(w=1,...,W\) . The patients possess a priority coefficient \(U_q\) utilized in the determination of the sum of weighted waiting times, and delays over all patients. The coefficient is utilized to distinguish between inpatient and emergency patients. The coefficient is used to distinctive between inpatient and emergency patients.
Let \(A_q\) be the release time for the surgery of each patient. Let \(D_q\) due time for the surgery of each patient. \(D_q\) - \(A_q\) be the clinical case for individual patient that will decrease if the patient does not receive his/her surgical services. Conversely, when compared with the elective patients, the emergency patients delays will result in a higher penalty on the objective function. Thus,the advance emergency patients arrival predication be , \(q\in P \cup I\)
The operating room planning and scheduling notations are presented by [ 82 ] as the following: P is the elective patients index, \((p=1,...,P)\) P is represent the number of the elective patients. i represented the non-elective patients \((i=1,...,I)\) where I is elective patients number. q indicate to the elective and non elective patients \((q=1,...,Q)\) where \(Q(=P+1)\) is the total number of patients. r refers to operating rooms \((r=1,...,R)\) , R R is the operating rooms number. b indicates the blocks \((b=1,...,B)\) , B is the total operating rooms blocks. s surgeon indicator \((s=1,...,S)\) , and S is the number of surgeons. e refer to expertise \((e=1,...,E)\) ,. E is the number of expertise d denotes the number of days in a week \((d=1,...,D)\) , D is the number of days. w number of weeks \((w=1,...,W)\) , W denotes the number of weeks.
\(C_{bdw}\) block ( b ) capacity in day ( d ) in a week ( w ). \(Y_{bdw}\) parameter occupation of block ( b ). \(\bar{t}_{q}\) surgery duration expectation for the patient q . \(A_{q}\) releasing time for the patient q surgery. \(D_{q}\) a sufficient time for patient q surgery. \(U_{q}\) clinical priority factor of patient. \(m_{j}\) in the objective function the weight term j \((j=1,...,7)\) . \(B^{E}_{edw}\) a number of blocks that are assigned to expertise e in day d in week w . \(E^{Q}_{q}\) expertise which patient q needs \((E^{Q}_{q}=1,...,E)\) . \(B^{R}_{rdw}\) is a group of blocks that are assigned to room r in day d in a week w . \(S^{p}_{p}\) denotes the surgeon assigned to operate patient p \((S^{p}_{p}=1,...,S)\) . \(B^{Q}_{qdw}\) is set of blocks that the patient undergo surgery in day d in week w . \(O^{max}_{b}\) overtime permitted by each block. \(O^{max}_{r}\) overtime permitted by each operating room. \(N^{max}_{s}\) The total number of surgeries allowed in that day by a surgeon. \(D_{dw}\) is calculated by \(D*(w-1)+d\) ,total number of waiting days by patient during the planning horizon \((D*W)\) . Decision variables: \(X_qbdw\) \(=1\) if the patient q is scheduled undergo surgery in block b in day d in week w ;0 otherwise. \(O_{bdw}\) is the amount of overtime of block b in day d in week w . \(n_{sdw}\) \(=1\) if the surgeon s is scheduled for surgery in day d in week w ;0 otherwise. The mathematical formulation for operating room scheduling using deterministic approaches is generated according to the mean value of surgery duration as follow:
Subject to:
4.6 Operating room scheduling data sets
Operating room scheduling problems have been studied by various researchers and tested based on different data sets up on their countries hospital. To the best of our knowledge, no commonly utilized test sets were identified for other healthcare scheduling issues, such as the issue of surgical scheduling. In this review, we have presented a data set which has been introduced by [ 83 ], which involved (20,880) instances with small family subset instances which involved (146) instances. This data set was generated based on real life data from Dutch hospitals (11 surgical specialties), the experimental design for real-life instance generation shown in Table 11 . Whilst, Table 12 presents the statics outcomes, and the experiment design for the generation of theoretical instances shown in Table 13 https://www.utwente.nl/en/choir/research/BenchmarkORScheduling/introduction .
4.7 Operating room scheduling in optimization
The literature in scheduling operating room has a wide range of methodologies that fit with optimization domain. Various heurstics and metaheurtics has been applied to tackle operating room scheduling problem. In this context, constructed a weekly operating theater surgery scheduling using open scheduling strategy has been proposed by [ 1 ]. The objectives of this work is in the maximization of the operating rooms usage, and the minimization of the operating theatre overtime expenditure, in addition to the minimization of the unanticipated idle time among surgical patients. The solution procedure in this work is distinguished into two phases, the first phase involves the assignment of a specific date for surgeon to each patient, and that the surgeons are free to assign his case in the time block. Next, the daily scheduling is determined in order to fix the operation sequence and takes into consideration the recovery beds that are available. The proposed method is characterized by a set-partitioning integer-programming model, and where the solution is arrived through a column-generation-based heuristic process. The second phase which entails the daily scheduling problem is outlined as a two-staged hybrid flow-shop model, that is resolved by a hybrid genetic algorithm, utilizing a Tabu search procedure for executing local search. A evaluation of the proposed method has been done with different actual surgery schedules based on Belgian university hospital data. The results showed lesser idle time between the surgical cases as derived from the surgery schedules, in addition to the greater operating rooms usage, with minimal overtime. Furthermore [ 84 ] proposed a novel two-stage stochastic mixed-integer programming model to solve surgery schedules across multiple operating room under uncertainty has been developed by [ 84 ]. The main idea in this paper observes the enablement of numerous operations to be completed simultaneously, because of the availed presence of various operating room, aid and support from other surgeons, especially from the principal staff surgeon. It described the benefit behind the sharing of resources among the surgeons. The summaries of all optimization algorithm and data sets with categorize is illustrated in (Table 14 )
4.7.1 Surgery scheduling problem in optimization
Surgical scheduling problem was resolved using different optimization method. Some of those researchers used deterministic models, whereas others used stochastic method. In the optimization field, there are several researchers who applied different techniques to solve this problem. In recent years [ 104 ] solved the surgical scheduling procedures by applying a discrete event simulation model in the first stage, that evaluated the 12 varying sequencing and patient appointment time-setting, including expected patient waiting time, in addition to the expected surgical suite overtime as per day. In the second stage, a bi-criteria genetic algorithm (GA) was utilized to evaluate whether there are more superior solutions can be obtained for the single-day scheduling problem. Moreover, the efficiency of the bi-criteria genetic algorithm in the event of a the surgery date change was investigated. In addition, [ 105 ] considered the application of operational surgery scheduling problems at a medium sized Norwegian hospital. In the study, the execution of the scheduling planning for day scheduling, with the weekly scheduling and admission planning was discussed. The proposed method used a generalized model for surgery scheduling problems. The equalization of computational loads between a construction and an enhancement method was achieved through the implementation of a parented model solution using an on-line learning. The result of this algorithm showed an excellent performance traversing various problem categories. In the same context, [ 85 ] has been proposed two exact and metaheurstic method to scheduling surgery in operating room integrated with post-anesthesia recovery beds. Table 3 presents the surgery scheduling problem and the respective methods employed and patients categories.
4.8 Discussion
Operating rooms are an important and expensive sector in the most hospitals [ 70 ]. Thus, various studies have been conducted on scheduling and planning of the operating room under operational, tactical [ 119 ], strategic levels, which concerned as a decision level for operating rooms.
Various solution procedures have been utilized to tackle this problem, heuristic and metaheuristic methods have been intensified in the literature in the context of optimization. Due to the high constraints problem could not be solved using the exact method. The uncertainty in scheduling techniques are the most difficult task, and they are more concrete, since, the uncertainty in time frame is the most interesting topic. Operating room scheduling integrated with other healthcare services such as patient [ 13 ] scheduling, nurse [ 120 ] is limited. However, the integration between an operating room with other systems in the hospital will enhance the hospital performance and will lead to improving the hospitalization services (Table 14 ) summaries recent methods, versions and categories. Moreover, most studies have pay particular attention to elective patients than on, non-elective patients. Urgent patients and emergency patients get less attention (Table 15 ). Furthermore, surgery scheduling problem involved three forms of scheduling [ 121 ], first the surgeon is assigned by hospital administration, then the surgeon is assigned to time block, and finally the last minute adjustment (if required). Surgery scheduling problem has been addressed by various approaches and considered elective/uncertain patients. Tackling elective and emergency patients in surgery scheduling is limited. Several articles consider the problem separately, while others have used integrated models [ 122 ]. Most studies have focused on surgery scheduling integrated with other healthcare scheduling such as with operating room [ 108 ], patient scheduling [ 116 ], physician scheduling [ 77 ]. The integrating between surgery scheduling with different healthcare problem could provide high-quality services, and minimizing overtime cost. Developing multi decision healthcare scheduling system which combines between surgery scheduling, operating room planning, and physician scheduling is better to address a real-life situation and balancing hospital resource utilization.
5 Other healthcare scheduling and planning problems
In healthcare scheduling problems many problems receive less attention by researchers, in this section will surveyed and give an overview of other healthcare scheduling such as scheduling physicians [ 123 , 124 , 125 ], home healthcare [ 126 , 127 , 128 ], telemedicine scheduling [ 129 ]. Physician scheduling is a real-world problem which arises in hospitals, physician scheduling is a type of staff schedules with more complex regulation. Physician scheduling is defined as assigning a physician to duty such as surgeries, clinics, scopes, calls, administration and others over time slots /shifts according to planning horizons with different types of preferences and constraints [ 125 ]. Physician scheduling problem have two roster planning cyclic/ad-hoc which refer to planning period must be reconstructed because physicians may have different work rosters each week. Where as cyclic planning refer to set models for doctors, with or without weekly rotation. Planning and scheduling in physician problem has been arouse in a three decision level (strategic, tactical and operational planning). However, physician scheduling is represented by day-to-day scheduling, in which the physician is given various duties [ 77 ]. Scheduling physician problems have been studied by different researchers such as [ 125 ] who proposed a mathematical programming models to solve a master physician scheduling problem. In addition [ 123 ] and [ 130 ] had proposed a mix integer linear programming for solving this problem. In addition [ 131 ] studied the scheduling of physicians in the pediatric intensive care unit (PICU) too. On the other hand [ 77 ] integrated physicians and surgery scheduling for the purpose of solving operating room scheduling problems by using mix integer linear programming. Furthermore, [ 132 ] had described physician problems in a case study, in Swedish public hospitals. Moreover [ 133 ] had presented the problem from the perspectives of US hospitals. The author have studied different types of physician scheduling using different priorities. Besides that, [ 134 ] had studied the problem by using a case hospital from the King Khalid University a Hospital in the Kingdom of Saudi Arabia. Home healthcare scheduling another healthcare complex optimization problem which has been grown in various decision levels, such as assigning staff or scheduling shifts [ 135 ]. For instance, various sets of nurses could be allocated to different clients which are located in diverse areas. Therefore, various constraints, requirements, and preference should be considered, such as nurse expertise, clients requirements, and nurse working time. However, balancing the expertise of nurses and customers is a standard function of home healthcare scheduling optimization and the selection of skills considered varies based on the needs of the client and the particular regulatory environment. The major solution method of home healthcare scheduling has been done using metaheurstic algorithm [ 136 , 137 ]. Recently the field of telemedicine has attracted a multitude of researchers because it provides a new platform for patients to access the healthcare services. It provides medical care for patients in distant remote areas such as villages that need outreach services.
6 Conclusion and future work
In this survey paper, we address healthcare scheduling problem as an optimization problem. Scheduling in healthcare is segregated into two types; personnel and resources. This review on healthcare scheduling has identified the areas of healthcare scheduling such as patient admission scheduling, nurse rostering problem, operating room scheduling problem and other healthcare scheduling problem. The objective of all scheduling systems in optimization aspect is to reduce the cost and patient’s waiting time and maximize the resources efficiency. The quality of the solution is dependent upon the cost function which is involved in the summation of the soft constraints. In addition, this review summarized all scheduling systems on healthcare, and are supported by most successful algorithms, which have used a diverse spectrum of search methodologies. We noticed that several latest sophisticated systems obtained significant results. Furthermore, the metaheuristics algorithms involved in the local search methods and population-based method, have been highlighted in this paper. However, the major successful algorithms are from nature-inspired algorithms, which proved their ability to solve N/P hard problem. This is due to their ability to explore the search space, especially swarm-based algorithms. The challenges for future research direction are to:
Utilized other metaheuristic algorithms such as a swarm-based algorithm for solving healthcare scheduling problems in order to obtain better results.
Study and analysed the robustness of each algorithm that has been applied to each problem.
Build a scheduling system for the hospital, which covers the entire hospital dynamically.
Focusing on particular real-world problems on healthcare such as telemedicine which will help during a disaster such as COVID 19 pandemic.
We can also be adapting big data analytic methods in order to get real data sets for different scheduling systems, by focusing on the most complex situations such as COVID 19 pandemic and get historical data for a number of patients and nurse shift as well as physician scheduling, to come up with new data sets regarding those problems.
Most studies focus on the elective patients more than other patients type, further research direction could be on scheduling triage, emergency, urgent patients could be an interesting topic if it is integrated with other scheduling techniques problems such as physician scheduling and nurse scheduling.
Integrated scheduling system which involved patients, nurse, physician, and operating rooms could improve the service quality for the medical system.
https://people.cs.kuleuven.be/wim.vancroonenburg/pas/
Fei H, Meskens N, Chu C. A planning and scheduling problem for an operating theatre using an open scheduling strategy. Comp Industrial Eng. 2010;58(2):221–30.
Article Google Scholar
Rais A, Viana A. Operations research in healthcare: a survey. Int Trans Operation Res. 2011;18(1):1–31.
Article MathSciNet Google Scholar
Batun S, Begen MA. Optimization in healthcare delivery modeling: Methods and applications. In Handbook of Healthcare Operations Management, pages 75–119. Springer, 2013.
Oueida S. Modeling a New Computer Framework for Managing Healthcare Organizations: Balancing and Optimizing Patient Satisfaction, Owner Satisfaction, and Medical Resources. CRC Press; 2020.
Hall RW, et al. Handbook of healthcare system scheduling. Springer; 2012.
Gupta D, Denton B. Appointment scheduling in health care: Challenges and opportunities. IIE transactions. 2008;40(9):800–19.
Rinder MM, Weckman G, Schwerha D, Snow A, Dreher PA, Park N, Paschold H, and Young W. Healthcare scheduling by data mining: Literature review and future directions. J Healthcare Eng, 3, 2012.
Marynissen J, Demeulemeester E. Literature review on integrated hospital scheduling problems. KU Leuven, Faculty of Economics and Business, KBI_1627, 2016.
Van den Bergh J, Beliën J, De Bruecker P, Demeulemeester E, De Boeck L. Personnel scheduling: A literature review. Euro J Oper Res. 2013;226(3):367–85.
Article MathSciNet MATH Google Scholar
Rahimi I, and Gandomi AH. A comprehensive review and analysis of operating room and surgery scheduling. Arch Comp Methods in Eng. 2020.
Zhu S, Fan W, Yang S, Pei J, Pardalos PM. Operating room planning and surgical case scheduling: a review of literature. J Combi Opt. 2019;37(3):757–805.
Ahmadi-Javid A, Jalali Z, Klassen KJ. Outpatient appointment systems in healthcare: A review of optimization studies. Euro J Oper Res. 2017;258(1):3–34.
Ceschia S, Schaerf A. Modeling and solving the dynamic patient admission scheduling problem under uncertainty. Artif Intell Med. 2012;56(3):199–205.
Lusby RM, Schwierz M, Range TM, Larsen J. An adaptive large neighborhood search procedure applied to the dynamic patient admission scheduling problem. Artif Intell Med. 2016;74:21–31.
Bilgin B, Demeester P, Misir M, Vancroonenburg W, Berghe GV. One hyper-heuristic approach to two timetabling problems in health care. J Heuristics. 2012;18(3):401–34.
Demeester P, de Causmaecker P, and Vanden Berghe G. Applying a local search algorithm to automatically assign patients to beds. In Proceedings of the 22nd conference on quantitative methods for decision making (Orbel 22), pages 35–36, 2008.
Demeester P, Souffriau W, De Causmaecker P, Berghe GV. A hybrid tabu search algorithm for automatically assigning patients to beds. Artif Intell Med. 2010;48(1):61–70.
Ceschia S, Schaerf A. Dynamic patient admission scheduling with operating room constraints, flexible horizons, and patient delays. J Sched. 2016;19(4):377–89.
Sigurpalsson AO, Runarsson TP, and Saemundsson RJ. Stochastic master surgical scheduling under ward uncertainty. In International Conference on Human-Centred Software Engineering, pages 163–176. Springer, 2019.
Ceschia S, Schaerf A. Local search and lower bounds for the patient admission scheduling problem. Comp Operations Res. 2011;38(10):1452–63.
Vancroonenburg W, de Causmaecker P, and Vanden Berghe G. Patient-to-room assignment planning in a dynamic context. In Proceedings of the 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT-2012), pages 193–208. Citeseer, 2012.
Granja C, Almada-Lobo B, Janela F, Seabra J, Mendes A. An optimization based on simulation approach to the patient admission scheduling problem using a linear programing algorithm. J Biomed info. 2014;52:427–37.
Hammouri AI, and Alrifai B. Investigating biogeography-based optimisation for patient admission scheduling problems. J Theo Appl Info Tech. 70(3), 2014.
Range TM, Lusby RM, Larsen J. A column generation approach for solving the patient admission scheduling problem. Euro J Oper Res. 2014;235(1):252–64.
Article MATH Google Scholar
Kifah S, Abdullah S. An adaptive non-linear great deluge algorithm for the patient-admission problem. Info Sci. 2015;295:573–85.
Vancroonenburg W, De Causmaecker P, Berghe GV. A study of decision support models for online patient-to-room assignment planning. Ann Oper Res. 2016;239(1):253–71.
Turhan AM, Bilgen B. Mixed integer programming based heuristics for the patient admission scheduling problem. Comp Oper Res. 2017;80:38–49.
Guido R, Solina V, Mirabelli G, and Conforti D. Offline patient admission, room and surgery scheduling problems. In New Trends in Emerging Complex Real Life Problems, pages 275–283. Springer, 2018.
Guido R, Groccia MC, Conforti D. An efficient matheuristic for offline patient-to-bed assignment problems. Euro J Oper Res. 2018.
Bolaji AL, Bamigbola AF, Shola PB. Late acceptance hill climbing algorithm for solving patient admission scheduling problem. Knowledge-Based Systems. 2018;145:197–206.
Doush IA, Al-Betar MA, Awadallah MA, Hammouri AI, Raed M, ElMustafa S, and ALkhraisat H. Harmony search algorithm for patient admission scheduling problem. J Intel Sys, 2018;29(1):540–553.
Bastos LS, Marchesi JF, Hamacher S, Fleck JL. A mixed integer programming approach to the patient admission scheduling problem. Euro J Operational Res. 2019;273(3):831–40.
Hammouri AI. A modified biogeography-based optimization algorithm with guided bed selection mechanism for patient admission scheduling problems. J King Saud Univ-Comp Info Sci, 2020.
Zhu YH, Toffolo TA, Vancroonenburg W, Berghe GV. Compatibility of short and long term objectives for dynamic patient admission scheduling. Comp Operations Res. 2019;104:98–112.
Diamant A, Milner J, Quereshy F. Dynamic patient scheduling for multi-appointment health care programs. Prod Operations Manage. 2018;27(1):58–79.
Zhu S, Fan W, Liu T, Yang S, Pardalos PM. Dynamic three-stage operating room scheduling considering patient waiting time and surgical overtime costs. J Combinatorial Opt. 2020;39(1):185–215.
Ernst AT, Jiang H, Krishnamoorthy M, Sier D. Staff scheduling and rostering: A review of applications, methods and models. Euro J Operational Res. 2004;153(1):3–27.
Burke EK, De Causmaecker P, Berghe GV, Van Landeghem H. The state of the art of nurse rostering. J Sched. 2004;7(6):441–99.
Awadallah MA, Khader AT, Al-Betar MA, Bolaji AL. Global best harmony search with a new pitch adjustment designed for nurse rostering. J King Saud Univ Comp Info Sci. 2013;25(2):145–62.
Google Scholar
F. Della Croce and F. Salassa. A variable neighborhood search based matheuristic for nurse rostering problems. Ann Oper Res. 218(1):185–199, 2014.
Haspeslagh S, De Causmaecker P, Schaerf A, Stølevik M. The first international nurse rostering competition 2010. Ann Oper Res. 2014;218(1):221–36.
McCollum B, Schaerf A, Paechter B, McMullan P, Lewis R, Parkes AJ, Gaspero LD, Qu R, Burke EK. Setting the research agenda in automated timetabling: The second international timetabling competition. Info J Comp. 2010;22(1):120–30.
Pillay N, and Qu R. Nurse rostering problems. In Hyper-Heuristics: Theory and Applications, 2018;61–66. Springer.
Smet P. Nurse rostering: models and algorithms for theory, practice and integration with other problems. 2015.
Rajeswari M, Amudhavel J, Pothula S, Dhavachelvan P. Directed bee colony optimization algorithm to solve the nurse rostering problem. Comp Intell Neurosci. 2017;2017:
Awadallah MA, Al-Betar MA, Khader AT, Bolaji AL, Alkoffash M. Hybridization of harmony search with hill climbing for highly constrained nurse rostering problem. Neural Comp Appl. 2017;28(3):463–82.
Awadallah MA, Bolaji AL, Al-Betar MA. A hybrid artificial bee colony for a nurse rostering problem. Appl Soft Comp. 2015;35:726–39.
Santos HG, Toffolo TA, Gomes RA, Ribas S. Integer programming techniques for the nurse rostering problem. Ann Oper Res. 2016;239(1):225–51.
Dang NTT, Ceschia S, Schaerf A, de Causmaecker P, and Haspeslagh S. Solving the multi-stage nurse rostering problem. In Proceedings of the 11th international conference of the practice and theory of automated timetabling. 2016;473–475.
Mischek F, and Musliu N. Integer programming model extensions for a multi-stage nurse rostering problem. Ann Oper Res. 2017;1–21.
Legrain A, Omer J, and Rosat S. A rotation-based branch-and-price approach for the nurse scheduling problem. Math Prog Comp. 2019;1–34.
Ceschia S, Guido R, and Schaerf A. Solving the static inrc-ii nurse rostering problem by simulated annealing based on large neighborhoods. Ann Oper Res. 2020;1–19.
Chen PS, and Zeng ZY. Developing two heuristic algorithms with metaheuristic algorithms to improve solutions of optimization problems with soft and hard constraints: An application to nurse rostering problems. Appl Soft Comp. 2020;106336.
Turhan AM, and Bilgen B. A hybrid fix-and-optimize and simulated annealing approaches for nurse rostering problem. Comp Industrial Eng. 2020;106531.
Yabing N, Bing W, and Xingbao H. An adaptive method with local search for nurse rostering problem. In 2015 34th Chinese Control Conference (CCC). 2015;2726–2731. IEEE.
Strandmark P, Qu Y, and Curtois T. First-order linear programming in a column generation based heuristic approach to the nurse rostering problem. Comp Opera Res. 2020;104945.
Hadwan M, Ayob M, Rassam MA, and Hezam EA. Deluge harmony search algorithm for nurse rostering problems. In 2019 First International Conference of Intell Comp Eng (ICOICE). 2019;1–5. IEEE.
Vu SN, Nguyen MHN, Duc LM, Baril C, Gascon V, Dinh TB. Iterated local search in nurse rostering problem. In Proceedings of the Fourth Symposium on Info Com Tech. 2013;71–80.
Zhuo X, Huang H, Cai Z, and Hu H. An hybrid evolutionary algorithm with scout bee global search strategy for chinese nurse rostering problems. In 2015 IEEE Congress on Evolutionary Computation (CEC). 2015;769–775. IEEE.
Arajy YZ, Abdullah S, Kifah S. Non-liner great deluge algorithm for handling nurse rostering problem. Int J Appl Eng Res. 2017;12(15):4959–66.
Hadwan M, Ayob M, Al-Hagery M, and Al-Tamimi BN. Climbing harmony search algorithm for nurse rostering problems. In International Conference of Reliable Information and Communication Technology. 2018;74–83. Springer.
Ramli R, Abd Rahman R, Rohim N. A hybrid ant colony optimization algorithm for solving a highly constrained nurse rostering problem. J Info Comm Tech. 2019;18(3):305–326.
Nie T, Wang B, and Zhang X. Hybrid harmony search algorithm for nurse rostering problem. In Harmony Search Algorithm. 2016;109–120. Springer.
Awadallah MA, Khader AT, Al-Betar MA, and Bolaji AL. Hybrid harmony search for nurse rostering problems. In 2013 IEEE Symposium on Computational Intelligence in Scheduling (CISched), 2013;60–67. IEEE.
Abobaker RA, Ayob M, and Hadwan M. Greedy constructive heuristic and local search algorithm for solving nurse rostering problems. In 2011 3rd Conference on Data Mining and Optimization (DMO). 2011;194–198. IEEE.
Yin PY, Chiang YT. Cyber swarm algorithms for multi-objective nurse rostering problem. Int J Innovative Comp, Info Control. 2013;9(5):2043–63.
Rae C, and Pillay N. Investigation into an evolutionary algorithm hyperheuristic for the nurse rostering problem. In Proceedings of the 10th International Conference on the Practice and Theory of Automated, PATAT, pages 527–532, 2014.
Wu JJ, Lin Y, Zhan ZH, Chen WN, Lin TB, and Chen JY. An ant colony optimization approach for nurse rostering problem. In 2013 IEEE International Conference on Systems, Man, and Cybernetics, pages 1672–1676. IEEE, 2013.
Jin SH, Yun HY, Jeong SJ, Kim KS. Hybrid and cooperative strategies using harmony search and artificial immune systems for solving the nurse rostering problem. Sustainability. 2017;9(7):1090.
Pariente JMM. Operating theatre planning and scheduling in real-life settings: Problem analysis, models, and solution procedures. PhD thesis, Universidad de Sevilla, 2016.
Guerriero F, Guido R. Operational research in the management of the operating theatre: a survey. Health care management science. 2011;14(1):89–114.
Cardoen B, Demeulemeester E, Beliën J. Operating room planning and scheduling: A literature review. Euro J Oper Res. 2010;201(3):921–32.
Denton B, Viapiano J, Vogl A. Optimization of surgery sequencing and scheduling decisions under uncertainty. Health care management science. 2007;10(1):13–24.
Levine WC, Dunn PF. Optimizing operating room scheduling. Anesthesiology clinics. 2015;33(4):697–711.
Romanyuk A, Silva A. Optimization of an operating room surgical schedule. Louis: Ese. wustl. edu. Washingon University in St; 2012.
Xiang W, Yin J, Lim G. An ant colony optimization approach for solving an operating room surgery scheduling problem. Comp Industrial Eng. 2015;85:335–45.
Van Huele C, Vanhoucke M. Analysis of the integration of the physician rostering problem and the surgery scheduling problem. J Med Sys. 2014;38(6):43.
Roland B, Di Martinelly C, Riane F, Pochet Y. Scheduling an operating theatre under human resource constraints. Comp Industrial Eng. 2010;58(2):212–20.
Magerlein JM, Martin JB. Surgical demand scheduling: a review. Health services research. 1978;13(4):418.
Samudra M, Van Riet C, Demeulemeester E, Cardoen B, Vansteenkiste N, Rademakers FE. Scheduling operating rooms: achievements, challenges and pitfalls. J Sched. 2016;19(5):493–525.
Addis B, Carello G, Grosso A, Tànfani E. Operating room scheduling and rescheduling: a rolling horizon approach. Flexible Services and Manufacturing Journal. 2016;28(1–2):206–32.
Kamran MA, Karimi B, Dellaert N. Uncertainty in advance scheduling problem in operating room planning. Comp Industrial Eng. 2018;126:252–68.
Leeftink G, Hans EW. Case mix classification and a benchmark set for surgery scheduling. J Sched. 2018;21(1):17–33.
Batun S, Denton BT, Huschka TR, Schaefer AJ. Operating room pooling and parallel surgery processing under uncertainty. Info J Comp. 2011;23(2):220–37.
Latorre-Núñez G, Lüer-Villagra A, Marianov V, Obreque C, Ramis F, Neriz L. Scheduling operating rooms with consideration of all resources, post anesthesia beds and emergency surgeries. Comp Industrial Eng. 2016;97:248–57.
Molina-Pariente JM, Hans EW, Framinan JM. A stochastic approach for solving the operating room scheduling problem. Flex Serv Manu J. 2018;30(1–2):224–51.
Kroer LR, Foverskov K, Vilhelmsen C, Hansen AS, Larsen J. Planning and scheduling operating rooms for elective and emergency surgeries with uncertain duration. Oper Res Healthcare. 2018;19:107–19.
Xiang W. A multi-objective aco for operating room scheduling optimization. Nat Comp. 2017;16(4):607–17.
Lee S, and Yih Y. Surgery scheduling of multiple operating rooms under uncertainty and resource constraints of post-anesthesia care units. In IIE Annual Conference. Proceedings, page 1. Institute of Industrial and Systems Engineers (IISE), 2012.
Ansarifar J, Tavakkoli-Moghaddam R, Akhavizadegan F, and Amin SH. Multi-objective integrated planning and scheduling model for operating rooms under uncertainty. Proceedings of the Institution of Mechanical Engineers, Part H: J Eng Med, 232(9):930–948, 2018.
Akbarzadeh B, Moslehi G, Reisi-Nafchi M, Maenhout B. A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering. J Sched, pages 1–24, 2020.
Varmazyar M, Akhavan-Tabatabaei R, Salmasi N, Modarres M. Operating room scheduling problem under uncertainty: Application of continuous phase-type distributions. IISE Transactions. 2020;52(2):216–35.
Akbarzadeh B, Moslehi G, Reisi-Nafchi M, Maenhout B. The re-planning and scheduling of surgical cases in the operating room department after block release time with resource rescheduling. Euro J Oper Res. 2019;278(2):596–614.
Ali HH, Lamsali H, Othman SN. Operating rooms scheduling for elective surgeries in a hospital affected by war-related incidents. J Med Sys. 2019;43(5):139.
D. Clavel, D. Botez, C. Mahulea, and J. Albareda. Software tool for operating room scheduling in a spanish hospital department. In 2018 22nd International Conference on System Theory, Control and Computing (ICSTCC), pages 413–420. IEEE, 2018.
Belkhamsa M, Jarboui B, Masmoudi M. Two metaheuristics for solving no-wait operating room surgery scheduling problem under various resource constraints. Comp Ind Eng. 2018;126:494–506.
Timuçin T, and Biroğul S. Effect the number of reservations on implementation of operating room scheduling with genetic algorithm. In The International Conference on Artificial Intelligence and Applied Mathematics in Engineering. 2019;252–265. Springer.
Khaniyev T, Kayiş E, Güllü R. Next-day operating room scheduling with uncertain surgery durations: Exact analysis and heuristics. Euro J Oper Res. 2020.
Lin TK, and Chou YY. A hybrid genetic algorithm for operating room scheduling. Health Care Management Science, pages 1–15, 2019.
Timucin T, and Birogul S. Implementation of operating room scheduling with genetic algorithm and the importance of repair operator. In 2018 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), pages 1–6. IEEE, 2018.
Aringhieri R, Landa P, Soriano P, Tànfani E, Testi A. A two level metaheuristic for the operating room scheduling and assignment problem. Comp Oper Res. 2015;54:21–34.
L. I. Almaneea and M. I. Hosny. A two level hybrid bees algorithm for operating room scheduling problem. In Science and Information Conference, pages 272–290. Springer, 2018.
Mateus C, Marques I, Captivo ME. Local search heuristics for a surgical case assignment problem. Oper Res Healthcare. 2018;17:71–81.
Gul S, Denton BT, Fowler JW, Huschka T. Bi-criteria scheduling of surgical services for an outpatient procedure center. Prod Oper Manage. 2011;20(3):406–17.
Riise A, Mannino C, Burke EK. Modelling and solving generalised operational surgery scheduling problems. Comp Oper Res. 2016;66:1–11.
Bruni M, Beraldi P, Conforti D. A stochastic programming approach for operating theatre scheduling under uncertainty. IMA J Manage Math. 2015;26(1):99–119.
Chaabane S, Meskens N, Guinet A, Laurent M. Comparison of two methods of operating theatre planning: application in belgian hospital. J Sys Sci Sys Eng. 2008;17(2):171–86.
Denton BT, Miller AJ, Balasubramanian HJ, and Huschka TR. Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper Res. 58(4-part-1):802–816, 2010.
Fei H, Chu C, Meskens N, Artiba A. Solving surgical cases assignment problem by a branch-and-price approach. Int J Prod Eco. 2008;112(1):96–108.
Fügener A, Hans EW, Kolisch R, Kortbeek N, Vanberkel PT. Master surgery scheduling with consideration of multiple downstream units. Euro J Oper Res. 2014;239(1):227–36.
Hans E, Wullink G, Van Houdenhoven M, Kazemier G. Robust surgery loading. Euro J Oper Res. 2008;185(3):1038–50.
Herring WL, Herrmann JW. The single-day surgery scheduling problem: sequential decision-making and threshold-based heuristics. OR spectrum. 2012;34(2):429–59.
Mannino C, Nilssen EJ, Nordlander TE. A pattern based, robust approach to cyclic master surgery scheduling. J Sched. 2012;15(5):553–63.
Marques I, Captivo ME, Pato MV. An integer programming approach to elective surgery scheduling. OR spectrum. 2012;34(2):407–27.
Min D, Yih Y. An elective surgery scheduling problem considering patient priority. Comp Oper Res. 2010;37(6):1091–9.
Saremi A, Jula P, ElMekkawy T, Wang GG. Appointment scheduling of outpatient surgical services in a multistage operating room department. Int J Prod Eco. 2013;141(2):646–58.
Zhang Z, Xie X. Simulation-based optimization for surgery appointment scheduling of multiple operating rooms. IIE Transactions. 2015;47(9):998–1012.
Bai M, Storer RH, Tonkay GL. A sample gradient-based algorithm for a multiple-or and pacu surgery scheduling problem. IISE Transactions. 2017;49(4):367–80.
Siqueira CL, Arruda EF, Bahiense L, Bahr GL, Motta GR. Long-term integrated surgery room optimization and recovery ward planning, with a case study in the brazilian national institute of traumatology and orthopedics (into). Euro J Oper Res. 2018;264(3):870–83.
Di Martinelly C, Baptiste P, Maknoon M. An assessment of the integration of nurse timetable changes with operating room planning and scheduling. Int J Prod Res. 2014;52(24):7239–50.
May JH, Spangler WE, Strum DP, Vargas LG. The surgical scheduling problem: Current research and future opportunities. Prod Oper Manage. 2011;20(3):392–405.
Molina-Pariente JM, Fernandez-Viagas V, Framinan JM. Integrated operating room planning and scheduling problem with assistant surgeon dependent surgery durations. Comp Industrial Eng. 2015;82:8–20.
Bruni R, Detti P. A flexible discrete optimization approach to the physician scheduling problem. Oper Res Healthcare. 2014;3(4):191–9.
M. Gendreau, J. Ferland, B. Gendron, N. Hail, B. Jaumard, S. Lapierre, G. Pesant, and P. Soriano. Physician scheduling in emergency rooms. In International Conference on the Practice and Theory of Automated Timetabling, pages 53–66. Springer, 2006.
Gunawan A, Lau HC. Master physician scheduling problem. J Oper Res Soc. 2013;64(3):410–25.
Demirbilek M, Branke J, Strauss A. Dynamically accepting and scheduling patients for home healthcare. Health care management science. 2019;22(1):140–55.
Demirbilek M, Branke J, and Strauss AK. Home healthcare routing and scheduling of multiple nurses in a dynamic environment. Flex Services Manu J. 2019;1–28.
Restrepo MI, Rousseau LM, and Vallée J. Home healthcare integrated staffing and scheduling. Omega. 2019;102057.
Erdogan SA, Krupski TL, Lobo JM. Optimization of telemedicine appointments in rural areas. Service Science. 2018;10(3):261–76.
Gross CN, Fügener A, and Brunner JO. Online rescheduling of physicians in hospitals. Flex Services Manu J. 2017;1–33.
Smalley HK, Keskinocak P, Vats A. Physician scheduling for continuity: an application in pediatric intensive care. Interfaces. 2015;45(2):133–48.
António Ferreira Rodrigues Nogueira dos Santos M, and Kurt Olof Eriksson H. Insights into physician scheduling: a case study of public hospital departments in sweden. International journal of health care quality assurance. 2014;27(2):76–90.
Damcı-Kurt P, Zhang M, Marentay B, Govind N. Improving physician schedules by leveraging equalization: Cases from hospitals in us. Omega. 2018.
Gharbi A, Louly M, and Azaiez M. Physician scheduling using goal programming-an application to a large hospital in saudi arabia. In Control, Decision and Information Technologies (CoDIT), 2017 4th International Conference on. 2017;0922–0925. IEEE.
Fikar C, Hirsch P. Home health care routing and scheduling: A review. Comp Oper Res. 2017;77:86–95.
Allaoua H, Borne S, Létocart L, Calvo RW. A matheuristic approach for solving a home health care problem. Electronic Notes in Discrete Mathematics. 2013;41:471–8.
Bennett AR, Erera AL. Dynamic periodic fixed appointment scheduling for home health. IIE Trans Healthcare Sys Eng. 2011;1(1):6–19.
Download references
Author information
Authors and affiliations.
Faculty of engineering technology /Department of Computer Engineering, University Malaysia Perlis, Kanger, 02600, Arau, Perlis, Malaysia
Zahraa A. Abdalkareem, Amiza Amir & Phaklen Ekhan
Artificial Intelligence Research Center (AIRC) College of Engineering and Information Technology , Ajman University , Ajman, UAE
Mohammed Azmi Al-Betar
Department of Information Technology, Al-Huson University College Al-Balqa Applied University, P.O. Box 50, Al-Huson, Irbid, Jordan
Department of Computer Information Systems , Al-Balqa Applied University , 19117, Al- Salt, Jordan
Abdelaziz I. Hammouri
Department of Islamic English studies , Alimam Aladham university college , Baghdad, Iraq
Zahraa A. Abdalkareem
You can also search for this author in PubMed Google Scholar
Corresponding authors
Correspondence to Zahraa A. Abdalkareem , Mohammed Azmi Al-Betar or Abdelaziz I. Hammouri .
Ethics declarations
Conflict of interest.
The authors declare that they have no conflict of interest.
Rights and permissions
Reprints and Permissions
About this article
Cite this article.
Abdalkareem, Z.A., Amir, A., Al-Betar, M.A. et al. Healthcare scheduling in optimization context: a review. Health Technol. 11 , 445–469 (2021). https://doi.org/10.1007/s12553-021-00547-5
Download citation
Received : 18 November 2020
Accepted : 05 April 2021
Published : 10 April 2021
Issue Date : May 2021
DOI : https://doi.org/10.1007/s12553-021-00547-5
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Metaheurstic
- Meta-heurstics
- Nurse scheduling
- Patient admission scheduling
- Patient to bed assignment
- Operating room scheduling
- Operating theater
- Surgery scheduling
- Surgical scheduling
- Physician scheduling
- Healthcare scheduling
An official website of the United States government
The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.
The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.
- Publications
- Account settings
- Advanced Search
- Journal List
- Healthcare (Basel)
Solving Operating Room Scheduling Problem Using Artificial Bee Colony Algorithm
Associated data.
The data presented in this study are available on request from the corresponding author. The data are not publicly available due to privacy.
Many healthcare institutions are interested in reducing costs and in maintaining a good quality of care. The operating room department is typically one of the most costly units in a hospital. Hospital managers are always interested in finding effective ways of using operating rooms to minimize operating costs. In this research, we study the operating room scheduling problem. We consider the use of a weekly surgery schedule with an open scheduling strategy that takes into account the availabilities of surgeons and operating rooms. The objective is to minimize the total operating cost while maximizing the utilization of the operating rooms but also minimizing overtime use. A revised mathematical model is proposed that can provide optimal solutions for a surgery size up to 110 surgical cases. Next, two modified heuristics, based on the earliest due date (EDD) and longest processing time (LPT) rules, are proposed to quickly find feasible solutions to the studied problem. Finally, an artificial bee colony (ABC) algorithm that incorporates the initial solutions, a recovery scheme, local search schemes, and an elitism strategy is proposed. The computational results show that, for a surgery size between 40 and 100 surgical cases, the ABC algorithm found optimal solutions to all of the tested problems. For surgery sizes larger than 110 surgical cases, the ABC algorithm performed significantly better than the two proposed heuristics. The computational results indicate that the proposed ABC is promising and capable of solving large problems.
1. Introduction
In most hospitals, the operating room department is both a high-cost and a high-revenue unit. Hospital managers are always seeking methods to devise schedules that maximize the utilization of operating rooms but also minimize the total cost. An open scheduling strategy is applied in some hospitals, i.e., surgeons can choose any workday for their surgeries, and anesthetists and nurses cooperate with the surgeons to maximize efficiency. In this paper, we study an operating room scheduling problem. We consider the use of a weekly surgery schedule with an open scheduling strategy that takes into account the availabilities of surgeons and operating rooms. The objective is to minimize the total operating cost while maximizing the utilization of the operating rooms but also minimizing overtime use.
First, we assigned a set of surgeries Ω to M d operating rooms within the planning horizon ( H ) to minimize the total operating cost. Each surgery has an operating duration t i and a due date D i . If the due date of a surgery falls within the current planning horizon ( D i ≤ H ), it has to be scheduled therein. However, if the due date is later than the planning horizon ( D i > H ), it can either be scheduled in the current planning horizon or postponed to a later date. All surgeries have to be scheduled no later than their due dates ( d i ≤ D i ). Each surgery can only be scheduled at most once over the planning horizon. Once a surgery starts, it has to continue until it is finished. Each surgery is assigned to a specific surgeon in advance. Ω l indicates a set of surgeries that are assigned to surgeon l . Every surgeon has a maximum operating time for day d ( A l d ); overtime is not allowed. We assume that all operating rooms are multifunctional. Each operating room can be used for any of the scheduled surgeries. Anesthesia and nursing staff and equipment are always available when needed. Each operating room k on day d has regular opening hours ( R T k d ) and a maximum permissible overtime ( O T k d ). The hospital manager wants to maximize the utilization of operating rooms. If the total operating time scheduled for operating room k on day t ( f k d ) is less than its regular opening hours, waste cost U C k d = max 0 , R T k d − f k d ∀ k , d is incorporated, thereby discouraging unused time. Overtime-operating cost O C k d = max 0 , f k d − R T k d ∀ k , d is also introduced if the total operating time scheduled for operating room k on day t ( f k d ) exceeds its regular opening hours. We assume that the waste cost equals the amount of unused time while the overtime-operating cost equals the amount of overtime multiplied by a “penalty” value ( α ). The objective is to minimize the total operating cost, i.e., min ∑ d = 1 H ∑ k = 1 m d C k d where C k d = U C k d + α O C k d .
Due to its importance in practice, more and more researchers have focused their attention on the operating room scheduling problem in recent years [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 ]. Some researchers have attempted to assign surgeries to operating rooms to maximize the efficiency of operating room utilization and to minimize idle time and overtime costs [ 1 , 2 ]. However, in practice, before surgery, patients are usually treated by a specific surgeon who performed the diagnosis and provided consultation. Hence, surgery is typically assigned to a specific surgeon. Whenever surgery is assigned to a specific day, the related surgical staff will be allocated by the operating planning manager.
In tackling this problem, some researchers have taken into account the availabilities of surgeons and operating rooms [ 3 , 4 ] while others have considered the availabilities of multiple resources (such as operating rooms, surgeons, equipment, and recovery beds) [ 5 , 6 , 7 , 8 , 9 ]. Recently, some researchers studied a daily surgery scheduling problem taking into account multiple resources and stages, i.e., pre-surgery, surgery, and post-surgery; such an approach in which the different resources required in each stage are taken into account is called “comprehensive operating room scheduling”. In the present research, the “no-wait” constraint is considered between the three stages. Surgeries are known in advance (i.e., were elective in nature). The allocation of resources is considered throughout the process: pre-operative holding units (PHU) beds in the first stage; operating rooms, surgeons, nurses, and anesthetists in the second stage; and post anesthesia care unit (PACU) beds in the third stage. The objective is to minimize the maximum end time of the last activity in stage 3 and the total idle time in the operating rooms [ 10 , 11 , 12 ]. As more resources and stages are considered, operating scheduling problems become progressively more complicated.
This research considers a similar problem to that addressed in [ 3 , 4 ]. In [ 3 ], the authors studied a tactical operating room planning problem by taking into account the availabilities of surgeons and operating rooms. The objectives were to maximize operating room utilization and to minimize overtime cost. They first constructed a mathematical model that assigned surgeries to operating rooms over a period of one week by using an open scheduling strategy. Next, they reformulated the mathematical model as a set-partitioning model and then solved it by using a column-generation-based, heuristic procedure with four criteria. In [ 4 ], the authors studied a dynamic scheduling problem that consisted of three stages: the first was to assign operating days to each specialty; the second was to address the surgeon assignment problem; and the third was to deal with the assignment and sequence of patients. The objective was to minimize total patient waiting and operating room overtime costs. Zhu et al. [ 4 ] used a hybrid Grey Wolf Optimizer)–Variable Neighborhood Search (GWO-VNS) algorithm combining the Grey Wolf Optimizer (GWO) with a Variable Neighborhood Search (VNS). The operating room scheduling problem was shown to be NP-hard through a reduction to the 0–1 multiple knapsack problem [ 13 ].
The operating room department is typically the unit with the highest costs and revenue. Hence, it is important to ensure the efficient use of operating rooms. The purpose of this research is to obtain an efficient operating schedule that maximizes the utilization of operating rooms while minimizing idle time and overtime. Considering the complexity of operating room scheduling problems, we propose the use of easy-to-implement heuristics and an artificial bee colony (ABC) to solve the studied problem efficiently.
2. Mathematical Model
We considered assigning a set of surgeries to operating rooms within a planning horizon to minimize total operating cost. The notations used in this section are given in Table 1 .
Notations used in this article.
The studied problem was formulated as a mathematical model by Fei et al. [ 3 ]. In [ 3 ], the objective function was formulated as Min ∑ d = 1 N D ∑ k = 1 M d C k d = max R k d − ∑ i ∈ Ω t i z i k d , β ∑ i ∈ Ω t i z i k d − R k d . The objective function is nonlinear due to the max term. Also, the work in [ 3 ] failed to consider Constraint (4). Without Constraint (4), a surgery i with D i ≤ H might be scheduled in day d = 1 to D i first and then may be scheduled in day d = D i to H again. It violates the condition that every surgery can only be scheduled at most once over the planning horizon, and hence, it is infeasible. We modified the model in [ 3 ] so that it can find an optimal solution for the studied problem. First, we revised the objective function in [ 3 ] as Constraints (1), (7), and (8) so that the objective function is linear. Second, we added Constraint (4) to prevent a surgery from being scheduled twice. The modified mixed integer programming (MIP) model for the studied problem is as follows:
Decision variable x i k d = 1 if surgery i is assigned to operating room k on day d ; otherwise = 0. The objective function seeks to minimize the cost of total unused time and overtime. Constraint (2) denotes that, if a surgery’s deadline is smaller or equal to H , it should be scheduled exactly once before its deadline. Constraint (3) indicates that, if a surgery’s deadline is larger than H , it schedules at most once over the planning horizon. Constraint (4) ensures that each surgery can only be scheduled at most once over the planning horizon. Constraint (5) ensures that the total operating time of any operating room on any planning day would not exceed its maximum permissible overtime. Constraint (6) ensures that the total operating time assigned to each surgeon per day cannot exceed their maximum working hours on that day. Constraints (7) and (8) ensure that C k d takes either the value of waste cost for the unused time of operating room k on day d or the value of α times the overtime operating cost of operating room k on day d depending on which value is larger. Constraints (9) and (10) show the nonnegativity and integrality restrictions.
3. Heuristics
Two easy-to-implement heuristics based on the varied earliest due date (EDD) rule and varied longest processing time (LPT) rule are proposed for the studied problem. We describe the steps of the two heuristics as follows.
3.1. Modified EDD Heuristic (MEDD)
In step 1, the MEDD heuristic first sorts all surgeries in EDD order. It breaks ties by using the LPT rule. In step 2, the MEDD heuristic tries to find operating room k on day d that surgery x can be assigned to without exceeding the regular opening time of the operating room k and the maximum operating time available of surgeon l , x ∈ Ω l . The search starts from the first operating room k = 1 on first day d = 1 and ends on the last operating room k = M d on last day d = D x . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. In step 3, if surgery x cannot be assigned to solution π without exceeding the regular opening time of the operating room and the maximum operating time available of surgeon l , x ∈ Ω l . Then, the MEDD heuristic tries to find operating room k on day d that surgery x can be assigned to without exceeding the maximal permissible overtime of operating room and the maximum operating time available of surgeon l , x ∈ Ω l . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. In step 4, if surgery x cannot be scheduled into schedule π after steps 2–3 and if D x ≤ H , then the MEDD heuristic randomly chooses one operating room k on day d , d ≤ D x . Add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. However, if D x > H , then the MEDD heuristic will remove surgery x from U and go back to step 2. In the last step, step 5 applies RecoveryScheme to ensure that the generated schedule π is feasible. Figure 1 shows the flow chart of the MEDD heuristic.
The flow chart of the modified earliest due date (MEDD) heuristic.
MEDD Heuristic
Step 1. Sort all surgeries by the EDD rule. Break any ties using the LPT rule. Save all the sorted surgeries in set U . Initially, set schedule π = {null}.
Step 2. If U = null , go to Step 5. Otherwise, try to schedule the first surgery x , x ∈ U , x ∈ Ω l in operating room k on day d if it satisfies f k d ( π ) ≤ R T k d and g l d π ≤ A l d . Try k = 1 first; if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > D x . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2.
Step 3. Try to schedule the first surgery x , x ∈ U , x ∈ Ω l in operating room k on day d if it satisfies f k d ( π ) ≤ R T k d + O T k d and g l d π ≤ A l d . Try k = 1 first; if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > D x . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2.
Step 4. For the first surgery x , x ∈ U , if D x ≤ H , then randomly choose one operating room k on day d , d ≤ D x . Add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. Otherwise, remove surgery x from U and go back to step 2.
Step 5. Apply RecoveryScheme (described in Section 4.3 ) to schedule π .
3.2. Modified LPT Heuristic (MLPT)
In step 1, the MLPT heuristic first sorts all surgeries in LPT order. It breaks ties by using the EDD rule. Then, in steps 2–4, it handles surgeries that have due dates smaller than or equal to the planning horizon ( D x ≤ H ) based on their sorted order in U . In step 2, the MLPT heuristic tries to find operating room k on day d that surgery x can be assigned to without exceeding the regular opening time of the operating room k and the maximum operating time available of surgeon l , x ∈ Ω l . The search starts from the first operating room k = 1 on the first day d = 1 and ends at the last operating room k = M d on the last day d = D x . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. In step 3, if surgery x cannot be assigned into solution π without exceeding the regular opening time of the operating room and the maximum operating time available of surgeon l , x ∈ Ω l , then the MLPT heuristic tries to find operating room k on day d that surgery x can be assigned to without exceeding the maximal permissible overtime of operating room and the maximum operating time available of surgeon l , x ∈ Ω l . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. In step 4, if surgery x cannot be scheduled into schedule π after steps 2–3, then the MLPT heuristic randomly chooses one operating room k on day d , d ≤ D x . Add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2. steps 5–6, the MLPT heuristic handles surgeries that have due dates larger than the planning horizon ( D x > H ). The procedures are similar to steps 2–3. If k and d are not found in steps 5–6, the MLPT does not consider scheduling x into schedule π anymore. It removes surgery x from U and goes back to step 5. In the last step, step 7 applies RecoveryScheme to ensure that the generated schedule π is feasible. Figure 2 shows the flow chart of the MLPT heuristic.
The flow chart of modified longest processing time (MLPT) heuristic.
MLPT Heuristic
Step 1. Sort all surgeries by the LPT rule. Break any ties by using the EDD rule. Save all the sorted surgeries in set U . Initially, set schedule π = {null}.
Step 2. If U = null , go to step 7. Otherwise, selects the first surgery x , x ∈ U , x ∈ Ω l that satisfies D x ≤ H . Try to schedule surgery x in operating room k on day d if it satisfies f k d ( π ) ≤ R T k d and g l d π ≤ A l d . Try k = 1 first; if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > D x . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2.
Step 3. Select the first surgery x , x ∈ U , x ∈ Ω l that satisfies D x ≤ H . Try to schedule surgery x into operating room k on day d if it satisfies f k d ( π ) ≤ R T k d + O T k d and g l d π ≤ A l d . Try k = 1 first; if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > D x . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2.
Step 4. Select the first surgery x , x ∈ U , x ∈ Ω l that satisfies D x ≤ H . Randomly choose one operating room k on day d , d ≤ D x . Add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 2.
Step 5. If U = null , go to step 7. Otherwise, select the first surgery x , x ∈ U , x ∈ Ω l . Try to schedule surgery x into operating room k on day d if it satisfies f k d ( π ) ≤ R T k d and g l d π ≤ A l d . Try k = 1 first; if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > H . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 5.
Step 6. Select the first surgery x , x ∈ U , x ∈ Ω l . Try to schedule surgery x into operating room k on day d if it satisfies f k d ( π ) ≤ R T k d + O T k d and g l d π ≤ A l d . Try k = 1 first; if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > H . If k and d are found, then add surgery x into operating room k on day d , update schedule π , remove surgery x from U , and go back to step 5. If k and d are not found, then remove surgery x from U and go back to step 5.
Step 7. Apply RecoveryScheme (described in Section 4.3 ) to schedule π .
4. Artificial Bee Colony (ABC) Algorithm
The ABC algorithm was originally proposed by Karaboga [ 14 ]. It is a newly developed metaheuristic that simulates bees’ food search behavior. Compared to other metaheuristics, it has the advantages of being simple, flexible, and robust [ 15 , 16 ]. According to [ 1 ], the surgery scheduling problem is similar to the parallel machine scheduling problem. The ABC algorithm has been applied to several parallel machine scheduling problems [ 17 , 18 , 19 , 20 ], and the results are promising. Hence, we chose the ABC algorithm to solve the studied problem. The ABC algorithm works in an iterative process. The colony of artificial bees consists of three groups: employed bees, onlooker bees, and scout bees. Each employed bee corresponds to a food source. The location of a food source corresponds to a possible solution to the studied problem and the nectar amount of the food source represents the quality of the solution. Employed bees are responsible for performing simple and quick exploitation (neighborhood search) on available food sources and for informing the onlooker bees about the nectar amounts of the sources. Next, the onlooker bees select existing food sources and conduct more detailed exploitation based on the information they receive from the employed bees. The higher the nectar amount of a food source, the higher the probability it would be selected by onlooker bees. If the quality (fitness) of the food source (solution) cannot be improved after performing simple and quick exploitation, the corresponding food source is abandoned and the employed bee is converted to a scout bee. The scout bee will then seek a new food source randomly. We describe the implementation of the ABC algorithm as follows.
4.1. Coding Scheme
We adopt the same coding scheme as used in [ 2 ] to represent a solution on hand. The surgery symbols are denoted using integers. The partition symbols denoted with “R” or “D” designate the partition of surgeries to operating rooms and operating days, respectively. Since not all the surgeries can be scheduled into the current planning horizon, the length of a solution varies. For example, suppose 10 surgeries are waiting to be scheduled into two days, each day has two operating rooms available. A solution can be represented as follows: (9 2 R 1 D 7 10 R 3 6 4). The corresponding schedule is surgeries 9 and 2 in operating room 1 on day 1; surgery 1 in operating room 2 on day 1; surgeries 7 and 10 in operating room 1 on day 2; and surgeries 3, 6, and 4 in operating room 2 on day 2. Surgeries 5 and 8 are not assigned. Another possible solution (8 3 5 R D 7 2 R 9 6) represents surgeries 8, 3, and 5 in operating room 1 on day 1; no surgery in operating room 2 on day 1; surgeries 7 and 2 in operating room 1 on day 2; and surgeries 9 and 6 in operating room 2 on day 2. Surgeries 1, 4, and 10 are not assigned.
4.2. Initialization
In the ABC algorithm, each employed bee is dispatched to work on a specific food source and each food source is associated with a solution. In order to give the ABC algorithm good initial solutions, we inseredt two solutions generated by using the MEDD and MLPT heuristics into the initial solutions. The remaining initial solutions were randomly generated by using the following RandomlyGenerateSolutionScheme to make up SN initial population.
Randomly Generate Solution Scheme
Step 1. For a given problem instance, sort all surgeries by the EDD rule. Break any ties by using the LPT rule. Save all the sorted surgeries in set U . Initially, set π = null .
Step 2. If U = null , go to step 3. Otherwise, try to schedule the first surgery x , x ∈ U into schedule π . If D x ≤ H , randomly choose one operating room k on day d , d ≤ D x and add surgery x into operating room k on day d , update schedule π , and remove surgery x from U . If D x > H , randomly choose one operating room k on day d , d ≤ H and add surgery x in operating room k on day d , update schedule π , and remove surgery x from U . Go back to step 2.
Step 3. Apply RecoveryScheme (described in Section 4.3 ) to generate a feasible solution π .
4.3. RecoveryScheme
The studied operating room scheduling problem is a highly constrained combinatorial optimization problem. A feasible solution needs to meet all the due dates of scheduled surgeries, to meet each surgeon’s maximum available operating time on each day, and to meet the maximum permissible overtime of each operating room on each day. All those constraints are hard constraints. Violations of any of those hard constraints will lead to infeasible solutions. As the number of surgery increases, the number of hard constraints increases, and the probability of generating infeasible solutions becomes very high. Hence, we proposed a RecoveryScheme that can recover an infeasible solution into a feasible solution. We describe the RecoveryScheme as below. For a given schedule π , assuming B and B c are the set of scheduled surgeries and the set of unscheduled surgeries (i.e., B c is B ′ s complementary set where B + B c = Ω ) . In step 1, the RecoveryScheme removes surgeries that violate due date constraints to B c . In step 2, it removes surgeries that violate the constraint f k d ( π ) ≤ R T k d + O T k d from B to B c . In step 3, it removes surgeries that violate the constraint g l d π ≤ A l d from B to B c . In step 4, it sorts all surgeries in set B c by the EDD rule. For surgeries x , where D x ≤ H , it first tries to find an operating room k on day d that adds surgeries x into operating room k on day d that can keep schedule π feasible. If k and d are found, then it adds surgery x into operating room k on day d , removes surgery x from B c , updates schedule π , and goes back to step 4. If k and d are not found, it randomly chooses one operating room k on day d , d ≤ D x , adds surgery x to operating room k on day d , removes surgery x from B c , and updates schedule π . Here, the schedule π might violate the constraints f k d ( π ) ≤ R T k d + O T k d or g l d π ≤ A l d again. Step 4 is repeated until there are no more surgeries x , x ∈ B c that have due dates smaller or equal to the planning horizon. For the remaining surgeries in set B c , step 5 tries to schedule more surgeries x , x ∈ B c randomly to operating room k on day d if it satisfies f k d ( π ) ≤ R T k d + O T k d and g l d π ≤ A l d . Step 6: if schedule π is feasible, then RecoveryScheme outputs the final feasible schedule π and terminates the recovery process. Otherwise, it goes back to step 1 and continues the recovery process.
RecoveryScheme
Step 1: For a given schedule π , update B and B c . Remove surgeries x , x ∈ B that are scheduled later than their due dates ( d i > D i ) to B c . Update schedule π .
Step 2: Calculate f k d ( π ) ∀ d , k . Find k * and d * that satisfies f k * d * ( π ) > R T k * d * + O T k * d * ∀ d , k . Randomly remove surgery (surgeries) x that is (are) scheduled in operating room k * on date d * from B to B c until f k * d * ( π ) ≤ R T k * d * + O T k * d * . Update schedule π .
Step 3: Calculate g l d π ∀ d , l . Find l * and d * that satisfy g l * d * π > A l * d * ∀ d , k . Randomly remove surgery (surgeries) x , x ∈ Ω l * that is (are) scheduled on d * from B to B c until g l * d * π ≤ A l * d * . Update schedule π .
Step 4: Sort the surgeries into set B c by the EDD rule. Try to schedule surgeries x , x ∈ B c , x ∈ Ω l , D x ≤ H into operating room k on day d if it satisfies f k d ( π ) ≤ R T k d + O T k d and g l d π ≤ A l d . Try k = 1 first, if k is not feasible, then try k = k + 1 until k > M d . Similarly, try d = 1 first; if d = 1 is not feasible, then try d = d + 1 until d > D x . If k and d are found, then add surgery x into operating room k on day d , remove surgery x from B c to B , update schedule π , and go back to step 4. Otherwise, randomly choose one operating room k on day d , d ≤ D x . Add surgery x into operating room k on day d , remove surgery x from B c to B , and update schedule π . Repeat step 4 until there are no more surgeries x , x ∈ B c that satisfies D x ≤ H .
Step 5: For the remaining surgeries in set B c . Let U = B c . Choose the first surgery x , x ∈ U . Randomly choose one operating room k on day d from schedule π . If adding surgery x into operating room k on day d satisfies f k d ( π ) ≤ R T k d + O T k d and g l d π ≤ A l d , then insert it into and update schedule π . Otherwise, remove surgery x from U . Repeat step 5 until U = n u l l .
Step 6: If schedule π is feasible, then output the final feasible schedule π and terminate the recovery process. Otherwise, go back to step 1.
4.4. Local Search Schemes
Two local search schemes were proposed in this research. They are used to intensify and diversify the solution pool. The proposed local search schemes are described below.
4.4.1. Internal Swap
Step 1: For a given schedule π , randomly choose two surgeries x , y x , y ∈ B
Step 2: If D x ≥ d y , D y ≥ d x , and x , y are not scheduled in the same operating room on the same date, then swap x and y and update schedule π . Otherwise, go back to step 1.
Step 3: Apply RecoveryScheme to schedule π .
The InternalSwap tries to find two scheduled surgeries x and y from a given schedule π . Step 2 ensures that the swapping of surgeries x and y satisfies d i ≤ D i constraints. Step 3 ensures that the schedule π is feasible after swapping.
4.4.2. External Swap
Step 1: For a given schedule π , randomly choose one surgery x , x ∈ B and one unscheduled surgery y , y ∈ B c .
Step 2: If D x > H , then swap x and y and update schedule π . Otherwise, go back to step 1.
The ExternalSwap tries to find a scheduled surgery x and an unscheduled surgery y from a given schedule π . Step 2 ensures that the swapping of surgeries x and y satisfies the constraints d x ≤ D x and d y ≤ D y . Step 3 ensures that schedule π is feasible after swapping.
4.4.3. InternalInsertion
Step 1: For a given schedule π , randomly choose one surgery x , x ∈ B . Suppose that surgery x is scheduled in operating room k ′ on day d ′ . Randomly choose one operating room k ( k ≠ k ′ ) on day d ( d ≠ d ′ ).
Step 2: If D x ≥ d , then insert surgery x into operating room k on day d and update schedule π . Otherwise, go back to step 1.
InternalInsertion tries to find a scheduled surgery x and one operating room k on day d from a given schedule π . Step 2 ensures that surgery x inserted into operating room k on day d satisfies the constraint d x ≤ D x . Step 3 ensures that the schedule π is feasible after insertion.
4.4.4. ExternalInsertion
Step 1: For a given schedule π , randomly choose one surgery x , x ∈ B c and randomly choose one operating room k on day d .
ExternalInsertion tries to find an unscheduled surgery x and one operating room k on day d from a given schedule π . Step 2 makes sure that surgery x inserted into operating room k on day d satisfies the constraint d x ≤ D x . Step 3 ensures that the schedule π is feasible after insertion.
Our initial trials indicated that ExternalInsertion outperformed ExternalSwap, that ExternalSwap outperformed InternalInsertion, and that InternalInsertion outperformed InternalSwap. In our ABC, we combined and used different local search schemes to form two types of local search strategies, namely ExplorationProcess and ExploitationProcess. The ExplorationProcess is a simple and efficient way to diversify the current solution pool; the ExploitationProcess is a greedy search to intensify a given solution. ExplorationProcess and ExploitationProcess are described below.
4.4.5. ExplorationProcess
Step 0. Initially, set s = 0.
Step 1. Randomly generate an integer number aa from a uniform distribution (1,4). If aa = 1, go to step 2. If aa = 2, go to step 3. If aa = 3, go to step 4. If aa = 4, go to step 5.
Step 2. Perform InternalSwap on schedule π . If a smaller cost is found, then update schedule π and terminate the procedure. Otherwise, s = s + 1. If s < S , then go back to step 1. Otherwise, go to step 6.
Step 3. Perform InternalInsertion on schedule π . If a smaller cost is found, then update schedule π and terminate the procedure. Otherwise, s = s + 1. If s < S , then go back to step 1. Otherwise, go to step 6.
Step 4. Perform ExternalSwap on schedule π . If a smaller cost is found, then update schedule π and terminate the procedure. Otherwise, s = s + 1. If s < S , then go back to step 1. Otherwise, go to step 6.
Step 5. Perform ExternalInsertion on schedule
π . If a smaller cost is found, then update schedule π and terminate the procedure. Otherwise, s = s + 1. If s < S , then go back to step 1. Otherwise, go to step 6.
Step 6. Randomly generate an integer number bb from a uniform distribution (1,2). If bb = 1, then output the final schedule π ; otherwise, discard schedule π and apply RandomlyGenerateSolutionScheme to generate a new schedule.
4.4.6. ExploitationProcess
Step 1. Apply ExternalInsertion. If a smaller cost is found, then go to step 1; otherwise, go to step 2.
Step 2. Apply ExternalSwap. If a smaller cost is found, then go to step 2; otherwise, go to step 3.
Step 3. Apply InternalInsertion. If a smaller cost is found, then go to step 3; otherwise, go to step 4.
Step 4. Apply InternalSwap. If a smaller cost is found, then go to step 4; otherwise, go to step 5.
Step 5. Terminate ExploitationProcess.
4.5. Fitness Value and Selection
We defined the objective value of schedule π as the total operating cost ( ∑ d = 1 H ∑ k = 1 M d C k d ). Since we are minimizing the objective, the fitness value of a solution π is inversely proportional to its objective ( π ) , as shown in Formula (11). Next, we applied a basic roulette wheel [ 21 ] selection mechanism to the sampling space ( p s ) to form a new population. A roulette wheel selects a new population based on a fitness-proportional probability distribution. A bee’s probability for selection can be calculated from Formula (12).
4.6. Elitism Strategy
In each iteration, we saved the top MaxElite unique solutions and their attributes in the elite list (EliteSolutions). The elite solutions are sorted by nondecreasing order of total cost. When the current best solution does not update for several iterations, the search might get trapped into a local optimal. When this occurs, we apply an elitism strategy to help the search escape from the local optimal. Our elitism strategy is described below.
Elitism Strategy
Step 1: Apply ExternalInsertion ∀ d , k . For a given schedule π , try to perform an external insertion for every surgery x , x ∈ B c to all operating rooms on all dates. Precisely, select the r th ( r = 1,..., B c ) surgery x and try to insert it into operating room k , k = 1 , … , M d on day d , d = 1 , … , H . If insert surgery x into operating room k on day d can keep the schedule feasible with a smaller cost than the cost before insertion, then insert it into and update schedule π , and update EliteSolutions. The procedure is repeated for the current schedule π until all surgeries in set B c have been examined.
Step 2: Apply ExternalSwapforAllPairs. For a given schedule π , try to perform an external swap for each pair of surgeries x , x ∈ B and y , y ∈ B c . Specifically, select the r th ( r = 1,..., B ) surgery from the schedule in π and try to swap it with all surgeries in set B c . If swapping x and y can keep the schedule feasible with a smaller cost than the cost before the swap, then swap the surgeries, update schedule π , and update EliteSolutions. The procedure is repeated for the current schedule π until all pairs of surgeries in set B and B c have been examined.
Step 3: Apply InternalInsertion ∀ d , k . For a given schedule π , try to perform an internal insertion for every surgery x , x ∈ B to all feasible operating rooms on all feasible dates. Precisely, select the r th ( r = 1,..., B ) surgery x from schedule π . Assuming surgery x is scheduled in operating room k ′ on day d ′ . Try to insert surgery x into operating room k , k = 1 , … , M d , k ≠ k ′ on day d , d = 1 , … , D x , d ≠ d ′ . If inserting surgery x into operating room k on day d can keep the schedule feasible with a smaller cost than the cost before insertion, then insert it into and update schedule π , and update EliteSolutions . The procedure is repeated for the current schedule π until all surgeries in set B have been examined.
Step 4: Apply InternalSwapforAllPairs. For a given schedule π , try to perform an internal swap for each pair of two surgeries x , y x , y ∈ B . specifically, select the r th ( r = 1,..., B ) surgery x from the schedule π . Assuming that surgery x is scheduled in the operating room k ′ on day d ′ , Try to swap it with all other surgeries in set B but exclude surgeries that are also scheduled in operating room k ′ on day d ′ . If swapping x and y can keep the schedule feasible with a smaller cost than the cost before the swap, then swap the surgeries, update schedule π , and update EliteSolutions. The procedure is repeated for the current schedule π until all pairs of two surgeries in set B have been examined.
4.7. The Implementation of the Proposed ABC Algorithm
Based on the details (coding, initialization, a recovery scheme, local search schemes, fitness value and selection, and elitism strategy) presented in the previous subsection, the implementation of the proposed ABC algorithm is described as follows. We also provide a flow chart of the proposed ABC in Figure 3 .
The flow chart of the artificial bee colony (ABC) algorithm.
Step 0: Let SolutionSet be the set of solutions found by all bees and EliteSolutions be the set of elite solutions. Initially, set EliteSolutions = {null}, and iteration without improvement counter IWOI = 0.
Step 1: Insert the two solutions generated by using the MEDD and MLPT heuristics. The remaining initial solutions are randomly generated by using RandomlyGenerateSolutionScheme to make up the SN initial population. Each initial solution corresponds to an employed bee that is associated with a food source.
Step 2: Set SolutionSet = {null}. Each employed bee works on a food source (a solution) and evaluates their nectar amounts by imposing ExplorationProcess to see if a better solution can be found. Once a better solution π has been found, the employed bee will save the new food source, update π , and terminate the initial exploration. If the quality of the food source (a solution) cannot be improved after performing a maximum allowable number of iterations ( S ), there is a 50% probability that the employed bee will keep the food source. In the other 50% probability, the food source is abandoned. If the food source is abandoned, the employed bee is converted to a scout bee. The scout bee will then start to search for a new food source by using RandomlyGenerateSolutionScheme to randomly generate a new solution. After all the employed bees ( SN ) have finished with the exploration process, the ABC algorithm sorts all the solutions in nondecreasing order of total cost.
Step 3: After all employed bees have finished the exploration process, the onlooker bees will receive nectar information of the food sources from the employed bees. The SN onlookers then select existing food sources (the enlarge food source size is 2 × SN ) to be further explored in a probabilistic manner by using Formula (12). The better the solution, the higher the probability it would be selected by the onlooker bees.
Step 4: After the onlooker bee has selected a food source, it conducts a more detailed neighborhood search on it by applying ExploitationProcess. After all onlooker bees ( SN ) have finished the exploitation process, the ABC algorithm sorts all the solutions in nondecreasing order of total cost and saves them into SolutionSet.
Step 5: Check whether any solutions in SolutionSet has outperformed the solutions in EliteSolutions. If yes, update EliteSolutions and set IWOI = 0; otherwise, set IWOI = IWOI + 1.
Step 6: Check whether IWOI has reached the maximum number of non-improving iterations required to trigger the search procedure for elite solutions (IWOI > MIWOI): if yes, apply the ElitismStrategy to all solutions stored in EliteSolutions. Otherwise, select SN employed bees from SolutionSet by using Formula (12) and go back to step 2.
Step 7: Check whether the EliteSolutions has been updated. If yes, set IWOI = 0 and select SN employed bees from SolutionSet by using Formula (12) and go back to Step 2. Otherwise, go to step 8.
Step 8: Terminate the ABC algorithm and report the final best solution in EliteSolutions.
We conducted some preliminary experiments to check the performance of the ABC algorithm for different parameter settings. In order to find a tradeoff between solution quality and computation time, the following settings are used for the parameters in the ABC algorithm.
MaxElite = 5
5. Computational Results
In this section, we present several computational results regarding the performance of the proposed MEDD heuristic, MLPT heuristic, and ABC algorithm. The problems were solved in the following environment:
Hardware for running the algorithm: ASUS TeK (AMD Ryzen 7 4700 U 2.00 GHz, memory: 8 GB).
Algorithm development environment: Microsoft Visual C + + 2019.
Software for running the MIP model: AMPL with CPLEX 11.2 solver.
The testing data were generated as follows:
The planning horizon is 5 days (a week). According to Combes et al. [ 22 ] and Fei et al. [ 3 ], the Pearson III distribution fits the distribution of surgery’s operating time very well. Hence, the operating times of surgeries are generated from the Pearson III distribution. In this study, test problems were generated in a manner similar to that of [ 3 ].
The surgery operating time, t i , was generated from the Pearson III distribution in the range (40, 150) with the mean at 90 and a standard deviation of 15 (unit: minute).
The due date of surgery i , D i , was generated from a uniform distribution in the range (1,14) (unit: day).
Each surgery was randomly assigned to a surgeon in advance. For each surgery i , we randomly generated an integer number l from a uniform distribution (1,8). Then, surgery i was assigned to surgeon l .
The cost ratio of ordinary working hours and overtime ones was set to α = 1.5.
The number of surgeons was set to 8, and the maximum operating time (unit: hour) available of surgeons during the planning horizon was as follows [ 3 ].
From Monday to Friday ( A l d ),
Surgeon 1: (8,0,7,0,6)
Surgeon 2: (8,4,5,6,5)
Surgeon 3: (12,3,6,7,8)
Surgeon 4: (5,3,4,8,10)
Surgeon 5: (6,5,0,6,8)
Surgeon 6: (6,0,5,7,9)
Surgeon 7: (0,6,6,6,9)
Surgeon 8: (0,6,6,8,10)
The number of operating rooms considered was set to 6, and the regular opening hours and maximum overtime hours during the planning horizon were given as follows [ 3 ].
Regular opening hours from Monday to Friday ( R T k d ):
Operating room 1: (8,5,4,6,5)
Operating room 2: (5,7,8,5,4)
Operating room 3: (7,6,7,8,6)
Operating room 4: (4,5,8,4,8)
Operating room 5: (8,8,5,7,4)
Operating room 6: (8,-,5,4,7), where “-“ means the operating room is not available.
Maximum overtime hours from Monday to Friday ( O T k d . ):
Operating room 1: (2,3,3,0,2)
Operating room 2: (0,0,1,2,2)
Operating room 3: (2,2,2,2,1)
Operating room 4: (1,3,1,2,0)
Operating room 5: (2,0,2,2,0)
Operating room 6: (0,-,2,2,0), where “-“ means the operating room is not available.
The number of surgeries waiting to be operated Ω was set to 40, 50, 60, …, 150. We used Ω = 40–110 to represent small problems and Ω = 120–150 to represent large problems. For each setting of Ω, 20 instances were randomly generated. In total, there are 240 instances that are generated and tested.
For small problems, we compared the MEDD heuristic, MLPT heuristic, and ABC algorithm with the optimal solutions found using the MIP model. Table 2 shows the results of small problem instances. For each tested surgery size Ω, we report the average of 20 randomly generated instances. The first column reports the optimal solution obtained by solving the MIP model. Table 2 shows that the MEDD heuristic outperforms the MLPT and that the ABC algorithm improved the initial solutions obtained by the two heuristics significantly. The MEDD heuristic is 8.47% deviated from the optimal solution on average, the MLPT is 17.68% deviated from the optimal solution on average, and the ABC algorithm is 0.1% deviated from the optimal solution on average. The proposed ABC algorithm can find optimal solutions for all of the tested instances of surgery size Ω = 40, 50, 60, 70, 80, 90, and 100.
The performance of the heuristics and the ABC algorithm for small problem instances.
Opt. is obtained by solving the mixed integer programming (MIP) model. The result is the average of 20 randomly generated instances.
For a surgery size larger than 110, the problems fail to be solved by the MIP model due to an out of memory error. Hence, for large problem instances, we compared the MEDD heuristic and MLPT heuristic with the ABC algorithm. Table 3 shows that the MEDD heuristic outperforms the MLPT and that the ABC algorithm has improved the initial solutions obtained by the two heuristics significantly. The cost obtained by the ABC algorithm decreases dramatically when compared to the cost obtained by the two heuristics. In all, the MEDD heuristic is 471.8% deviated from the ABC algorithm on average and the MLPT is 669.72% deviated from the ABC algorithm.
The performance of the heuristics and the ABC algorithm for large problem instances.
Moreover, we took the costs from Table 2 and Table 3 and demonstrated the comparison of four methods in Figure 4 . For the number of surgeries between 40 and 100, the ABC algorithm was able to find the cost that is the same as the optimal solution for all testing instances. For the number of surgeries between 110 and 150, the mathematical model cannot find an optimal solution as it ran out of memory. Hence, Figure 4 does not report the results of optimal solutions for the number of surgeries between 110 and 150. For the number of surgeries between 110 and 150, the ABC algorithm outperforms the MEDD and MLPT in terms of total cost significantly.
Comparison of four methods.
Table 4 shows the computation time of the MIP model, heuristics, and the ABC algorithm. The MIP model spent more time finding an optimal solution than the heuristics and the ABC algorithm. The MIP model spent about 446.31 s to find an optimal solution for 100 surgery problem instances on average. As mentioned before, the MIP model can only solve small problem instances. Two heuristics can find a feasible solution in less than a second for all problem instances. As the number of surgery increases, the computation time of the ABC algorithm increases. On average, the ABC spent about 98.38 s to find a feasible solution that is significantly better than the two heuristics.
The computational time of the MIP model, heuristics, and the ABC algorithm.
The result is the average of 20 randomly generated problem instances.
We also report the number of scheduled surgeries for each surgery size Ω . The result shows that almost all surgeries have been scheduled into the planning horizon for Ω between 40 and 100 problem instances. Table 4 shows that the total cost of all methods is high for Ω = 40–100 problem instances. This is probably because the operating rooms are underused and unused costs occur. For Ω between 120 and 150, the ABC algorithm schedules about 115 surgeries into the planning horizon on average, and the total costs are relatively low compared to other problem sizes. This is probably because the capacities of the operating rooms are full. In another word, the operating rooms are fully used. The ABC algorithm tried to schedule surgeries into the regular opening time and only a small amount of overtime is needed.
Furthermore, we examined the convergence curves of the proposed ABC. We maintain the termination condition of the ABC but count the number of iterations until the ABC is terminated. Figure 5 shows four typical convergence curves for some of the test instances of Ω = 130. Specifically, instances 1, 13, 14, and 20 are chosen and reported in Figure 5 . The other instances have similar results. From the curves, the ABC has a steep descent for early generations. The ABC, on average, takes 400 iterations to converge to the best solution for the 20 tested instances of surgery size Ω = 130.
The converge curves of the proposed ABC.
Since this research studied the same problem as [ 3 ] and we used the same manner as [ 3 ] to generate testing data, we made a comparison of our results with [ 3 ]. In [ 3 ], the authors first constructed a mathematical model that assigned surgeries into operating rooms within one week by using the open scheduling strategy. Next, they reformulated the mathematical model as a set-partitioning model and then solved it by using a column-generation based heuristic (CGBH) procedure with four criteria, namely H1, H2, H3, and H4. The proposed CGBH procedure with four criteria was compared with each other to find a solution with the best performance. Moreover, the best approximate solution, obtained by the CGBH procedure after running all the criteria proposed, was compared with the lower bound obtained by an explicit column generation (CG) procedure (the optimal solution of the linear relaxation of the set-partitioning model). They tested surgery size Ω = 40, 60, 80, 100, 120, 140, and 160. For each surgery size Ω, 10 problem instances were generated and tested. Therefore, totally, 70 problem instances are generated and tested. Instead of solving a mathematical model to obtain an optimal solution, the work in [ 3 ] solves the explicit CG procedure to obtain a lower bound. All the tested instances of surgery size Ω = 40, 60, and 80 are optimally solved by the explicit CG procedure. As for those instances of large size Ω = 100, 120, 140, and 160, the CGBH procedure with criterion H2 can obtain the best solution among those four criteria in most of the cases once it obtains a feasible solution. However, H2 cannot always obtain a feasible solution, especially in the scenario of Ω = 160. In fact, the CGBH procedure with four criteria cannot always obtain a feasible solution for each instance. Among the 70 tested instances, 100% of them can be solved by the CGBH procedure with criterion H1 within 10 times of execution; 74.29% can be solved by the CGBH procedure with criterion H2; 72.85% can be solved by the CGBH procedure with criterion H3; and 71.43% can be solved by the CGBH procedure with criterion H4. Next, they compared the approximate solution obtained by H with the lower bound obtained by the explicit CG procedure. H represents the objective value of the best approximate solution, selected among approximate solutions obtained by the CGBH procedure after running all those four criteria. They reported that 45 instances (45/70 = 64.29%) can be optimally solved by the explicit CG procedure. For surgery size Ω = 100, 120, 140, and 160, H deviated by 0.13%, 2.2%, 4.73%, and 34.58% from the lower bound on average ((H-lower bound)/H). Lastly, the work in [ 3 ] showed the computational time used by the CGBH procedure with four criteria. The largest one, surgery size Ω = 140, took about 15 min by H.
In this research, all the tested instances of surgery sizes Ω = 40, 50, 60, 70, 80, 90, 100, and 110 are optimally solved by the modified MIP model. The proposed ABC algorithm can find optimal solutions for all the tested instances of surgery size Ω = 40, 50, 60, 70, 80, 90, and 100. The MIP model cannot solve problems of surgery size larger than 110 due to memory issues. Hence, for large problem instances, we compared the MEDD and MLPT heuristics with the ABC algorithm. The results indicate that the ABC algorithm improved the initial solutions obtained by the two heuristics significantly. The cost found by the ABC algorithm decreases dramatically when compared to the cost found by the two heuristics. In all, the MEDD heuristic deviated by 471.8% from the ABC algorithm on average and the MLPT deviated by 669.72% from the ABC algorithm. Moreover, the ABC algorithm and the two proposed heuristics can always obtain a feasible solution for all the tested problem instances. Lastly, Table 4 shows the computational time of the four methods. The largest one, surgery size Ω = 150, takes about 6.7 min using the ABC algorithm. Hence, we can conclude that the ABC algorithm can find better solutions more efficiently than the CGBH procedure with the four criteria proposed in [ 3 ].
6. Conclusions and Future Work
An operating room department is a unit with the high cost and high revenue. Hence, it is important to ensure the efficient use of operating rooms. In this research, we have considered constructing a weekly surgery schedule with an open scheduling strategy by taking the availabilities of surgeons and operating rooms into account. The objective is to minimize total operating costs. We first provided a revised mathematical model that can find optimal solutions for small problem instances. Moreover, two modified heuristics were proposed that can find feasible solutions for the studied problem very quickly. Finally, an ABC algorithm that incorporates initial solutions, a recovery scheme, local search schemes, and elite strategy was proposed. The computational results show that, for surgery size Ω = 40–100, the ABC algorithm found optimal solutions for all the tested problems. For surgery size Ω = 120–150, the ABC algorithm improved the initial solutions found by the two proposed heuristics significantly. The solutions of MEDD heuristic deviated from the solutions of ABC algorithm by 471.8% on average, and for the results of MLPT, the deviation was 669.72%. We concluded that the ABC algorithm can solve the studied problems efficiently with less operating cost and higher utilization of operating rooms.
Since all test data were generated randomly, our future work can involve collaborating with local hospitals and testing our algorithm on real data to make the results of our research more practical. Further work can also include studying more complex problems with more constraints and variables, such as the availability of anesthetists, nurses, and recovery beds.
Author Contributions
Conceptualization, Y.-K.L.; formal analysis, Y.-K.L.; methodology, Y.-K.L. and M.-Y.L.; writing—original draft, M.-Y.L.; writing—review and editing, Y.-K.L. and M.-Y.L. All authors have read and agreed to the published version of the manuscript.
This research was funded by Ministry of Science and Technology of Taiwan grant number MOST 109-2221-E-035-050.
Institutional Review Board Statement
Not applicable.
Informed Consent Statement
Data availability statement, conflicts of interest.
The authors declare no conflict of interest.
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
IMAGES
VIDEO
COMMENTS
The six steps of problem solving involve problem definition, problem analysis, developing possible solutions, selecting a solution, implementing the solution and evaluating the outcome. Problem solving models are used to address issues that...
Insects have been used to solve many crimes, including a 1991 “Ken and Barbie” murder and a 1997 murder of two young children. Forensic entomology is the study of insects primarily for medico-legal purposes.
When multiplying or dividing different bases with the same exponent, combine the bases, and keep the exponent the same. For example, X raised to the third power times Y raised to the third power becomes the product of X times Y raised to th...
This linear relaxation problem is solved by a CG approach in which each column represents a plan for one operating room and is generated by solving a sub-
Based on this set partitioning formulation, a so-called branch-and-price exact
Request PDF | Solving surgical cases assignment problem by a branch-and-price approach | In this paper, we study a surgical cases assignment problem (SCAP)
developed a branch-and-price approach to solving a surgery assignment problem.
Solving GAP, some effective exact methods have been proposed to solve classical GAP, such as branch and bound [6], branch and price [19], etc.
Abstract Branch-and-price algorithms based on Dantzig-Wolfe decomposition have shown great success in solving mixed integer linear optimization problems (MILPs)
the Surgical Case Assignment (SCAP) problems for the common Operating ... The -constraint method is used to solve the multi-objective.
The relaxation of the restricted master problem is solved by the revised simplex method. Then new decomposition. Page 15. Sub-problem/Pricing Problem.
This paper summarizes the latest healthcare scheduling problems ... surgical cases assignment problem by a branch-and-price approach.
The computational results show that, for a surgery size between 40 and 100 surgical cases, the ABC algorithm found optimal solutions to all of
Solving surgical cases assignment problem by a branch-and-price approach. 112(1): 96-108. Fei, H., Chu, C., Meskens, N.J.A.o.O.R., 2009.