The Chemotherapy Treatment Scheduling (CTS) [29][30][31]35] problem consists of computing a schedule for patients requiring chemotherapy treatments. The CTS problem is a complex problem for oncology clinics since it involves multiple resources and aspects, including the availability of nurses, chairs, and drugs. Chemotherapy treatments have a cyclic nature, where the number and the duration of each cycle depend on the different types of cancer and the stage of the disease. Moreover, treatments may have different priorities that must be taken into account for preparing a solution. A proper solution to the CTS problem is thus crucial for improving the degree of satisfaction of patients and nurses, and for a better management of resources. Various studies, also in the context of the COVID19 emergency [32,36], have shown how delays in cancer surgery and treatment have a significant adverse impact on patient survival. This impact varies depending on the aggressiveness of the cancer, thus stressing the importance of developing a model capable of efficiently prioritize patients.
Complex combinatorial problems, possibly involving optimizations, such as the CTS problem, are usually the target applications of AI languages and tools such as Answer Set Programming (ASP). As a matter of fact, ASP has been successfully employed for solving hard combinatorial problems in several research areas, including Artificial Intelligence [8,9,18], Bioinformatics [20], Hydroinformatics [22], and it has been also employed to solve many scheduling problems [14,26,34,1,15,16,5,6,19,8], and in industrial applications (see, e.g., [2,17]). The success of ASP is due to different factors, including a simple but rich syntax [12], which includes optimization statements as well as powerful database-inspired constructs like aggregates, an intuitive semantics [10], and the availability of efficient solvers (see, e.g., [4,23,33,25,3]).
In this paper, we propose the first ASP encoding for solving the CTS problem, and then we tested our solution by experimenting with several instances simulating real-world scenarios. Results obtained using the state-of-the-art ASP solver clingo [24] show that ASP is a suitable solving methodology for the CTS problem.
To summarize, the main contributions of this paper are the following:
• We provide an ASP encoding for solving the complete CTS problem (Section 4). • We generated several instances simulating real-world scenario and conducted an experimental analysis assessing the good performance of our solution (Section 5).
• We analyze related literature (Section 6).
The paper is completed by Section 2, which contains needed preliminaries about ASP, by an informal description of the CTS problem in Section 3, and by conclusions and possible topics for future research in Section 7.
Answer Set Programming (ASP) [10] is a programming paradigm developed in the field of nonmonotonic reasoning and logic programming. In this section we overview the language of ASP. More detailed descriptions and a more formal account of ASP, including the features of the language employed in this paper, can be found in [10,13]. Hereafter, we assume the reader is familiar with logic programming conventions.
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(t 1 , . . . , t n ), where p is a predicate of arity n and t 1 , . . . , t n are terms. An atom p(t 1 , . . . , t n ) is ground if t 1 , . . . , t n are constants.
A ground set is a set of pairs of the form consts : conj , where consts is a list of constants and conj is a conjunction of ground standard atoms. A symbolic set is a set specified syntactically as {T erms 1 : Conj 1 ; • • • ; T erms t : Conj t }, where t > 0, and for all i ∈ [1, t], each T erms i is a list of terms such that |T erms i | = k > 0, and each Conj i 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:
An aggregate atom is of the form f (S) ≺ T , where f (S) is an aggregate function, ≺ ∈ {<, ≤, >, ≥, =, =} 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:
where a 1 , . . . , a n are standard atoms, b 1 , . . . , b k are atoms, b k+1 , . . . , b m are standard atoms, and n, k, m ≥ 0. A literal is either a standard atom a or its negation not a. The disjunction a 1 ∨ . . . ∨ a n is the head of r, while the conjunction b 1 , . . . , b k , not b k+1 , . . . , not b m 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 [11] ω 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 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 U P and the Herbrand base B P of P are defined as usual. The ground instantiation G P of P is the set of all the ground instances of rules of P that can be obtained by substituting variables with constants from U P .
An interpretation I for P is a subset I of B P . 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 G P and an interpretation I, the reduct [21] of G P w.r.t. I is the subset G I P of G P obtained by deleting from G P 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 G I P (i.e., I is a minimal model for G I P ) [21]. Given a program with weak constraints Π = P, W , the semantics of Π extends from the basic case defined above. Thus, let G Π = G P , G W be the instantiation of Π; a constraint ω ∈ G W 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 G P that minimizes the sum of the weights of the violated weak constraints in G W in a prioritized way.
In this section, we provide an informal description of the CTS problem and its requirements.
The CTS problem consists of computing a schedule for chemotherapy patients. Chemotherapy treatment plans have a cyclic nature, following a schema that depends on the required treatment and each different treatment session requires different drugs to be dispensed. The input of the problem is a list of registrations, corresponding to treatment sessions for the patients, where each registration includes:
• the drugs to be dispensed, with a maximum of 3 drugs per session;
• the priority level of the registration, where 1, 2, and 3 correspond to registrations with high, medium, and low priority, respectively; and • the day before which the treatment must start, if the registration corresponds to the first session of the patient, or the number of waiting days before the subsequent session, otherwise.
Registrations range over a period of time of 14 days, where each day is composed by 8 time slots. Then, each hospital has c available chairs, each chair can be assigned to at most ntreat treatments, n nurses working in the hospital, k patients that a nurse can visit per time slot, and a maximum quantity of available drugs for each day. In our setting, c, ntreat, n, and k are fixed and set to 15, 10, 5, and 4, respectively.
The output of the problem is a schedule of registrations to time slots according to the following requirements:
• the first session treatment must be scheduled before the date reported in the registration; • the subsequent sessions must be scheduled exactly after the number of waiting days specified in the registration; • each chair can be used by only one patient for each time slot;
• if the treatment requires more than one time slots, then the patients must always use the same chair; • each nurse can assist from 1 to k patients for each time slot;
• each chair can be assigned to at most ntreat treatments;
• treatments cannot exceed the maximum quantity of drugs available for each day; • treatments must be scheduled as soon as possible, therefore it is not possible that a day has no scheduled registration and subsequent days have scheduled registrations; • since some drugs might require a long time to be prepared, treatments cannot be scheduled at the latest available time slot.
Moreover, as a further requirement, registrations with the highest priorities should be scheduled before other registrations.
Starting from the specifications in the previous section, here we present the ASP encoding, based on the input language of clingo [23], for the scheduling problem.
Data Model. The input data is specified by means of the following atoms:
• Instances of reg(REGID,PRIOR,M,DUEDATE,TID1,TID2,TID3) represent the registrations, characterized by an id (REGID), a priority score (PRIOR, we recall that 1 is the highest priority and 3 is the lowest priority), a value indicating an internal order of treatments (M, where 0 indicates the first treatment, 1 the second treatment, etc.), the date by which the treatments must be carried out (DUEDATE), the ids of treatments (TID1, TID2, TID3) that must be carried out. where ID is the identifier of the nurse and D is the day.
Moreover, we also take advantage of three constants, namely c, k, and ntreat, corresponding to the ones described in the previous section. The output is an assignment represented by atoms of the form
x(RID,DAY,TS,TID1,TID2,TID3,PRIOR,M)
where the intuitive meaning is that the registration with id RID is assigned to the day DAY and its starting time slot is TS, whereas the terms TID1, TID2, TID3, PRIOR, and M are the ones of reg(REGID,PRIOR,M,DUEDATE,TID1,TID2,TID3), described above. Encoding. The related encoding is shown in Figure 1, and is described in the following. To simplify the description, we denote as r i the rule appearing at the line i of Figure 1.
Rules r 1 and r 2 guess an assignment for the registrations to a day DAY and a time slot TS, where r 1 is used to guess the first day of the treatment and r 2 the subsequent days. Rules r 3 , r 4 , and r 5 are auxiliary rules which are used for deriving atoms of the form res(RID,DAY,H,NCHAIR,NNURSE) starting from the assignment derived in rules r 1 and r 2 . Basically, those atoms include, for each registration of a given day, all the time slots where the registration is assigned, and the number of chairs and nurses required by the registration. Then, rules r 6 and r 7 guess the chairs and the nurses that must be assigned to each selected registration. Subsequent rules, from r 8 to r 16 , are used to check that the schedule fulfills all the requirements. In particular, rules r 8 and r 9 ensure that each chair is assigned to at most one patient and each nurse can visit at most k patients for each time slot, respectively. Rule r 10 enforces that a patient has always the same chair until the treatment is not finished. Rule r 11 is used to guarantee that the number of assigned chairs does not exceed the number of available chairs, denoted with the constant c. Rules r 12 and r 13 ensure that each treatment does not exceed the allotted time expressed by instances of mss and the number of treatments assigned to a chair does not exceed the maximum number of treatments (denoted with the constant ntreat), respectively. Rule r 14 guarantees that treatments start before the last available slot of mss. Rule r 15 ensures that if a day has at least one scheduled registration, then all previous days must also have at least one scheduled registration, whereas rule r 16 is used to enforce that the maximum availability of the drugs is not exceeded for each day. Then, weak constraints from r 17 to r 19 are used to optimize the schedule of the registrations according to their priority. In particular, registrations with the highest priority must be scheduled before other registrations. Note that this optimization is considered for the first day of treatment only. Finally, weak constraint r 20 is used to schedule the treatments as soon as possible. Note that r 20 is somehow subsumed by weak constraints from r 17 to r 19 , however we find out that adding this weak constraints slightly improves the overall performance in our experiments.
In this section we report the results of an empirical analysis of the CTS problem. Data have been randomly generated using parameters inspired by real-world data. In this way we can simulate different scenarios and use them to test our encoding. The experiments were run on a AMD Ryzen 5 2600 CPU @ 3.40GHz with 7.6 GB of physical RAM. The ASP system used was clingo [23], using arguments -restart-on-model for a faster optimization and -parallel-mode 12 for parallel execution. The time limit was set to 300 seconds.
The generated benchmarks vary for the number of patients and drug availability but they all consider a 14-days calendar. Two different scenarios were considered. The first one (scenario α) is characterized by an amount of drugs that allow the system to use the available chairs in a high percentage. For the second one (scenario β), we severely reduced the number of available drugs, to test the encoding in a situation in which the drugs become a limitation for the system and then the usage of the chairs is reduced. Each scenario was tested with 10 different randomly generated inputs for each of the different groups of patients: 60, 80, and 100. The characteristics of the tests are the following:
• 2 different benchmarks, comprising a planning period of 14 working days, and different numbers of available drugs, as reported in Table 1 and in Table 2, for each group of patients; • 3 different types of drugs that are assigned to the patients following the schema reported in Table 3; • For each patient, there are 6 different registrations, each corresponding to a day of treatment, following the schema reported in Table 3, with the first one having a randomly generated priority and a due date of the treatment with a value inside a range of days based on the priority. In this way, we simulate the common situation where a manager takes a list of patients with different priorities and tries to schedule every patient as soon as possible, taking into account the priority.
The priorities of the first registration have been generated from uneven distribution of three possible values (with weights respectively of 0.20, 0.40, and 0.40 for registrations having priority 1, 2, and 3, respectively). Depending on the priority the due date of the treatment is randomly assigned from three different ranges: [1,6) for priority 1, [6,11) for priority 2, and [11,15) for priority 3, respectively. The parameters of the test have been summed up in Table 4. In particular, for each group of patients (60, 80 and, 100), we reported the mean and the standard deviation of the number of patients with priority 1, 2 and 3, respectively.
The encoding was tested on each scenario (α, i.e. drugs abundance, and β, i.e. drugs scarcity) and with each number of patients (60, 80 or 100). We summarized our results in Tables 5 and 7 for scenario α and Tables 6 and 8 for scenario β, respectively. In each of these tables we report the average for each day, calculated over 10 tests with randomly generated input, of the infusion chairs occupation and the usage of each treatment drug as a percentage over the maximum quantity that could be produced in that day. As a general observation, these results show that our solution is capable to reach a good level of chairs occupation and drugs usage, especially in the first half of the planning period. In the second half, the efficiency decreases for the simple reason that many patients have either finished their treatments or are in their later stages, which are less time and drug consuming (see Table 3). In a real-world application, a new schedule with new patients would actually be planned such that the second half of the first schedule would overlap with first half of the second schedule, thus having some slots pre-occupied and filling all spaces left empty.
Finally, we present some more detailed results achieved on one instance of scenario α. In particular, we present in Fig. 2 the occupation of a chair during the planning period, while in Fig. 3 we show the drug usage. Fig. 4 reports the day the first session of each treatment, subdivided by patient priority, was scheduled: as we can see priority 1 patients begin their treatment at the first day available, then priority 2 are obviously favoured over priority 3 patients. In Fig. 5 we show the aggregated number of patients treated per day: note that this number can significantly vary because the duration of the sessions can be very different depending on the phase of the treatment.
In this section we review related literature devoted to acknowledging some of the most interesting works published in the latest years which dealt with the CTS problem. Sevinc et al. [35] addressed the CTS problem through a two-phase approach. In the first one an adaptive negative-feedback scheduling algorithm is adopted to control the load on the system, while in the second phase two heuristics based on the 'Multiple Knapsack Problem' have been evaluated to assign patients to specific infusion seats. The overall design has been put to test at a local chemotherapy center and has yielded good results for patient waiting times, orderly execution of chemotherapy regimen and utilization of infusion chairs. Huang et al. [30] developed and implemented a model to optimize safety and efficiency in terms of staffing resource violations measured by nurse-to-patient ratios throughout the workday and at key points during treatment to decide when to schedule patients according to their visit durations. The optimization model was built using Excel Solver. Hahn-Goldberg et al. [29] addressed in partic- ular dynamic uncertainty that arises from requests for appointments that arrive in real time and uncertainty due to last minute scheduling changes through a proactive template of an expected day in the chemotherapy centre using a deterministic optimization model updated, to accommodate last minute additions and cancellations to the schedule, by a shuffling algorithm. Huggins et al. [31] presented a mixed-integer programming optimization model developed with the objective of maximizing resource utilization, while balancing human workload, in particular taking into account variability in length of treatment, increased patient demand, and resource limitations.
In this paper we have employed ASP for solving the CTS problem, and we then presented the results of an experimental analysis on instances generated in order to simulate real-world scenarios. The proposed solution and the good results confirm that ASP is a viable AI tool for solving hard scheduling problems, mainly due to the available modeling rules and constructs, and availability of efficient solvers.
Concerning future work, we are currently improving the analysis by investigating with other parameters, e.g. with k = 7, given that a range between 4 and 7 for k is often employed in papers, or with 20 and 40 patients. We also plan to to include the design, encoding and analysis of a re-scheduling solution, in case the off-line solution, as proposed in this paper, cannot be fully implemented for circumstances such as canceled registrations, and the evaluation of heuristics and optimization techniques (see, e.g., [7,27,28]) for further improving the effectiveness of our solution. Finally, we plan to experimentally confront to the alternative solutions mentioned in the related work section, assuming such solutions are publicly available and the comparison is significant, and to analyse with real data when they become available.