Introduction

Medical technology has played and will play a major role in the well being of human beings. Hospitals are places where the medical technology is put into practical use. Many hospitals have an operation theatre. The operating theatre is one of the most expensive departments in the hospital and it is here the surgeries are performed. Surgeons as well as administrators have a responsibility to ensure that theatre facilities are used as fully as possible and also that good use is made of the operating time in the theatre so that the dividend from the investments on the operation theatre is maximized.

The operating theatre is composed of several operating rooms and one or more recovery room where several beds will be available for the patients to recuperate. There will also be a waiting room where the patients are prepared for surgery. Thus, there should be a seamless flow of patients from the waiting room to the recovery room. For this there should be an optimal number of beds in the recovery room as well as waiting room. The patient cannot occupy the operating table for want of bed in the recovery room or the patient be prepared for surgery on the surgical table. Also, in some cases there is a waiting list of patients who want to undergo surgery because of the limited availability of specialized equipment and their waiting time has to be minimized. Thus, in operation theatre scheduling, the patient satisfaction and resource efficiency needs to be maximized. The hospitalisation costs, i.e. the patient stay duration, and the overtime costs, i.e. the resource overloads, are used as indices for patient satisfaction and resource efficiency, respectively. A good system of planning and scheduling in theatre will enable more work, including emergencies, to be carried out at a reasonable time, improve the patient and carer experience, and improve employee satisfaction and morale. It is for these reasons operation theatre scheduling using scientific techniques is increasingly being done in many hospitals.

One of the variables required for operation theatre scheduling is the duration of the surgery. It plays an important role in scheduling of the surgeries, human resource planning and in many other logistic as well as planning activities. However, each patient needs a particular surgical procedure, which defines the human (surgeon) and material (equipment) resources to be used and the duration of surgery. The duration of the surgery also depends on several other factors such as experience of the surgeon, supporting staff, type of anaesthesia, precondition of the patient, etc. The actual list of variables that govern the duration of surgery and the duration of stay of the patient in the recovery room will itself depend on the type of surgery. Thus, it is a challenging task to come up with a framework to predict the duration of surgery time for a given patient.

This work focuses on developing a general framework to forecast the surgery time, given the type of surgery and the list of variables that govern its duration. Using the surgery time predicted by this framework, algorithms are developed for scheduling the operating room optimally.

There are two types of surgery—elective and emergency. Here we consider scheduling of elective surgeries alone. The scheduling of operation theater for emergency surgery cannot be done as it is done for elective surgery because of different patient arrival characteristics and the need to have near zero patient waiting time. Also, usually there would be separate operating rooms for emergency surgery. For elective surgery, the patient gets an appointment for surgery and arrives at the pre determined time. Then, the patient is prepared for surgery, taken to the operating table, surgery performed and then taken to the recovery room. The patient then stays in the recovery room for some time. Because the patient cannot occupy the operating table for want of bed in the recovery room or the patient be prepared for surgery on the surgical table, the scheduling of the operation theater depends on the duration of each of these jobs which in turn will vary with the type of surgery and patient profile among other variables. Even though estimating the duration of each of these jobs is equally important, here we focus on forecasting the surgery time and schedule the operating theater based on it alone, assuming all other resources are available readily. We note that the same framework could be used for forecasting the duration of the other jobs and the entire process scheduled, this is not done here, however, and is delegated for a future work in this area.

Considering the problem of forecasting the surgical time in some detail, we observe that the surgery time depends on factors like the patient profile, type of anesthesia used, experience of the anesthesiologist, surgeon and supporting staff, etc. Patient profile includes patient precondition, sex, age, etc. For example, if the patient has high blood pressure, which is a precondition, his/her blood pressure has to be monitored which will take sometime, the type of anesthesia would be different which again would influence the duration of surgery. The experience (in years) of the individuals also plays a role, with the duration of surgery reducing somewhat with experience. Thus, it is a challenging task in itself to find out the independent variables that influence the surgery time.

This work illustrates the working of the general framework developed to forecast surgery time for three types of surgeries, namely, cataract surgery, corneal transplant surgery and Oculoplastic surgery. These surgeries are chosen mainly because these are the major type of surgeries performed in the operation theatre in the ophthalmology department of a local hospital for which the required data is readily available. Similarly, even though using the developed algorithm any operating theatre could be scheduled, for the same reasons mentioned above, the operation theater in the ophthalmology department of the same local hospital is only scheduled.

Literature review

