The problem of finding a Master Surgical Schedule (MSS) consists of scheduling different specialties to the operating rooms of a hospital clinic. To produce a proper MSS, each specialty must be assigned to some operating rooms. The number of assignments is different for each specialty and can vary during the considered planning horizon. Realizing a satisfying schedule is of upmost importance for a hospital clinic. Recently, a compact solution based on Answer Set Programming (ASP) to the MSS problem has been introduced and tested with satisfying results, but only on synthetic data. In this paper, we also adapt the encoding and test our overall solution on real data from ASL1 Liguria in Italy. The experiments show that our ASP solution provides satisfying results also when tested on real data.
Digital Health, defined as the usage of information and communication technologies in medicine
and in the management processes of healthcare, arose several years ago, but has gained increasing
importance in recent years. Thanks to new technologies and also due to new challenges such as
an aging society, the COVID-19 pandemic and the need to reduce high costs. One of the major
problems related to modern hospitals are long waiting lists that reduce patients’ satisfaction and
the level of care offered to them. The Master Surgical Schedule (MSS) represents which specialty
is assigned to each operating room in a particular day and session. The administrative practices
of surgical departments on this task can have a large impact on hospital costs, patient outcomes
and on the overall efficiency of a hospital. Many papers have analyzed this problem (see for
example [
In this paper we first present a mathematical formulation of the MSS problem. We then
apply ASP to solve the MSS problem, by presenting a compact ASP encoding obtained by
modularly representing input specifications in ASP, and then running an experimental analysis
on randomly generated MSS benchmarks, obtained by varying the number of days and trying
different scenarios [
The paper is structured as follows. Sections 2 and 3 present an informal description of the MSS problem, and its precise mathematical formulation, respectively. Then, Section 4 shows our ASP encoding, whose experimental evaluation is presented in Section 5. Section 6 adapts and test the solution on real data. The paper ends by discussing related work and conclusions in Section 7 and 8, respectively.
With the computation of an MSS, a hospital can see in which days, sessions and operating rooms (ORs) each specialty will do the surgeries. This is important since by looking at the MSS the hospital can manage the personnel and the resources in advance. The MSS is thus often scheduled for long periods of time and as soon as possible, to be able to assign the surgery to the patients in time and to properly organize the personnel. To schedule the MSS a hospital should evaluate the percentage of time that needs to be assigned to each specialty and the allowed errors for such a period of time, in order to better respond to the patients’ needs. The percentage of assignments is evaluated as the number of times each specialty is assigned divided by the total number of sessions available in the period considered. To produce a proper schedule, the solution must assign the specialties taking into account the percentage targets and the allowed errors of each specialty. At most n sessions are associated to each day, where n is equal to the maximum number of sessions that could be assigned to an OR. Each session is identified by an id. For example, in a hospital with the maximum number of sessions equal to 2, day 1 will be linked to sessions 1 and 2, while day 2 will be linked to sessions 3 and 4, and so on for all the remaining days. Each session is then linked to all the ORs and the scheduler must assign a specialty to each session. Since the MSS is planned for a long period of time, hospitals could desire that the target assignment of each specialty is respected not for all the considered days, but may vary, e.g., on a monthly or weekly basis. Another aspect that could change during the considered period and between the ORs are the sessions. The usage of each OR is often splitted in two sessions for each day but, sometimes, some ORs can be split in a different number of sessions, higher or used even for just one session. In particular, the single-session solution could be used when a specialty requires particular resources and the time to prepare them is long enough that changing the specialty at mid day would be a waste of time. Moreover, some ORs could be unavailable in some days and the scheduler must be able to consider these unavailability.
Overall, the MSS problem takes as input the number of ORs and specialties, the number of days to consider for the scheduling, the number of sessions for each day, and the different target values for each specialty, and computes the assignment of the different specialties to the available ORs of a hospital in the considered planning horizon. An optimal solution minimizes the difference between the percentage of usage of each specialty and the target value of each period. An example of MSS is presented in Table 1. In particular, the table is the result obtained by our solution, that we will show later in the paper, considering 90 days and fixed target value for each month. Moreover, we considered a hospital with 10 ORs, each splitted in 2 sessions in each day, and 5 specialties (these numbers corresponding to hospitals of small-medium size in Italy) SP1 . . . SP5 : The table shows the MSS for the first 7 days of the solution. In particular, each row represents a day and the sessions linked to that day, the columns report the ORs, and the intersection shows the specialty assigned to the OR in that day and session.
In this section, we provide a mathematical formulation of the basic version of the problem (called Scenario A later).
Definition 1. Let • day be a constant that is equal to the number of days considered; • max_session be a constant that is equal to the maximum number of session associated to an operating room in a day; • s_count be a constant that is equal to day × max_session and represents the number of sessions that must be assigned to each operating room; • D = {t : t ∈ [1..day]} be the set of all days;
Let mss : OR × S × SP D ↦→ {0, 1} be a function such that mss(o, s, sp, d) = 1 if the session s in the day d and in the operating room o is assigned to the specialty sp, and 0 otherwise. Moreover, for a given mss, let Amss = {(o, s, sp, d) : o ∈ OR, s ∈ S, sp ∈ SP, d ∈ D, mss(o, s, sp, d) = 1}.
Then, given sets OR, SP, S, D, DD and functions δ , ρ, ε, ω, ζ , the MSS problem is defined as the problem of finding a schedule x, such that (c1) |{ρ(o, d) = s}|=1 ∀o ∈ OR, ∀d ∈ D, ∀s ∈ S; (c2) |{sp : mss(o, s, sp, d) = 1}|=1 ∀ o ∈ OR, ∀ s ∈ S, ∀ sp ∈ SP, ∀ d ∈ D, ρ(o, d) = s; (c3) |{mss(o, s, sp, d) = 1}|=0 ∀ o ∈ OR, ∀ s ∈ S, ∀ sp ∈ SP, ∀ d ∈ D, ρ(o, d) = s, δ (or, sp) = 0; (c4) |{mss(o, s, sp, d) = 1}|=0 ∀ o ∈ OR, ∀ s ∈ S, ∀ sp ∈ SP, ∀ d ∈ D, ρ(o, d) ̸= s; (c5) ζ (sp, d1, d2) > 0 ∀ sp ∈ O, ∀ (d1, d2) ∈ DD; (c6) |ε(sp, d1, d2) − ζ (sp, d1, d2)| ≤ ω(sp, d1, d2) ∀ sp ∈ O, ∀ (d1, d2) ∈ DD;
Condition (c1) ensures that at each operating room is assigned to a session scount times. Condition (c2) ensures that each operating room, in each day and session is assigned to exactly one specialty. Condition (c3) ensures that no operating room is assigned to a not allowed specialty. Condition (c4) ensures that each specialty is assigned to an operating room in the right session and day. Condition (c5) ensures that the percentage of times a specialty is assigned is bigger than 0 in every range of days required. Condition (c6) ensures that the percentage target of time a specialty is assigned minus the actual percentage is less than the allowed error. Definition 2 (Distance target percentage). Given a solution mss, let tmss = ∑ | ε(sp, d1, d2) − ζ (sp, d1, d2) | . Intuitively, tmss represents the sum of sp∈SP,(d1,d2)∈DD; the distance between the target percentage and the actual percentage of times each specialty is assigned to the operating rooms in the range between d1 and d2.
Definition 3 (Optimal solution). A solution mss is said to dominate a solution mss’ if |tmss| < |tmss′ |. A solution is optimal if it is not dominated by any other solution.
We assume the reader is familiar with syntax and semantics of ASP. Starting from the
specifications in the previous section, here we present our compact and efficient ASP solution for the
MSS problem, organized in two paragraphs containing input and output data model, and the ASP
encoding, respectively. The ASP encoding is based on the input language of CLINGO [
END}, targetShare(_,_,_START,END). 3 {mss(OR,SID,SP,DAY) : operatingRoom(OR, SP)} == 1 :- session(SID,DAY,OR). 4 effectiveShare(SP,PERCENTAGE,START,END) :- SESSION = #count{ OR,SID,DAY : mss(OR,SID,SP,DAY), D >= START, D < END}, n_session(N,START,END), specialty(SP), PERCENTAGE = ((SESSION*100) / N). 5 :- effectiveShare(SP,PERCENTAGE,START,END), targetShare(SP,TARGET,ERROR,START,END), PERCENTAGE < (TARGET-ERROR). 6 :- effectiveShare(SP,PERCENTAGE,START,END), targetShare(SP,TARGET,ERROR,START,END), PERCENTAGE > (TARGET+ERROR). 7 :- effectiveShare(SP,PERCENTAGE,START,END), PERCENTAGE <= 0. 8 :∼ effectiveShare(SP,ES,START,END), targetShare(SP,TS,ERR,START,END). [|ES-TS|@1,SP,START]
• Instances of day(DAY) represent the available days.
The output is an assignment represented by an atom of the form mss(OR,SID,SP,DAY), where the intuitive meaning is that the operating room with id OR in the session with id SID and in the day DAY is assigned the specialty SP.
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.
Auxiliary atoms in the heads of rules r1, r2 and, r4 are derived by the encoder to simplify the other rules. In particular, rule r1 assigns the correct session ids to each operating room for all the days considered. The assignment is made assigning an id such that the number of ids assigned in each active day is equal to the number of sessions in which the operating room is splitted. Rule r2 evaluates the total number of sessions available in the range of days between the values start and end. This value is then used to evaluate the percentage of assignment of each specialty. Rule r3 assigns one of the possible specialties to a session of every operating room. Rule r4 derives an atom that represents the assignment percentage of each specialty. In particular, it counts the number of sessions linked to each specialty and divides it by the total number of sessions that are available in that period. Then, rules r5 and r6 check that the percentage of each specialty is compatible with the target values and the allowed errors. Rule r7 ensures that the percentage of each specialty is bigger than 0. Finally, weak constraint r8 minimizes the difference between the assigned and target percentage of each specialty in each period of time.
In this section, we report the results of an empirical analysis of the MSS problem via ASP (second
paragraph). For the problem, data have been randomly generated using parameters inspired by
literature and real world data (first paragraph).The experiments were run on a AMD Ryzen 5 2600
CPU @ 3.40GHz with 16 GB of physical RAM. The ASP system used was CLINGO [
MSS benchmarks. Data are based on the sizes and parameters of a typical middle sized hospital, with 5 different specialties and 10 ORs. Each specialty is associated with a target value for each month and an error, that is equal to 10 for all the specialities. Each specialty can be assigned to just some randomly selected ORs and the target value is assigned by dividing the number of ORs in which the specialty can be assigned to the total number of ORs, and adding to the result a random value in the range between -5 and 5. To test our solution we considered four different scenarios. In the first scenario, that we will call Scenario A, we considered to have the constant max_session equal to 2, while the constant d_count has values from 30 to 180. Moreover, in this scenario the target value for each specialty is equal for each month. For this scenario, we considered 10 instances, each with different target values for all the specialties, for each range of days considered. In particular, we tested the scalability of the scheduler by considering an increasing number of days: 30, 60, 90, 120, 150 and, 180.
Then, we generated a second scenario, that we will call Scenario B, that is based on the Scenario A considering 90 days. The difference with Scenario A is that for each month the target value is increased or decreased by a random value between -2 and 2, thus for each specialty there are three different target values. Changes in the target values could be done by the hospital manager because of different availability of doctors or due to the increase of the surgeries of some specialty.
For the third and fourth scenario, named Scenario C and D, respectively, we again considered a planning horizon fixed to 90 days. The constant max_session is equal to 2 for the Scenario C, while for the Scenario D is equal to 3. This means that, in the fourth scenario, one randomly selected operating room is splitted in three sessions. The difference between the Scenario C and the others is that, for 5 days, three ORs are unavailable, meaning that no session can be assigned to them during that days. The scenarios C and D aim thus at evaluating what is the impact of limiting the usage of the ORs, or changing the number of sessions, respectively. Results of our MSS solution. First, we tested the performances of the scheduler in the basic scenario (Scenario A). The results for this scenario are shown in Figure 2, which represents the range of seconds required to reach the optimal solution in all the 10 instances tested with the different number of days considered, identified by the minimum and maximum times for solving the instances in the set, together with the mean and the median time. From the figure it can be seen that the scheduler is able to optimally schedule the MSS in a mean time of less than 10 seconds even considering 180 days of planning horizon, which is a remarkable result. Moreover, besides being able to reach an optimal solution in less than 10 seconds on average, from the figure it can be noted that even in the worst case, the scheduler is able to find the optimal solution in less than 30 seconds.
Then, we tested the performance of the scheduler in the Scenario B. Testing the scheduler with the 10 instances with 90 days in this scenario we found that the scheduler was able to reach the optimal solution on average in 3 seconds, that is a time that is very near to the time required in Scenario A. Thus, this analysis reveals that even changing the target values in each month for all the specialties, our solution maintains very good performance.
Having evaluated now the performance in Scenario A and B, we then tested the scheduler in Scenario C and D. Table 2 reports the time required by each instance in Scenario A and in these more constrained scenarios, on 90 days planning horizon.
From the table we can see that the timing obtained by Scenario C is almost equal to the original one. So, even if three ORs are unavailable for 5 days, the scheduler is able to compute the optimal solution in the same time required in the Scenario A. In the Scenario D, the scheduler obtained the optimal solution almost in the same time as in the Scenario A for all but one instance: Indeed, the third instance requires 4 seconds instead of 2 seconds to reach the optimal solution (from a preliminary analysis, this harder instance corresponds to a setting in which a higher number of sessions is set to an OR assigned to only one specialty with low target).
Overall, we can say that also in Scenario C and D the scheduler is able to reach highly satisfying results, also when compared to the basic Scenario A.
In this section, we present the results obtained by using real data and the modification done to use the solution with the new data. The section is split into two parts: in the first one we present the results obtained by trying to replicate the same MSS used by the real hospital. In the second one, we present a new encoder that tries to increase the quality of the MSS. Producing an MSS that reduces the shift between specialties is crucial to reducing the costs of a hospital since it allows for a reduction in the work needed to prepare the ORs for different specialties. Moreover, keeping the specialties to the same percentage of assignments, if possible, eases the organization of the personnel turnover.
Replicate the results with real data. After having tested our solution in different scenarios
with synthetic data in Section 5, we wanted to test it with real data. To accomplish this, we used
data from ASL1 Liguria, Italy, already used in [
In this case, we wanted to assign the ORs to the different specialties of the hospital with the same percentages of assignments. In order to complete these tests, we derived the number of ORs, number of specialties, possible assignments of specialties to ORs, and percentage of assignments of each specialty from the real data. Then, we used this information as input, of which an excerpt obtained from the Imperia hospital can be seen in Figure 3. We tested the solution considering 90 days in a different, real, setting where, differently from the synthetic data, the number of ORs is larger than the number of specialties. The solution was able to find an optimal solution in less than a second. This means that the solution managed to assign the different ORs as requested by the hospitals very rapidly and, moreover, the error was equal to 0. This allows us to confirm the goodness of our solution, even on real data.
Additions to consider real data. In the following, we present an addition to the already presented solution that we did to increase the quality of the MSS produced by the hospital and that allows us to derive the percentage of assignments to assign to each specialty. Indeed, in the rest of the work, we consider the target of assignment of the specialties as an input. Here, we want to consider the case in which a hospital wants to derive the assignments considering the number of expected patients and caring about the quality of the MSS. To produce a better MSS, we want to obtain an MSS in which: the ORs are assigned, as much as possible, to the same specialty for all the sessions in a day, every week the specialties are assigned to the same day, and the percentage of time assigned to each specialty every month does not change. Indeed, analyzing the real data, we found that many ORs were assigned to different specialties on consecutive days and, even if not needed, looking at the number of patients, the percentage of time assigned to the different specialties varies a lot during the months.
Starting from the ASL1 data, we derived the number of patients assigned each month for every specialty, considering it as a prediction of future needs, and used this information as a new input for a modified version of the encoder in Figure 1.
Data Model. The input data is the same as the one presented in Section 4 but for the atom targetShare(SP,TARGET,ERROR,START,END) that is not used and is replaced by an atom needed(SP, EXPECTED, START, END) that represents for each specialty (SP) the expected percentage (EXPECTED) of utilization needed for patients of that specialty (ERROR) in the range of days between START and END. The output is the same as in Section 4.
Encoding. The related encoding is the same as presented in Figure 1 but without the rules appearing in lines 5, 6, and, 7 and the weak constraint in line 8, plus the rules in Figure 4. In the following, we describe such additional rules.
In particular, rule r9 ensures that the percentage of sessions assigned to each specialty is more than the expected percentage. Rule r10 is used to derive the difference between the percentage of sessions assigned to a specialty and the expected percentage for the specialty in which the difference is bigger than a value equal to 10. Weak constraint r11 minimizes the assignments of two different specialties to the same OR and on the same day in different sessions. Weak constraint r12 minimizes the assignments of two different specialties to the same OR in a one-week time gap. Weak constraint r13 minimizes the difference in the percentage of sessions assigned to each specialty each month. Finally, weak constraint r14 minimizes the value obtained with rule r10, thus, it reduces the unnecessary assignments.
Testing the solution with the new encoder with the data of the Imperia hospital, we obtained an optimal solution in 5.8 seconds. Thus, the solution is able to obtain an MSS in which for every day, each OR has just one specialty assigned, and every week the specialties are assigned to the same day. Moreover, the difference in the percentage of sessions assigned to each specialty every month is 0, while keeping the value higher than the expected need.
Upon testing the new solution with real data, we can afrfim its viability as a valid option for generating a MSS, especially when the hospital prioritizes enhancing the overall quality of the MSS over achieving specific assignments for each specialty.
The section is organized in two paragraphs: the first presents works that highlights the importance of solving the MSS problem and alternative methods for solving the problem, with a focus on the works using real data. The second paragraph, instead, mentions works in which ASP has been already successfully employed to closely related scheduling problems.
Solving the MSS problem. In [
The work in [
In this paper, we have presented an analysis of the MSS problem modeled and solved with ASP. We started from an informal description of the problem, formulated it in precise mathematical terms, and then presented our ASP solution. Results on synthetic benchmarks show that the ASP solution is able to optimally solve the MSS problem even when considering large planning horizons, up to 6 months. Moreover, solving more difficult scenarios, in which, e.g., targets and number of sessions change within the planning horizon, reduce just slightly the performance of the scheduler. Further, we adapted the encoding and tested our solution on real data from ASL1 Liguria in Italy, still obtaining satisfying results. Results also demonstrate that our solution is more targeted towards increasing the quality of the MSS compared to the original schedules on the real data. For what concerns future works, we plan to investigate rescheduling solutions, that may come into play when the MSS scheduling can not be implemented for some reasons, e.g., sudden unavailability of ORs. Finally, we plan to compare our solution to other logic-based formalisms: Preliminary analysis in [32] has shown that the ASP solution described in Section 4, compared to other logic-based formalisms via automatic translations of ASP instances, was able to reach the optimal solution in less time than the other formalisms such as MaxSAT solvers. We plan to confirm these results on the improved solution presented in Section 6 concerning real data. tion to the chemotherapy treatment scheduling problem, Theory and Practice of Logic Programming 21 (2021) 835–851. [30] 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. [31] P. Cappanera, M. Gavanelli, M. Nonato, M. Roma, Decomposition approaches for scheduling chronic outpatients’ clinical pathways in Answer Set Programming, Journal of Logic and Computation (2023) exad038. URL: https://doi.org/10.1093/logcom/exad038. doi:10.1093/logcom/exad038. [32] M. Mochi, G. Galatà, M. Maratea, Master Surgical Scheduling via Answer Set Programming, Journal of Logic and Computation (2023) exad035. doi:10.1093/logcom/exad035.