scheduling techniques research paper

Advertisement

Healthcare scheduling in optimization context: a review

• Review Paper
• Published: 10 April 2021
• Volume 11 , pages 445–469, ( 2021 )

Cite this article

• 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  

21k Accesses

43 Citations

10 Altmetric

Explore all metrics

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.

Similar content being viewed by others

The role of artificial intelligence in healthcare: a structured literature review

Silvana Secinaro, Davide Calandra, … Paolo Biancone

An exhaustive review of the metaheuristic algorithms for search and optimization: taxonomy, applications, and open challenges

Kanchan Rajwar, Kusum Deep & Swagatam Das

Stochastic home health care routing and scheduling problem with multiple synchronized services

Mohammed Bazirha, Abdeslam Kadrani & Rachid Benmansour

Avoid common mistakes on your 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

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
• Find a journal
• Publish with us
• Track your research

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

Preview improvements coming to the PMC website in October 2024. Learn More or Try it out now .

• Advanced Search
• Journal List
• Springer Nature - PMC COVID-19 Collection

Healthcare scheduling in optimization context: a review

Zahraa a. abdalkareem.

1 Faculty of engineering technology /Department of Computer Engineering, University Malaysia Perlis, Kanger 02600 Arau, Perlis, Malaysia

5 Department of Islamic English studies , Alimam Aladham university college , Baghdad, Iraq

Mohammed Azmi Al-Betar

2 Artificial Intelligence Research Center (AIRC) College of Engineering and Information Technology , Ajman University , Ajman, UAE

3 Department of Information Technology, Al-Huson University College Al-Balqa Applied University, P.O. Box 50, Al-Huson, Irbid, Jordan

Phaklen Ekhan

Abdelaziz i. hammouri.

4 Department of Computer Information Systems , Al-Balqa Applied University , 19117, Al- Salt, Jordan

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.

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. ​ Fig.1 1 and ​ and2 2 .

Number of covered article

Healthcare scheduling papers between 2010-2020

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. ​ Fig.2), 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.

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 ​ Table1 1 ).

Other healthcare problem in optimization context

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.

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.

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.

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 A D i , discharge date D D i , and time horizon for the elective patient should be fixed, and unchangeable.
• HC3: Time horizon should be continuous.
• HC4: Two patients ( P i 1 , P i 2 ) 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:

Default values of the weights of the cost components [ 18 ]

• 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 ​ Table2 2 .

Soft constraints weight [ 17 ]

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.

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).
• 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.
• 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.

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 ⋃ P M = P .
• P H is a set of in-patients and r p is the room occupied by in-patient where p ∈ P H
• D : is a set of days.
• R : the set of rooms and c r is the capacity of room r ∈ 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 ∈ 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 ∈ 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:

• 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 ∈ 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. 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. Z :the cardinally of a set Z . and 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 ( P d + - 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.

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.
• 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.

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.

PASP Data sets versions

The original data set which belong to the first version of the problem 1 is firstly reported by [ 17 ]. The data set consists of 13 instances as shown in Table ​ Table3. 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 ​ Figure3 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.

Data set 2 [ 13 ]

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.

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 ​ Table7 7 summarizes the patient admission scheduling problem versions, approaches, and data sets.

Summaries of PASP versions, methods, patients, and data sets

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.

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 ​ Table8, 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.

Nurse scheduling type shifts [ 40 ]

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.

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.

Nurse regulation

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.

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 ​ Table10 10 summaries of NRP and various version with its method, datasets, and categories

Summaries of NRP versions, methods,categories, and data sets

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.

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.

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.

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 ].

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.

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 ].

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 ∈ P ∪ 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 ). 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 edw E 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 rdw R 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 qdw Q is set of blocks that the patient undergo surgery in day d in week w . O b max overtime permitted by each block. O r max overtime permitted by each operating room. N s max 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 q b d w = 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: ∑ w ∑ d ∑ b ∈ B e E d w \ E q Q = e ∨ B qdw Q X qbdw ⩽ 1 ∀ q 14 ∑ q t ¯ q X qbdw ⩽ ( y bdw C bdw ) + O + bdw ∀ b , d , w 15

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 ​ Table11. 11 . Whilst, Table ​ Table12 12 presents the statics outcomes, and the experiment design for the generation of theoretical instances shown in Table ​ Table13 13 https://www.utwente.nl/en/choir/research/BenchmarkORScheduling/introduction .

Experimental design for real-life instance generation [ 83 ]

Statistics of the outcome

Shows the experiment design for the generation of theoretical instances [ 83 ]

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 ​ (Table14 14 )