Cardoen et al. [1] provides an excellent review of the state of the art in operation room scheduling and discussion on the various objective functions and analysis procedures adopted. Based on the requirement of the local hospital, the operating room is scheduled so that the work load on each of the tables is nearly the same. Chaabane et al. [2] considers two different objective functions for operating theatre planning. In one the surgeon constraints are optimized while in the other patient constraints are met. Linear Programming Model method is used for optimization. The Monte Carlo simulation method has been used by Dexter et al. [3] to find the delay in the schedule between different surgeon’s cases in the same operating room on the same day using upper prediction bounds for case durations. Guinet et al. and Jebali et al. [4, 5] use mixed integer program and minimizes the patients cost. Kraft et al. [6] presented the prediction of length of stay of patients with spinal cord injury in Veteran’s Health Administration Hospital is presented. Data mining methods like artificial neural network is used in order to predict the length of stay of patients in the hospital. Lorraine et al. [7] uses integer linear programming and constraint programming to optimally schedule nurses such that the work load on each of them is the same. They also demonstrate the efficacy of integer linear programming in finding an optimal solution. Pham et al. [8] proposed a new surgical case scheduling approach which uses a novel extension of the job shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem. They assume that the required hospital resources for the surgery are readily available and maximized the utilization of the operating theatre. The hierarchical approach for the weekly scheduling of operating rooms is reported by Testi et al. [9]. This paper focuses on surgical activity planning in order to improve overall operating theatre efficiency in terms of overtime and throughput as well as waiting list reduction, while improving department organization. This scheduling of the operating room requires prediction of the duration of surgery time. Combes et al. [10] uses rough sets to forecast the surgery time. A process of knowledge discovery in databases using this data mining method to forecast surgery time is also pioneered by them. Till then the variability in the duration of the surgery with the patient profile is not considered. Roland et al. [11] proposed a two stage planning of operation theater such as the planning phase and scheduling phase respectively. Chen et al. [12] has proposed operating room scheduling that integrates both quantitative and qualitative multiple objectives for improving the OR scheduling quality. Augusto et al. [13] has proposed a Lagrangian relaxation based method to solve the scheduling problem. Concurring with [10] it is found that variability in the surgery time with patient profile needs to be considered for a realistic scheduling of the operation theatre and hence this problem is addressed here.

Despite the proliferation of computerized planning and scheduling procedures proposed by the scientific community, the implementation rate of satisfying technological planning or evaluation systems still seems to be low. In order to increase the operating theatre efficiency, a closer cooperation between the academic institutions and the practitioners should be encouraged [14].

Artificial neural networks

An artificial neural network, often just called a “neural network”, is a mathematical model which attempts to capture the brain’s problem solving ability and apply them to information systems. The complexity of real neurons is highly abstracted when modeling artificial neurons. These basically consist of inputs which are multiplied by weights (strength of the respective signals), and then a mathematical function determines the activation of the neuron. Another function computes the output of the artificial neuron. The higher a weight of an artificial neuron is, the stronger the input which is multiplied by it will be. Weights can also be negative, so we can say that the signal is inhibited by the negative weight. Depending on the weights, the computation of the neuron will be different. By adjusting the weights of an artificial neuron one can obtain the required output for specific inputs. But when we have an ANN of hundreds or thousands of neurons, it is complicated to find by hand all the necessary weights. But there are algorithms which can adjust the weights of the ANN in order to obtain the desired output from the network. This process of adjusting the weights is called learning or training.

The learning process consists of determining values for the weights Wi which lead to an optimal association of the inputs and outputs. The flowchart for this learning process is shown in Fig. 1 wherein the target denotes the desired output. Thus, ANNs can be and are used to find the relationship between various variables.

Fig. 1
figure 1

Flowchart for learning process of ANN

Full size image

Regression analysis

Regression analysis is the statistical technique that identifies the relationship between two or more quantitative variables: a dependent variable, whose value is to be predicted, and an independent or explanatory variable (or variables), about which knowledge is available. Thus, the general purpose of multiple regressions is to find the relationship between several independent or predictor variables and a dependent or criterion variable. This technique is useful when the form of the equation that represents the relationship between the variables is known. In a linear regression analysis, the relation between an independent variable X and a dependent variable Y is linear, thus, \( Y = {\hbox{a}} + {\hbox{b}}X \) (where a and b are constants). Here a linear equation of the form, \( Y = {{\hbox{a}}_0} + {{\hbox{a}}_1}{X_1} + {{\hbox{a}}_2}{X_2} + \ldots + {{\hbox{a}}_n}{X_n} \), where ai’s are constants and X i’s are independent variables is assumed to relate the independent variables and the dependent variable. The model constants ai’s are determined using all the available data using standard regression analysis technique. Logistic regression and Artificial intelligence models like artificial neural networks are the most common models for processing multivariate data in the medical literature [15, 16]. Hence we have used the two methods, artificial neural networks and multiple linear regression analysis, to predict the duration of surgery and their performance ranked.

