The Operating Room Scheduling (ORS) problem deals with the optimization of daily operating room surgery schedule. It is a challenging problem given it is subject to many constraints, like to determine the start time of different surgeries and allocating the required resources, including the availability of beds in different units. In the last years, Answer Set Programming (ASP) has been successfully employed for addressing and solving the ORS problem. However, due to the inherent difficulty of retrieving real data, all the analysis on ORS encodings have been performed on synthetic data so far. In this paper, instead, we deal with the real case of ASL1 Liguria, and present adaptations of the ASP encodings to include real requirements of such case. Further, we analyze the resulting encodings on these real data. Results on some scenarios show that the ASP solutions produce satisfying results also when tested on real, challenging data.
To manage the ORs, a solution has to provide the date and the starting time of the surgeries
required, considering the availability of ORs and beds, and the other resources requested. More
in details, the Operating Room Scheduling (ORS) [
However, due to the inherent difficulty of retrieving real data, all the analysis on ORS encodings via ASP have been performed on synthetic data so far. In this paper, instead, we deal with the real case of ASL1 Liguria for computing weekly schedules, which include data from the cities of Sanremo, Imperia, and Bordighera in the Liguria region, Italy. We present adaptations of the ASP encodings employed so far in the literature to include real requirements of such cases. We then define three scenarios: in the first scenario, our goal is to test whether our solution is able to replicate the schedule that the hospital indeed followed, while the last two scenarios evaluate whether "better" schedules could have been determined. Further, we analyze the resulting encodings on the real data: results show that our solutions are able to both replicate and improve the original schedule, thus indicating that ASP produces satisfying results also when tested on real, challenging data.
The paper is structured as follows. Section 2 describes the target problem in an informal way, whose ASP encoding is presented in Section 4, after having introduced syntax and semantics of ASP in Section 3. Section 5 presents the results of our experiments on the defined scenarios. The paper ends in Section 6 and 7 by discussing related work and by drawing conclusions and possible topics for further research, respectively.
This section provides the description and the requirements of the ORS problem as implemented in ASL1 Liguria, Italy, which is a local health authority consisting of three hospitals: Bordighera, Sanremo, and Imperia. The elements of the waiting list are called registrations. Each registration links a particular surgical procedure, with a duration, to a patient, to a specialty, and to a type of hospitalization.
The overall goal of the ORS problem is to assign the maximum number of registrations to the ORs. As the first requirement, the assignments must guarantee that the sum of the duration of surgeries assigned to a particular OR does not exceed the opening time of the OR itself. Of the three hospitals, Bordighera had two ORs available from 07:30 to 13:30, while Imperia and Sanremo had vfie ORs available from 07:30 to 20:00.
Moreover, registration can be linked to different types of hospitalizations. Specifically, patients could undergo Day Surgery or Ordinary Surgery, with the latter requiring the assignment of a bed to the patient before and/or after the surgery. Therefore, the solution must ensure that the number of patients requiring a bed for a particular specialty is not bigger than the number of available beds for that surgery in every day. The number of available beds for the different specialties of the hospitals is based on the originally available number of beds less the number of beds already occupied by the hospitalized patients. The total number of beds available for each specialty in Imperia and Sanremo are presented in Tables 1 and 2, while Bordighera has no beds availability. Finally, there are two aspects that are more specific to the data we considered for the ORS problem: the priority levels and an implied rule derived from the data. Registrations are not all equal: they can be related to different medical conditions and can be on the waiting list for different periods of time. These two factors can be unified in a unique concept: priority. In our settings, we introduced four different priority categories, namely P1, P2, P3, and P4. The first one gathers the patients originally assigned by the hospital: it is required that these registrations are all assigned to an OR. Then, the registrations of the other two categories are assigned to the top of the ORs capacity, prioritizing P2 over P3 and P3 over P4. Regarding the implied rule, by analyzing the considered original data, we derived the limited usage of an OR. Thus, we decided to introduce a specific rule to avoid the usage of that particular OR.
Answer Set Programming (ASP) [
Syntax. The syntax of ASP is similar to the one of Prolog. Variables are strings starting with an 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 ⟨consts : con j⟩, where consts is a list of constants and con j is a conjunction of ground standard atoms. A symbolic set is a set specified syntactically as {Terms1 : Con j1; · · · ; Termst : Con jt }, where t > 0, and for all i ∈ [1,t], each Termsi is a list of terms such that |Termsi| = k > 0, and each Con ji is a conjunction of standard atoms. A set term is either a symbolic set or a ground set. Intuitively, a set term {X : a(X , c), p(X );Y : b(Y, m)} stands for the union of two sets: the first 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, ≺ ∈ { <, ≤ , > , ≥ , ̸=, =} is an 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 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 {Terms : Conj} also appears in a positive atom in Conj.
A weak constraint [
:∼ b1, . . . , bk, not bk+1, . . . , not bm. [w@l]. where w and l are the weight and level of ω, respectively. (Intuitively, [w@l] is read as "weight w at level l”, where the weight is the “cost” of violating the condition in the body of ω, whereas levels can be specified for defining a priority among preference criteria). An ASP program with weak constraints is Π = ⟨P,W ⟩, 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 defined 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 ℓ ∈ I (resp., ℓ ̸∈ 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 satisfies the guard; otherwise, it is false.
A ground rule r is satisfied 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 satisfies all rules of a program. Given a ground program GP
and an interpretation I, the reduct [
Given a program with weak constraints Π = ⟨P,W ⟩, the semantics of Π extends from the basic case defined above. Thus, let GΠ = ⟨GP, GW ⟩ be the instantiation of Π; a constraint ω ∈ 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 {p}, where p is an atom. Choice rules can be viewed as a syntactic shortcut for the rule p | p′, where p′ is a fresh new atom not appearing elsewhere in the program, meaning that the atom p can be chosen as true.
Starting from the specifications in Section 2, here we present our compact and efficient ASP
solution for the scheduling problem, organized in two subsections, presenting the encoding to
replicate the schedule of the hospital and the encodings to improve the schedule of the hospital,
respectively. In turn, each subsection contains two paragraphs with input and output data models,
and the ASP encoding, respectively. The ASP encoding is based on the input language of CLINGO
[
Data Model. The input data is specified by means of the following constants and atoms: • The constant time_disp represents the opening time of the ORs. • Instances of registration(NOSOLOGICAL,P,SP,REG,DUR,RICOV,IN,OUT) represent the registration of the patient identified by in ID ( NOSOLOGICAL) with priority level (P), and the requested specialty (SP) characterized by a type of hospitalization (REG), the duration of the surgery (DUR) plus the information regarding if the patient is already hospitalized (RICOV), and the number of days the patient requires a bed, before (IN) and after (OUT) the surgery, respectively. • Instances of mss(OR,SP,DAY) represent which specialty (SP) is assigned to an OR (OR) in a day (DAY). 1 {x(NOSOLOGICAL, P, OR, SP, DAY, DUR)} :- registration(NOSOLOGICAL, P, SP, _, DUR, _, _, _), mss(OR, SP, DAY). 2 :- x(NOSOLOGICAL, _, _, _, DAY1, _), x(NOSOLOGICAL, _, _, _, DAY2, _), DAY1 != DAY2. 3 :- x(NOSOLOGICAL, _,OR1, _, _, _), x(NOSOLOGICAL, _,OR2, _, _, _), OR1 != OR2. 4 :- mss(OR, _, DAY), #sum {DUR, NOSOLOGICAL : x(NOSOLOGICAL, _, OR, _, DAY, DUR)} > timeDisp. 5 stay(NOSOLOGICAL, SP, DAY - IN..DAY - 1) :- x(NOSOLOGICAL, _, _, SP, DAY, _), registration(NOSOLOGICAL, _, SP, "Ordinario", _, 0, IN, _), IN > 0. 6 stay(NOSOLOGICAL, SP, DAY..OUT + DAY) :- x(NOSOLOGICAL, _, _, SP, DAY, _),
registration(NOSOLOGICAL, _, SP, "Ordinario", _, 0, _, OUT), OUT >= 0. 7 :- beds(N, SP, DAY), #count {NOSOLOGICAL : stay(NOSOLOGICAL, SP, DAY)} > N. 8 :- not x(NOSOLOGICAL, _,OR, _, DAY, _), givenSchedule(NOSOLOGICAL, DAY, OR).
• Instances of beds(N,SP,DAY) represent the number (N) of available beds for a specialty (SP) in the day (DAY). • Instances of givenSchedule(NOSOLOGICAL,DAY,OR) represent the original schedule of the hospital, characterized by the patient identified by an ID ( NOSOLOGICAL) scheduled in a day (DAY) in an OR (OR).
The output is an assignment represented by an atom of the form x(NOSOLOGICAL,P,OR,SP,DAY,DUR), where the intuitive meaning is that the patient identified by an ID ( NOSOLOGICAL) having a priority (P), linked to a specialty (SP), is assigned to the OR OR in the day DAY with a surgery duration equal to (DUR).
Encoding. The related encoding is shown in Figure 1, and is described next. To simplify the description, we denote as ri the rule appearing at line i of Figure 1.
Rule r1 assigns an OR and a day to the registrations. Rules r2 and 3 ensure that each registration is assigned just to one day and OR, respectively. Rule r4 ensures that the sum of the duration of the surgeries assigned to every OR is lower than the time at disposal time_disp. Auxiliary atoms in the heads of rules r5, r6 and, r8 are derived by the encoding to simplify the other rules. Rules r5 and r6 evaluate the days and the specialty on which every assigned patient requires a bed before and after the surgery, respectively. Rule r7 ensures that the number of patients requiring a bed is less than the available ones. Rule r8 ensures that the schedule of the hospital and the newly generated schedule are equal.
Here we present the new rules for the ASP encodings that aim at improving the original schedule: the first one assigns the patients of the original schedule without taking into account the original date and ORs (OPT1), while the second encoding (OPT2) assigns new patients on top of the original schedule, and we take into account a constraint derived from the data. Encodings. The ASP encoding OPT1 is made by the rules in Figure 2, where we denote with ri the rule appearing at line i, plus the rules from r1 to r7 from Figure 1. 9 :- not x(NOSOLOGICAL, _,_, _, _, _), registration(NOSOLOGICAL, 1,_,_,_,_,_,_). 10 :∼ not x(NOSOLOGICAL, _,_, _, _, _), registration(NOSOLOGICAL, 2,_,_,_,_,_,_).
[1@3,NOSOLOGICAL] 11 :∼ not x(NOSOLOGICAL, _,_, _, _, _), registration(NOSOLOGICAL, 3,_,_,_,_,_,_).
[1@2,NOSOLOGICAL] 12 :∼ not x(NOSOLOGICAL, _,_, _, _, _), registration(NOSOLOGICAL, 4,_,_,_,_,_,_).
[1@1,NOSOLOGICAL]
Rule r9 ensures that all the patients with priority 1 are assigned, while weak constraints r10, r11, and r12 minimize, with a decreasing optimization priority level, the number of not assigned patients with priority 2, 3, and 4, respectively, by paying a penalty of 1 for every not assigned patient with that priority level.
The ASP encoding OPT2 is composed, instead, of the rule in Figure 3, where we denote with ri the rule appearing at line i, plus the rules from r1 to r8 from Figure 1 and rules from r9 to r12 from Figure 2. Rule r13 ensures that the OR identified by the id "OR A" is used just by one patient, as in the original data.
In this section, we report the results of an empirical analysis conducted using the defined ASP
encodings, on the three scenarios previously defined. For all the settings we used original data.
In particular, for the first scenario, we used data corresponding to a weekly schedule of the
hospital. While, for OPT1 and OPT2, we used data corresponding to a weekly schedule of
the hospital plus, in order to augment the number of patients to schedule, a random selection
of patients scheduled in the future by the hospital. The experiments were run on a Apple
M1 CPU @ 3.22 GHz with 8 GB of physical RAM. The ASP system used was CLINGO [
Data Description. To test our solution for scheduling surgeries, we utilized data from hospitals of ASL1 of Liguria region, Italy. The hospitals in ASL1 serve a population of around 213 thousand people. For our analysis, we used data from a weekly schedule of surgeries across the three hospitals, as well as data from other weeks, including a list of available beds and ORs for all hospitals.
We collected and prepared the data for testing by working with vfie different xls files, each file represents a different type of data, in particular: • The operating list of the considered week of surgeries, from 04/03/2019 to 10/03/2019, which provided information on the required surgery, the operating room, and the specialty originally scheduled. • The historical list of surgeries scheduled in 2019, which includes information on the required surgery, the starting and ending time of the surgery, and the date of the surgery. • The list of ORs in each hospital and their opening hours. • The list of patients hospitalized the week before the considered week of the scheduling, along with their admission and discharge times.
• The list of beds in each specialty at each hospital.
The initial data set contained several issues commonly found in real-world data, including incomplete information, inaccuracies, and inconsistencies between files. In order to address these issues, we performed data cleaning procedures such as correcting typos, filling in missing values by deriving data from other files, removing duplicate rows of the same patient, dropping columns with non-meaningful information, and creating new columns by merging information from different columns.
Through these cleaning procedures, we were able to obtain a more accurate and compact representation of the original data.
Tested Settings. Having presented the data, now we will present the different settings we utilized to test the encodings. In the first scenario, the solution has to provide a schedule for the patients of the considered week and the number of available resources, beds and ORs, replicating the original schedule. This scenario was meant to confirm the consistency of the schedule produced by our encoding with the schedule of the patients as done by the hospital. For the two remaining scenarios, OPT1 and OPT2, we wanted to test our solution by scheduling the patients scheduled by the hospital plus other patients. This enabled us to assess how the ASP solution could have improved patient’s assignment and optimized resource allocation. In particular, in OPT2, the solution had to schedule the original patients in the same way done by the hospital and try to schedule as many new additional patients as possible. In OPT1, we considered both the original patients and additional patients but did not impose constraints requiring the ASP solution to replicate the hospital’s schedule. In the hospital of Bordighera, we had to make a slight change between OPT1 and OPT2. Indeed, the hospital scheduled just 1 patient in one OR, without using it for other patients. Thus, we decided to discard this OR in OPT1, while we maintained it just for that patient in OPT2 (this is linked to rule r13 in Figure 3). Both for OPT1 and OPT2, a selection of new patients was needed. To select these additional patients and distinguish them from the original ones, we introduced the concept of priority. In particular, originally scheduled patients were assigned to priority 1. The patients with priority 1 are forced to be assigned, freely in OPT1 while following the original schedule in OPT2. Then, we randomly select a number of patients assigned by the hospital in the following weeks, assigning priority 2 to patients assigned in the next week, priority 3 to patients assigned after 2 weeks, and priority 3 to patients assigned at least 3 weeks later. The number of additional patients the solution will try to schedule is linked to the original number of scheduled patients. Each setting was tested with 10 different instances composed of different samples of additional patients. In particular, for all the hospitals, the solution tried to schedule a number of patients equivalent to the 250% of the original one. OPT1 and OPT2 enable us to assess the potential impact of our solution in terms of reducing patient waiting lists and optimizing resource allocation.
Scenario 1 consists of recreating the same schedule done by the hospital. The solution is obtained in less than 0.5 seconds for all the hospitals, indicating the correctness of the implemented rules and the obtained resources availability. In Tables 3, 4, and 5 can be seen the original percentage usage of the ORs obtained by the three hospitals of Bordighera, Imperia, and Sanremo, respectively. These results represent the benchmarks to compare with in OPT1 and OPT2.
Tables 6, 7, and 8 show the results obtained in this setting in terms of the percentage of patients assigned in all the ten instances in the hospitals of Bordighera, Imperia, and Sanremo, respectively. As can be seen from the tables, the solution is able to increase the number of assigned patients significantly for all the hospitals. Indeed, patients P1 are the patients originally scheduled, while all the other patients represent the additional ones. Moreover, even if not all the patients with priority 2 are assigned, some patients with lower priorities are. This is due to the fact that a bottleneck of the hospitals taken into account is beds availability. Thus, once all the beds are occupied, the solution is able to schedule some patients with lower priorities that do not require a bed before and/or after the surgery. To corroborate the explanation above, the percentages of beds usage in the different specialties, in Sanremo, are presented in Table 9. From the table it can be seen that the beds are used almost at full capacity throughout the week; thus, for the solution is not possible to assign additional patients requiring a bed. In the hospital of Imperia, beyond the beds, even the ORs are used almost at full capacity with the additional patients. In particular, in Figure 4, it can be seen a comparison between the obtained percentage usage of the ORs with the ASP solution in OPT1 and the usage obtained by the ASL1. Without following the previous assignments of ASL1, the ASP solution is able to schedule three times the number of patients originally scheduled.
The results obtained in this setting are summarized for each hospital in Figure 5. In particular, from the figure, it can be noted the advantage of using the ASP solution. Indeed, while both settings assign additional patients, the difference between them lies in the usage of ASP (OPT1) to assign the originally scheduled patients. Therefore, all the additional patients assigned in OPT1 result from a more efficient schedule for the original patients. However, not all comparisons seem to suggest better results with OPT1: we will now delve into the results of each hospital in more detail. In particular, in Bordighera, the second and the third settings assign the same number of patients. This seems to suggest that the assignments done by the ASP solution didn’t improve the original schedule but, as previously mentioned, in OPT2 the schedule assigns the patients as in the original schedule and in this hospital, 1 patient is assigned to an OR is not used in the OPT1, since it was used just by one patient. Therefore, even if using fewer resources, the solution of OPT1 is still able to match the performance of OPT2, meaning that the patients were scheduled more appropriately.
In Imperia, the total number of patients assigned in OPT2 is actually higher than the one assigned in OPT1 but, as can be seen in Table 10, the schedule provided by OPT1 is of higher
OPT2 A B C
d e ign 400 s s a s t n e i t ap 200 f o r e b m u N 0
quality, since it is able to assign more patients with higher priority, even if at the detriment of patients with lower priorities. Finally, in Sanremo, the schedule done by OPT1 outperforms that of OPT2 by assigning more patients while not decreasing the quality of the solution. As such, considering all the priorities, OPT1 has assigned at least the same number of patients as OPT2 in each priority group.
P2
This section is organized into two paragraphs: The first one is focused on existing works that use
different techniques to solve the ORS problem, with a focus on the works using real data. While
the second presents some works in which ASP has been employed in the healthcare domain.
Solutions to the Operating Room Scheduling Problem In [
Solving Healthcare Domain Problems with ASP. ASP has been successfully used for solving
hard combinatorial and application scheduling problems in several research areas. In the
Healthcare domain (see, e.g., [
In this paper we have adapted and tested on real data ASP encodings for the ORS problem. The evaluated scenarios show that our ASP encoding (i) is able to mimic the original schedule implemented in the hospitals of ASL1 Liguria, and (ii) could have greatly improved such schedule in terms of efcfiiency. Future works include the definition of an encoding for the rescheduling problem, which takes place when the original schedule can not be implemented for some reason, and the development of a web application for the easy use of our solution. Joint Conference on Rules and Reasoning (RuleML+RR 2021), volume 12851 of Lecture Notes in Computer Science, Springer, 2021, pp. 111–125. [26] S. Caruso, G. Galatà, M. Maratea, M. Mochi, I. Porro, Scheduling pre-operative assessment clinic with answer set programming, Journal of Logic and Computation (2023). URL: https://doi.org/10.1093/logcom/exad017. doi:10.1093/logcom/exad017, exad017. [27] P. Cappanera, M. Gavanelli, M. Nonato, M. Roma, Logic-based benders decomposition in answer set programming for chronic outpatients scheduling, TPLP (To Appear) abs/2305.11969 (2023). URL: https://doi.org/10.48550/arXiv.2305.11969. doi:10.48550/ arXiv.2305.11969. arXiv:2305.11969.