The ASP methodology has been recognized to be a viable solution to many practical applications, including scheduling problems, and in particular in the healthcare domain, of high interest in this period given the COVID-19 pandemic, where ASP proved to be an e ective solution to some interesting problems. In this paper we present an overview of scheduling problems in the healthcare domain that have been successfully solved via ASP in the last two years. Starting from two "basic" problems, i.e., referred to the scheduling of operating rooms in presence of scarce resources (e.g., ICU beds) and the Nurse Scheduling problem, we show how we have improved such solutions, and mention further problems we have dealt with, including the Chemotherapy Scheduling problem. On top of all problems, we are working on providing explainability features, of utmost importance in this eld, that for the moment are being instantiated on a single problem.
Answer Set Programming (ASP) [
Recently, ASP has been also applied to solving scheduling problems, and in particular problems in the healthcare domain, of high interest in this period given the COVID-19 pandemic.
In this paper we present an overview of scheduling problems in the
healthcare domain that have been successfully solved via ASP in the last two years
(mainly) in Genova, and from this year in the context of the Scheduling and
Resource Management topic of the CLAIRE COVID-19 Task Force4. The
starting point are two basic problems that we have overviewed in [
The paper is structured as follows. Section 2 introduces our starting problems, while Section 3 describes the improvements we made over these problems. Then, Section 4.2 outlines further problems we have solved, and Section 5 concludes the paper and envisages directions for future research. 2
In this section we brie y describe our two starting problems, outlined in [
The Nurse Scheduling problem (NSP) consists of generating a schedule of
working and rest days for nurses working in hospital units. The schedule should
determine the shift assignments of nurses for a predetermined window of time,
and must satisfy requirements imposed by the Rules of Procedure of hospitals.
Our NSP de nition contains requirements from the International Nurse
Rostering Competition [
In particular, three di erent types of requirements have been considered, namely hospital, nurses, and balance requirements.
Hospital requirements include the di erent types of shifts that can be considered, namely morning (7 A.M. { 2 P.M.), afternoon (2 P.M. { 9 P.M.), and night 4 https://covid19.claire-ai.org/. (9 P.M. { 7 A.M.). In order to ensure the best assistance program for patients, each shift is associated with a minimum and a maximum number of nurses that must be present in the hospital.
Nurses requirements are expressed to guarantee a fair workload between nurses. Therefore, a limit on the minimum and maximum number of working hours per year is imposed. Moreover, additional requirements are imposed to ensure an adequate rest period to each nurse: (a) nurses are legally guaranteed 30 days of paid vacation, (b) the starting time of a shift must be at least 24 hours later than the starting time of the previous shift, and (c) each nurse has at least two rest days each fourteen days window. In addition, after two consecutive working nights there is one special rest day which is not included in the rest days of (c).
Finally, balance requirements ensure that the number of times a nurse can be assigned to morning, afternoon and night shifts is xed.
Solutions for this problem can be found in [
In the following we will call a registration each single planned surgery inserted in the hospital waiting list. A registration is associated to a patient and is characterized by a predicted surgery duration and length of stay (LOS) in the hospital ward, it is assigned to a specialty (e.g. General Surgery, Orthopedics, etc.) and has a priority score, which takes into account two di erent factors: the surgical procedure urgency and the time already spent in the waiting list. We have classi ed each registration according to three di erent priority categories, namely P1, P2 and P3. The rst one gathers either very urgent registrations or the ones that have been longer in the waiting list; these registrations must be assigned to the OR schedule. The P2 registrations should be assigned but can be postponed in case of necessity, while the last category collects the registrations that may be used to ll any possible hole left in the schedule.
The schedule is organized in a series of OR time blocks, uniquely identi ed by the OR id and the time and date when the block is scheduled. The number and distribution of the OR blocks available for each specialty during the whole planning period is given by the cyclic timetable of the hospital, referred to as the Master Surgical Schedule (MSS) and set beforehand by the hospital management.
The overall goal of our formulation of the ORS problem is to assign the maximum number of registrations, subject to the following constraints: each registration assigned to a OR block must belong to the same specialty associated to the block, each registration must be assigned to a single block and to a bed of the specialty associated to the block by the MSS for all the LOS, the sum of the surgery durations of the registrations assigned to a OR block must not exceed the length of the block itself, the registrations belonging to the priority category P1 must all be assigned, while the number of unassigned registrations belonging to the other categories must be minimized, prioritizing the P2 ones.
3
In this section we will describe, in two subsections, the improvements that have been made, or are currently undertaken, to the problems outlined in Section 2 in the last couple of years. 3.1
Employee scheduling problem. The NSP has been generalized to consider every employee type needed to operate an hospital or a clinic, such as kitchen sta , cleaning sta , nurses and unlicensed assistive personnel. All sta should be appropriately allocated to provide high quality and e cient health services. E ective employee scheduling considers factors such as patient needs, sta needs, organisational needs, the workforce and skills required to deliver services, and workforce availability.
The automatically generated sta schedule must take into consideration employees working restrictions, the required skill-mix, safe sta ng hours, employees agreed clinical unavailability and, when feasible, sta preferences and personalised working patterns. In particular, according to the constraints we considered, each employee: is entitled to one day o every N days (where N is customizable for each employee type), can only be quali ed to perform certain shifts (e.g., only in the morning and afternoon but not at night), cannot work more than two consecutive night shifts, after each night shift, he/she can be assigned either another night shift or a rest, can express preferences on the shifts to be assigned (e.g., an operator can be quali ed for all shifts but would prefer to avoid the nights), can request holidays, that may be expressed either as preferences, with no guarantee that the requested dates are fully respected, or as constraints. In order to cover the situations where the employees of more than one facility needs to be scheduled, and some of these employees can be moved between di erent facilities depending on their daily needs, our solution supports a two-phase scheduling procedure. The rst phase of scheduling deals with the allocation of shifts of employees working permanently in a single structure, covering one month (but several months can be scheduled in sequence). Typically not all shifts are expected to be covered at this stage. In the second phase, the shifts left uncovered in the rst phase are assigned to the most mobile operators, who can move from facility to facility as required. For each facility the classic shifts in the morning, afternoon and night are considered, with some variations based on the di erent possible contracts.
Rescheduling procedure for NSP. The Nurse Rescheduling Problem (NRP) addresses situations where an already computed schedule is not usable because of sudden absences of some nurses. Nurses are following a previously computed schedule, and some of them report impossibility to work on some future days, for example because of health problems or personal issues. The previously computed schedule has to be changed starting from a future day that must not follow any reported absence.
The new schedule needs to satisfy all requirements of the NSP with the exception that any absence due to health problems must not be rescheduled. Additionally, the new schedule minimizes the di erences with the previous schedule, and such a minimization has priority over any other optimality NSP requirements.
A solution for the NRP can be found in Section 6 of [
Solution to the MSS problem. In Section 2.2 we considered the MSS as set beforehand by the hospital management, so among the inputs of the problem and encoding. However, one may want to have the control over it (the hospital management) or to have the possibility to tune and modify it. For these reasons, we have de ned an encoding for computing the MSS. Starting from the set of available ORs, the available sessions and their durations, the specialties and a planning horizon, we have de ned an encoding for computing a MSS for that planning horizon. The ASP encoding devoted to the MSS computation can be uni ed to the ORS encoding in a modular way, given that the output (predicate) of the MSS encoding has been designed for corresponding to the input predicate of the ORS encoding.
ORS with ward and ICU beds. The ORS problem is extended with the task of assigning maximum patients to operating rooms, taking into account di erent specialties, surgery durations, and the availability of beds for the entire length of stay (LOS) both in the Intensive Care Unit (ICU) and in the specialty wards. Given that patients may have priorities, the solution has to nd an accommodation for the patients with highest priorities, and then to the other with lower priorities, if space is still available, at the same time taking into proper account beds availability.
The overall goal of the ORS with beds management is to assign the maximum number of registrations to the ORs, taking explicitly into consideration the availability of beds in the wards and in the ICU. We have ensured that a particular registration can only be assigned to an OR only if there is an available bed for the patient in the ward for the entire LOS.
In our model, a patient's LOS has been subdivided in the following phases: a LOS in the ward before surgery: It is possible that a patient is admitted to the ward a day (or more) before the surgery takes place; the LOS after surgery, It considers the duration of patient stay after surgery which can be further subdivided into the ICU LOS (duration of stay in ICU) and the following ward LOS (duration of stay in the specialty ward). Following two requirements related to the beds management are considered: ward bed requirement. Here we consider a situation where each specialty is linked to a ward with a variable number of available beds exclusively dedicated to the patients associated to that specialty.
ICU bed requirement. Here we consider ICU as a particular type of ward that is accessible to patients from any specialty. However, only a small percentage of patients is expected to need to stay in the ICU.
ORS with PACU beds. Details on the treatment of beds have been explained in the previous paragraph. In this paragraph we introduce another type of beds we have analyzed. Similarly as above, we have also extended the ORS encoding in order to take into account also Post Anesthetic Care Unit (PACU) beds. After a surgery, (fortunately) not all patients need an ICU bed, but a (vast) majority need a PACU bed, where they can recover from the anesthetic. Patients that need a bed go either in PACU or in ICU. These PACU beds are separated to those of the ward and the ICU, and the characteristic of their usage is that they are occupied by a patients for a limited (in minutes) amount of time, often related to a percentage of the surgery duration. The requirements and constraints entailed by the presence of PACU are similar to those of ICU, and have been added to the previous encoding in a modular way, while ensuring that a patient may go in PACU or ICU alternatively.
Rescheduling procedure for ORS. Similarly to the NSP problem, but for slightly di erent reasons, it is important to design a rescheduling procedure also in case of the ORS problem. Also in this case, the rescheduling procedure is applied to a previously planned schedule, i.e., we start from an already created schedule that could not be executed fully till the end due to some reasons, e.g., some patients could not be operated in their assigned slots or the patients may delete their registration. In such situation all those postponed registrations (or surgeries) must be reallocated to one of the next slots in the remaining part of the original planning period. Once planned, a speciality schedule does not in uence other specialties so it makes sense to reschedule one specialty at a time. Since we already have the initial schedule for the planning period, we assume that in day 2 (out of a planning period of 5 days) a number of registrations from a specialty had to be postponed to a next day. In order to insert the postponed registrations in the new schedule we have to make sure that the start of the schedule leaves enough available OR time by automatically dropping the necessary registrations from the old schedule. The encoding for the rescheduling procedure has been de ned starting from the ORS encoding, substituting the old schedule (considered now as input of the problem) with the new to be computed, and modularly adding the necessary rules for representing the wanted rescheduling behavior. 4
In this section we present, in two separate subsections, a new scheduling problem we have solved with ASP, and explainability features we are adding to one of our solutions. 4.1
The Chemotherapy Treatment Scheduling (CTS) problem consists of generating a calendar of treatment following a chemotherapy regimen for every patient. We call registration every single treatment inserted on the waiting list. A registration is associated with a patient and a sequential number, since every patient will follow a chemotherapy regimen and the sequential number represents the order to follow. The registration is characterized by the drugs that the patient needs, the days to wait for the next treatment, i.e., the registration associated with the same patient and the next sequential number, and has a priority score with values from 1 to 3.
Each drug has a di erent time of administration, represented as time slot in our solution, and dose. Every treatment needs a nurse and a chair; the number of nurses, chairs, and, the times slot in which the treatments can take place are set beforehand according to the hospital or clinic availability.
The goal of our solution to the CTS problem is to schedule all registrations following some constraints: each treatment must be separated from the previous treatment of the same person by the number of days indicated in the registration; each registration must be assigned to an available chair and to an available nurse; each patient to which more drugs are assigned in a treatment has to stay in the same chair during all the time of the treatment; the sum of a drug used during a day must not exceed the available quantity of that drug; each patient with a priority 1 must have the rst treatment before a speci c day n, such as the one with priority 2 that must have the rst treatment before a speci c day n + m and the one with priority 3 must have the rst treatment before the end of the planning days considered.
A solution based on ASP can be found in [
In order to isolate those elements we analyze the registrations in the waiting list with the highest priority, since the lower priority registrations can not lead to unsatis ability, the availability of the beds and the OR time blocks. Once the UIEs are isolated, it is possible to track the inconsistencies that led to the unsatis ability, e.g., if it is found that the issue is due to the number of beds of a certain speciality we may state that the issue is generated because the number of available beds in that speciality is too low or the registrations for that speciality is too high. Once the UIEs and their causes have been identi ed it is possible to proceed with the explanation in human language of the causes of the unsatis ability. Moreover, we use the gathered data to isolate elements of interest (EI) that are used as suggestions for the user to remove the UIE; e.g., if the issue is due to the lack of beds in a certain speciality, we can give as EI the list of all the registrations with high priority belonging to that speciality. Furthermore, it is given to the user the possibility to remove from the input set any EI making, the user an integral part of the error identi cation process. Thus, the user perceive the explanation as more reliable since he took part to the identi cation process. 5
In this document we have overviewed the extended and new contributions to solvoling scheduling problems in the healthcare domain we carried out in the last couple of years mainly in Genova, by employing the ASP methodology. As a result, we can say that in all studied problems up to now ASP led to satisfying solutions, both on the scienti c and application view-points.
In the future we would like to continue the e ort in the following four
directions: (i) add new problems, e.g., at the moment we are working on planning
and scheduling the pre-surgery phase, (ii) deepen the integration of the solutions
for the various problems in order to be able to solve bigger and more concrete
problems, (iii) confront our solutions to others available in the state of the art,
whenever possible and meaningful, and (iv) turn our ASP encodings into usable
applications, by allowing, e.g., to set parameters and run the encoding via a web
interface, as we have already done for the basic ORS problem [