Adaptive neuro fuzzy inference system

While ANN is a good technique that emulates the way a human brain makes a judgment, a limitation is the way it handles the input data. In the case of human reasoning, input data need not always be crisp but could have linguistic labels like “small”, “high”, etc. Also, the response to the data need not always follow a strict “yes-no rule”. A fuzzy inference system using fuzzy rules can model qualitative aspects of human behavior. This was first explored by Takagi and Sugeno and has since been used in numerous applications involving predictions [17].

Fuzzy inference systems are composed of five functional blocks. These are (a) a rule base containing a number of if-then rules (b) a database which defines the membership function, (c) a decision making interface that operates the given rules (d) a fuzzification interface that converts the crisp inputs into “degree of match” with the linguistic values like high or low, etc. and (e) a de-fuzzification interface that reconverts to a crisp output.

Adaptive Neuro Fuzzy Inference system (ANFIS) is a hybrid technique which combines the adaptive learning capability of ANN along with the intuitive fuzzy logic of human reasoning, formulated as a feed-forward neural network. Hence, the advantages of a fuzzy system can be combined with a learning algorithm. Fusion of Artificial Neural Networks (ANN) and Fuzzy Inference Systems (FIS) is used by researchers in various scientific and engineering areas due to the growing need of adaptive intelligent systems to solve the real world problems. ANN learns by adjusting the weights of interconnections between layers. FIS uses fuzzy set theory, fuzzy if-then rules, and fuzzy reasoning.

Forecasting the duration of surgery

  1. 1.

    The surgery time is forecast by taking into account the surgical environment in order to minimize the variability in the predicted surgery time. Variables such as Experience (in years) of each of the surgeons performing operation (At most 2 surgeons are involved in a surgery)

  2. 2.

    Experience of accompanying theatre staff (in years)

  3. 3.

    Type of anaesthesia (Local or General)

  4. 4.

    Experience of anaesthetist

  5. 5.

    Patient preconditions like existence of Redness of eye, diabetics, hypertension, watery eyes or any other sources of infection

  6. 6.

    Patient age

  7. 7.

    Duration of surgery

constitutes the surgical environment. The actual set of environment variables depends on the type of surgery.

Data for corneal transplant surgery

From the data given in Table 5 of Appendix, it is inferred that the same surgeons are performing the surgery. Hence, this variable is not considered in the ANN or regression models. Type of anesthesia (0—Local, 1—General) for this type of surgery is decided by the age of the patient. Hence, this variable is also not considered for the ANFIS or ANN or regression models. For this type of surgery three preconditions—diabetics (0), hypertension (1), and infection of the eye (2)—are considered to influence the duration of surgery. Hence, three variables are used for each of these three preconditions which take a value of 1 if that precondition is present or else take a value of −1. The range of other input variables—patient age and experience of the anesthetist and nurse—is linearly scaled so that it varies between −1 and 1. These input variables were scaled taking physically reasonable extreme values. Thus, age is assumed to vary between 0 and 100 and the experience of the nurse between 8 and 20 and that of the anesthetist between 7 and 20.

Data for cataract surgery

From the data given in Table 6 in Appendix, it is inferred that the same surgeons and anesthetist are performing the surgery. Hence, these variables are not considered in the prediction models. Type of anesthesia (0—Local, 1—General) for this type of surgery is always local. Hence, this variable is also not considered for the ANN or regression models. For this type of surgery three preconditions—diabetics (0), hypertension (1), and infection of the eye (2)—are considered to influence the duration of surgery. Hence, three variables are used for each of these three preconditions which take a value of 1 if that precondition is present or else take a value of −1. The range of other input variables—patient age and experience of the nurse—is linearly scaled so that it varies between −1 and 1. These input variables were scaled taking physically reasonable extreme values. Thus, age is assumed to vary between 0 and 100 and the experience of the nurse between 3 and 15 years.

Data for oculoplastic surgery

