The Nuclear Medicine Scheduling (NMS) problem consists of assigning patients to a day, in which the patient will undergo the medical check, the preparation, and the actual image detection process. The schedule of the patients should consider the different requirements of the patients and the available resources, e.g., varying time required for different diseases and radiopharmaceuticals used, number of injection chairs, and tomographs available. In this paper we present a solution where modeling and solving are done via Answer Set Programming. Experiments employing real data show that the solution provides satisfying results in a short time.
Nuclear Medicine is a medical specialty that uses radiopharmaceuticals, a particular kind of drug containing radioactive elements, to treat or diagnose diseases. According to data by the Italian Ministry of Health, almost 2 millions nuclear medicine exams have been carried on during 2022 in Italy1. The process of treating patients with this technique is complex since it involves multiple resources of the hospital and requires multiple steps of varying time. Moreover, often these drugs contain radioactive elements characterized by short half-lives, meaning that they decay rapidly after their preparation. Thus, the timing should be as precise as possible in order to obtain images of good quality. Addressing this problem effectively is crucial due to the nature of the diagnosed illnesses and treated through nuclear medicine, alongside the significant costs associated with this kind of technique. An efficient, possibly optimal, solution can reduce the waiting time of the patients and can thus increase the effective utilization of the resources, avoiding waste of time and resources. Nevertheless, reducing the unnecessary time spent by the patients in the hospital is vital for increasing the satisfaction of the patients.
Thus, the Nuclear Medicine Scheduling (NMS) problem consists of assigning patients to a day, in which the patient will undergo the medical check, the preparation, and the actual image detection process. The schedule of the patients consider the different requirements of the patients and the available resources, e.g., varying time required for different procedures and radiopharmaceuticals used, number of injection chairs and tomographs available. We followed the definition of the problem given by Medipass 2, leading provider of technological innovation across cancer care and diagnostic imaging in Italy, in collaboration with SurgiQ3, an Italian company active in planning and scheduling solutions.
Complex combinatorial problems, possibly involving optimizations, such as the NMS problem,
are usually the target applications of AI languages for knowledge representation and reasoning,
such as Answer Set Programming (ASP). The success of ASP is due to different factors, including
a simple but rich syntax [
Subsequently, we propose a solution leveraging ASP, where we design an encoding that
encapsulates the problem specifications. This encoding is then processed using the
state-ofthe-art system CLINGO [
The paper is structured as follows. Sections 2 and 3 present an informal description of the problem and a precise, mathematical formulation, respectively. Then, after the needed background on ASP in Section 4, Section 5 shows our ASP encoding, whose experimental evaluation is presented in Section 6. The paper ends by discussing related works and conclusions in Section 7 and 8, respectively.
The NMS problem consists of assigning patients to a day and to a tomograph and/or injection chair if required by the patient or the specific procedure. In our problem, for each day we consider a set of 120 time slots (TS), each representing 5 minutes. Each patient needs an exam and each exam is linked to a protocol defining the phases and the time required for each phase. We considered 11 different protocols. Each protocol can encompass up to four phases, represented as (p1) anamnesis, (p2) medical check, (p3) radiopharmaceuticals injection and bio-distribution time, and (p4) image detection. Moreover, each phase can require a different amount of time depending on the exam. Table 1 shows the total time needed by each protocol and the partial time required by each phase, expressed in the number of time slots used.
Due to the high number of phases required by each patient and the variety of the considered protocols, in many clinics the schedule of the patients is sub-optimal. A sub-optimal schedule is problematic not only because of the high cost of the drugs and machines involved in the exams, 2https://ergeagroup.com/it/. 3https://surgiq.com/. but is particularly detrimental for the patients since the order and the time required by each phase, in particular the injection and the bio-distribution time, is fundamental for a proper image detection.
Different clinics have different resource availability and may have different requirements in defining a proper solution. Here we present the criteria followed in the clinic that provided us with the real data of the patients and that we use to define the problem. We considered a clinic with two rooms, each with one tomograph and three injection chairs. We started from a list of patients, each requiring a specific protocol, to be assigned in a day. A proper solution must satisfy the following conditions: • a starting and an ending time should be assigned to every scheduled patient for each required phase; • there must be at most two patients concurrently in the medical check phase; • the injection phase must be done in an injection chair or on a tomograph according to the required protocol; • each injection chair and tomograph can be used by just one patient at the same time; • patients requiring an injection chair must be assigned to the tomograph of the same room; • protocol identified by the id 815 cannot be assigned on the same day and tomograph for more than one patient.
The solution should maximize the number of scheduled patients in the considered days and, to increase the satisfaction of the patients and the effectiveness of the exams, the solution should also try to minimize the unnecessary time spent in the clinic by the patients.
Let N be the set of reservation numbers, D be the set of days, TS denote the set of time slots, and PR be the set collecting the protocol numbers referred to exams. Each protocol may comprise a maximum of four phases, represented by the set P = {p1, p2, p3, p4}. Let R denote the set of rooms and S = T ∪ C ∪ {ε} be the set representing the available resources, given by the union of the set T of tomographs, the set C of chairs and the element ε denoting that it is no required a resource.
Moreover, let: • λ : T × PR → N be the function that returns the maximum number of exams that can be executed on a tomograph of a specific protocol, for all the protocols that require a limitation; • ω : P × PR → N be the function that returns the number of time slots required for each phase of a specific protocol; • β : PR → {0, 1} be the function that assigns the value 1 if the protocol requires both a chair and a tomograph, 0 otherwise; • α : S × R → {0, 1} be the function that assigns the value 1 if there is an association between the resource and the room, 0 otherwise. Furthermore, let A = α− 1(1) be the set collecting all the good associations between resource and room.
To associate a reservation number, a day, and a protocol, we now introduce the notion of registration.
Definition 1. A registration ρ is a function of the form ρ : N × D × PR → {0, 1} such that ρ(n, d, x) = 1 if there exists a reservation n on a day d for the protocol x, 0 otherwise. Let R = ρ− 1(1) = {(n, d, x) ∈ N × D × PR | ρ(n, d, x) = 1} be the set collecting all the registrations.
Consequently, we define the notion of assignment to link together a registration with a specific phase of the protocol under consideration and a time slot.
Definition 2. An assignment τ is a function of the form τ : R × P × TS → {0, 1} such that τ(n, d, x, p, y) = 1 if a phase p and an initial time slot y are assigned to a registration. Let T = τ− 1(1) = {(n, d, x, p, y) ∈ R × P × TS | τ((n, d, x), p, y) = 1} be the set collecting all the assignments.
Before presenting the main problem of this paper, we define the concept of scheduling, which connects an assignment with a resource and its allocation.
Definition 3. A scheduling σ is a function of the form σ : T × A → {0, 1} that assigns the value 1 if there exists a reservation number n on day d for the protocol x, referred to the phase p on time slot y, using the resource s in the room r. The set S = σ − 1(1) = {t = (n, d, x, p, y, s, r) | σ (t) = 1} collects all the tuples eligible as scheduling.
Definition 4 (NMS). The Nuclear Medicine Scheduling (NMS) problem is defined as the problem of finding a set ψ of tuples t = (n, d, x, p, y, s, r) ∈ S that satisfies the following conditions: (c1) ∀(y, s) ∈ TS × S |{(n, d, x, p, y′, s, r) ∈ ψ | p ̸= p1 ∧ y ∈ {y′, . . . , y′ + w(p, x)}}| ≤ 1; (c2) ∀y ∈ TS |{(n, d, x, p, y′, s, r) ∈ ψ : p = p1 ∧ y ∈ {y′, . . . y′ + w(p, x)}}| ≤ 2; (c3) ∀x ∈ PR : β (x) = 1, it holds that t′ = (n, d, x, p′, y′, c, r′) and t′′ = (n, d, x, p′′, y′′,t, r′′) belong to ψ iff r′ = r′′; (c4) ∀t ∈ T |{x | (n, d, x, p, y, s, r) ∈ ψ}| ≤ λ (t, x); (c5) t′ = (n, d, x, pi, y′, s′, r) and t′′ = (n, d, x, pi+1, y′′, s′′, r) belong to ψ iff y′′ ≥ y′ + ω(pi, x) (c6) ∀t = (n, d, x, p, y, s, r) ∈ ψ it holds that y + ω(p, x) ∈ T S (c7) ∀t = (n, d, x, p, y, s, r) ∈ ψ – if p = p1 it holds that s = ε, – if p = p2 or p = p3 and β (x) = 1 it holds that s = c, with c ∈ C, – if p = p2 or p = p3 and β (x) = 0 it holds that s = t, with t ∈ T , – if p = p4 it holds that s = t, with t ∈ T .
The specified conditions are necessary to enforce the following constraints: (c1) each resource (chair or tomograph) can be used by at most one patient at a time; (c2) at most two patients at a time are allowed during the anamnesis phase; (c3) patients requiring an injection chair must be assigned to the tomograph of the same room; (c4) the number of protocols executed on a single tomograph is limited; (c5) given two consecutive phases pi and pi+1 for a patient, the initial time slot of pi+1 must be consistent with respect to pi, i.e. pi+1 must start after that pi has terminated; (c6) each schedule must not exceed the available time slot; (c7) the resources must be well distributed, i.e. the phase anamnesis does not include any resource, the phases 2 and 3 may require a chair or a tomograph depending on the protocol, and the last phase requires the usage of a tomograph.
As previously explained, an optimal solution aims to maximize the number of scheduled patients on the considered days while minimizing the idle time spent in the clinic by patients. In order to define the notion of the optimal solution, we want to evaluate the idle time spent by a patient. Accordingly, given (n, d, x, p1, y′, s′, r) and (n, d, x, p4, y′′, s′′, r) ∈ ψ let Htime(n) = (y′′ + ω(p4, x)) − y′) be the time spent by the patient in the hospital deriving from the scheduling and let Rtime(n) = ∑p∈P ω(p, x) be the minimum time required to execute the protocol. Definition 5 (Dominating Solution). Let δψ = ∑n∈N |Htime(n) − Rtime(n)| be the sum of the differences between the actual time required by a protocol and the time allocated by the solution for that protocol for each patient n, and let Σψ = {(n, d, x, p, y, s, r) ∈ ψ}. A solution ψ dominates a solution ψ′ if • |Σψ′ | < |Σψ |, or if • |Σψ′ | = |Σψ | ⇒ δψ < δψ′ .
Definition 6 (Maximal Scheduling Solution). A scheduling solution is maximal if any other scheduling solution does not dominate it.
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, e.g., the function #count computes the number of terms.
An aggregate atom is of the form f (S) ≺ T , where f (S) is an aggregate function, ≺ ∈ { <, ≤ , >, ≥ , ̸=, =} is a 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 [16] ω is of the form: :∼
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 w, 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 [17] of GP w.r.t. I is the subset GIP of GP obtained by deleting from GP the rules in which a body literal is false w.r.t. I. An interpretation I for P is an answer set (or stable model) for P if I is a minimal model (under subset inclusion) of GIP (i.e., I is a minimal model for GIP) [17].
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.
In this section, we present the ASP encoding for the problem presented in Section 2 and formalized
in Section 3. The underlying encoding is based on the input language of CLINGO [
T and the chair C to the room R, respectively; • instances of required_chair(PrID) denote the necessity of a chair for the phases 1 and 2 for the protocol PrID; • instances of cost(PrID, NumTS) represent the total duration in terms of time slots, denoted as NumTS, of the phases within the protocol identified by PrID; • instances of limit(PrID,N) denote the maximum number N of exams with protocol number PrID that can be executed on a fixed tomograph in a day.
The output consists of assignments represented by the atom x(ID,D,TS,PrID,P) where the intuitive meaning is that the registration with identification number ID for the exam with protocol number PrID, regarding the phase P, has been scheduled for the day D during the time slot TS. Additionally, it includes atoms chair(C,ID,D) and tomograph(T,ID,D), denoting the 1 0 {x(ID, D, TS, PrID, 0) : avail(TS, D)} 1 :- reg(ID, D, PrID). 2 {x(ID, D, START, PrID, P+1) : avail(START,D), START >= TS+NumTS, START < TS+NumTS+6} = 1 :- x(ID, D, TS, PrID, P), exam(PrID, P, NumTS), P >= 0, P < 3. 3 :- x(ID, _, TS, PrID, 3), exam(PrID, 3, NumTS), TS + NumTS > 120. 4 timeAnamnesis(ID, TS..TS+NumTS-1) :- x(ID, D, TS, PrID, 0), exam(PrID, 0,
NumTS). 5 :- #count{ID: timeAnamnesis(ID, TS)} > 2, avail(TS,D). 6 timeOccupation(ID, D, TS, END-1, PrID) :- x(ID, D, TS, PrID, 1), x(ID, D,
END, PrID, 3). 7 res(ID, D, TS..END,0) :- timeOccupation(ID, D, TS, END, PrID), required_chair(PrID). 8 res(ID, D, TS..TS+NumTS-1,1) :- x(ID, D, TS, PrID, 3), exam(PrID, 3,
NumTS), required_chair(PrID). 9 res(ID, D, TS..END+NumTS-1,1) :- timeOccupation(ID, D, TS, END, PrID), exam(PrID, 3, NumTS), not required_chair(PrID). 10 :- #count{ID: tomograph(T, ID, D), x(ID, D, _, PrID, _)} > N, limit(PrID,
N), tomograph(T,_). 11 1 {chair(C, ID, D) : chair(C, _)} 1 :- x(ID, D, _, PrID, _), required_chair(PrID). 12 1 {tomograph(T, ID, D) : tomograph(T, _)} 1 :- x(ID, D, _, PrID, _). 13 :- chair(C, ID, D), tomograph(T, ID, D), chair(C, R1), tomograph(T, R2), R1 != R2. 14 chair(C, ID, D, TS) :- chair(C, ID, D), res(ID, D, TS, 0). 15 tomograph(T, ID, D, TS) :- tomograph(T, ID, D), res(ID, D, TS, 1). 16 :- #count{ID: tomograph(T, ID, D, TS)} > 1, tomograph(T,_), avail(TS,D). 17 :- #count{ID : chair(C, ID, D, TS)} > 1, chair(C,_), avail(TS,D). 18 :∼ not x(ID, D, _, _,0), reg(ID, D, _). [1@2, ID, D] 19 :∼ x(ID, _, START, PrID, 0), x(ID, _, END, _, 3), cost(PrID, NumTS), END
START - NumTS >= 0. [END - START - NumTS@1, ID]
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 may assign or not the registration with identifier ID to a specific time slot TS for the day D in phase 0, i.e. the phase of the anamnesis. Rule r2 assigns an already scheduled session for a given phase P to the subsequent planned phases, under the condition that the start of the phase does not extend beyond the latest available time slot for a session on that day. Furthermore, it ensures that the subsequent phase starts at most 5 time slots after the ending of the previous phase. Rule r3 ensures that the duration of the final phase is also consistent with the time slots, ensuring that all phases are completed within the specified limit. Rule r4 keeps track of the time slots allocated to a patient during phase 0 via the auxiliary atom timeAnamnesis(ID, TS). Rule r5 restricts the number of patients during the anamnesis phase to a maximum of two. Rule r6 produces the auxiliary atom timeOccupation(ID,D,TS,END,PrID), representing the duration needed for each patient ID from the initial time slot TS of phase 1 to the final one END of phase 2, concerning the protocol PrID on the day D. Rule r7 produces the auxiliary atom res(ID, D, TS, 0) for each time slot derived from the previous rule. Specifically, the constant 0 denotes that a chair is required for each of these time slots. Rules r8 and r9 produce the atom res(ID,D,TS,1), which differs from the previous one for the constant 1, indicating the use of a tomograph. From rule r8, it is inferred that a tomograph is employed during phase 3, whereas rule r9 indicates the tomograph’s usage from phase 1 to 3, according to the atom timeOccupation. Rule r10 ensures that the limit of protocols that can be executed on a single tomograph is respected. Rule r11 produces the atom chair(C,ID,D) representing the assignment of a chair C on the day D to the patient ID when the protocol PrID requires a chair. Rule r12 produces the atom tomograph(T,ID,D) representing the assignment of a tomograph T on the day D to the patient ID. Rule r13 prevents the patient who moves from the chair to the tomograph from changing room. Rule r14 and r15 generate the atoms chair(C,ID,D,TS) and tomograph(T,ID,D,TS) respectively, indicating the time slots TS during which the chair C and tomograph T are utilized by the patients ID on the day D. Rule r16 and r17 ensure that at most one patient is assigned to each tomograph and chair in every time slot, respectively. Finally, the optimal solution is achieved through the application of rule r18, which minimizes (with the highest priority) the number of registrations not assigned to a schedule, and rule r19, which minimizes the duration of patient appointments beyond the time necessary to perform the test.
In this section, we report the results of an empirical analysis of the NMS problem via ASP. The
data used for the empirical analysis are real data coming from a medium size hospital provided by
Medipass. We performed experiments on an Apple M1 CPU @ 3.22 GHz machine with 8 GB of
physical RAM. The ASP system used was CLINGO [
We tested instances of more than a year of daily exams. In particular, we tested 366 instances, each corresponding to a weekday excluding weekends, resulting in a total of 72 weeks. The solution schedules the patients in a day in a range of 10 hours, split into 120 time slots of 5 minutes. Each patient is linked to one of the possible exams. In particular, one exam protocol is required by more than 85% of the patients, thus, the majority of the patients need a exam protocol that requires 2 time slots for the anamnesis and other 2 time slots for medical preparation, 10 time slots for the drug injection and the bio-distribution time and, at last, the image detection requires 7 time slots. The other patients can be associated with one of the other 11 possible protocols. The schedule is done having as available resources two rooms for the radiotherapy. In each room, there is a tomograph and 3 chairs. The number of patients requiring exam changes every day but, on average, there are 29 patients to be scheduled, with a maximum of 37 patients.
The results obtained by testing the encoding presented in Section 5 with the real data are reported in the following.
We decided to schedule the patients with a time limit of 60 seconds. This allows the hospital to get a result in a very short time and to get an estimation of the usefulness of our solution in a time-constrained environment. Figure 2 presents the average, the maximum, and the minimum times required to obtain a solution according to the number of patients to be scheduled. In this way, it is possible to analyze the waiting time a hospital should expect to get a solution, depending on the number of patients to be assigned. From the graph it can be seen that up to 29 patients all the instances are optimally solved before the time limit. While on average the instances are solved optimally in less than 60 seconds in the instances with less than 36 patients. We were able to test the encoding in just a few days having 36 and 37 patients and, in that case, the encoding is not able to optimally schedule the patients. In general, we are able to nfid the optimal solution for more than 60% of the instances.
After analyzing the time required to generate schedules on different days, we proceed to evaluate the quality of the results obtained. Specifically, we first examine the number of registrations that the solution fails to assign during the day, as this was the primary optimization criterion. Subsequently, we assess the second optimization criterion.
To gain a better understanding of the schedule’s quality, we present the results considering all schedules and we specifically focus on non-optimal solutions. Even when the solution is optimal, some days still have a high number of unassigned patients due to constraints imposed by the data.
When considering instances where the encoding failed to find an optimal solution, we observed that in the majority of cases (more than 80%), the solution assigns the exam to over 80% of the possible patients. In the remaining instances, the solution still manages to assign over 70% of the total patients in all cases. These findings indicate that even under strict time limits, the results remain of satisfactory quality, a crucial aspect for operational scenarios.
Next, we summarize the results obtained across all instances, whether optimally or nonoptimally solved. Figure 3 illustrates the number of schedules with at least a certain percentage of assigned patients. Unlike the non-optimal solutions, optimally solved instances occasionally Average time (s) Max time (s) Min time (s)
26 27 28 29 30
Number of Patients 0 2 exhibit a percentage of assigned patients below 60%, attributed to resource limitations, which we further investigate. However, overall, the majority of solutions have a patient assignment rate exceeding 80%. 200 s n o i t lu150 o s f o re100 b m u N 50 40% 50%
60% 70% Percentage of assigned patients 80% 90%
As previously discussed, some optimal solutions exhibit a low percentage of assigned patients. Here, we aim to analyze in more details this scenario to ensure that no better solution could have been identified. Specifically, we focus on the only instance where the schedule fails to assign an exam to more than 50% of the patients. In this case, the schedule assigns exams to 16 out of the total 33 patients. Upon closer examination, we find that among the 33 patients, 14 require protocol with id 823, while the remaining 19 require protocol with id 815. The solution successfully assigns exams to all 14 patients with protocol id 823. However, due to the nature of the protocol with id 815, the solution can only assign one patient with this protocol to each tomograph. Consequently, it manages to assign exams to just 2 patients. This limitation explains the low percentage of assigned patients in this instance.
Finally, after examining the results related to the first optimization criterion, we proceed to analyze the second one. Specifically, we focus on the average waiting time for each patient, quantified as the unnecessary number of time slots spent in the hospital. In over 70% of instances, the encoding successfully assigns patients with zero waiting times. This indicates that in these solutions, patients can adhere to their protocols optimally. These results greatly improve those obtained by the hospital in terms of unnecessary time spent in the hospital by the patients. Indeed, in the original schedule of the hospital, just 19% of the considered days had zero waiting times for each patient. Moreover, while in the ASP-based solution we have 95% of days with less than 5 time slots of waiting time, in the original schedule there were just 75% of days with this average waiting time.
The section is organized in two paragraphs: The first is focused on alternative methods for solving the NMS problem, while the second mentions works in which ASP has been employed in scheduling problems.
Solving the NMS problem. Pérez et al. [18] proposed four different scheduling solutions to the NMS, each giving priority to a different aspect. Specifically, the first solution focuses on the preferences of the patients. The second one assigns the patients as soon as possible. The third one is a combination of the first two, while the fourth one fixes the technologists to the machines and assigns the patients based on the machine availability. The proposed solutions were tested on the data of one of the biggest hospitals in Texas and tested in a simulated environment. Another work using real data to validate the solution is from Xiao et al. [19]. The authors got the data from the West China Hospital and proposed a two-step solution. The first step is the development of a nonlinear integer programming model considering the settings of the hospital and the drugs. After obtaining the solution of the first step, they developed a stochastic online algorithm following different scheduling strategies to adapt the solution to the real requests of patients. Akhavizadegan et al. [20] addressed the NMS problem using a Markov decision process (MDP) to decide how many patients to schedule in a day from a tactical perspective and which patient can move on to the next phase from an operational perspective. The MDP is then solved using two heuristic algorithms and a mathematical programming model. This system is evaluated against historical data of patients scheduled following a First-Come-First-Served strategy. The historical data comes from the public Hospital in Tehran-Iran.
Solving scheduling 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., [21] for a recent survey), the first solved problems were the Nurse Scheduling
Problem [22, 23, 24], where the goal is to create a scheduling for nurses working in hospital
units, and the Operating Room Scheduling [25, 26], whose goal is to assign operating rooms to
patients. More recent problems include the Chemotherapy Treatment Scheduling problem [
In this paper, we have presented an analysis of the NMS problem, modeled and solved with ASP. We started from a mathematical formulation of the problem, whose specifications come from a real scenario, and then presented our ASP solution. Results on real data show satisfying outcomes in terms of quality in a relatively short time.
Future works include improving the scalability of the encoding and providing the solution of the NMS rescheduling problem, which comes into play when the computed schedule can not be implemented due to some unavailability, and the implementation of a web application for easy usage of our solution. Additionally, exploiting the modularity of ASP, we plan to extend the program taking into account the fairness of the scheduling, ensuring that all the protocols are assigned equally, and a level of priority among patients. [16] F. Buccafurri, N. Leone, P. Rullo, Enhancing Disjunctive Datalog by Constraints, IEEE
Transactions on Knowledge and Data Engineering 12 (2000) 845–860. [17] W. Faber, G. Pfeifer, N. Leone, Semantics and complexity of recursive aggregates in answer set programming, Artificial Intelligence 175 (2011) 278–298. [18] E. Pérez, L. Ntaimo, W. E. Wilhelm, C. Bailey, P. McCormack, Patient and resource scheduling of multi-step medical procedures in nuclear medicine, IIE Transactions on Healthcare Systems Engineering 1 (2011) 168–184. URL: https://doi.org/10.1080/19488300. 2011.617718. doi:10.1080/19488300.2011.617718. [19] Q. Xiao, L. Luo, S. Zhao, X. bin Ran, Y. bing Feng, Online appointment scheduling for a nuclear medicine department in a chinese hospital, Computational and Mathematical Methods in Medicine 2018 (2018). URL: https://api.semanticscholar.org/CorpusID:5061754. [20] F. Akhavizadegan, J. Ansarifar, F. Jolai, A novel approach to determine a tactical and operational decision for dynamic appointment scheduling at nuclear medical center, Computers & Operations Research 78 (2017) 267–277. [21] M. Alviano, R. Bertolucci, M. Cardellini, C. Dodaro, G. Galatà, M. K. Khan, M. Maratea, M. Mochi, V. Morozan, I. Porro, M. Schouten, Answer set programming in healthcare: Extended overview, in: IPS and RCRA 2020, volume 2745 of CEUR Workshop Proceedings, CEUR-WS.org, 2020. URL: http://ceur-ws.org/Vol-2745/paper7.pdf. [22] M. Alviano, C. Dodaro, M. Maratea, An advanced answer set programming encoding for nurse scheduling, in: AI*IA, volume 10640 of LNCS, Springer, 2017, pp. 468–482. [23] C. Dodaro, M. Maratea, Nurse scheduling via answer set programming, in: LPNMR, volume 10377 of LNCS, Springer, 2017, pp. 301–307. [24] M. Alviano, C. Dodaro, M. Maratea, Nurse (re)scheduling via answer set programming,
Intelligenza Artificiale 12 (2018) 109–124. [25] C. Dodaro, G. Galatà, M. Maratea, I. Porro, Operating room scheduling via answer set programming, in: AI*IA, volume 11298 of LNCS, Springer, 2018, pp. 445–459. [26] C. Dodaro, G. Galatà, M. K. Khan, M. Maratea, I. Porro, An ASP-based solution for operating room scheduling with beds management, in: P. Fodor, M. Montali, D. Calvanese, D. Roman (Eds.), Proceedings of the Third International Joint Conference on Rules and Reasoning (RuleML+RR 2019), volume 11784 of Lecture Notes in Computer Science, Springer, 2019, pp. 67–81. [27] S. Caruso, G. Galatà, M. Maratea, M. Mochi, I. Porro, Scheduling pre-operative assessment clinic with answer set programming, Journal of Logic and Computation 34 (2023) 465–493.
URL: https://doi.org/10.1093/logcom/exad017. doi:10.1093/logcom/exad017. [28] M. Balduccini, Industrial-size scheduling with ASP+CP, in: J. P. Delgrande, W. Faber (Eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, volume 6645 of Lecture Notes in Computer Science, Springer, 2011, pp. 284–296. [29] D. Abels, J. Jordi, M. Ostrowski, T. Schaub, A. Toletti, P. Wanko, Train scheduling with hybrid asp, in: M. Balduccini, Y. Lierler, S. Woltran (Eds.), Logic Programming and Nonmonotonic Reasoning, Springer International Publishing, Cham, 2019, pp. 3–17. [30] M. M. S. El-Kholany, M. Gebser, K. Schekotihin, Problem decomposition and multi-shot asp solving for job-shop scheduling, 2022. arXiv:2205.07537.