The optimization of daily operating room surgery schedule can be problematic because of many constraints, like to determine the start time of di erent surgeries and allocating the required resources, including the availability of surgical teams for complete surgical procedures. Recently, Answer Set Programming (ASP) has been successfully employed for addressing and solving real-life scheduling and planning problems in the health-care domain. In this paper we present an enhanced solution using ASP for scheduling operating rooms taking explicitly into consideration availability of surgical teams, that include a surgeon and an anesthetist in di erent specialties for the entire duration of the surgery. We tested our solution on di erent benchmarks with realistic parameters for schedule's length up to the target 5-days planning. The results of our experiments show that ASP is a suitable methodology for solving also such enhanced problem.
Hospitals, whose production output is service, often come across issues of long waiting times, surgeries cancellation for patients and even worst resource overload occur frequently. Within every hospital, Operating Rooms (ORs) are an important unit. As indicated by [30], the ORs account for approximately 33% of the total hospital budget because it includes high sta costs (e..g, surgeons, anaesthetists, nurses) and material cost. Nowadays, in most modern hospitals, long surgical waiting lists are present because of ine cient planning. Therefore, it is extremely important to improve the e ciency of ORs to enhance the survival rate and satisfaction of patients, thereby improving the overall quality of healthcare system.
The management of ORs basically consists of both planning for providing the
date of surgery for each patient, taking into account the availability of ORs
and surgeons, and determining the sequence of operations in each OR each day,
taking into account the availability of di erent resources. The Operating Room
Scheduling (ORS) [
In recent years a solution based on Answer Set Programming (ASP) [
The paper is structured as follows. Section 2 presents needed preliminary about ASP. Then, Section 3 describes the target problem in an informal way, whose ASP encoding is presented in Section 4. Section 5 shows the results of our experiments. The paper ends in Section 6 and 7 by discussing related work, and by showing conclusions and possible topics for further research. 2
Answer Set Programming (ASP) is a programming paradigm developed in the
eld of non monotonic reasoning and logic programming. It is a form of
declarative programming oriented towards di cult primarily NP-hard search problems
and is based on the stable model (answer set) semantics. This section presents
the syntax and semantics of the ASP language [
Syntax. The syntax of ASP is similar to the one of Prolog. Variables are strings starting with uppercase letter and constants are non-negative integers or strings starting with lowercase letters. A term is either a variable or a constant. A standard atom is an expression p(t1; : : : ; tn), where p is a predicate of arity n and t1; : : : ; tn are terms. An atom p(t1; : : : ; tn) is ground if t1; : : : ; tn are constants. A ground set is a set of pairs of the form hconsts : conji, where consts is a list of constants and conj is a conjunction of ground standard atoms. A symbolic set is a set speci ed syntactically as fT erms1 : Conj1; ; T ermst : Conjtg, where t > 0, and for all i 2 [1; t], each T ermsi is a list of terms such that jT ermsij = k > 0, and each Conji is a conjunction of standard atoms. A set term is either a symbolic set or a ground set. Intuitively, a set term fX : a(X; c); p(X); Y : b(Y; m)g stands for the union of two sets: the rst one contains the X-values making the conjunction a(X; c); p(X) true, and the second one contains the Y -values making the conjunction b(Y; m) true. An aggregate function is of the form f (S), where S is a set term, and f is an aggregate function symbol. Basically, aggregate functions map multisets of constants to a constant. The most common functions implemented in ASP systems are the following: { #count , number of terms; { #sum, sum of integers.
An aggregate atom is of the form f (S) T , where f (S) is an aggregate function, 2 f<; ; >; ; 6=; =g is a comparison operator, and T is a term called guard. An aggregate atom f (S) T is ground if T is a constant and S is a ground set. An atom is either a standard atom or an aggregate atom. A rule r has the following form:
a1 _ : : : _ an :{ b1; : : : ; bk; not bk+1; : : : ; not bm: where a1; : : : ; an are standard atoms, b1; : : : ; bk are atoms, bk+1; : : : ; bm are standard atoms, and n; k; m 0. A literal is either a standard atom a or its negation not a. The disjunction a1 _ : : : _ an is the head of r, while the conjunction b1; : : : ; bk; not bk+1; : : : ; not bm is its body. Rules with empty body are called facts. Rules with empty head are called constraints. A variable that appears uniquely in set terms of a rule r is said to be local in r, otherwise it is a global variable of r. An ASP program is a set of safe rules, where a rule r is safe if both the following conditions hold: (i) for each global variable X of r there is a positive standard atom ` in the body of r such that X appears in `; and (ii) each local variable of r appearing in a symbolic set fTerms : Conj g also appears in Conj .
A weak constraint ! is of the form: where w and l are the weight and level of !, respectively. (Intuitively, [w@l] is read \as weight w at level l", where weight is the \cost" of violating the condition in the body of w, whereas levels can be speci ed for de ning a priority among preference criteria). An ASP program P is a nite set of rules. An ASP program with weak constraints is = hP; W i, where P is a program and W is a set of weak constraints.
A standard atom, a literal, a rule, a program or a weak constraint is ground if no variables appear in it.
Semantics. Let P be an ASP program. The Herbrand universe UP and the Herbrand base BP of P are de ned as usual. The ground instantiation GP of P is the set of all the ground instances of rules of P that can be obtained by substituting variables with constants from UP .
An interpretation I for P is a subset I of BP . A ground literal ` (resp., not `) is true w.r.t. I if ` 2 I (resp., ` 62 I), and false (resp., true) otherwise. An aggregate atom is true w.r.t. I if the evaluation of its aggregate function (i.e., the result of the application of f on the multiset S) with respect to I satis es the guard; otherwise, it is false.
A ground rule r is satis ed by I if at least one atom in the head is true w.r.t. I whenever all conjuncts of the body of r are true w.r.t. I.
A model is an interpretation that satis es all rules of a program. Given a
ground program GP and an interpretation I, the reduct [
Given a program with weak constraints = hP; W i, the semantics of extends from the basic case de ned above. Thus, let G = hGP ; GW i be the instantiation of ; a constraint ! 2 GW is violated by an interpretation I if all the literals in ! are true w.r.t. I. An optimum answer set for is an answer set of GP that minimizes the sum of the weights of the violated weak constraints in GW in a prioritized way.
Syntactic shortcuts. In the following, we also use choice rules of the form fpg, where p is an atom. Choice rules can be viewed as a syntactic shortcut for the rule p _ p0, where p0 is a fresh new standard atom not appearing elsewhere in the program. 3
This section provides the description and the requirements of our problem. The elements of the waiting list are called registrations. Moreover, registrations are not all equal, as they can belong to di erent specialties and can be in the waiting list for a long period of time. All ORs are available for 5 consecutive hours (300 minutes) in a single shift while a full day consists of two shifts. Of course, the assignments must guarantee that the sum of the predicted duration of surgeries assigned to a particular OR shift does not exceed the length of the shift itself. For each registration we consider three priority score P1, P2, and P3, where P1 is for high priority or very urgent, P2 is medium priority and P3 is for low priority. Since P1 gathers high priority registrations, they must be all assigned to an OR, followed by P2 registrations over the P3. Additionally, in each specialty (considered to be 5 as target in small-medium-sized Hospitals) surgical teams are allocated with number of surgeons and anaesthetists every day as shown in Table 1. Every surgeon works speci cally for 4 hours every day; also surgeons in each specialty are assigned only to a single shift in a day, i.e., they either work in the morning or in evening shift as shown in Table 2. The anaesthetists are also linked to specialty and their work duration is 6 hours every day, but they can work together with surgeons during any shift of the day as shown in Table 3. In our model we also assume that surgeons for each surgery is predetermined. Once a surgery is started in an OR it cannot be interrupted. Further, surgeons cannot operate on more than one patient at the same time. The overall goal is to assign the maximum number of registrations to the ORs, respecting the priorities, and taking into account the availability of respective surgical teams in a particular specialty for the complete surgery duration. 4
In this section we present the input predicates and our ASP encoding, in two di erent subsections. 4.1
The input data to our model is speci ed by means of the following atoms: { Instances of registration(R,P,SU,_,SP,_,_) represent the registrations, where we outline only the main variables: with an id (R), a priority score (P) , a surgery duration (SU) in minutes, and the id of the specialty (SP ) it belongs to. representing that the registration (R) with priority (P) is assigned with surgeon id (SR) and anaesthetist id (AN) to the operating room (O) during the shift (S) of the day (D) with a slot time (ST). { Instances of mss(O,S,SP,D) link each operating room (O) to a shift (S) for each specialty (SP) and planning day (D), as established by the hospital Master Surgical Schedule (MSS). { Instances of surgeon(SR,SP,S) represent the surgeons with an id (SR) for each specialty (SP) and shift (S). { Instances of an(AN,SP,S) show the anaesthetists with an id (AN) for each specialty (SP) and shift (S). { Instances of time(S,ST) show the time slots (ST) for each shift (S), i.e, each shift is divided it into ST time slots (which are always 30 in our setting) and each of them corresponds to a speci c length expressed in minutes. As an example, each shift can be divided into 30 time slots where each time slot lasts 10 minutes. The length of each slot depends on the di erent scenarios. In particular, we consider 4 di erent variants (or scenario) of the problem, where the length of each time slot is set to 10 (scenario A), 20 (scenario B), 30 (scenario C), and 60 (scenario D) minutes, respectively. The choice of the length is injected in the encoding by specifying a constant, called shift_duration, that represents the total length (expressed in minutes) of the shift, e.g., shift_duration is set to 300 if each time slot lasts 10 minutes (30 time slots times 10 minutes), whereas it is set to 600 if each time slot lasts 60 minutes. { Instances of surgWT(SWT,SR,D) represent the total work time in hours (SWT) for surgeons with id (SR) for each day (D). { Instances of anWT(AWT,AN,D) represent the total work time in hours (AWT) for anaesthetists with id (AN) for each day (D).
The output is stored in an assignment represented by atom of the following form: x(R,P,SR,AN,O,S,D,ST) representing that the registration (R) with priority (P) is assigned with surgeon id (SR) and anaesthetist id (AN) to the operating room (O) during the shift (S) of the day (D) with a slot time (ST).
(r1) {x(R,P,SR,AN,O,S,D,ST): (ST+SU) <= shift_duration} :registration(R,P,SU,_,SP,_,_), mss(O,S,SP,D), surgeon(SR,SP,S), an(AN,SP,S), time(S,ST). (r2) :- registration(R,_,_,_,_,_,_), #count{R,SR,AN,O,S,D,ST : x(R,P,SR,AN,O,S,D,ST)}>1. (r3) :- x(R1,_,_,_,O,S,D,ST), x(R2,_,_,_,O,S,D,ST), R1 != R2. (r4) :- #count{R:x(R,_,_,_,O,S,_,ST), registration(R,_,SU,_,_,_,_), T>=ST, T<ST+SU}>1, mss(O,S,_,_), time(S,T). (r5) :- #count{R:x(R,_,SR,_,_,S,_,ST)} > 1, surgeon(SR,_,S), time(S,ST). (r6) :- #count{R:x(R,_,SR,_,_,S,_,ST), registration(R,_,SU,_,_,_,_), T>=ST, T<ST+SU}>1, surgeon(SR,_,S), time(S,T). (r7) :- #count{R:x(R,_,_,AN,_,S,_,ST)} > 1, an(AN,_,S), time(S,ST). (r8) :- #count{R:x(R,_,_,AN,_,S,_,ST), registration(R,_,SU,_,_,_,_), T>=ST, T<ST+SU}>1, an(AN,_,S), time(S,T). (r9) :- #sum{SU,R:x(R,_,SR,_,_,_,D,_), registration(R,_,SU,_,_,_,_)} > SWT, surgWT(SWT,SR,D). (r10) :- #sum{SU,R:x(R,_,_,AN,_,_,D,_), registration(R,_,SU,_,_,_,_)} > AWT, anWT(AWT,AN,D). (r11) :- #count{R:x(R,1,_,_,_,_,_,_)} < totRegsP1. (r12) : M=#count{R:x(R,2,_,_,_,_,_,_)}, N=totRegsP2-M. [N@3]. (r13) : M=#count{R:x(R,3,_,_,_,_,_,_)}, N=totRegsP3-M. [N@2]. The related ASP encoding is shown in Figure 1, and is described in this subsection. The encoding is based on the Guess&Check programming methodology.
Rule (r1) guesses an assignment for the registrations, surgeons and anaesthetists to an OR in a given day, shift and with a time slot among the ones permitted by the MSS for the particular specialty the registrations, surgeons and anaesthetists belongs to, such that the registrations assigned with a slot time and surgery duration should be less than shift_duration of OR. We recall that shift_duration is a constant that depends on the di erent scenario considered (see Section 4.1).
After guessing an assignment for the registrations, the encoding presents constraints, related to general and work-time requirements, and to registrations of priority 1, to discard some unwanted assignments. All such constraints are explained in the following paragraphs, together with weak constraints for dealing with the optimization on registrations having priority 2 and 3.
General requirements. Rule (r2) checks that same registration with same surgeon and anaesthetist should not be assigned more than once in di erent OR or shifts at the same time. Rule (r3) ensures that di erent registrations cannot be assigned in the same OR and shift at the same time slot. Rule (r4) checks that di erent registrations cannot be assigned at di erent times ,in the same OR and shift until the end time of the previous surgery to avoid time overlapping. Rule (r5) shows that the same surgeon cannot be assigned at the same time slot in di erent ORs in the same shift. Rule (r6) checks that the same surgeon cannot be assigned at di erent times in di erent OR in the same shift until the end of previous surgery. Rule (r7) ensures that the same anaesthetist cannot be assigned at the same time slot in di erent ORs in the same shift. Rule (r8) checks that the same anaesthetist cannot be assigned to di erent times to di erent ORs in the same shift until the previous surgery is nished.
Work time requirements. Rules (r9) and (r10) are related to the work time of surgeons and anaesthetist to impose that the total number of registrations assigned to a surgeon cannot increase her/his total work hours in a day; similarly for anaesthetist the rule ensures that the total number of registrations assigned should not increase the total work hours in a day.
Priorities and optimization. Finally, since we model a priority based system, we want to be sure that every registration having priority 1 is assigned rst, then we assign as much as possible the others, giving preference to registrations having priority 2 over those having priority 3. This is accomplished through constraint (r11) for priority 1 and the weak constraints (r12) and (r13) for priority 2 and 3, where totRegsP1, totRegsP2 and totRegsP3 are constants representing the total number of registrations having priority 1, 2 and 3, respectively. 5 5.1
This section reports about the results of an empirical analysis of the ORS
problem with surgical teams. The ASP system used is clingo [
For each scenario, the characteristics of the tests are as follows: { 4 di erent benchmarks, with a planning period of 1, 2, 3 and 5 working days; { For each benchmark the total number of randomly generated registrations were 350 for 5 days, 210 for 3 days, 140 for 2 days and 70 for 1 days; { 5 specialties; { 20 surgeons assigned to the 5 specialties; { 20 anaesthetists assigned to the 5 specialties; { 4 hours of work time in a day for each surgeon; { 6 hours of work time in a day for each anaesthetist; { 10 ORs distributed among the specialties; { 5 hours morning and afternoon shifts for each OR summing up to 500, 300, 200 and 100 hours of OR available time for the four benchmarks; Experiments have been run on a HP 630 Notebook with Intel(R) Core(TM) i3 CPU M380@2.53GHz. Results of the experiments are reported for scenario A in Table 5, for scenario B in Table 6, for scenario C in Table 7 and for scenario D in Table 8, respectively.
Each benchmark was tested 10 times with di erent randomly generated inputs. A time limit of 300 seconds was set for each experiment. In each table averages for 10 instances for each benchmark are reported. The rst three columns show the number of assigned registrations out of the generated ones for each priority P1, P2 and P3, while the last three columns show a measure of the total time occupied by the assigned registrations as a percentage of the total OR time available (indicated as OR time E in the tables) and the total percentage of surgeons and anesthetists working time (indicated respectively as Surg WT E and Anest WT E in the tables).
As we can see in scenario A (Table 5) with slot interval of 10 minutes we obtain results only for schedules up to 3 days, while in the case of the 5-day benchmark the computation time exceeds our time limit of 300 seconds on all instances. Scenario B (Table 6) details the scheduling results with slot intervals of 20 minutes. It can be seen that OR e ciency is 75% while the Surgeons and Anesthetists WT e ciency remain greater than 90% and 60%, respectively, for all benchmarks in this scenario.
In scenario C (Table 7) with a slot interval of 30 minutes, the OR e ciency is around 76% while the Surgeons and Anesthetists WT e ciency are enhanced up to 95% and 63% for all benchmarks respectively.
In scenario D (Table 8) with a slot interval of 60 minutes, OR e ciency is almost 79% while the Surgeons WT e ciency is further enhanced to more than 95%, and Anesthetists WT e ciency is up to 65%.
In all the evaluated benchmarks for di erent scenarios we can observe that the OR e ciency and the anesthetists e ciency are limited by the fact that we reached the ceiling of the surgeons maximum working hours. Considering that in our setup we had one anesthetist for each surgeon, the ratio between anesthetist and surgeon e ciencies is the same that the ratio between their maximum working time of the surgeons and the anesthetists, i.e., 2/3. In a real application, this would be a useful information for the hospital manager to quantify the excess of anesthetists and reorganize their numbers or their working times.
Overall we obtained satisfying results but for the 5-day schedule length for the more ne-grained time interval of Scenario A. In order to further investigate the issue, we moved on a di erent dimension and tested the Scenario A con guration with half the number of registrations (35 instead of 70 for each planning day), surgeons (10 instead of 20), anesthetists (10 instead of 20) and ORs (5 instead of 10). With these numbers we can reach acceptable solutions after 60 seconds of computation time (see Table 9) for every benchmark, including the 5-day one. In the previous analysis the issue was caused by the excessive computation required, especially in the grounding phase, by such a number of registrations, surgeons and anesthetists with the ner time sensitivity of 10 minutes. 6
In this section we will discuss some relevant works related to this research.
Meskens et al [30] considered the surgical teams in the computation of an OR
schedule, and developed a model using Constraint Programming (CP) with
multiple constraints such as availability, sta preferences and a nities among
surgical teams. They optimize the use of ORs by minimizing makespan and
maximizing a nities among surgical team members. The e ectiveness of their proposed
method for improving surgical cases was evaluated using real data from an
hospital. Hamid et al [29] incorporated the decision-making styles (DMS) of the
surgical team to improve the compatibility level by considering constraints such
as the availability of material resources, priorities of patients, and availability,
skills, and competencies of the surgical team. They developed a multi-objective
mathematical model to schedule surgeries. Two metaheuristics, namely
Nondominated Sorting Genetic Algorithm and Multi-Objective Particle Swarm
Optimization, were developed to nd pareto-optimal solutions. Xiang et al [34]
proposed an Ant Colony Optimization (ACO) approach to surgical scheduling
taking into account all resources in the entire process of a surgery. The
problem was represented as an extended multi-resource constrained exible job shop
scheduling problem, which was solved using a two-level hierarchical graph to
integrate sequencing job and allocating resources. To evaluate the e ciency of
ACO, a Discrete Event System (DES) model of an OR system was developed in
the simulation platform SIMIO. Monteiro et al. [31] developed a comprehensive
multi-objective mathematical model using epsilon-constraint method coupled
to the CPLEX solver. Vijayakumar et al. [33] used Mixed Integer
Programming (MIP) model for multi-day, multi-resource, patient-priority-based surgery
scheduling. First Fit Decreasing algorithm was developed. From a solution time
perspective, their model took long hours or in most cases was unable to
optimally solve the problem. Belkhamsa et al. [
About, instead, other scheduling problems in which ASP have been pro
ciently employed: Nurse Scheduling Problem [
In this paper we employed ASP for solving ORs problem with surgical teams. The
results of our experiments con rm that ASP is a suitable methodology for
addressing planning and scheduling problems in health-care system. We presented
the results of an experimental analysis on several directions to check scalability
of our solution in terms of e ciency, considering shift duration, surgeons and
anesthetist working hours. This solution achieved satis ed ORs, surgeons' and
anaesthetists' e ciency also for the planning length of 5 days. As a future work
we would like rst to investigate other parameters and con gurations, e.g., with
less anesthetists for which we expect that the e ciency of the anesthetists would
increase. We also want to integrate the extension of the ORS model with beds
management with the one presented in this paper, in order to have a more
complete uni ed solution. We also plan to compare to alternative methods, assuming
this is possible (i.e., availability of alternative solutions), and viable (i.e., very
same problem solved). Finally, through results are satisfying, we plan to work
also on improving performance by both evaluating more solvers, e.g., WASP [
Databases. New Generation Comput. 9(3/4), 365{386 (1991) 23. Giunchiglia, E., Leone, N., Maratea, M.: On the relation among answer set solvers.
Ann. Math. Artif. Intell. 53(1-4), 169{204 (2008) 24. Giunchiglia, E., Maratea, M.: On the Relation Between Answer Set and SAT Procedures (or, Between cmodels and smodels). In: ICLP. LNCS, vol. 3668, pp. 37{51.
Springer (2005) 25. Giunchiglia, E., Maratea, M.: Solving optimization problems with DLL. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) ECAI. Frontiers in Arti cial Intelligence and Applications, vol. 141, pp. 377{381. IOS Press (2006) 26. Giunchiglia, E., Maratea, M., Tacchella, A.: Dependent and independent variables in propositional satis ability. In: Flesca, S., Greco, S., Leone, N., Ianni, G. (eds.) JELIA. Lecture Notes in Computer Science, vol. 2424, pp. 296{307. Springer (2002) 27. Giunchiglia, E., Maratea, M., Tacchella, A.: (In)E ectiveness of look-ahead techniques in a modern SAT solver. In: Rossi, F. (ed.) CP. Lecture Notes in Computer Science, vol. 2833, pp. 842{846. Springer (2003) 28. Giunchiglia, E., Maratea, M., Tacchella, A., Zambonin, D.: Evaluating search heuristics and optimization techniques in propositional satis ability. In: Gore, R., Leitsch, A., Nipkow, T. (eds.) IJCAR. vol. 2083, pp. 347{363. Springer (2001) 29. Hamid, M., Nasiri, M.M., Werner, F., Sheikhahmadi, F., Zhalechian, M.: Operating room scheduling by considering the decision-making styles of surgical team members: A comprehensive approach. Computers & Operation Research 108, 166{181 (2019) 30. Meskens, N., Duvivier, D., Hanset, A.: Multi-objective operating room scheduling considering desiderata of the surgical team. Decis. Support Syst. 55(2), 650{659 (2013). https://doi.org/10.1016/j.dss.2012.10.019, https://doi.org/10.1016/j. dss.2012.10.019 31. Monteiro, T., Meskens, N., Wang, T.: Surgical scheduling with antagonistic human resource objectives. International Journal of Production Research 53(24), 7434{ 7449 (2015) 32. Ricca, F., Grasso, G., Alviano, M., Manna, M., Lio, V., Iiritano, S., Leone, N.: Team-building with answer set programming in the gioia-tauro seaport. Theory and Practice of Logic Programming 12(3), 361{381 (2012) 33. Vijayakumar, B., Parikh, P.J., Scott, R., Barnes, A., Gallimore, J.: A dual binpacking approach to scheduling surgical cases at a publicly-funded hospital. European Journal of Operation Research 224(3), 583{591 (2013) 34. Xiang, W., Yin, J., Lim, G.: An ant colony optimization approach for solving an operating room surgery scheduling problem. Comput. Ind. Eng. 85, 335{345 (2015) 35. Zhou, B., Yin, M., Lu, Z.: An improved lagrangian relaxation heuristic for the scheduling problem of operating theatres. Comput. Ind. Eng. 101, 490{503 (2016)