From the data given in Table 7 of Appendix, it is inferred that the same surgeons and anesthetist are performing the surgery. Hence, these variables are not considered in the ANN or regression models. Type of anesthesia (0—Local, 1—General) for this type of surgery does not depend on other variables. Hence, this variable is considered in the prediction models. For this type of surgery three preconditions—diabetics (0), hypertension (1), and infection of the eye (2)—are considered to influence the duration of surgery. Hence, three variables are used for each of these three preconditions which take a value of 1 if that precondition is present or else take a value of −1. The range of other input variables—patient age and experience of the nurse—is linearly scaled so that it varies between −1 and 1. These input variables were scaled taking physically reasonable extreme values. Thus, age is assumed to vary between 0 and 100 and the experience of the nurse between 3 and 15.

Prediction using adaptive neuro fuzzy inference systems

The ANFIS architecture used in our study uses Sugeno type fuzzy inference systems and Triangular membership function is used to train the given data set. The results of fuzzy inference prediction obtained using Matlab software for the three surgeries namely corneal transplant, cataract and occuplastic surgeries are shown in Fig. 2(a, b and c) respectively. The average root mean square error between the actual and predicted values is reported as 0.1557, 0.070 and 0.1431 for the corneal transplant surgery, cataract surgery and occuplastic surgery respectively.

Fig. 2
figure 2

a Actual vs. predicted surgery time for Corneal transplant surgery b Actual vs. predicted surgery time for cataract surgery c Actual vs. predicted surgery time for Occuplastic surgery

Full size image

Prediction using artificial neural networks

Separate ANN and regression models are developed for each type of surgery studied. A feed forward network with just one hidden layer is used. The number of the neurons in the hidden layer is varied between 5 and 13. The resulting RMS error is tabulated in Table 1 from which it was found that 11 neurons are required to obtain least RMS error. This 11 neurons hidden layer model is used for further analysis.

Table 1 RMS error for various ANN models
Full size table

Performance analysis of ANN and regresion model

Using the actual data collected from 100 patient records from a local hospital for each type of surgery and reported in Appendix Tables 5, 6, 7, the ANN (or the regression) model is calibrated. The regression equations for the regression prediction are given in Eqs 1 to 3.

$$ {\hbox{Surgery}}\,{\hbox{time}}\,{\hbox{for}}\,{\hbox{corneal}}\,{\hbox{transplant}} = 0.5145 + 0.0494*\,{\hbox{Age}} + 0.113*\,{\hbox{Exp}}\,{\hbox{Staff}} - 0.0674*{\hbox{Exp}}\,{\hbox{Anesth}}{.} + 0.0001*{\hbox{Diabetics}} - 0.0022*{\hbox{Hypertension}} - 0.0065*{\hbox{Infected}}\,{\hbox{eye}} $$
(1)
$$ {\hbox{Surgery}}\,{\hbox{time}}\,{\hbox{for}}\,{\hbox{cataract}}\,{\hbox{surgery}} = 0.7307 + 0.1133*{\hbox{Age}} - 0.0098*{\hbox{Exp}}\,{\hbox{Staff}} - 0.0117*{\hbox{Diabetics}} - 0.0328*{\hbox{Hypertension}} - 0.0002*{\hbox{Infected}}\,{\hbox{eye}} $$
(2)
$$ {\hbox{Surgery}}\,{\hbox{time}}\,{\hbox{for}}\,{\hbox{Ocuplastic}}\,{\hbox{surgery}} = 0.6828 + 0.0435*{\hbox{Age}} + 0.0068*{\hbox{Exp}}\,{\hbox{Staff}} - 0.0535*{\hbox{Type}}\,{\hbox{of}}\,{\hbox{Anesth}}. + 0.0404*{\hbox{Diabetics}} - 0.0001*{\hbox{Hypertension}} - 0.0227*{\hbox{Infected}}\,{\hbox{eye}} $$
(3)

The prediction of this calibrated model for the same 100 records is presented in Fig. 3(a, b and c). Figure 3(a) presents the actual and predicted surgery time for corneal transplant surgery, Fig. 3(b) portrays the actual and predicted surgery time for cataract surgery and Fig. 3(c) for Oculoplastic surgery. In Table 2 the RMS error for all the prediction models for the three types of surgeries is recorded. It is seen from the table that ANFIS outperforms the ANN and regression model. Hence, for subsequent prediction of the duration of surgery, for scheduling the operation room, ANFIS model is used.

Fig. 3
figure 3

a Actual and Predicted surgery Time for ANN and Multiple Regression analysis in Corneal Transplant b Actual and Predicted surgery Time for ANN and Multiple Regression analysis in Cataract surgery c Actual and Predicted surgery Time for ANN and Multiple Regression analysis in Oculoplastic Surgery

Full size image
Table 2 Comparison of RMS error
Full size table

Scheduling of operating theater

Based on the requirements of local hospital and a survey of objective functions used in the literature for scheduling of operating theater, it is required that the total duration of surgery on each of the beds is nearly the same.

