The problem of planning and scheduling chemotherapy treatments in oncology clinics is a complex problem, given that the solution has to satisfy (as much as possible) several requirements such as the cyclic nature of chemotherapy treatment plans, and the availability of resources, e.g. treatment time, nurses, and pharmacy quantities. At the same time, realizing a satisfying schedule is of upmost importance for obtaining the best health outcomes. In this paper we present a solution to the problem based on Answer Set Programming (ASP), that recently proved to be a consistent methodology for solving complex scheduling problems involving optimization. Results of an experimental analysis, conducted on benchmarks with realistic sizes and parameters, show that ASP is a suitable solving methodology also for this important scheduling problem.
The Chemotherapy Treatment Scheduling (CTS) [29{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 di erent types of cancer and the stage of the
disease. Moreover, treatments may have di erent 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 [
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 Arti cial Intelligence [
In this paper, we propose the rst 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 [
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. 2
Answer Set Programming (ASP) [
Syntax. The syntax of ASP is similar to the one of Prolog. Variables are strings starting with uppercase letter and constants are non-negative integers or strings starting with lowercase letters. A term is either a variable or a constant. A standard atom is an expression p(t1; : : : ; tn), where p is a predicate of arity n and t1; : : : ; tn are terms. An atom p(t1; : : : ; tn) is ground if t1; : : : ; tn are constants. A ground set is a set of pairs of the form hconsts : conji, where consts is a list of constants and conj is a conjunction of ground standard atoms. A symbolic set is a set speci ed syntactically as fT erms1 : Conj1; ; T ermst : Conjtg, where t > 0, and for all i 2 [1; t], each T ermsi is a list of terms such that jT ermsij = k > 0, and each Conji is a conjunction of standard atoms. A set term is either a symbolic set or a ground set. Intuitively, a set term fX : a(X; c); p(X); Y : b(Y; m)g stands for the union of two sets: the rst one contains the X-values making the conjunction a(X; c); p(X) true, and the second one contains the Y -values making the conjunction b(Y; m) true. An aggregate function is of the form f (S), where S is a set term, and f is an aggregate function symbol. Basically, aggregate functions map multisets of constants to a constant. The most common functions implemented in ASP systems are the following: #count , number of terms; #sum, sum of integers.
An aggregate atom is of the form f (S) T , where f (S) is an aggregate function, 2 f<; ; >; ; 6=; =g is a comparison operator, and T is a term called guard. An aggregate atom f (S) T is ground if T is a constant and S is a ground set. An atom is either a standard atom or an aggregate atom. A rule r has the following form:
a1 _ : : : _ an :{ b1; : : : ; bk; not bk+1; : : : ; not bm: where a1; : : : ; an are standard atoms, b1; : : : ; bk are atoms, bk+1; : : : ; bm are standard atoms, and n; k; m 0. A literal is either a standard atom a or its negation not a. The disjunction a1 _ : : : _ an is the head of r, while the conjunction b1; : : : ; bk; not bk+1; : : : ; not bm is its body. Rules with empty body are called facts. Rules with empty head are called constraints. A variable that appears uniquely in set terms of a rule r is said to be local in r, otherwise it is a global variable of r. An ASP program is a set of safe rules, where a rule r is safe if the following conditions hold: (i) for each global variable X of r there is a positive standard atom ` in the body of r such that X appears in `; and (ii) each local variable of r appearing in a symbolic set fTerms : Conj g also appears in a positive atom in Conj .
A weak constraint [
A standard atom, a literal, a rule, a program or a weak constraint is ground if no variables appear in it.
Semantics. Let P be an ASP program. The Herbrand universe UP and the Herbrand base BP of P are de ned as usual. The ground instantiation GP of P is the set of all the ground instances of rules of P that can be obtained by substituting variables with constants from UP .
An interpretation I for P is a subset I of BP . A ground literal ` (resp., not `) is true w.r.t. I if ` 2 I (resp., ` 62 I), and false (resp., true) otherwise. An aggregate atom is true w.r.t. I if the evaluation of its aggregate function (i.e., the result of the application of f on the multiset S) with respect to I satis es the guard; otherwise, it is false.
A ground rule r is satis ed by I if at least one atom in the head is true w.r.t. I whenever all conjuncts of the body of r are true w.r.t. I.
A model is an interpretation that satis es all rules of a program. Given a
ground program GP and an interpretation I, the reduct [
Given a program with weak constraints = hP; W i, the semantics of extends from the basic case de ned above. Thus, let G = hGP ; GW i be the instantiation of ; a constraint ! 2 GW is violated by an interpretation I if all the literals in ! are true w.r.t. I. An optimum answer set for is an answer set of GP that minimizes the sum of the weights of the violated weak constraints in GW in a prioritized way. 3
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 di erent treatment session requires di erent 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 rst 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 xed 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 rst 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 speci ed 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. 4
Starting from the speci cations in the previous section, here we present the
ASP encoding, based on the input language of clingo [
Data Model. The input data is speci ed 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 rst 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.
Instances of mss(DAY,TS) represent the available time slots for each day, e.g., mss(1,1), ..., mss(1,8) denote that 8 slots are available for the day 1, where each slot has a xed duration (30 minutes or 1 hour) depending on the scenario. Instances of type(TID, QUANT, NCHAIRS, NNURSES, D) represent for each treatment, denoted by its identi er TID, the amount of drugs (QUANT), the number of chairs (NCHAIRS), the number of nurses (NNURSES), and the duration expressed (D) required by the treatment.
Instances of drug(TID,MAX) represent for each treatment, denoted by its identi er TID, the maximum availability of the required drug for each day (MAX).
Instances of chair(ID) represent the available chairs, with its identi er ID. Instances of nurse(ID,D) represent the nurses available in a speci c day, where ID is the identi er 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 ri the rule appearing at the line i of Figure 1.
Rules r1 and r2 guess an assignment for the registrations to a day DAY and a time slot TS, where r1 is used to guess the rst day of the treatment and r2 the subsequent days. Rules r3, r4, and r5 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 r1 and r2. 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 r6 and r7 guess the chairs and the nurses that must be assigned to each selected registration. Subsequent rules, from r8 to r16, are used to check that the schedule ful lls all the requirements. In particular, rules r8 and r9 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 r10 enforces that a patient has always the same chair until the treatment is not nished. Rule r11 is used to guarantee that the number of assigned chairs does not exceed the number of available chairs, denoted with the constant c. Rules r12 and r13 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 r14 guarantees that treatments start before the last available slot of mss. Rule r15 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 r16 is used to enforce that the maximum availability of the drugs is not exceeded for each day. Then, weak constraints from r17 to r19 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 rst day of treatment only. Finally, weak constraint r20 is used to schedule the treatments as soon as possible. Note that r20 is somehow subsumed by weak constraints from r17 to r19, however we nd out that adding this weak constraints slightly improves the overall performance in our experiments. 5
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 di erent 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 [
The generated benchmarks vary for the number of patients and drug availability but they all consider a 14-days calendar. Two di erent scenarios were considered. The rst 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 di erent randomly generated inputs for each of the di erent groups of patients: 60, 80, and 100. The characteristics of the tests are the following: 2 di erent benchmarks, comprising a planning period of 14 working days, and di erent numbers of available drugs, as reported in Table 1 and in Table 2, for each group of patients; 3 di erent types of drugs that are assigned to the patients following the schema reported in Table 3; For each patient, there are 6 di erent registrations, each corresponding to a day of treatment, following the schema reported in Table 3, with the rst 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 di erent priorities and tries to schedule every patient as soon as possible, taking into account the priority.
The priorities of the rst 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 di erent 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. 5.2
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 rst half of the planning period. In the second half, the e ciency decreases for the simple reason that many patients have either nished 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 rst schedule would overlap with rst half of the second schedule, thus having some slots pre-occupied and lling 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 rst session of each treatment, subdivided by patient priority, was scheduled: as we can see priority 1 patients begin their treatment at the rst 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 signi cantly vary because the duration of the sessions can be very di erent depending on the phase of the treatment. 6
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. [
schedules with 60 (top left), 80 (top right) and 100 Fig. 5. Total number of patients treated in each day of the planning period for scenario with 60 (top left), 80 (top right) and 100 (bottom left) patients (bottom left). 7
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 con rm that ASP is a viable AI tool for solving hard scheduling problems, mainly due to the available modeling rules and constructs, and availability of e cient 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 o -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., [