Summaries of OR method,version,data sets,categories

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 ​ Table3 3 presents the surgery scheduling problem and the respective methods employed and patients categories.

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 ​ (Table14) 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 ​ (Table15). 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.

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 – 125 ], home healthcare [ 126 – 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.

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.

Declarations

The authors declare that they have no conflict of interest.

1 https://people.cs.kuleuven.be/wim.vancroonenburg/pas/

Contributor Information

Zahraa A. Abdalkareem, Email: moc.liamg@51020102aarhaz , Email: ym.ude.paminu.liamtneduts@nandaaarhaz .

Mohammed Azmi Al-Betar, Email: oj.ude.uab@ratebhom .

Abdelaziz I. Hammouri, Email: oj.ude.uab@zizA .

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• My Account Login
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• Open access
• Published: 06 October 2021

Optimization of an appointment scheduling problem for healthcare systems based on the quality of fairness service using whale optimization algorithm and NSGA-II

• Ali Ala 1 ,
• Fawaz E. Alsaadi 2 ,
• Mohsen Ahmadi 3 &
• Seyedali Mirjalili 4 , 5  

Scientific Reports volume  11 , Article number:  19816 ( 2021 ) Cite this article

13k Accesses

46 Citations

4 Altmetric

Metrics details

• Engineering
• Health care
• Mathematics and computing

Effective appointment scheduling (EAS) is essential for the quality and patient satisfaction in hospital management. Healthcare schedulers typically refer patients to a suitable period of service before the admission call closes. The appointment date can no longer be adjusted. This research presents the whale optimization algorithm (WOA) based on the Pareto archive and NSGA-II algorithm to solve the appointment scheduling model by considering the simulation approach. Based on these two algorithms, this paper has addressed the multi-criteria method in appointment scheduling. This paper computes WOA and NSGA with various hypotheses to meet the analysis and different factors related to patients in the hospital. In the last part of the model, this paper has analyzed NSGA and WOA with three cases. Fairness policy first come first serve (FCFS) considers the most priority factor to obtain from figure to strategies optimized solution for best satisfaction results. In the proposed NSGA, the FCFS approach and the WOA approach are contrasted. Numerical results indicate that both the FCFS and WOA approaches outperform the strategy optimized by the proposed algorithm.

Similar content being viewed by others

Multi-criteria assignment problems for optimising the emergency medical services (EMS), considering non-homogeneous speciality of the emergency departments and EMS crews

Mariusz Drabecki, Eugeniusz Toczyłowski, … Klaudia Kułak

Two-stage multi-objective optimization for ICU bed allocation under multiple sources of uncertainty

Fang Wan, Julien Fondrevelle, … Antoine Duclos

An operations research approach to automated patient scheduling for eye care using a multi-criteria decision support tool

Luke Evans, Jennifer H. Acton, … Daniel Gartner

Introduction

The fundamental role of healthcare systems is to provide low-cost, timely, and relevant access to health services for all patients. The purposes of such scheduling can be divided into minimizing the cost of services, maximizing patient satisfaction, minimizing waiting time, maximizing Fairness policy, and cost efficiency in healthcare 1 . One of the crucial issues in healthcare is fairness, which is a method of assigning resources to healthcare such that all patients get, on average, an equal share of resources over time when a patient is admitting, that patient uses the complete services this policy always shares between patients (include in regular and emergency one) and doctors. Aside from fairness in appointment scheduling, further encouragement is achieved through a novel gain framework unique to the division and was not reported previously. Another critical issue on fairness is in mending personal scheduling preferences that mean each doctor has his or her scheduling preferences 2 . In making a schedule, these should be met as much as possible. Appointment scheduling is a system that makes access to healthcare facilities manageable and results from efficient and successful healthcare services. In this way, the planning of appointments leads to patient satisfaction. The planning of appointments is used for various sections, initial visits, individual visits, and optional operations. For first clinics, doctors split their time into individual or multiple slots based on their appointments. The rules of access to primary care also depend on patients’ urgency and the quality of services. For example, first emergency cases are scheduled, and patients are regularly visited or followed up. Also, some clinics allow open access systems that designate patients the same day, irrespective of urgency. Besides the advanced access rules, primary care providers should also accept walks daily that can cause other scheduled patients to wait directly 3 . Like primary clinics with equal time slots, time slots have a high variation in specialty clinics. Access regulations help to determine the time for each appointment and possible future urgent appeals 4 . The Whale Optimization Algorithm based on the Pareto Archive and the NSGA-II algorithm is presented to solve the appointment scheduling model using a simulation method. This article explored the multi-criteria technique in appointment scheduling using these two algorithms. This article computes them using multiple assumptions to satisfy the analysis and diverse aspects connected to WOA and NSGA. In the last part of the model, this article evaluated NSGA and WOA with three examples, as well as the fairness policy first come first serve (FCFS), to determine the essential element to consider in order to achieve the most significant satisfaction outcomes from the figure to strategies optimal solution.

The structure of the paper is as following sections. In the “ Introduction ” section, the background of the problems and motivation of the research are presented. In the “ Literature review ” section, a brief review of the state-of-the-art research and the advantages and disadvantages of some methods are illustrated. In the “ Proposed approach ” section, the features of the presented algorithm are illustrated. Moreover, in the “ Methods and materials ” section, the sequential appointment scheduling process is described. In the proposed structure of the WOA algorithm, a recovery procedure is designed that applies and improves the solutions. Also, in the “ Results ” section, the proposed method’s finding is depicted in the computational and numerical analysis field. Furthermore, in the “ Discussion ” section, the overall findings of the presented method are illustrated and compared with other techniques. Finally, in the “ Conclusion ” section, the summary of the results focusing on the future works is provided.

Literature review

This section provides a brief review of the state-of-the-art research and the advantages and disadvantages of some methods. Moreover, the results of the papers are explained. Dogru and Melouk 5 stated that the distinction between in-patients and the hospital’s outpatient is traditionally not so clear. Recently there was a move from hospital to ambulatory care where more patients were treated in space for ambulatory treatments. Takashima et al. 6 presented that the emergency department is also an entry route. Such patients are usually referred to as emergency patients at the outset of their treatment status. This paper is hospitalized once admitted to a normal unit. This research focuses on outpatient scheduling problems, with limited reference to the most relevant literature on general patient scheduling problems, as these two topics somewhat overlap. On the other hand, Zhang et al. 7 presented a new numerical programming model for an expanded open shop issue with clinic prices for an Integrated Practice Unit (IPUs). The new model addresses its benefits and presents some essential inequalities to improve linear programming relaxation. The purpose of the issue is to minimize a combination of makeup and overall working time or an IPU to reduce closing time and maximum patient waiting time.

The arrival times for a patient series were called decision indicators by Zhang et al. 8 . The model seeks to reduce the weighted costs generated by a patient’s waiting period, server overtime, and server acceleration due to overcrowding. This paper presented suitable mathematical formulations for this approach as a model for Simulation Optimization (SO) and a Stochastic Integer Programming (SIP) model. Cayirli and Yang 9 proposed that the influence of these optimization programming factors is calculated using the ideal concept that already changes patients’ appointment times to minimize the adverse effects of these factors to the exclusion of their residual or actual impacts on overall cost efficiency. Sauré et al. 10 introduced ways to overcome these two challenges; they expose a framework incorporating stochastic service times with the advanced scheduling problem. This way, this paper considers the waiting time before the service day and the free time-workload on the service day of the health care service. It is a standard procedure for a patient to contact the hospital a couple of days in advance to book an appointment the day they decide to see the doctor. The main factor affecting both operating performance and patient satisfaction is timely access to outpatient clinics. Some well-crafted appointment plans would provide adequate care to the patient without increasing Laganga and Lawrence 11 . Thankfully, most healthcare providers face long waiting times. This concept is complex by a no-show, variability of service time, and the patient’s desired appointment. The healthcare staff’s work environment significantly influences the patients’ health. Therefore, strengthening these conditions will contribute to the effectiveness of the treatment process being improved. It is understood that productive workforce efficiency has always been a vital concern of any enterprise and one of the most effective methods of achieving productivity benefits. For this reason, staff and patient scheduling are a field that has become particularly critical in certain high-demand and often restricted staff healthcare facilities. As the healthcare requirement increases, appointment scheduling significantly impairs the capacity utilization of healthcare care and service quality. However, the hospital appointment scheduling is limited by several factors such as lack of spaces, number of beds, outpatient category, and surgical schedule. Considering that these variables complicate appointment scheduling, the conventional fairness strategy for first come-first serve (FCFS) cannot guarantee performance. Also, the two primary objectives of healthcare services, i.e., increasing the capacity utilization of medicinal resources and keeping fairness, usually challenge one another. Thus, an adequate and fair strategy is demanded appointment scheduling of outpatients. As described above, the growing demands for this service require appropriate patient and staff schedules to guarantee the total number of patients benefiting through high labor force use. In addition to increasing the number of patients, balancing the physiotherapist workload, and keeping a daily schedule is often crucial. For them, the case study is performed in the physiotherapy department of the Shanghai United Hospital because of hard-working constraints. Lastly, the selected patients are scheduled throughout a working day to minimize their waiting time. Harper et al. 12 developed a simulated model for controlling and preparing beds in healthcare centers.

Hutzschenreuter et al. 13 designed an outpatient flow structure. They implemented an operator method to allow for an optimal mix of patients from different departments. Demeester et al. 14 built a hybrid Tabu search algorithm that allocates beds in the proper units to outpatient clinics. Both algorithms above are run regularly to do the scheduling job. However, everyday scheduling optimization cannot always assure the algorithm’s improved long-term effect. Zhang et al. 15 assigned its robustness, and global convergence capability defines it. Thus, the Genetic Algorithm (GA) is fit to solve the problem of appointment scheduling. This paper discusses a new GA for optimizing the selection policy for fairness, separate from all the above strategies in the following paragraphs. In time, the algorithm reviews optimization of a long-term admission plan rather than directly doing the scheduling research. In order to make the equity more reliable than a discrete event simulation model, it is necessary to use discrete event modeling techniques if the mechanism under study can be represented as a series of operations naturally. For instance, agent-based modeling might be the solution if the behavior, rather than attempting to construct a global workflow, is easier to explain than to attempt. Likewise, group dynamics should be extended if you are interested in aggregate values and not in the relationship of individual units. The simulation model measures the value of the normal function, which is contrasted with the mathematical model below. The hospital healthcare system that will be analyzed here has a discrete event structure. As previously mentioned, much software has been released for this purpose, which can be named ANY LOGIC software 16 , one of the most popular professional simulation software. For instance, a new optimization algorithm named WOA has been recently developed by Mirjalili and Lewis 17 for meta-heuristic algorithms. It is known that whales are the most intelligent aquatic species. Humpback whales’ unique hunting activity is the main inspiration of the WOA algorithm. Humpback whales use a hunting method called the bubble net feeding system. WOA has been widely used in the literature to solve different optimization problems.

Emary et al. 18 introduced a WOA-based feature choice method. The introduced variants and the original algorithms were benchmarked using unimodal, multimodal, fixed-dimensional, and composite benchmark functions. The test was performed using a series of assessment metrics that show the potential of the proposed models to outperform. Reddy et al. 19 also implemented an original strategy to solve feeder reconfiguration to minimize significant total loss and optimize energy savings in a spaced distribution network by using the algorithm for whale optimization. Anand and Dinakaran 20 used WOA to limit the size of the resources of the optimally distributed generator (D.G). Such tools were the small-scale power generation plants that can provide power in the distribution system to households, businesses, or industrial types of equipment. Besides, Nasiri et al. 21 suggested a WOA-based clustering approach and demonstrated the W.O’s merits. In classifying area too. Although the original version of WOA was successful, some works suggested that its performance could deteriorate when some issues were resolved by Jadhav and Gomathi 22 . The Simulated Annealing (SA) algorithm was applied by Mafarja and Mirjalili 23 as a local search method to enhance the WOA to choose the optimal subset of features to develop classification accuracy. Ling et al. 24 used the Lévy Flight for regional optimization to improve the WOA. However, the WOA weight algorithm has been suggested by Dong et al. 25 . The developers hybridize WOA with a pattern analysis technique to overcome maximal power flow problems. Jiang and Deng 26 showed that the whales attack the prey by circling spirally around them and releasing bubbles in a circular shape. It is established that there are many types of WOA modifications and implementations. It is impossible to compare each new proposed WOA with all other types. There are different benchmark functions, which can be used to test any new modifications. According to the research findings, the Non-dominating Sorted Genetic Algorithm (NSGA-II) and the WOA have been investigated in the healthcare sector. WOA outperforms other standard algorithms in terms of computation time and harmonizing utilization by addressing Pareto optimal solutions. When compared to WOA, its variations and comparison with standard measurements also perform well.

Proposed approach

In this section, the features of the presented algorithm are illustrated. We explain the algorithm using AnyLogic professional: V8.7.3 16 , which can simulate and carry out discrete, agent base, and system dynamics simultaneously. Although this software can simulate general numerical spectra of processes, it has many specialized pallets for road transport research issues, Railroads, and even simulations of the transmission lines of liquids, which can be seen in Fig.  1 . This paper has introduced a new algorithm for this research based on GA: The whale optimization algorithm (WOA) has the same structure as the traditional WOA for optimizing scheduling techniques, except that a local search operator is introduced to optimize solutions. The WOA algorithm includes three operators modeling humpback whale’s behavior in the beast quest, prey encircling, and bubble-net behavior. In this research, the proposed model is solved with the random WOA essence of the meta-heuristic algorithms, and exactly which algorithm is superior cannot be stated. This paper is also seeking to use relatively new algorithms to solve the model in the current research. By comparing them with the well-known Non-Dominated Sorting Genetic Algorithm (NSGA-II) algorithm, they evaluated their performance scientifically and practically for the problem under investigation.

Proposed flowchart for the whale optimization algorithm.

The WOA starts with a random set of solutions. According to each search factor, the search agents arbitrarily change their location with the best solution obtained in each iteration. Parameter A is lowered from two to zero to provide discovery and exploitation. The location of the quest agents can be updated in two ways. The random search agent is selected if \(|A|>1\) ; otherwise, the best solution is selected. Depending on the p-value, the whale can switch between two spiral and rotational motions. Ultimately, the whale’s algorithm ends after reaching the set satisfaction criterion. The following is the pseudo-code of the algorithm. There are two stages of mining and discovery in the WOA. In the operating phase, the strategy of the bubble-net attack is used to demonstrate the process based on the current optimum search agent. This attack involves two methods, including pride and spiral swimming. Each whale changes its location independently in the discovery process, depending on the randomly selected search agent. As seen in the following tables, the runtime of the algorithms shows that runtime values and runtime comparisons indicate that the multi-objective WOA has a higher resolution time. Because of the proposed structure of the proposed method, this method intelligently searches many points of the answer space in each iteration. This method consumes more computational time than the NSGA-II method. According to the comparison findings, the WOA can supply higher-quality replies than the NSGA-II algorithm. The whale method is better capable of identifying and retrieving the active region than the NSGA-II algorithm. It can provide more excellent dispersion responses than the NSGA-II algorithm.

Methods and materials

Description of the sequential appointment scheduling process.

Once the hospital generates outpatient appointment service, the hospital manager is constantly faced with a challenge for how many patients should be accepted when slots are assigned to these patients in the surroundings. A sequence of patients is calling in to request an appointment in the future session. Patients arriving at the hospital are split into two groups: regular patients and emergency hospital admitting patients. Urgent outpatients are often admitted as long as they follow normal patients. The fairness principle is followed. Emergency patients at both stages shall be served without a line upon entering one of the triages, doctors, pharmacy, laboratory, or radiographic units. However, to assume another emergency patient is on the queue list of waiting places. In this case, the newly arriving emergency patient will be put in the emergency service line until the screening of the former emergency patient is complete. The critical aspect to note is that doctors may understand that regular patients should be treated in an emergency during the visit, which has also been considered in the model. The start number for patient servers (referred to in the program as the resource) is used as the default slider number in each section to initiate the method. For further explanation of the model, Ordinary and emergency patients are logged in with the distribution functions stated in the tables in the preceding Fig.  2 , marked with NormalEnt and EmergenctEnt , respectively. The number inserted next to each indicates that several patients of each type were logged in at this particular moment. There were 76 regular patients and one emergency patient. It shows that all 76 patients admitted to the hospital entered the admission ward, and 51 were admitted to the triage ward. The model assumes that the change in fairness policy does not include people being serviced. The upper left number indicates the number mentioned. The high correct number indicates the current busy patients who are checking by doctors. That will be the maximum number of personnel assigned to each department. In the figure above, after a patient is diagnosed in the triage department, the doctor is examined (FirstPhysicianCheck1 station).

Simulation model of appointment scheduling for two different patient type.

In this case, several events may occur:

The doctor determines that the patient does not need treatment or is healthy and requires no special treatment. The Sink is Health counters the number of these patients.

The doctor realizes that the patient will better by getting the drug, so by writing a prescription and following the patient’s medication, whose statistical distribution is listed in the above tables, the patient is an exit from the ExitPharmacy , which when taken, is one Logged out of this port.

As shown in the figure, the doctor will send the patient to the radiography. After viewing the photograph taken by the physician and taking medicine from the pharmacy, it will be removed from the ExitRG port.

Alternatively, the third part of the laboratory will happen instead of the radiography. The patient will eventually exit the ExitLab portal.

In another case, the patient is referred to because of their specific conditions to the radiographic and laboratory departments. After seeing the results by the doctor, the outpatient then walks to the clinic and leaves the ExirRGLab portal after taking the drug.

In the other case, the doctor will prescribe that patient be admitted to the ward or according to the patient’s condition. It should be transported to a specialized hospital where that can take better healthcare services. On the other hand, for an emergency hospital or patients whose doctor determines they have emergency conditions, the route is described for regular patients except for the higher priority (Fairness) considered for this patient segment. None of these people, in the regular client queue, will have the slightest delay, and as soon as they enter each part, they will be dealt with out of the queue, as shown in Fig.  3 .

A simulation model for emergency patients with high priority fairness policy.

The equity priority for each patient specified in the settings option is set at zero for regular patients and 2 for emergency patients. These two parameters are optional and should be perceived as a higher amount for emergency patients. There are only two types of patients; no matter what name is found will make any difference. Also, emergency patients should be given priority over regular patients. This paper calls the system run with the values of the initial parameters run 0. At this stage, it is observed that this paper has about one efficiency in the acceptance section.

To determine if an increase in the number of admissions can reduce waiting times and keep performance at a high level, this paper will increase the number of individuals in the admission department in a few steps to maximize the number of people who can keep getting high. In Fig.  4 . After raising the number from three to six and hitting the number six (blue), this paper sees a substantial decrease in output. This paper base the number 5 on the research and continue with the simulation model. Moreover, this is what this paper call run 1.

Admission section efficiency in a different run in the admission department.

Problem statement

The difficulty is a fixed number of similar outpatients I scheduled over a D-day planned period. Every other day consists of T-periods, specified in increments of 1 h. This paper suggests a problem of mid-term scheduling, where lineups are produced for up to several weeks. The appointment cannot move over to the next day of preparation. At most, one admits starting per day is permitted in this discontinuous planning problem. The outpatients have some distinctive features, such as minimum waiting period, maximum waiting period, the total time between successive admissions seeing a doctor, waiting time, and limits on overtime per week. According to the general waiting time rules, every shift must be given a lunch break within a specified period. This period is defined by the minimum amount of time on duty before and after the break. Besides, all the changes allocated to one or more physicians may fulfill a specific start time window to account for the patient or general preferences. Due to the number of empty beds and a particular policy like the FCFS, the hospital accepts satisfied patients in the waiting line each day. Provided that doctors and resources are restricted, the surgeries mentioned below are subject to certain constraints.

Patients suffering from eye trauma need surgery the day after they arrive. When the condition cannot be met, the patient may be automatically moved to another hospital.

Surgical treatment and other operations (except for ocular trauma surgery) should not be performed on the same day.

Some cataract patients need only one eye operation, although other patients need both eyes to undergo surgery.

First, the latter will have surgery for one eye, and 2 days later, surgery service on the other eye. When a patient is admitted for surgery, the patient must go through 4 stages before leaving the hospital. Figure  5 presents those four levels. Phase 1 is the stage of planning, in which the hospital prepares for the procedure. The patient waits for the surgery during step 2 if the process cannot be scheduled immediately after step 1. It implies that stage 2 is a waste of resources and can be minimized if a proper approach allows the patients to be admitted. Phase 3 is for the surgery, and step 4 is for post-operative resumption. This study suggests that all patients arriving are on time if they appear for their appointment and are presented following a first-in-first rule; the service times are identically and independently distributed exponentially across patients.

Noise signal in WOA.

As explained above, an outpatient’s situation determines the length of all steps and cannot be optimized. The second phase, however, includes a waste of sources, so it may its time. While wasting a patient’s time and money, step two also allows the bed resource unused to the max. In such healthcare delivery networks, the bed is one of the bottlenecks impacting healthcare services’ productivity levels. Moreover, reducing the average time of stage two improves the serving rate. The policy is fair but potentially ineffective if the department sticks to the fairness policy. The fairness policy will result in a more extended average period of stage two.

On the other hand, if the unit accepts only outpatients with the required minimum stage two times (and this is a greedy strategy), there may be appointment disparity among different patients, which may eventually affect the system’s effectiveness. Furthermore, a strategy other than fairness and greedy is required for an effective and equitable health service. The optimization goal in this work is to find an optimal approach to minimize the waiting time and ensure fair and comfortable treatment of all types of patients. This paper refers to GA. To the question of seeking an efficient and equitable appointment scheduling method rather than directly scheduling the appointment. Therefore, the algorithm is tested only once for a suitable strategy to compare with the simulation of discrete events to determine the policy will be fair and equal to accept. All the scheduling work is done daily following the optimized strategy.

The overall problem was split into three sequential and logical levels. It was pretty tricky and impractical for even small-size test problems to solve the entire problem in a single phase within a reasonable time. As described, arranging and consulting the patient scheduling to a clinic is the issue under discussion. It is assumed that the hospital has the M department. Each section has a different number of operators to process different operations. Also, each section can only perform some services. This system has n patients, some referring to emergency patients and some as regular patients. Each patient has several operations that must be completed in different sections. Besides that, it might, while planning, have a patient diagnosed as an emergency patient. Generally, emergency patients are visited before regular patients in this model and have higher priority (Fairness). After doing some actions like visiting a doctor, the diagnosis may be based on the hospitalization of the patient, in which case the patient is referred to a hospitalized ward with a limited number of beds.

As mentioned above, Eq. ( 1 ) is one of the goal functions: to minimize patients’ mean total weighting time. Equation ( 2 ) is another purpose that reduces patient dissatisfaction due to increased patient waiting time in the hospital. Constraint ( 3 ) states that each patient’s operation can only be examined or processed in a single position in one ward. Constraint ( 4 ) ensures that the maximum number of people (operators) can be allocated to patient operations in each segment. Constraint ( 5 ) assigns zero position to each imaginary patient. Constraints ( 6 ) and ( 7 ) set the time of begin and finish of processing of the first position of each segment assigned to the imaginary patient, respectively. It equals zero. Also, these Constrains indicate that all units are available at zero moments and are ready to receive patients. Constraint ( 8 ) prevents a patient from assigning an operation to the position of a segment if the other area is empty. It constrains guarantees that patients will be sequenced in a single sequence. Constraint ( 9 ) indicates that the start time of each sequential position of the ward is more extended than when the patient was in the hospital. Constrain ( 10 ) suggests that each sequence’s start time is longer than the required for completing the place before that segment. Constraint ( 11 ) ensures that the start time of each sequence position is longer than the minimum time required to complete the primary operations of the patients being processed at that position. Since more than one operator per processor per section, the “minimum completion time” is set to visit the next patient as soon as the first operator is idle. Constraint ( 12 ) states that the time elapsed for each processing position in the ward is equal to when it began, plus the processing time for patients assigned to that position. Constraint ( 13 ) guarantees the processing of operations based on their sequence in each patient’s schedule, which is specified because of referral (or illness). The constrain means that the following process will not start until the prerequisite operation is completed and completed. Constraint ( 14 ) indicates the priority of emergency patients over other patients. This group includes patients who are initially admitted as emergency patients. This constraint guarantees that in all departments and situations, these patients will be visited before regular patients. Constraint ( 15 ) indicates the priority of emergency patients over other patients. This group includes patients who have been identified as emergency patients during the planning process. This constraint guarantees that in all departments and situations, these patients will be visited before regular patients. Limit ( 16 ) is applied to select the part to operate the pieces capable of showing it. Constraint ( 17 ) is considered to calculate the completion of patients’ operations according to the selected sequences. Constraint ( 18 ) ensures that the number of hospitalized patients does not exceed the available beds. Constraint ( 19 ) specifies the range of values allowed for the decision variable.

Improving the procedure

In the proposed structure of the WOA algorithm, a recovery procedure is designed that applies and improves the solutions selected in the previous section. Improvement outputs are selected as the population of the next iteration of the algorithm. Implementation of the improvement procedure in this research is based on a variable neighborhood search (VNS). The VNS structure uses four Neighborhood Search Structures (NSS). These structures are used in VNS format, and their general structure is as follows Kardani-Moghaddam et al. 27 .

Each of the solutions in the population is answered to the VNS algorithm, and a response will be output. The corrective procedure will then be applied to the rest of the answer matrices. It will modify and replace the input answer as appropriate. The overall structure of the recovery procedure will be as follows:

Fairness algorithms in appointment scheduling

Fairness is an important issue to examine in appointment scheduling methods to give excellent service to patients arriving at various periods. In this part, the mathematical modeling is developed to include fairness. This section sets an NSGA-II (Non-dominated Sorted Genetic Algorithm) for handling sequential appointment scheduling with care delivery and fairness constraint (FCFC). NSGA-II is a well-known multi-objective optimization algorithm, quick sorting and powerful. Input parameters, including cutting speed, feed rate, flow rate, etc., are necessary conditions for optimizing the machining operations to reduce or maximize the machining efficiency.

Mutation operator

In this research, to implement the mutation operator, this paper used four neighborhood search structures described in the initial solution production section, such that a random number is generated between 1 and 4 and then given the production number One of the first, second, third, or fourth structures applies to the answer.

Intersection operator

The intersection operator designed in this algorithm is described below. This paper first assigns a number according to the patient number. For example, suppose this paper has four patients, each involving four operations. The number of wards in the hospital equals four. The procedure for assigning the number to the patients is shown below. In the following matrix, the numbers given below the operation are assigned an operation number. In this way, they are displaying the answers to combine the answers changes to three lines. Below is an instance of how to get creative with this line.

The differential between the maximum and minimum average waiting time, developed and implemented, is applied as a fairness constraint where α represents the acceptable threshold level.

The practical procedures of a scheduling policy for appointment scheduling with patient choice and service fairness in opinion as below:

Patients who refuse to admit the approval will be sent away. The method concludes each given call-in slot when no further profit is achieved by scheduling additional patients, or no intervals can be scheduled that satisfy the fairness requirement at the same time.

Computational analysis

As mentioned, the present paper deals with the presentation and solution of the appointment scheduling problem model in the hospital. In this regard, a two-objective mathematical model concerning fairness in fuzzy conditions is presented. The WOA algorithm based on the Pareto Archive and NSGA-II algorithm has been used to solve the model in this research. In this part of the research, the results of model solving for various problems are presented. The performance of WOA and NSGA-II is benchmarked. To test the efficiency of the proposed whale algorithm, the algorithm was implemented in the MATLAB software environment 28 . The results of its implementation in a sample problem as a case study and practical problems done by GAMS version 24.9.1 software 29 was compared with the results obtained from the NSGA-II algorithm. The remainder of this chapter describes the computational results. All the calculations were done with the i7 7500U 12 GB–1 TB–R5 M335 4 GB Core computer. Whale population size parameters, number of variable neighborhood search iterations and number of iterations in the whale optimization algorithm and population size parameters, mutation rate, intersection rate, and number of iterations in the NSGA-II algorithm are among these parameters. To adjust the settings of the whale algorithm, the values of each of these parameters are studied at three levels, which are shown in Table 1 .

In addition, to adjust the parameters of NSGA-II, two settings of mutation rate and intersection rate at three levels and population size at three levels have been studied. These levels are shown in the following Table 2 .

Moreover, each problem is executed for each of the combinations mentioned above, and the gap criterion for each problem is computed. Finally, the corresponding graph is plotted. Also, for designing the parameter, the Taguchi experiment with the L9 method was used. The orthogonal table for the two algorithms is shown in Table 3 .

Figures  5 and 6 illustrate the parameter analysis of the Taguchi method, as shown in Fig.  5 . Also, where population size is at level 2, the number of algorithm iterations at level 2, and search Neighborhood is sufficient at level 1. In WOA, the population size is 150, the number of VNS repeats is 5, and the number of iterations is 300. Figures  7 and 8 show the Taguchi method for parameter adjustment, as seen in Fig.  7 , level 3 for the jump rate and level 1 for the intersection rate; Level 3 is more effective for replicating the algorithm and population size. Therefore, 300 for population size, 500 for algorithm replication, 0.01 for mutation rate, and 0.75 for intersection rate are considered (see Table 4 ).

Average effect on WOA.

Noise signal in NSGA algorithm.

The average effect in NSGA algorithm.

Numerical analysis

The objective of numerical methods is to examine the algorithm’s ability and provide some perspectives into facilitating realistic appointment scheduling. Firstly, two examples are given in this section to demonstrate the application of the two myopic scheduling algorithms. This paragraph analyzes the execution of the presented integrated whale algorithm and the NSGA-II algorithm to solve the designed problems. To evaluate the validity of the model, two small-scale issues are addressed by the whale algorithm. Details of the parameters and results of solving these two problems are presented below. The first problem consists of three patients and three sections, the parameters of which are shown in Table 5 .

As seen in Fig.  9 , Patient 3, as an emergency patient, is admitted to the first and third ward before other patients. Completion times for patients 1 to 3 are 26, 14, and 11, respectively (see Table 6 ).

Optimal patient scheduling for the three patient and three ward problem.

Besides the mentioned problem, there is a further problem with 5 patients, and 4 units have been solved. The parameters related to this problem are presented in Table 7 .

From Table 8 , NSGA-optimized approaches outperform FCFS and the WOA f1 approach in all five instances. The proposed NSGA meets the WOA Strategy on the second level but does not surpass the FCFS Strategy. Nevertheless, for its poor performance in f1, the FCFS approach is not successful. The results are consistent with the suggestion that the FCFS approach provides a fair system but does not consider capital. The implications of the greedy technique on f1 are because patients are admitted only based on the estimated duration of stage 2 but without any regard to the difference between the entries of various patient groups. Case 3 comes from a hospital, and the results in contrast with example 1 and case 2 are relatively odd. Therefore, an optimal strategy is difficult to achieve in this situation. In case 3, NSGA manages to outdo the WOA and the FCFS approach. However, their dominance is not as evident as in example 1 and case 2. The distribution of f1 and f2 values, in example 1 to case 3, is shown in Fig.  10 . The target values of the strategies developed by NSGA, the FCFS strategy, and the WOA strategy are illustrated.

Distribution of objective function attributes in different theory situations.

Figure  10 reveals that almost half of the solutions found by NSGA are better f1 and have better f2 than FCFS and WOA. Practically, all of the answers given by NSGA are better f1. Based on Fig.  10 , considering the above, this paper suggests an NSGA designed to improve healthcare admission approaches for patients. This paper develops a chromosome coding scheme to optimize admission strategies to identify the assessment functions for two goals: efficiency and fairness. The introduced algorithms use hospital historical information. This paper, the algorithm proposed, will solve other difficulties with changed constraints without adjusting the coding strategy and the algorithm structure. Studies are carried out on three occasions, and the solution implemented by the proposed WOA is contrasted with the policy of justice and the strategy of NSGA. Numerical findings indicate that both the Fairness and WOA approaches are outperformed by the method optimized by the proposed algorithm. Most patients would be handled equally due to the fairness policy.

This study randomly generated two algorithms and solved several practical problems to compare two WOA and NSGA-II. Comparative results for solving these problems according to the indices presented in Tables 6 and 7 are shown. The following table shows the difficulties in n/m, where n represents the number of patients and m the number of wards. Also, for solving the sample problems, the model parameters are set as follows: In the fuzzy settings, to produce triangular numbers \(({m}_{1}, {m}_{2}, {m}_{3})\) , the first m2 is constructed, and then a random number r is generated in the interval (0,1) and m1 using the relationship of \({m}_{2}\times (r-1)\) and m3 with Using the relation \({m}_{2}\times (r + 1)\) will be produced. For determining fuzzy parameters, \({m}_{2}\) are randomly assigned, and two values of m1 and m3 are determined using MATLAB R2015a (MATLAB 8.5). For this reason, only the amount of m2 is set in the parameter setting of this parameter.

Uniform distribution over the interval produces patients’ weights and weights of completion time [1, 9].

Processing time for patient operations inwards is generated using a uniform distribution over the interval [100,1].

The job preparation time is produced uniformly between 20 and 40% of the average completion time.

The comparative results in Tables 9 and 10 and the charts on the relative indices show that the whale algorithm is, in all cases, more capable of producing better quality responses than the NSGA-II algorithm. The whale algorithm can produce higher dispersion responses than the NSGA-II algorithm. In other words, the whale algorithm is more capable of detecting and extracting the active region than the NSGA-II algorithm. As shown in the tables above, the NSGA-II algorithm produces higher-order solutions than the WOA. The epsilon constraint method produces Pareto optimal solutions to variable and linear scheduling problems in which all criteria and decision variables take on numerical values. The suggested method is illustrated with four benchmark functions in addition to the WOA and NSGA methodologies in the health appointment scheduling problem. The epsilon constraint method and its variants have been applied in many systems and applications described as an essential way to solve multi-objective linear programming problems and preferred over competing techniques. However, it comes down in this research in the camper to WOA. These weaknesses are summed up by the useless managing of the actual quality and Pareto analysis statements of the optimal solutions and the significant time required to implement it as more objective functions are introduced to a problem. The epsilon constraint algorithm optimizes one objective function while treating all other objectives as constraints. Although the model is widely used for multi-objective linear programming problems based on computational and results, we still limit ourselves to using WOA to solve this constraint as more benefits are obtained.

As seen in the following Tables 9 , 10 and 11 , the runtime of the algorithms show that runtime values and runtime comparisons indicate that the multi-objective WOA has a higher resolution time. Because of the proposed structure of the proposed method, this method intelligently searches many points of the answer space in each iteration. This method consumes more computational time than the NSGA-II method. According to the comparison findings, the WOA can supply higher-quality replies than the NSGA-II algorithm. The whale method is better capable of identifying and retrieving the active region than the NSGA-II algorithm. It can provide more excellent dispersion responses than the NSGA-II algorithm. Also, Low divergence and simple localization are downsides of the WOA compared to the NSGA. However, the WOA’s advantage is clear. The neglect demonstrates that the WOA algorithm used in the fairness application outperforms the regular NSGA in both global and local searches.

Overall, the present paper dealt with the presentation and solution of the appointment scheduling problem model in the hospital under the fairness approach. A two-objective mathematical model concerning fairness in fuzzy conditions was presented. WOA and NSGA-II algorithms were employed to solve the model as two multi-objective optimization algorithms. In addition to these two algorithms, this paper discussed multiple strategies in appointment scheduling. This paper has calculated WOA and NSGA with different hypotheses to satisfy the evaluation and patient-related variables in hospitals and the final part of the model. Finally, this paper has three case studies on NSGA and WOA plus a fairness strategy. Then this paper computed the FCFS to find the most crucial element obtained from the figure to scenarios optimized by the proposed NSGA contrasted with the FCFS and WOA. Experimental results show that the approach optimized by the proposed algorithm outperforms both the FCFS and the WOA strategies.

Besides those algorithm optimizations for this paper, this paper discussed a simulation model for two types of patients in normal and emergency conditions. In contrast, it has been modeled in Any Logic simulation software based on doctors, beds, and other services. In the simulation section, this paper found that the fairness objectives for each patient in the settings option were set at zero for regular patients and 2 for emergency patients. In emergency patients, these two numbers are optional and can only be considered a higher amount. Since there are only two groups of patients, whatever amount is found will not make any difference. Then this paper simulates two types of patients with some random default data to gain the most propriety (Fairness) results and patient satisfaction. Knowing this final results efficiency comes out, this paper calls the system run with the values of the initial parameters run 0. At this stage, it is observed that this paper has about one efficiency in the acceptance section. To determine if an increase in the number of admissions can reduce waiting times and keep performance at a high level, this paper will increase the number of individuals in the admission department in a few steps to maximize the number of people who can keep getting high. Other uncertainties can be added to the models for future research, such as available time of service and patients in urgency. Several case studies on the subject of simulation optimization explain lognormal service time. To what extent it will affect the income, and the optimum allocation of intervals remains unclear. Another possible direction would be to model the correlations between various doctors. The free doctor will help diagnose some of the patients when one doctor is loaded. Cooperation also occurs when the data is released among doctors. Patients may pick a different doctor instead of the primary care provider appointed.

Abbreviations

Numbers of patients

Patient index

Patient condition mode 1 = Emergency/0 = normal

Number of departments (admission, triage, pharmacy, lab, etc.)

Number of operations related to patients

If it is possible in m section to diagnose hospitalization = 1/otherwise = 0

Number of beds in each section

i Th patient arrival time

j Th operation of i th patient

The number of people in the m th department who can process the patient for o ij operations

Fuzzy processing time O ij operation in section m th

This parameter indicates the permissibility of processing O ij in the m th section, which equals 1 if the O ij operation is permitted in the m th section; otherwise, it is 0.

Indicates the position or queue in sections

Decreased patient satisfaction rate due to increased overwriting and cost

The rate of i th patient fairness is fuzzy

The parameter is the same as 1 if the action O ij is done in section m th at position i th. Otherwise, it is equal to 0.

The parameter is the same 1 if the action O ij is done in section m th at position i th emergency patient; otherwise, it is equal to 0.

The parameter is the same 1 if the action O ij is done in section m th at position i th the diagnosis is based on the patient’s hospitalization; otherwise, it is equal to 0.

The start time of the practical processing that is in the l th position of the m th part

The end time of the practical processing that is in the l th position of the m th part

The start time of the practical processing in the l th position and the m th part

Abdalkareem, Z. A., Amir, A., Al-Betar, M. A., Ekhan, P. & Hammouri, A. I. Healthcare scheduling in optimization context: A review. Health Technol. (Berl.) 11 , 445–469 (2021).

Article   Google Scholar  

Zhan, Y., Wang, Z. & Wan, G. Home service routing and appointment scheduling with stochastic service times. Eur. J. Oper. Res. 288 , 98–110 (2021).

Article   MathSciNet   Google Scholar  

Shnits, B., Bendavid, I. & Marmor, Y. N. An appointment scheduling policy for healthcare systems with parallel servers and pre-determined quality of service. Omega (United Kingdom) 97 , 102095 (2020).

Google Scholar  

Dewi, S. K. & Utama, D. M. A new hybrid whale optimization algorithm for green vehicle routing problem. Syst. Sci. Control Eng. 9 , 61–72 (2021).

Dogru, A. K. & Melouk, S. H. Adaptive appointment scheduling for patient-centered medical homes. Omega (United Kingdom) 85 , 166–181 (2019).

Takashima, M., Schults, J., Mihala, G., Corley, A. & Ullman, A. Complication and failures of central vascular access device in adult critical care settings. Crit. Care Med. 46 , 1998–2009 (2018).

Zhang, P., Bard, J. F., Morrice, D. J. & Koenig, K. M. Extended open shop scheduling with resource constraints: Appointment scheduling for integrated practice units. IISE Trans. 51 , 1037–1060 (2019).

Zhang, Z., Berg, B. P., Denton, B. T. & Xie, X. Appointment scheduling and the effects of customer congestion on service. IISE Trans. 51 , 1075–1090 (2019).

Cayirli, T. & Yang, K. K. Altering the environment to improve appointment system performance. Serv. Sci. 11 , 138–154 (2019).

Sauré, A., Begen, M. A. & Patrick, J. Dynamic multi-priority, multi-class patient scheduling with stochastic service times. Eur. J. Oper. Res. 280 , 254–265 (2020).

Laganga, L. R. & Lawrence, S. R. Clinic overbooking to improve patient access and increase provider productivity. Decis. Sci. 38 , 251–276 (2007).

Harper, P. R. & Shahani, A. K. Modelling for the planning and management of bed capacities in hospitals. J. Oper. Res. Soc. 53 , 11–18 (2002).

Hutzschenreuter, A. K., Bosman, P. A. N., Blonk-Altena, I., Van Aarle, J. & La Poutré, H. Agent-based patient admission scheduling in hospitals. In Proc. International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, Vol. 3, 1733–1740 (International Foundation for Autonomous Agents and Multiagent Systems, 2008).

Demeester, P., Souffriau, W., De Causmaecker, P. & Vanden Berghe, G. A hybrid tabu search algorithm for automatically assigning patients to beds. Artif. Intell. Med. 48 , 61–70 (2010).

Zhang, J., Chung, H. S. H. & Lo, W. L. Clustering-based adaptive crossover and mutation probabilities for genetic algorithms. IEEE Trans. Evol. Comput. 11 , 326–335 (2007).

Sharbini, H., Sallehuddin, R. & Haron, H. Optimization of crowd evacuation simulation model in emergency situation. PalArch's J. Archaeol Egypt/Egyptol. 17(10), 850–863 (2020).

Mirjalili, S. & Lewis, A. The whale optimization algorithm. Adv. Eng. Softw. 95 , 51–67 (2016).

Emary, E., Zawbaa, H. M. & Sharawi, M. Impact of Lèvy flight on modern meta-heuristic optimizers. Appl. Soft Comput. J. 75 , 775–789 (2019).

Reddy, P. D. P., Reddy, V. C. V. & Manohar, T. G. Whale optimization algorithm for optimal sizing of renewable resources for loss reduction in distribution systems. Renew. Wind. Water Sol. https://doi.org/10.1186/s40807-017-0040-1 (2017).

Anand, R. V. & Dinakaran, M. Handling stakeholder conflict by agile requirement prioritization using Apriori technique. Comput. Electr. Eng. 61 , 126–136 (2017).

Nasiri, J. & Khiyabani, F. M. A whale optimization algorithm (WOA) approach for clustering. Cogent Math. Stat. 5 , 1483565 (2018).

Jadhav, A. N. & Gomathi, N. WGC: Hybridization of exponential grey wolf optimizer with whale optimization for data clustering. Alex. Eng. J. 57 , 1569–1584 (2018).

Mafarja, M. M. & Mirjalili, S. Hybrid whale optimization algorithm with simulated annealing for feature selection. Neurocomputing 260 , 302–312 (2017).

Ling, Y., Zhou, Y. & Luo, Q. Lévy flight trajectory-based whale optimization algorithm for global optimization. IEEE Access 5 , 6168–6186 (2017).

Dong, W. et al. Intelligent fault diagnosis of rolling bearings based on refined composite multi-scale dispersion q-complexity and adaptive whale algorithm-extreme learning machine. Meas. J. Int. Meas. Confed. 176 , 108977 (2021).

Jiang, T. & Deng, G. Optimizing the low-carbon flexible job shop scheduling problem considering energy consumption. IEEE Access 6 , 46346–46355 (2018).

Kardani-Moghaddam, S., Khodadadi, F., Entezari-Maleki, R. & Movaghar, A. A hybrid genetic algorithm and variable neighborhood search for task scheduling problem in grid environment. Procedia Eng. 29 , 3808–3814 (2012).

Hasanien, H. M. Whale optimization algorithm for automatic generation control of interconnected modern power systems including renewable energy sources. IET Gener. Transm. Distrib. 12 (3), 607–614 (2018).

Lohmann, T. et al. High-performance prototyping of decomposition methods in GAMS. INFORMS J. Comput. 33 (1), 34–50 (2021).

Download references

Author information

Authors and affiliations.

Department of Industrial Engineering & Management, Shanghai Jiao Tong University, Shanghai, 200240, China

Information Technology Department, Faculty of Computing and Information Technology, King Abdulaziz University, Jeddah, Saudi Arabia

Fawaz E. Alsaadi

Department of Industrial Engineering, Urmia University of Technology, Urmia, Iran

Mohsen Ahmadi

Centre for Artificial Intelligence Research and Optimization, Torrens University Australia, Brisbane, QLD, 4006, Australia

Seyedali Mirjalili

Yonsei Frontier Lab, Yonsei University, Seoul, South Korea

You can also search for this author in PubMed   Google Scholar

Contributions

A.A. and M.A. wrote and analyzed the main manuscript context and F.A and S.A.M. reviewed the draft manuscript.

Corresponding author

Correspondence to Seyedali Mirjalili .

Ethics declarations

Competing interests.

The authors declare no competing interests.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Cite this article.

Ala, A., Alsaadi, F.E., Ahmadi, M. et al. Optimization of an appointment scheduling problem for healthcare systems based on the quality of fairness service using whale optimization algorithm and NSGA-II. Sci Rep 11 , 19816 (2021). https://doi.org/10.1038/s41598-021-98851-7

Download citation

Received : 04 August 2021

Accepted : 08 September 2021

Published : 06 October 2021

DOI : https://doi.org/10.1038/s41598-021-98851-7

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

This article is cited by

Differential evolution for cleft lip and/or cleft palate patient treatment scheduling problems: a northern thailand hospital case study.

• Chawis Boonmee
• Kosit Akarawongsapat
• Krit Khwanngern

Annals of Operations Research (2024)

Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption

• Darshan Chauhan
• Avinash Unnikrishnan
• Priyadarshan N. Patil

Towards automatically generating meal plan based on genetic algorithm

• Mingliang Li

Soft Computing (2024)

SleepSmart: an IoT-enabled continual learning algorithm for intelligent sleep enhancement

• Samah A. Gamel
• Fatma M. Talaat

Neural Computing and Applications (2024)

Modeling and optimization of bakery production scheduling to minimize makespan and oven idle time

• Majharulislam Babor
• Olivier Paquet-Durand
• Bernd Hitzmann

Scientific Reports (2023)

By submitting a comment you agree to abide by our Terms and Community Guidelines . If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Advances, Systems and Applications

• Open access
• Published: 13 June 2023

A survey of Kubernetes scheduling algorithms

• Khaldoun Senjab 1 ,
• Sohail Abbas 1 ,
• Naveed Ahmed 1 &
• Atta ur Rehman Khan 2  

Journal of Cloud Computing volume  12 , Article number:  87 ( 2023 ) Cite this article

9049 Accesses

4 Citations

Metrics details

As cloud services expand, the need to improve the performance of data center infrastructure becomes more important. High-performance computing, advanced networking solutions, and resource optimization strategies can help data centers maintain the speed and efficiency necessary to provide high-quality cloud services. Running containerized applications is one such optimization strategy, offering benefits such as improved portability, enhanced security, better resource utilization, faster deployment and scaling, and improved integration and interoperability. These benefits can help organizations improve their application deployment and management, enabling them to respond more quickly and effectively to dynamic business needs. Kubernetes is a container orchestration system designed to automate the deployment, scaling, and management of containerized applications. One of its key features is the ability to schedule the deployment and execution of containers across a cluster of nodes using a scheduling algorithm. This algorithm determines the best placement of containers on the available nodes in the cluster. In this paper, we provide a comprehensive review of various scheduling algorithms in the context of Kubernetes. We characterize and group them into four sub-categories: generic scheduling, multi-objective optimization-based scheduling, AI-focused scheduling, and autoscaling enabled scheduling, and identify gaps and issues that require further research.

Introduction

Kubernetes is an open-source platform for automating the deployment, scaling, and management of containerized applications. It allows developers to focus on building and deploying their applications without worrying about the underlying infrastructure. Kubernetes uses a declarative approach to managing applications, where users specify desired application states, and the system maintains them. It also provides robust tools for monitoring and managing applications, including self-healing mechanisms for automatic failure detection and recovery. Overall, Kubernetes offers a powerful and flexible solution for managing containerized applications in production environments.

Kubernetes is well-suited for microservice-based web applications, where each component can be run in its own container. Containers are lightweight and can be easily created and destroyed, providing faster and more efficient resource utilization than virtual machines, as shown in Fig.  1 . Kubernetes automates the deployment, scaling, and management of containers across a cluster of machines, making resource utilization more efficient and flexible. This simplifies the process of building and maintaining complex applications.

Comparison between different types of applications deployments

Microservice-based architecture involves dividing an application into small, independent modules called microservices, Fig.  2 . Each microservice is responsible for a specific aspect of the application, and they communicate through a message bus. This architecture offers several benefits, such as the ability to automate deployment, scaling, and management. Because each microservice is independent and can be managed and updated separately, it is easier to make changes without affecting the entire system. Additionally, microservices can be written in different languages and can run on different servers, providing greater flexibility in the development process.

Comparison between different applications architectures

Kubernetes can quickly adapt to various types of demand intensities. For example, if a web application has few visitors at a given time, it can be scaled down to a few pods using minimal resources to reduce costs. However, if the application becomes extremely popular and receives a large number of visitors simultaneously, it can be scaled up to be serviced by a large number of pods, making it capable of handling almost any level of demand.

Kubernetes have been employed by many organizations in a diverse area of underlying applications and have gained the trust of being the best option for the management and deployment of containerized applications. In terms of recent applications, Kubernetes are proving to be an invaluable resource for IT infrastructure as they provide a sustainable path towards serverless computing that will result in easing up challenges in IT administration [ 1 ]. Serverless computing will provide end-to-end security enhancements but will also result in new infrastructure and security challenges as discussed in [ 1 ].

As the computing paradigm moves towards edge and fog computing, Kubernetes is proving to be a versatile solution that provides seamless network management between cloud and edge nodes [ 2 , 3 , 4 ]. Kubernetes face multiple challenges when deployed in an IoT environment. These challenges range from optimizing network traffic distribution [ 2 ], optimizing flow routing policies [ 3 ], and edge device’s computational resources distribution [ 4 ].

As can be seen from the diverse range of applications, and challenges associated with Kubernetes, it is imperative to study proposed algorithms in the related area to identify the state-of-the-art and future research directions. Numerous studies have focused on the development of new algorithms for Kubernetes. The main motivation for this survey is to provide a comprehensive overview of the state-of-the-art in the field of Kubernetes scheduling algorithms. By reviewing the existing literature and identifying the key theories, methods, and findings from previous studies, we aim to provide a critical evaluation of the strengths and limitations of existing approaches. We also hope to identify gaps and open questions in the existing literature, and to offer suggestions for future research directions. Overall, our goal is to contribute to the advancement of knowledge in the field and to provide a useful resource for researchers and practitioners working with Kubernetes scheduling algorithms.

To the best of authors’ knowledge, there are no related surveys found that specifically address the topic at hand. The surveys found are mostly targeted at the container orchestration in general (including Kubernetes), such as [ 5 , 6 , 7 , 8 ]. These surveys address Kubernetes breadthwise without targeting scheduling and diving deep into it and some even did not focus on Kubernetes. For example, some concentrated on scheduling in the cloud [ 9 ] and its associated concerns [ 10 ]. Others targeted big data applications in data center networks [ 11 ], or fog computing environments [ 12 ]. The authors have found two closely related and well-organized surveys [ 13 ] and [ 14 ] that targeted Kubernetes scheduling in depth. However, our work is different than these two surveys in terms of taxonomy, i.e., they targeted different aspects and objectives in scheduling whereas we categorized the literature into different four sub-categories: generic scheduling, multi-objective optimization-based scheduling, AI focused scheduling, and autoscaling enabled scheduling. Thereby focusing specifically on wide range of schemes related to multi-objective optimization and AI, in addition to the main scheduling with autoscaling. Our categorization, we believe, is more fine-grained and novel as compared to the existing surveys.

In this paper, the literature has been divided into four sub-categories: generic scheduling, multi-objective optimization-based scheduling, AI-focused scheduling, and autoscaling enabled scheduling. The literature pertaining to each sub-category is analyzed and summarized based on six parameters outlined in Literature review section.

Our main contributions are as follows:

A comprehensive review of the literature on Kubernetes scheduling algorithms targeting four sub-categories: generic scheduling, multi-objective optimization-based scheduling, AI focused scheduling, and autoscaling enabled scheduling.

A critical evaluation of the strengths and limitations of existing approaches.

Identification of gaps and open questions in the existing literature.

The remainder of this paper is organized as follows: In  Search methodology  section, we describe the methodology used to conduct the survey. In Literature review  section, we present the literature review along with results of our survey, including a critical evaluation of the strengths and limitations of existing approaches. A taxonomy of the identified research papers based on the literature review is presented as well. In  Discussion, challenges & future suggestions  section, we discuss the implications of our findings and suggest future research directions. Finally, in  Conclusions  section, we summarize the key contributions of the survey and provide our conclusions.

Search methodology

This section presents our search methodology for identifying relevant studies that are included in this review.

To identify relevant studies for our review, we conducted a comprehensive search of the literature using the following databases: IEEE, ACM, Elsevier, Springer, and Google Scholar. We used the following search terms: "Kubernetes," "scheduling algorithms," and "scheduling optimizing." We limited our search to studies published in the last 5 years and written in English.

We initially identified a total of 124 studies from the database searches, see Fig.  3 . We then reviewed the abstracts of these studies to identify those that were relevant to our review. We excluded studies that did not focus on Kubernetes scheduling algorithms, as well as those that were not original research or review articles. After this initial screening, we were left with 67 studies, see Fig.  4 .

Inclusion criteria

Exclusion criteria

We then reviewed the texts of the remaining studies to determine their eligibility for inclusion in our review. We excluded studies that did not meet our inclusion criteria, which were: (1) focus on optimizing Kubernetes scheduling algorithms, (2) provide original research or a critical evaluation of existing approaches, and (3) be written in English and published in the last 5 years. After this final screening, we included 47 studies in our review, see Fig.  4 . A yearly distribution of papers can be seen in Fig.  5 .

Detailed statistics showing the yearly breakdown of analyzed studies

We also searched the reference lists of the included studies to identify any additional relevant studies that were not captured in our database searches. We did not identify any additional studies through this process. Therefore, our review includes 47 studies on Kubernetes scheduling algorithms published in the last 5 years. These studies represent a diverse range of research methods, including surveys, experiments, and simulations.

Literature review

This section has been organized into four sub-categories, i.e., generic scheduling, multi-objective optimization-based scheduling, AI focused scheduling, and autoscaling enabled scheduling. A distribution of analyzed research papers in each category can be seen in Fig.  6 . The literature in each sub-category is analyzed and then summarized based on six parameters given below:

Methodology/Algorithms

Experiments

Applications

Limitations

Detailed statistics for each category in terms of analyzed studies

Scheduling in Kubernetes

The field of Kubernetes scheduling algorithms has attracted significant attention from researchers and practitioners in recent years. A growing body of literature has explored the potential benefits and challenges of using different scheduling algorithms to optimize the performance of a Kubernetes cluster. In this section, we present a review of the key theories, methods, and findings from previous studies in this area.

One key theme in the literature is the need for efficient effective scheduling of workloads in a Kubernetes environment. Many studies have emphasized the limitations of traditional scheduling approaches, which often struggle to handle the complex and dynamic nature of workloads in a Kubernetes cluster. As a result, there has been increasing interest in the use of advanced scheduling algorithms to enable efficient, effective allocation of computing resources within the cluster.

Another key theme in the literature is the potential benefits of advanced scheduling algorithms for Kubernetes. Many studies have highlighted the potential for these algorithms to improve resource utilization, reduce latency, and enhance the overall performance of the cluster. Additionally, advanced scheduling algorithms have the potential to support the development of new applications and services within the Kubernetes environment, such as real-time analytics and machine learning and deep learning, see AI Focused Scheduling section. 

Despite these potential benefits, the literature also identifies several challenges and limitations of Kubernetes scheduling algorithms. One key challenge is the need to address the evolving nature of workloads and applications within the cluster. Therefore, various authors focused on improving the autoscaling feature in Kubernetes scheduling to allow for automatic adjustment of the resources allocated to pods based on the current demand, more detailed discussion can be found in Autoscaling-enabled Scheduling section. Other challenges include the need to manage and coordinate multiple scheduling algorithms, and to ensure the stability and performance of the overall system.

Overall, the literature suggests that advanced scheduling algorithms offer a promising solution to the challenges posed by the complex and dynamic nature of workloads in a Kubernetes cluster. However, further research is needed to address the limitations and challenges of these algorithms, and to explore their potential applications and benefits.

In Santos et al. [ 15 ], for deployments in smart cities, the authors suggest a network-aware scheduling method for container-based apps. Their strategy is put into practice as an addition to Kubernetes' built-in default scheduling system, which is an open-source orchestrator for the automatic management and deployment of micro-services. By utilizing container-based smart city apps, the authors assess the suggested scheduling approach's performance and contrast it with that of Kubernetes' built-in default scheduling mechanism. Compared to the default technique, they discovered that the suggested solution reduces network latency by almost 80%.

In Chung et al. [ 16 ], the authors propose a new cluster scheduler called Stratus that is specialized for orchestrating batch job execution on virtual clusters in public Infrastructure-as-a-Service (IaaS) platforms. Stratus focuses on minimizing dollar costs by aggressively packing tasks onto machines based on runtime estimates, i.e., to save money, the allocated resources will be made either mostly full or empty so that they may then be released. Using the workload traces from TwoSigma and Google, the authors evaluate Stratus and establish that the proposed Stratus reduces cost by 17–44% compared to the benchmarks of virtual cluster scheduling.

In Le et al. [ 17 ], the authors propose a new scheduling algorithm called AlloX for optimizing job performance in shared clusters that use interchangeable resources such as CPUs, GPUs, and other accelerators. AlloX transforms the scheduling problem into a min-cost bipartite matching problem and provides dynamic fair allocation over time. The authors demonstrate theoretically and empirically that AlloX performs better than existing solutions in the presence of interchangeable resources, and they show that it can reduce the average job completion time significantly while providing fairness and preventing starvation.

In Zhong et al. [ 18 ], the authors propose a heterogeneous task allocation strategy for cost-efficient container orchestration in Kubernetes-based cloud computing infrastructures with elastic compute resources. The proposed strategy has three main features: support for heterogeneous job configurations, cluster size adjustment through autoscaling algorithms, and a rescheduling mechanism to shut down underutilized VM instances and reallocate relevant jobs without losing task progress. The authors evaluate their approach using the Australian National Cloud Infrastructure (Nectar) and show that it can reduce overall cost by 23–32% compared to the default Kubernetes framework.

In Thinakaran et al. [ 19 ], to create Kube-Knots, the authors combine their proposed GPU-aware resource orchestration layer, Knots, with the Kubernetes container orchestrator. Through dynamic container orchestration, Kube-Knots dynamically harvests unused computing cycles, enabling the co-location of batch and latency-critical applications and increasing overall resource utilization. The authors demonstrate that the proposed scheduling strategies increase average and 99th percentile cluster-wide GPU usage by up to 80% in the case of HPC workloads when used to plan datacenter-scale workloads using Kube-Knots on a ten-node GPU cluster. In addition, the suggested schedulers reduce energy consumption throughout the cluster by an average of 33% for three separate workloads and increase the average task completion times of deep learning workloads by up to 36% when compared to modern schedulers.

In Townend et al. [ 20 ], the authors propose a holistic scheduling system for Kubernetes that replaces the default scheduler and considers both software and hardware models to improve data center efficiency. The authors claim that by introducing hardware modeling into a software-based solution, an intelligent scheduler can make significant improvements in data center efficiency. In their initial deployment, the authors observed power consumption reductions of 10–20%.

In the work by Menouer [ 21 ], the author describes the KCSS, a brand-new Kubernetes container scheduling strategy. The purpose of KCSS is to increase performance in terms of makespan and power consumption by scheduling user-submitted containers as efficiently as possible. For each freshly submitted container, KCSS chooses the best node based on a number of factors linked to the cloud infrastructure and the user's requirements using a multi-criteria decision analysis technique. The author uses the Go programming language to create KCSS and shows how it works better than alternative container scheduling methods in a variety of situations.

In Song et al. [ 22 ], authors present a topology-based GPU scheduling framework for Kubernetes. The framework is based on the traditional Kubernetes GPU scheduling algorithm, but introduces the concept of a GPU cluster topology, which is restored in a GPU cluster resource access cost tree. This allows for more efficient scheduling of different GPU resource application scenarios. The proposed framework has been used in the production practice of Tencent and has reportedly improved the resource utilization of GPU clusters by about 10%.

In Ogbuachi et al. [ 23 ], the authors propose an improved design for Kubernetes scheduling that takes into account physical, operational, and network parameters in addition to software states in order to enable better orchestration and management of edge computing applications. They compare the proposed design to the default Kubernetes scheduler and show that it offers improved fault tolerance and dynamic orchestration capabilities.

In the work by Beltre et al. [ 24 ], utilizing fairness measures including dominant resource fairness, resource demand, and average waiting time, the authors outline a scheduling policy for Kubernetes clusters. KubeSphere, a policy-driven meta-scheduler created by the authors, enables tasks to be scheduled according to each user's overall resource requirements and current consumption. The proposed policy increased fairness in a multi-tenant cluster, according to experimental findings.

In Haja et al. [ 25 ], the authors propose a custom Kubernetes scheduler that takes into account delay constraints and edge reliability when making scheduling decisions. The authors argue that this type of scheduler is necessary for edge infrastructure, where applications are often delay-sensitive, and the infrastructure is prone to failures. The authors demonstrate their Kubernetes extension and release the solution as open source.

In Wojciechowski et al. [ 26 ], the authors propose a unique method for scheduling Kubernetes pods that makes advantage of dynamic network measurements gathered by Istio Service Mesh. According to the authors, this approach can fully automate saving up to 50% of inter-node bandwidth and up to 37% of application response time, which is crucial for the adoption of Kubernetes in 5G use cases.

In Cai et al. [ 27 ], the authors propose a feedback control method for elastic container provisioning in Kubernetes-based systems. The method uses a combination of a varying-processing-rate queuing model and a linear model to improve the accuracy of output errors. The authors compare their approach with several existing algorithms on a real Kubernetes cluster and find that it obtains the lowest percentage of service level agreement (SLA) violation and the second lowest cost.

In Ahmed et al. [ 28 ], the deployment of Docker containers in a heterogeneous cluster with CPU and GPU resources can be managed via the authors' dynamic scheduling framework for Kubernetes. The Kubernetes Pod timeline and previous data about the execution of the containers are taken into account by the platform, known as KubCG, to optimize the deployment of new containers. The time it took to complete jobs might be cut by up to 64% using KubCG, according to the studies the authors conducted to validate their algorithm.

In Ungureanu et al. [ 29 ], the authors propose a hybrid shared-state scheduling framework for Kubernetes that combines the advantages of centralized and distributed scheduling. The framework uses distributed scheduling agents to delegate most tasks, and a scheduling correction function to process unprioritized and unscheduled tasks. Based on the entire cluster state the scheduling decisions are made, which are then synchronized and updated by the master-state agent. The authors performed experiments to test the behavior of their proposed scheduler and found that it performed well in different scenarios, including failover and recovery. They also found that other centralized scheduling frameworks may not perform well in situations like collocation interference or priority preemption.

In Yang et al. [ 30 ], the authors present the design and implementation of KubeHICE, a performance-aware container orchestrator for heterogeneous-ISA architectures in cloud-edge platforms. KubeHICE extends Kubernetes with two functional approaches, AIM (Automatic Instruction Set Architecture Matching) and PAS (Performance-Aware Scheduling), to handle heterogeneous ISA and schedule containers according to the computing capabilities of cluster nodes. The authors performed experiments to evaluate KubeHICE and found that it added no additional overhead to container orchestration and was effective in performance estimation and resource scheduling. They also demonstrated the advantages of KubeHICE in several real-world scenarios, showing for example a 40% increase in CPU utilization when eliminating heterogeneity.

In Li et al. [ 31 ], the authors propose two dynamic scheduling algorithms, Balanced-Disk-IO-Priority (BDI) and Balanced-CPU-Disk-IO-Priority (BCDI), to address the issue of Kubernetes' scheduler not taking the disk I/O load of nodes into account. BDI is designed to improve the disk I/O balance between nodes, while BCDI is designed to solve the issue of load imbalance of CPU and disk I/O on a single node. The authors perform experiments to evaluate the algorithms and find that they are more effective than the Kubernetes default scheduling algorithms.

In Fan et al. [ 32 ], the authors propose an algorithm for optimizing the scheduling of pods in the Serverless framework on the Kubernetes platform. The authors argue that the default Kubernetes scheduler, which operates on a pod-by-pod basis, is not well-suited for the rapid deployment and running of pods in the Serverless framework. To address this issue, the authors propose an algorithm that uses simultaneous scheduling of pods to improve the efficiency of resource scheduling in the Serverless framework. Through preliminary testing, the authors found that their algorithm was able to greatly reduce the delay in pod startup while maintaining a balanced use of node resources.

In Bestari et al. [ 33 ], the authors propose a scheduler for distributed deep learning training in Kubeflow that combines features from existing works, including autoscaling and gang scheduling. The proposed scheduler includes modifications to increase the efficiency of the training process, and weights are used to determine the priority of jobs. The authors evaluate the proposed scheduler using a set of Tensorflow jobs and find that it improves training speed by over 26% compared to the default Kubernetes scheduler.

In Dua et al. [ 34 ], the authors present an alternative algorithm for load balancing in distributed computing environments. The algorithm uses task migration to balance the workload among processors of different capabilities and configurations. The authors define labels to classify tasks into different categories and configure clusters dedicated to specific types of tasks.

The above-mentioned schemes are summarized in Table 1 .

Scheduling using multi-objective optimization

Multi-objective optimization scheduling takes into account multiple objectives or criteria when deciding how to allocate resources and schedule containers on nodes in the cluster. This approach is particularly useful in complex distributed systems where there are multiple competing objectives that need to be balanced to achieve the best overall performance. In a multi-objective optimization scheduling approach, the scheduler considers multiple objectives simultaneously, such as minimizing response time, maximizing resource utilization, and reducing energy consumption. The scheduler uses optimization algorithms to find the optimal solution that balances these objectives.

Multi-objective optimization scheduling can help improve the overall performance and efficiency of Kubernetes clusters by taking into account multiple objectives when allocating resources and scheduling containers. This approach can result in better resource utilization, improved application performance, reduced energy consumption, and lower costs.

Some examples of multi-objective optimization scheduling algorithms used in Kubernetes include genetic algorithms, Ant Colony Optimization, and particle swarm optimization. These algorithms can help optimize different objectives, such as response time, resource utilization, energy consumption, and other factors, to achieve the best overall performance and efficiency in the Kubernetes cluster.

In this section, multi-objective scheduling proposals are discussed.

In Kaur et al. [ 35 ], the authors propose a new controller for managing containers on edge-cloud nodes in Industrial Internet of Things (IIoT) systems. The controller, called Kubernetes-based energy and interference driven scheduler (KEIDS), is based on Google Kubernetes and is designed to minimize energy utilization and interference in IIoT systems. KEIDS uses integer linear programming to formulate the task scheduling problem as a multi-objective optimization problem, taking into account factors such as energy consumption, carbon emissions, and interference from other applications. The authors evaluate KEIDS using real-time data from Google compute clusters and find that it outperforms existing state-of-the-art schemes.

In Lin et al. [ 36 ], the authors propose a multi-objective optimization model for container-based microservice scheduling in cloud architectures. They present an ant colony algorithm for solving the scheduling problem, which takes into account factors such as computing and storage resource utilization, the number of microservice requests, and the failure rate of physical nodes. The authors evaluate the proposed algorithm using experiments and compare its performance to other related algorithms. They find that the proposed algorithm achieves better results in terms of cluster service reliability, cluster load balancing, and network transmission overhead.

In Wei-guo et al. [ 37 ], the authors propose an improved scheduling algorithm for Kubernetes by combining ant colony optimization and particle swarm optimization to better balance task assignments and reduce resource costs. The authors implemented the algorithm in Java and tested it using the CloudSim tool, showing that it outperformed the original scheduling algorithm.

In the work by Oleghe [ 38 ], the idea of container placement and migration in edge servers, as well as the scheduling models created for this purpose, are discussed by the author. The majority of scheduling models, according to the author, are based mostly on heuristic algorithms and use multi-objective optimization models or graph network models. The study also points out the lack of studies on container scheduling models that take dispersed edge computing activities into account and predicts that future studies in this field will concentrate on scheduling containers for mobile edge nodes.

In Carvalho et al. [ 39 ], The authors offer an addition to the Kubernetes scheduler that uses Quality of Experience (QoE) measurements to help cloud management Service Level Objectives (SLOs) be more accurate. In the context of video streaming services that are co-located with other services, the authors assess the suggested architecture using the QoE metric from the ITU P.1203 standard. According to the findings, resource rescheduling increases average QoE by 135% while the proposed scheduler increases it by 50% when compared to other schedulers.

The above-mentioned schemes are summarized in Table 2 .

AI focused scheduling

Many large companies have recently started to provide AI based services. For this purpose, they have installed machine/deep learning clusters composed of tens to thousands of CPUs and GPUs for training their deep learning models in a distributed manner. Different machine learning frameworks are used such as MXNet [ 40 ], TensorFlow [ 41 ], and Petuum [ 42 ]. Training a deep learning model is usually very resource hungry and time consuming. In such a setting, efficient scheduling is crucial in order to fully utilize the expensive deep learning cluster and expedite the model training process. Different strategies have been used to schedule tasks in this arena, for examples, general purpose schedulers are customized to tackle distributed deep learning tasks, example include [ 43 ] and [ 44 ]; however, they statically allocate resources and do not adjust resource under different load conditions which lead to poor resource utilization. Others proposed dynamic allocation of resources after carefully analyzing the workloads, examples include [ 45 ] and [ 46 ].

In this section, deep learning focused schedulers are surveyed.

In Peng et al. [ 46 ], the authors propose a customized job scheduler for deep learning clusters called Optimus. The goal of Optimus is to minimize the time required for deep learning training jobs, which are resource-intensive and time-consuming. Optimus employs performance models to precisely estimate training speed as a function of resource allocation and online fitting to anticipate model convergence during training. These models inform how Optimus dynamically organizes tasks and distributes resources to reduce job completion time. The authors put Optimus into practice on a deep learning cluster and evaluate its efficiency in comparison to other cluster schedulers. They discover that Optimus beats conventional schedulers in terms of job completion time and makespan by roughly 139% and 63%, respectively.

In Mao et al. [ 47 ], the authors propose using modern machine learning techniques to develop highly efficient policies for scheduling data processing jobs on distributed compute clusters. They present their system, called Decima, which uses reinforcement learning (RL) and neural networks to learn workload-specific scheduling algorithms. Decima is designed to be scalable and able to handle complex job dependency graphs. The authors report that their prototype integration with Spark on a 25-node cluster improved average job completion time by at least 21% over existing hand-tuned scheduling heuristics, with up to 2 × improvement during periods of high cluster load.

In Chaudhary et al. [ 48 ], a distributed fair share scheduler for GPU clusters used for deep learning training termed as Gandivafair is presented by the authors. This GPU cluster utilization system offers performance isolation between users and is created to strike a balance between the competing demands of justice and efficiency. In spite of cluster heterogeneity, Gandivafair is the first scheduler to fairly distribute GPU time among all active users. The authors demonstrate that Gandivafair delivers both fairness and efficiency under realistic multi-user workloads by evaluating it using a prototype implementation on a heterogeneous 200-GPU cluster.

In Fu et al. [ 49 ], the authors propose a new container placement scheme called ProCon for scheduling jobs in a Kubernetes cluster. ProCon uses an estimation of future resource usage to balance resource contentions across the cluster and reduce the completion time and makespan of jobs. The authors demonstrate through experiments that ProCon decreases completion time by up to 53.3% for a specific job and enhances general performance by 23.0%. In addition, ProCon shows a makespan improvement of up to 37.4% in comparison to Kubernetes' built-in default scheduler.

In Peng et al. [ 50 ], the authors propose DL2, a deep learning-based scheduler for deep learning clusters that aims to improve global training job expedition by dynamically resizing resources allocated to jobs. The authors implement DL2 on Kubernetes and evaluate its performance against a fairness scheduler and an expert heuristic scheduler. The results show that DL2 outperforms the other schedulers in terms of average job completion time.

In Mao et al. [ 51 ], the authors propose a new container scheduler called SpeCon optimized for short-lived deep learning applications. SpeCon is designed to improve resource utilization and job completion times in a Kubernetes cluster by analyzing the progress of deep learning training processes and speculatively migrating slow-growing models to release resources for faster-growing ones. The authors conduct experiments that demonstrate that SpeCon improves individual job completion times by up to 41.5%, improves system-wide performance by 14.8%, and reduces makespan by 24.7%.

In Huang et al. [ 52 ], for scheduling independent batch jobs across many federated cloud computing clusters, the authors suggest a deep reinforcement learning-based job scheduler dubbed RLSK. The authors put RLSK into use on Kubernetes and tested its performance through simulations, demonstrating that it can outperform conventional scheduling methods.

The work by Wang et al. [ 53 ] describes MLFS, a feature-based task scheduling system for machine learning clusters that can conduct both data- and model-parallel processes. To determine task priority for work queue ordering, MLFS uses a heuristic scheduling method. The data from this method is then used to train a deep reinforcement learning model for job scheduling. In comparison to existing work schedules, the proposed system is shown to reduce job completion time by up to 53%, makespan by up to 52%, and increase accuracy by up to 64%. The system is tested using real experiments and large-scale simulations based on real traces.

In Han et al. [ 54 ], the authors present KaiS, an edge-cloud Kubernetes scheduling framework based on learning. KaiS models system state data using graph neural networks and a coordinated multi-agent actor-critic method for decentralized request dispatch. Research indicates that when compared to baselines, KaiS can increase average system throughput rate by 14.3% and decrease scheduling cost by 34.7%.

In Casquero et al. [ 55 ], the Kubernetes orchestrator's scheduling task is distributed among processing nodes by the authors' proposed custom scheduler, which makes use of a Multi-Agent System (MAS). According to the authors, this method is quicker than the centralized scheduling strategy employed by the default Kubernetes scheduler.

In Yang et al. [ 56 ], the authors propose a method for optimizing Kubernetes' container scheduling algorithm by combining the grey system theory with the LSTM (Long Short-Term Memory) neural network prediction method. They perform experiments to evaluate their approach and find that it can reduce the resource fragmentation problem of working nodes in the cluster and increase the utilization of cluster resources.

In Zhang et al. [ 57 ], a highly scalable cluster scheduling system for Kubernetes, termed as Zeus, is proposed by the authors. The main feature of Zeus is that based on the actual server utilization it schedules the best-effort jobs. It has the ability to adaptively divide resources between workloads of two different classes. Zeus is meant to enable the safe colocation of best-effort processes and latency-sensitive services. The authors test Zeus in a real-world setting and discover that it can raise average CPU utilization from 15 to 60% without violating Service Level Objectives (SLOs).

In Liu et al. [ 58 ], the authors suggest a scheduling strategy for deep learning tasks on Kubernetes that takes into account the tasks' resource usage characteristics. To increase task execution efficiency and load balancing, the suggested paradigm, dubbed FBSM, has modules for a GPU sniffer and a balance-aware scheduler. The execution of deep learning tasks is sped up by the suggested system, known as KubFBS, according to the authors' evaluation, which also reveals improved load balancing capabilities for the cluster.

In Rahali et al. [ 59 ], the authors propose a solution for resource allocation in a Kubernetes infrastructure hosting network service. The proposed solution aims to avoid resource shortages and protect the most critical functions. The authors use a statistical approach to model and solve the problem, given the random nature of the treated information.

The above-mentioned schemes are summarized in Table 3 .

Autoscaling-enabled scheduling

Autoscaling is an important feature in Kubernetes scheduling because it allows for automatic adjustment of the resources allocated to pods based on the current demand. It allows efficient resource utilization, improved performance, cost savings, and high availability of the application. Auto rescaling and scheduling are related in that auto rescaling can be used to ensure that there are always enough resources available to handle the tasks that are scheduled. For example, if the scheduler assigns a new task to a worker node, but that node does not have enough resources to execute the task, the auto scaler can add more resources to that node or spin up a new node to handle the task. In this way, auto rescaling and scheduling work together to ensure that a distributed system is able to handle changing workloads and optimize resource utilization. Some of the schemes related to this category are surveyed below.

In Taherizadeh et al. [ 60 ], the authors propose a new dynamic multi-level (DM) autoscaling method for container-based cloud applications. The DM method uses both infrastructure- and application-level monitoring data to determine when to scale up or down, and its thresholds are dynamically adjusted based on workload conditions. The authors compare the performance of the DM method to seven existing autoscaling methods using synthetic and real-world workloads. They find that the DM method has better overall performance than the other methods, particularly in terms of response time and the number of instantiated containers. SWITCH system was used to implement the DM method for time-critical cloud applications.

In Rattihalli et al. [ 61 ], the authors propose a new resource management system called RUBAS that can dynamically adjust the allocation of containers running in a Kubernetes cluster. RUBAS incorporates container migration to improve upon the Kubernetes Vertical Pod Autoscaler (VPA) system non-disruptively. The authors evaluate RUBAS using multiple scientific benchmarks and compare its performance to Kubernetes VPA. They find that RUBAS improves CPU and memory utilization by 10% and reduces runtime by 15% with an overhead for each application ranging from 5–20%.

In Toka et al. [ 62 ], the authors present a Kubernetes scaling engine that uses machine learning forecast methods to make better autoscaling decisions for cloud-based applications. The engine's short-term evaluation loop allows it to adapt to changing request dynamics, and the authors introduce a compact management parameter for cloud tenants to easily set their desired level of resource over-provisioning vs. service level agreement (SLA) violations. The proposed engine is evaluated in simulations and with measurements on Web trace data, and the results show that it results in fewer lost requests and slightly more provisioned resources compared to the default Kubernetes baseline.

In Balla et al. [ 63 ], the authors propose an adaptive autoscaler called Libra, which automatically detects the optimal resource set for a single pod and manages the horizontal scaling process. Libra is also able to adapt the resource definition for the pod and adjust the horizontal scaling process if the load or underlying virtualized environment changes. The authors evaluate Libra in simulations and show that it can reduce the average CPU and memory utilization by up to 48% and 39%, respectively, compared to the default Kubernetes autoscaler.

In another work by Toka et al. [ 64 ], the authors propose a Kubernetes scaling engine that uses multiple AI-based forecast methods to make autoscaling decisions that are better suited to handle the variability of incoming requests. The authors also introduce a compact management parameter to help application providers easily set their desired resource over-provisioning and SLA violation trade-off. The proposed engine is evaluated in simulations and with measurements on web traces, showing improved fitting of provisioned resources to service demand.

In Wu et al., the authors propose a new active Kubernetes auto scaling device based on prediction of pod replicas. They demonstrate that their proposed autoscaler has a faster response speed compared to existing scaling strategies in Kubernetes.

In Wang et al. [ 65 ] the authors propose an improved automatic scaling scheme for Kubernetes that combines the advantages of different types of nodes in the scaling process. They found that their scheme improves the performance of the system under rapid load pressure and reduces instability within running clusters compared to the default auto scaler.

In Kang et al. [ 66 ], the authors propose a method for improving the reliability of virtual networks by using optimization models and heuristic algorithms to allocate virtual network functions (VNFs) to suitable locations. The authors also develop function scheduler plugins for the Kubernetes system, which allows for the automatic deployment and management of containerized applications. The proposed method is demonstrated to be effective in allocating functions and running service functions correctly. This work was published in the 2021 edition of the IEEE Conference on Decision and Control.

In Vu et al. [ 67 ], propose a hybrid autoscaling method for containerized applications that combines vertical and horizontal scaling capabilities to optimize resource utilization and ensure quality of service (QoS) requirements. The proposed method uses a predictive approach based on machine learning to forecast future demand and a burst identification module to make scaling decisions. The authors evaluate the proposed method and find that it improves response time and resource utilization compared to existing methods that only use a single scaling mode.

The above-mentioned schemes are summarized in Table 4 .

Discussion, challenges & future suggestions

In Literature review section, a comprehensive review has been presented covering four sub-categories in the area of Kubernetes scheduling. It is crucial to provide a brief discussion on the categorized literature review that is presented in this section.

In the area of multi-objective optimization-based scheduling in Kubernetes, several research studies have been conducted to optimize various objectives such as minimizing the energy consumption and cost while maximizing resource utilization and meeting application performance requirements. These studies employ different optimization techniques such as genetic algorithms, particle swarm optimization, and ant colony optimization. Some studies also incorporate machine learning-based approaches to predict workload patterns and make scheduling decisions. There are still several challenges that need to be addressed. Firstly, the multi-objective nature of the problem poses a significant challenge in finding optimal solutions that balance conflicting objectives. Second, the dynamic nature of the cloud environment requires real-time adaptation of scheduling decisions to changing conditions. Overall, the research in multi-objective optimization-based scheduling in Kubernetes shows great potential in achieving efficient and effective resource management. Still, further work is needed to address the challenges and validate the effectiveness of these approaches in real-world scenarios.

On the other hand, AI-based scheduling in Kubernetes has been a popular area of research in recent years. Many studies have proposed different approaches to optimize scheduling decisions using machine learning and other AI techniques. One of the key accomplishments in this area is the development of scheduling algorithms that can handle complex workloads in a dynamic environment. These algorithms can consider various factors, such as resource availability, task dependencies, and application requirements, to make optimal scheduling decisions. Some studies have proposed reinforcement learning-based scheduling algorithms, which can adapt to changing workload patterns and learn from experience to improve scheduling decisions. Other studies have proposed deep learning-based approaches, which can capture complex patterns in the workload data and make accurate predictions. Overall, these studies have demonstrated that AI-based scheduling can improve the efficiency and performance of Kubernetes clusters. However, there are still some challenges that need to be addressed in this area. One of the main challenges is the lack of real-world datasets for training and evaluation of AI-based scheduling algorithms. Most studies use synthetic or simulated datasets, which may not reflect the complexities of real-world workloads. Another challenge is the trade-off between accuracy and computational complexity. Future research in this area could focus on developing more efficient and scalable AI-based scheduling algorithms that can handle large-scale, real-world workloads. This could involve exploring new machine learning and optimization techniques that can improve scheduling accuracy while reducing computational complexity.

Lastly, autoscaling enabled scheduling is an emerging research area that aims to optimize resource utilization and improve application performance by combining autoscaling and scheduling techniques. Several research studies have been published in this area in recent years. The analysis of these studies reveals that autoscaling enabled scheduling can lead to significant improvements in resource utilization and application performance. The studies have shown they can help reduce resource wastage, minimize the risk of under-provisioning, and improve application response times. However, despite these promising results, there are still some challenges that need to be addressed in this area. One of the main challenges is the complexity of designing effective autoscaling enabled scheduling algorithms. Developing algorithms that can adapt to dynamic workload changes and optimize resource utilization while maintaining application performance is a non-trivial task. Furthermore, there is a need for more research on the practical implementation of autoscaling enabled scheduling in real-world scenarios. Most of the existing studies have been conducted in controlled experimental settings, and there is a need to evaluate the effectiveness of auto scaling enabled scheduling in real-world applications. There are still several challenges that need to be addressed, including algorithm design, standardization, and practical implementation. Future research in this area should focus on addressing these challenges and developing more effective and practical auto scaling enabled scheduling techniques.

The research papers use diverse algorithms to enhance Kubernetes scheduling. These algorithms are tested on various platforms and environments, such as Spark, MXNet, Kubernetes, Google and TwoSigma's GPU cluster, workloads, Google compute, CPU-GPU, the National Cloud Infrastructure, benchmarks, ProCon, DL2, DRF, Optimus, CBP, PP, scaling, data centers, schedulers, CloudSim and Java, scenarios, cloud infrastructure, user need, RLSK, real trace, GaiaGPU and Tencent, real workload traces, simulations and web traces, Kubernetes, a new algorithm, Kubernetes failover and recovery, KubeHICE, real-world scenarios, BDI, BCDI, Kubernetes, a proposed algorithm, autoscalers, default auto scalers, video streaming, Tensorflow, Zeus, and latency-sensitive services. Some papers did not specify the details of the algorithms they used or the platforms and environments they tested on.

As can be seen in the previous sections, the survey extensively analyzes the current literature, and composes a taxonomy to not only effectively analyze the current state-of-the-art but also identify the challenges and future directions. Based on the analysis, the following areas have been identified as potential future research in the field:

As Kubernetes becomes more popular, there will be a growing need for advanced computation optimization techniques. In the future, Kubernetes may benefit from the development of more sophisticated algorithms for workload scheduling and resource allocation, potentially using AI or machine learning. Additionally, integrating Kubernetes with emerging technologies like serverless computing could lead to even more efficient resource usage by enabling dynamic scaling without pre-provisioned infrastructure. Ultimately, the future of computation optimization in Kubernetes is likely to involve a combination of cutting-edge algorithms, innovative technologies, and ongoing advancements in cloud computing.

Testing and implementation to reveal limitations or current learning algorithms for scheduling and potential improvements on large scale clusters. One important focus is on improving the tooling and automation around testing and deployment, including the development of new testing frameworks and the integration of existing tools into the Kubernetes ecosystem. Another key area is the ongoing refinement of Kubernetes' implementation and development process, with a focus on streamlining workflows, improving documentation, and fostering greater collaboration within the open-source community. Additionally, there is a growing emphasis on developing more comprehensive testing and validation strategies for Kubernetes clusters, including the use of advanced techniques like chaos engineering to simulate real-world failure scenarios. Overall, the future of testing and implementation in Kubernetes is likely to involve ongoing innovation, collaboration, and an ongoing commitment to driving the platform forward.

A number of methods are employing learning algorithms for resource balancing inside and outside the cluster. Even though the methods given encouraging results, new learning algorithms can be found to improve the scheduler, especially on large scale clusters.

Limitations and potential improvements in specific contexts, e.g., Green Computing. Minimizing the carbon footprint of a cluster is an ongoing challenge. Advanced schedulers are needed to be proposed in order to reduce the energy consumption and carbon footprint of clusters in IIoT setups. There is a huge opportunity for improving the existing methods and proposing new methods in this area.

Future research in Kubernetes resource management. Kubernetes resource management mostly relies on optimization modelling framework and heuristic-based algorithms. The potential for improving and proposing new resource management algorithms is a very promising area of research. Future research in Kubernetes resource management may focus on addressing the challenges of managing complex, dynamic workloads across distributed, heterogeneous environments. This may involve developing more sophisticated algorithms and techniques for workload placement, resource allocation, and load balancing, as well as exploring new approaches to containerization and virtualization. Additionally, there may be opportunities to leverage emerging technologies like edge computing and 5G networks to enable more efficient and scalable resource management in Kubernetes.

Most of the work done in the area of Kubernetes scheduling has been evaluated on small clusters. However, this might not always be tempting. One future research direction in Kubernetes scheduling is to use larger cluster sizes for algorithm evaluation. While Kubernetes has been shown to be effective in managing clusters of up to several thousand nodes, there is a need to evaluate its performance in even larger cluster sizes. This includes evaluating the scalability of the Kubernetes scheduler, identifying potential bottlenecks, and proposing solutions to address them. Additionally, there is a need to evaluate the impact of larger cluster sizes on application performance and resource utilization. This research could lead to the development of more efficient scheduling algorithms and better management strategies for large-scale Kubernetes deployments.

Scheduling should not only be considered from the static infrastructure point of view, but rather advanced context-aware scheduling algorithms may be proposed that could focus on developing new approaches to resource allocation and scheduling that take into account a broader range of contextual factors, such as user preferences, application dependencies, and environmental conditions. This may involve exploring new machine learning techniques and optimization algorithms that can dynamically adapt to changing conditions and prioritize resources based on real-time feedback and analysis. Other potential areas of research may include developing new models and frameworks for managing resources in Kubernetes clusters, improving container orchestration and load balancing, and enhancing monitoring and analytics capabilities to enable more effective use of context-aware scheduling algorithms.

As can be seen from the diversity of future directions, the potential for new research in Kubernetes is ripe with challenges of myriad levels of difficulty and effort. It provides future researchers with exciting opportunities to pursue and problems to tackle. We hope that this survey will facilitate future researchers in selecting a suitable challenge and solve new problems to expand the state-of-the-art in the area of Kubernetes.

Conclusions

In conclusion, the survey on Kubernetes scheduling provides a comprehensive overview of the current state of the field. It covers the objectives, methodologies, algorithms, experiments, and results of various research efforts in this area. The survey highlights the importance of scheduling in Kubernetes and the need for efficient and effective scheduling algorithms. The results of the experiments show that there is still room for improvement in this area, and future work should focus on developing new algorithms and improving existing ones. Overall, the survey provides valuable insight into the current state of Kubernetes scheduling and points to promising directions for future research.

Availability of data and materials

The corresponding author may provide the supporting data on request.

Mondal SK, Pan R, Kabir HMD, Tian T, Dai HN (2022) Kubernetes in IT administration and serverless computing: an empirical study and research challenges. J Supercomput 78(2):2937–2987

Article   Google Scholar  

Phuc LH, Phan LA, Kim T (2022) Traffic-Aware horizontal pod autoscaler in kubernetes-based edge computing infrastructure. IEEE Access 10:18966–18977

Zhang M, Cao J, Yang L, Zhang L, Sahni Y, Jiang S (2022) ENTS: An Edge-native Task Scheduling System for Collaborative Edge Computing. IEEE/ACM 7th Symposium on Edge Computing, SEC. pp 149–161

Google Scholar  

Kim SH, Kim T (2023) Local scheduling in kubeedge-based edge computing environment. Sensors 23(3):1522

E. Casalicchio (2019) “Container orchestration: A survey,” Syst Model, 221–235.

Pahl C, Brogi A, Soldani J, Jamshidi P (2017) Cloud container technologies: a state-of-the-art review. IEEE Transact Cloud Comput 7(3):677–692

Rodriguez MA, Buyya R (2019) Container-based cluster orchestration systems: A taxonomy and future directions. Software Pract Experience 49(5):698–719

Truyen E, Van Landuyt D, Preuveneers D, Lagaisse B, Joosen W (2019) A comprehensive feature comparison study of open-source container orchestration frameworks. Appl Sciences (Switzerland) 9(5):931

Arunarani AR, Manjula D, Sugumaran V (2019) Task scheduling techniques in cloud computing: a literature survey. Futur Gener Comput Syst 91:407–415

Vijindra and S. Shenai, (2012) Survey on scheduling issues in cloud computing. Procedia Eng 38:2881–2888

Wang K, Zhou Q, Guo S, Luo J (2018) Cluster frameworks for efficient scheduling and resource allocation in data center networks: a survey. IEEE Commun Surveys Tutor 20(4):3560–3580

Hosseinioun P, Kheirabadi M, Kamel Tabbakh SR, Ghaemi R (2022) A task scheduling approaches in fog computing: a survey”. Transact Emerg TelecommunTechnol 33(3):e3792

Rejiba Z, Chamanara J (2022) Custom scheduling in Kubernetes: a survey on common problems and solution approaches. ACM Comput Surv 55(7):1–37

Carrión C (2022) Kubernetes scheduling: taxonomy, ongoing issues and challenges. ACM Comput Surv 55(7):1–37

Article   MathSciNet   Google Scholar  

Santos J, Wauters T, Volckaert B, De Turck F (2019) Towards network-Aware resource provisioning in kubernetes for fog computing applications. Proceedings of the IEEE Conference on Network Softwarization: Unleashing the Power of Network Softwarization. pp 351–359

Chung A, Park JW, Ganger GR (2018) Stratus: Cost-aware container scheduling in the public cloud. Proceedings of the ACM Symposium on Cloud Computing. pp 121–134

Chapter   Google Scholar  

Le TN, Sun X, Chowdhury M, Liu Z (2020) AlloX: Compute allocation in hybrid clusters. Proceedings of the 15th European Conference on Computer Systems, EuroSys

Zhong Z, Buyya R (2020) A Cost-Efficient Container Orchestration Strategy in Kubernetes-Based Cloud Computing Infrastructures with Heterogeneous Resources. ACM Trans Internet Technol 20(2):1–24

Thinakaran P, Gunasekaran JR, Sharma B, Kandemir MT, Das CR (2019) Kube-Knots: Resource Harvesting through Dynamic Container Orchestration in GPU-based Datacenters. Proceedings - IEEE International Conference on Cluster Computing, ICCC

Townend P et al (2019) Invited paper: Improving data center efficiency through holistic scheduling in kubernetes. Proceedings - 13th IEEE International Conference on Service-Oriented System Engineering, 10th International Workshop on Joint Cloud Computing, and IEEE International Workshop on Cloud Computing in Robotic Systems, CCRS. pp 156–166

Menouer T (2021) KCSS: Kubernetes container scheduling strategy. J Supercomput 77(5):4267–4293

Song S, Deng L, Gong J, Luo H (2019) Gaia scheduler: A kubernetes-based scheduler framework. 16th IEEE International Symposium on Parallel and Distributed Processing with Applications, 17th IEEE International Conference on Ubiquitous Computing and Communications, 8th IEEE International Conference on Big Data and Cloud Computing. pp 252–259

Ogbuachi MC, Gore C, Reale A, Suskovics P, Kovacs B (2019) Context-aware K8S scheduler for real time distributed 5G edge computing applications. 27th International Conference on Software, Telecommunications and Computer Networks, SoftCOM

Beltre A, Saha P, Govindaraju M (2019) KubeSphere: An approach to multi-tenant fair scheduling for kubernetes clusters. 3rd IEEE International Conference on Cloud and Fog Computing Technologies and Applications, Cloud Summit. pp 14–20

Haja D, Szalay M, Sonkoly B, Pongracz G, Toka L (2019) Sharpening Kubernetes for the Edge. ACM SIGCOMM Conference Posters and Demos, Part of SIGCOMM. pp 136–137

Wojciechowski L et al (2021) NetMARKS: Network metrics-AwaRe kubernetes scheduler powered by service mesh. Proceedings - IEEE INFOCOM

Cai Z, Buyya R (2022) Inverse Queuing Model-Based Feedback Control for Elastic Container Provisioning of Web Systems in Kubernetes. IEEE Trans Comput 71(2):337–348

Article   MATH   Google Scholar  

El Haj Ahmed G, Gil-Castiñeira F, Costa-Montenegro E (2021) KubCG: A dynamic Kubernetes scheduler for heterogeneous clusters. Software Pract Experience 51(2):213–234

Ungureanu OM, Vlădeanu C, Kooij R (2019) Kubernetes cluster optimization using hybrid shared-state scheduling framework. ACM International Conference Proceeding Series

Yang S, Ren Y, Zhang J, Guan J, Li B (2021) KubeHICE: Performance-aware Container Orchestration on Heterogeneous-ISA Architectures in Cloud-Edge Platforms. 19th IEEE International Symposium on Parallel and Distributed Processing with Applications, 11th IEEE International Conference on Big Data and Cloud Computing, 14th IEEE International Conference on Social Computing and Networking and 11th IEEE Internation. pp 81–91

Li D, Wei Y, Zeng B (2020) A Dynamic I/O Sensing Scheduling Scheme in Kubernetes. ACM International Conference Proceeding Series. pp 14–19

Fan D, He D (2020) A Scheduler for Serverless Framework base on Kubernetes. ACM International Conference Proceeding Series. pp 229–232

Bestari MF, Kistijantoro AI, Sasmita AB (2020) Dynamic Resource Scheduler for Distributed Deep Learning Training in Kubernetes. 7th International Conference on Advanced Informatics: Concepts, Theory and Applications, ICAICTA

Dua A, Randive S, Agarwal A, Kumar N (2020) Efficient Load balancing to serve Heterogeneous Requests in Clustered Systems using Kubernetes. IEEE 17th Annual Consumer Communications and Networking Conference, CCNC

Kaur K, Garg S, Kaddoum G, Ahmed SH, Atiquzzaman M (2020) KEIDS: Kubernetes-Based Energy and Interference Driven Scheduler for Industrial IoT in Edge-Cloud Ecosystem. IEEE Internet Things J 7(5):4228–4237

Lin M, Xi J, Bai W, Wu J (2019) Ant colony algorithm for multi-objective optimization of container-based microservice scheduling in cloud. IEEE Access 7:83088–83100

Wei-guo Z, Xi-lin M, Jin-zhong Z (2018) Research on kubernetes’ resource scheduling scheme. ACM International Conference Proceeding Series

Oleghe O (2021) Container placement and migration in edge computing: concept and scheduling models. IEEE Access 9:68028–68043

Carvalho M, MacEdo DF (2021) QoE-Aware Container Scheduler for Co-located Cloud Environments,” Faculdades Catolicas

Chen T, Li M, Li Y, Lin M, Wang N, Wang M, Xiao T, Xu B, Zhang C, Zhang Z (2015) Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv preprint arXiv:1512.01274

Abadi M et al (2016) Tensorflow: a system for large-scale machine learning. Osdi 2016(16):265–283

Xing EP et al (2015) Petuum: A new platform for distributed machine learning on big data. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp 1335–1344

Verma A, Pedrosa L, Korupolu M, Oppenheimer D, Tune E, Wilkes J (2015) Large-scale cluster management at Google with Borg. 10th European Conference on Computer Systems, EuroSys. pp 1–15

Vavilapalli VK et al (2013) Apache hadoop YARN: Yet another resource negotiator. 4th Annual Symposium on Cloud Computing, SoCC. pp 1–16

Bao Y, Peng Y, Wu C, Li Z (2018) Online Job Scheduling in Distributed Machine Learning Clusters. Proceedings - IEEE INFOCOM. pp 495–503

Peng Y, Bao Y, Chen Y, Wu C, Guo C (2018) Optimus: An Efficient Dynamic Resource Scheduler for Deep Learning Clusters. Proceedings of the 13th EuroSys Conference, EuroSys

Mao H, Schwarzkopf M, Venkatakrishnan SB, Meng Z, Alizadeh M (2019) Learning scheduling algorithms for data processing clusters. SIGCOMM Conference of the ACM Special Interest Group on Data Communication. pp 270–288

Chaudhary S, Ramjee R, Sivathanu M, Kwatra N, Viswanatha S (2020) Balancing efficiency and fairness in heterogeneous GPU clusters for deep learning. Proceedings of the 15th European Conference on Computer Systems, EuroSys

Fu Y et al (2019) Progress-based Container Scheduling for Short-lived Applications in a Kubernetes Cluster. IEEE International Conference on Big Data, Big Data. pp 278–287

Peng Y, Bao Y, Chen Y, Wu C, Meng C, Lin W (2021) DL2: A Deep Learning-Driven Scheduler for Deep Learning Clusters. IEEE Trans Parallel Distrib Syst 32(8):1947–1960

Mao Y, Fu Y, Zheng W, Cheng L, Liu Q, Tao D (2022) Speculative Container Scheduling for Deep Learning Applications in a Kubernetes Cluster. IEEE Syst J 16(3):3770–3781

Huang J, Xiao C, Wu W (2020) RLSK: A Job Scheduler for Federated Kubernetes Clusters based on Reinforcement Learning. IEEE International Conference on Cloud Engineering, IC2E. pp 116–123

Wang H, Liu Z, Shen H (2020) Job scheduling for large-scale machine learning clusters. Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies. pp 108–120

Han Y, Shen S, Wang X, Wang S, Leung VCM (2021) Tailored learning-based scheduling for kubernetes-oriented edge-cloud system. Proceedings - IEEE INFOCOM

Casquero O, Armentia A, Sarachaga I, Pérez F, Orive D, Marcos M (2019) Distributed scheduling in Kubernetes based on MAS for Fog-in-the-loop applications. IEEE International Conference on Emerging Technologies and Factory Automation, ETFA. pp 1213–1217

Yang Y, Chen L (2019) Design of Kubernetes Scheduling Strategy Based on LSTM and Grey Model. Proceedings of IEEE 14th International Conference on Intelligent Systems and Knowledge Engineering, ISKE. pp 701–707

Zhang X, Li L, Wang Y, Chen E, Shou L (2021) Zeus: Improving Resource Efficiency via Workload Colocation for Massive Kubernetes Clusters. IEEE Access 9:105192–105204

Liu Z, Chen C, Li J, Cheng Y, Kou Y, Zhang D (2022) KubFBS: A fine-grained and balance-aware scheduling system for deep learning tasks based on kubernetes. Concurrency Computat Pract Exper 34(11):e6836. https://doi.org/10.1002/cpe.6836

Rahali M, Phan CT, Rubino G (2021) KRS: Kubernetes Resource Scheduler for resilient NFV networks. IEEE Global Communications Conference

Taherizadeh S, Stankovski V (2019) Dynamic multi-level auto-scaling rules for containerized applications. Computer J 62(2):174–197

Rattihalli G, Govindaraju M, Lu H, Tiwari D (2019) Exploring potential for non-disruptive vertical auto scaling and resource estimation in kubernetes. IEEE International Conference on Cloud Computing, CLOUD. pp 33–40

Toka L, Dobreff G, Fodor B, Sonkoly B (2021) Machine Learning-Based Scaling Management for Kubernetes Edge Clusters. IEEE Trans Netw Serv Manage 18(1):958–972

Balla D, Simon C, Maliosz M (2020) Adaptive scaling of Kubernetes pods. IEEE/IFIP Network Operations and Management Symposium 2020: Management in the Age of Softwarization and Artificial Intelligence, NOMS

Toka L, Dobreff G, Fodor B, Sonkoly B (2020) Adaptive AI-based auto-scaling for Kubernetes. IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGRID. pp 599–608

Wang M, Zhang D, Wu B (2020) A Cluster Autoscaler Based on Multiple Node Types in Kubernetes. IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference, ITNEC. pp 575–579

Kang R, Zhu M, He F, Sato T, Oki E (2021) Design of Scheduler Plugins for Reliable Function Allocation in Kubernetes. 17th International Conference on the Design of Reliable Communication Networks, DRCN

Vu DD, Tran MN, Kim Y (2022) Predictive hybrid autoscaling for containerized applications. IEEE Access 10:109768–109778

Download references

Acknowledgements

The author(s) received no financial support for the research and publication of this article.

Author information

Authors and affiliations.

Department of Computer Science, College of Computing and Informatics, University of Sharjah, Sharjah, UAE

Khaldoun Senjab, Sohail Abbas & Naveed Ahmed

College of Engineering and Information Technology, Ajman University, Ajman, UAE

Atta ur Rehman Khan

You can also search for this author in PubMed   Google Scholar

Contributions

Research was supervised by Sohail Abbas and Naveed Ahmed. Data collection, material preparation, and analysis were performed by Khaldoun. All authors read and approved the final manuscript. Conceptualization and revisions done by Sohail Abbas, Naveed Ahmed and Atta ur Rehman.

Corresponding author

Correspondence to Sohail Abbas .

Ethics declarations

Ethics approval and consent to participate.

Not applicable.

Consent for publication

Authors provide consent for publication.

Competing interests

The authors declare no competing interests.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Cite this article.

Senjab, K., Abbas, S., Ahmed, N. et al. A survey of Kubernetes scheduling algorithms. J Cloud Comp 12 , 87 (2023). https://doi.org/10.1186/s13677-023-00471-1

Download citation

Received : 27 January 2023

Accepted : 01 June 2023

Published : 13 June 2023

DOI : https://doi.org/10.1186/s13677-023-00471-1

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

• Cloud services
• Data center infrastructure
• Resource optimization
• Containerized applications
• Container orchestration
• Scheduling algorithm

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

Project Scheduling Tools and Techniques for Effective Construction Management

2019, Advances in Multidisciplinary & Scientific Research Journal Publication

Related Papers

IAEME Publication

Construction scheduling is a complex and challenging task demanding an in depth expertise. Consideration of several factors, their influences and likely impact on the schedule need a thorough understanding. It is mostly experience based knowledge in the form of heuristics, available with the experienced schedulers. In this connection this study mainly discusses the factors influencing construction scheduling and techniques through a comparative study of various international construction projects. About 40 relevant articles published over the last 25 years have been reviewed. However, each and every limited formalized knowledge is available in theoretical form, which is interesting to many researchers for many decades, a comprehensive research is made and a comparative study on the literatures was carried out and presented in this paper. The main aim of the paper is to highlight the major factors which are to be mainly considered for the successful completion of the project.

International Journal of Civil Engineering and Technology (IJCIET)

B. K. DAS , F. Rajak

Construction of building and infrastructure development is a part of great civilizations throughout the different time of development. The great examples of buildings such as great pyramid, Great Wall of China and many more ancient structures of historical importance, all are examples of marvellous Architecture. The basic part of completion of these buildings are design, execution and closure. Design is the foremost and important whereas the execution is the most important in order to complete the project in timely manner and with quality. There is certainly some excellent quality and construction management methodology was adopted during those time and someone is present there to manage the resources and time scheduling. In present time there are various mathematical tools and techniques are being used such as Bar chart, CPM, PERT etc. in construction project management to handle the construction projects. Various standalone and web-based packages are also in practice to handle the multi-tasking and complex construction environment. This paper aims to explore the start of management tools and techniques in historical era to present day time, when we are handling very complex construction practices.

robert mullen

Journal of Construction Engineering and Management

Matthew Liberatore

Aftab Hameed Memon

Challenge of completing construction projects within estimated time frame is biggest concern amongst the practitioners. Several approaches and tools have been introduced over the past years to enhance the management of the construction projects. This paper has identified commonly used techniques and software packages of time management together with their effectiveness level in large construction projects of Malaysia. Data was gathered through survey technique amongst the practitioners involved in handling large construction projects. Relative Importance Index calculation was employed to assess the level of effectiveness for time management techniques and software packages adopted in the construction project. The results highlighted that most common and effective time management technique and software Package are CPM and Microsoft Project respectively. Although, this technique and software package in almost every project is applied, but still the industry practitioners fail in achieving effective time management. Hence, this study recommends the further investigation be carried out in uncovering the related issue which hindrance in achieving the benefits of these in construction projects.

Mohamad Mohamad

Kalle Kahkonen

Project management standards are gradually moving to the direction where increasingly attention is put on cooperation and collaboration methods between different players involved in construction operation. Construction professionals and other experts i.e. in academia agree widely that this is essential. Construction business and its operations in general have not been isolated from the long term developments in different sectors such as outsourcing where core businesses is valued high and other operations are cut away. This has resulted in high number of specialized companies that on the other hand has increased the total number of partners in any kind of construction project. From the management viewpoint this is a different challenge and it has naturally provided the starting point for new kind of managerial tools and solutions. This paper provides discussion of the characteristics of modern construction and those as starting points for the development of new kind of construction ...

Mohamed Unais

mohamad mohamad

Jeethendrasai Kumar

RELATED PAPERS

Journal of Fluorine Chemistry

mohamed besheesh

Physical Review D

Pedro Moraes

Rachael Petersen

Adaptive and Integrated Water Management

Christian Regli

Medip Academy

Navus - Revista de Gestão e Tecnologia

Eliane Bianchi

Pakistan Journal of Biological Sciences

Rupa Mazumder

MANAS Sosyal Araştırmalar Dergisi

Elif Boyraz

Antonio Gargano

Prosiding Semirata 2013

Dr. Y U S F I A T I , M.Si

AIAA Journal

Mahfuz Ahmed

Printer Mesinfotocopy15

Physical chemistry chemical physics : PCCP

Tomohiro Hayashi

Mursalim Mursalim

Acta Scientiae Veterinariae

Felipe Moisés Mercado Duarte

Scientific Reports

Alireza Biglari

Current Problems of Psychiatry

Agata Banakiewicz

BMC Research Notes

daniel aguilar

SSRN Electronic Journal

Joseph James

Zeitschrift für Kristallographie - New Crystal Structures

Thulani Hlela

Journal of Labelled Compounds and Radiopharmaceuticals

Laurence Harwood

Liliana Lefticariu

Bisma Yudha Mandala

Dieudonné Leclercq

The Journal of Physical Chemistry A

Michael Shatruk

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024