Formulating this mathematically,

Min C max

Subject to:

$$ \begin{gathered} \sum\limits_{j = 1}^n {{x_{ij}}{ }{{\hbox{p}}_j}} { } \leqslant { }{{\hbox{C}}_{{ \max }}}{\hbox{ i}} = 1,...,m;{ } \hfill \\\sum\limits_{i = 1}^m {{x_{ij}}{ } = {\hbox{ 1 j}} = 1,....,n}; \hfill \\\end{gathered} $$

where, ‘pj’ is the duration of the jth surgery ‘m’ is the number of operating beds and ‘n’ is the number of surgeries to be scheduled and if surgery j is scheduled on bed i, x ij = 1 else x ij = 0. Thus, here a set of independent tasks has to be assigned to parallel identical processors in order to minimize schedule length. The tasks being independent, at no point in time, will the execution of a particular task, gain precedence over the others. This problem is known to be NP hard in the strong sense and is called the P||Cmax problem. Here this problem is solved using integer linear programming implemented in Time Optimization, Resources, Scheduling {TORSCHE} Toolbox for MATLAB developed by Czech Technical University in Prague.

A program has been developed using MATLAB software to predict the duration of surgery to take place using ANFIS and to schedule the operating room. For this a program has been developed which given a type of surgery decides the variables that determine the surgical environment and gets input regarding the same. Then the duration of surgery is predicted using the appropriate trained ANFIS model. Using this predicted duration of surgery the operations are scheduled using the P||Cmax algorithm implemented in TORSCHE toolbox.

The program is also self learning, in that the ANFIS model gets updated at the end of each day with the actual duration of the surgery for the operations performed on that day. This is necessary because the surgical environment changes with time and this requires constant updating of the model used to predict the surgery time. Use of ANFIS to predict the surgery time is particularly helpful in this context. It is possible to adapt the ANFIS so that the prediction is based on the data from the recent past and this is what is done here. This framework is yet to be evaluated in the actual hospital scenario. However, its performance is evaluated through a few trial runs.

Results and discussions

Assuming that only three types of surgeries namely—corneal transplant, cataract and Oculoplastic surgery—are performed in an operating theater having four beds, the problem of scheduling 10 surgeries to the four beds is studied. As a typical case, Table 3 lists the patients to be operated on a particular day. The last column in the table is the duration of surgery time as predicted by the ANFIS model. Figure 4a depicts the scheduling of these 10 patients to the four available beds. It is found that each of the beds is utilized for nearly the same amount of time (i.e. 78 min for Bed 1, 79 min for Bed 2, 82 min for Bed 3, 81 min for Bed 4). Table 4 lists another set of ten patients to be operated on a particular day. Figure 5a portrays the scheduling of these 10 patients. It can be seen from these figures that the difference in the total operation time between the beds is less than 10 min. This indicates that the workload is evenly distributed between the beds.

Table 3 Profile of 10 patients to be operated on a particular day used to obtain Fig. 4a
Full size table
Fig. 4
figure 4

Scheduling of 10 patients listed in Table 3 to 4 beds a Considering surgical environment b Not considering surgical environment

Full size image
Table 4 Profile of 10 patients to be operated on a particular day used to obtain Fig. 5a
Full size table
Fig. 5
figure 5

Scheduling of 10 patients listed in Table 4 to 4 beds a Considering surgical environment b Not considering surgical environment

Full size image

The case when the duration of surgery is not determined taking into account the surgical environment is examined. In this case, the mean surgery time for a given type of surgery is used for scheduling. Thus for corneal transplant and Oculoplastic surgery the mean surgery time is 30 min and for cataract the mean surgery time is 15 min. Figures 4b and 5b present the results of scheduling the patients based on the mean surgery time. It is clear from these graphs that even the total duration of the surgery time is not correct. Assignments based on rule of thumb to schedule cataract operations in one bed and longer duration operations such as Oculoplastic and corneal transplant in other beds does not seem to yield the optimal solution when the surgical environment is taken into account to predict the duration of surgery.

Conclusion

This paper focuses on scheduling of the operating theater such that there is no overload on any of the beds. This required an estimate of the duration of surgery. Three prediction models namely ANFIS, ANN and MLRA were developed to estimate the duration of surgery taking into account the surgical environment. The ANFIS model is found to out-perform the other two models. The scheduling is done using P||Cmax algorithm. Encouraging results have been obtained for optimal scheduling of Operation Theater, in simulations. The same has to be verified in real life scenario in a hospital.