Nurse (Re)scheduling via answer set programming 1

Abstract

The goal of the Nurse Scheduling Problem is to find an assignment of nurses to shifts according to specific requirements. Frequently, a computed schedule may become not usable because of sudden absences of some nurses. In this cases, Nurse Rescheduling amounts to the computation of a new schedule, which has to satisfy the original requirements and the new absences. Additionally, a good solution to the Nurse Rescheduling Problem must be as similar as possible to the original schedule, which practically means that the number of changes has to be minimized. This paper focuses on the requirements specified by an Italian hospital, and recently addressed by an approach based on Answer Set Programming (ASP). Even if promising results have been obtained with ASP, the original encoding presents some intrinsic weaknesses, which are identified and eventually circumvented in this paper. The new encoding is designed by taking into account both intrinsic properties of Nurse Scheduling and internal details of ASP solvers, such as cardinality and weight constraint propagators. The performance gain of clingo and wasp is empirically verified on instances from ASP literature. As an additional contribution, the performance of clingo and wasp is compared to other declarative frameworks, namely SAT and ILP; the best performance is obtained by clingo running the new ASP encoding. The advanced ASP encodings are then extended to solve Nurse Rescheduling, and an empirical evaluation is conducted with clingo and wasp.

1 Introduction

The Nurse Scheduling Problem (NSP) consists of generating a schedule of working and rest days for nurses employed 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. A proper solution to the NSP is crucial to guarantee the high level of quality of health care, to improve the degree of satisfaction of nurses, and the recruitment of qualified personnel. Given its practical relevance for the quality of hospital structures, NSP has been widely studied in the literature, and several variants have been considered [17, 22]. Such variants are usually grouped according to several factors, as the planning period, the different types of shifts considered, and requirements on the preferences of hospitals and nurses.

The NSP variant considered in this paper concerns a planning period fixed to one year with three different types of shifts (morning, afternoon and night) and requirements on nurses and hospitals provided by an Italian hospital. Specifically, such requirements concern restrictions to the number of working hours per year and to the number of times nurses are assigned to a specific shift.

However, in hospital units that operate 24 hours a day, 7 days for week, it is frequent that one planned schedule cannot be fulfilled due to sudden absences of nurses. The Nurse Rescheduling Problem (NRP), instead, occurs when one or more nurses notify their unavailability to attend one or more scheduled shifts, and aims at finding a new schedule taking into such unavailability, at the same time minimizing the differences with a previous computed schedule. It is important to emphasize here that rescheduling is usually independent from the quality of the schedule, and it is usually due to unpredictable events, e.g. illness of one or more nurses. When a sudden absence occurs, the planned schedule must be modified to ensure a good quality of the health care service. On the other hand, employees usually tend to organize their free time, thus modifications of a previously announced schedule may create personal inconveniences and may not be very well accepted by the workforce. Therefore, typically the schedule cannot be completely rebuilt from scratch. Instead, the goal should be to determine a new feasible scheduling minimizing the number of shift changes with respect to the previous schedule. Moreover, as argued in [23], rescheduling is a quite frequent activity and often requires reactive and immediate decisions. Thus, any approach aiming at solving the NRP should consider this additional requirement of being efficiently computed.

Complex combinatorial problems, such as NSP and NRP, are usually the target for the application of logic formalisms such as Answer Set Programming (ASP) [16]. Its simple syntax [18] and the intuitive semantics [34], combined with the availability of robust implementations (see, e.g. [4, 30]), make ASP an ideal candidate for addressing such problems. Indeed, ASP has been already successfully used for solving hard combinatorial and application problems in several research areas, including Artificial Intelligence [11, 25], Bioinformatics [27 , 39], Hydroinformatics [28], Databases [42], and also employed in industrial applications [2, 26]. Recently, the aforementioned variant of NSP has been modeled by means of an ASP encoding presented in [24]. The encoding resulted to be natural and intuitive, in the sense that it was designed by applying the standard modeling methodology, yet obtaining reasonable performance on solving the analyzed instances.

On the other hand, it turned out that the encoding presented in [24] shows some limitations and intrinsic weaknesses, mainly due to aggregates [5], i.e. operations on multi-sets of weighted literals that evaluate to some value. Indeed, the encoding exploits some aggregates with a quite large number of literals and few different weights, resulting to be counterproductive for the performance of modern ASP solvers [32], since they decrease their propagation power.

In this paper, we circumvented such limitations by taking into account only combinations of values that can lead to admissible schedules. Interestingly, the new encoding did not require to significantly sacrifice readability, as it remains intuitive and clear. Moreover, the new encoding is used as basis for an ASP-based solution for NRP.

The performance of the ASP solvers executed on the new encoding for NSP has been empirically evaluated on the same data and settings used in [24], showing a clear improvement in performance of state-of-the-art ASP systems clingo [30] and wasp [6]. As an additional contribution, the ASP-based approaches have been compared to other declarative frameworks, namely Propositional Logic Satisfiability (SAT) [9] and Integer Linear Programming (ILP) [35]. Results show that clingo and wasp executed on the new encoding outperform their counterparts executed on the original encoding. In particular, clingo executed on the new encoding is considerably faster than all other tested approaches.

The encoding for NRP has been tested by considering one previous schedule, and simulating sudden absences for nurses. Results on 150 random scenarios show that state-of-the-art ASP systems clingo and wasp can compute a solution for the NRP in few seconds.

The contributions of the paper can be summarized as follows:

We formalize the variant of NSP considered in [24] (Section 4.1).

We formalize the variant of NRP based on the variant of NSP considered in this paper (Section 4.2).

We propose a new ASP-based solution to the NSP overcoming some limitations of the encoding presented in [24] (Section 5.2).

We propose a new ASP-based solution to NRP (Section 6).

We present an experimental analysis comparing the basic and advanced ASP solutions as well as with SAT and ILP based solutions (Section 7.1). Results show a significant improvement of the performance of ASP solvers and, specifically, clingo performs better than all other alternatives.

We present an evaluation of rescheduling, which simulates sudden absences of nurses (Section 7.2). Results show that ASP systems can compute a solution for NRP in few seconds in our setting.

2 Preliminaries

We assume that the reader is familiar with basic knowledges on Answer Set Programming and ASP-Core-2 input language specification [18]. Minimal notions are anyhow introduced in this section in order to ease the understanding of the encodings presented in Sections 5–6.

The evaluation of an ASP program is usually made in two steps, called grounding and solving. First, the ASP program with variables is evaluated by the grounder, which is responsible to produce its variable-free (propositional) counterpart.

Example 2.1. (Grounding). Consider as example the following rules:

The grounding of p consists of 60 (i.e. 6 × 10) propositional rules of the following form:

Intuitively, choice rulep₁ enforces that exactly one atom between out(1,1,1), out(1,2,1) and out(1,3,1) must be true in an answer set. Similar considerations hold for other ground rules generated.

The grounding of c consists of 30 (i.e. 10 × 3) (integrity) constraints of the following form:

As example, constraint c₁ enforces that the count of true atoms among out(1,1,1), out(2,1,1), out(3,1,1), out(4,1,1), out(5,1,1), and out(6,1,1) must be greater than or equal to 2.

Finally, the grounding of w consists of 180 (i.e. 6 × 10 × 3) weak constraints of the following form:

Weak constraints are used to express conditions that should be preferably satisfied. Thus, they may be violated. The semantics of programs with weak constraints imposes a minimization on violations. For instance, the informal meaning of w₁ is “out(1,1,1) should preferably be false”. In addition, each weak constraint is associated to a weight and to a priority level (defined by the syntax [weight@level]). Optimal answer sets are those minimizing the sum of weights of the violated weak constraints at the highest priority level and, among them, those which minimize the sum of weights of the violated weak constraints in the next lower level. The process is applied recursively until the lowest level is reached.⊲

The propositional program produced by the grounder is evaluated by the solver, whose role is to produce an answer set. Modern ASP solvers implement the algorithm CDCL [32], which is based on the pattern choose-propagate-learn. Intuitively, the idea is to build an answer set step-by-step by starting from an empty interpretation, i.e. all atoms are initially undefined. Then, the algorithm heuristically chooses an undefined atom to be true in the answer set, and the deterministic consequences of this choice are propagated, i.e. new atoms are derived true or false in the answer set candidate. The propagation may lead to a conflict, i.e. an atom is true and false at the same time. In this case, the conflict is analyzed and a new constraint is added to the propositional program (learning). The conflict is then repaired, i.e. choices leading to the conflict are retracted and a new undefined atom is heuristically selected. The algorithm then iterates until no undefined atoms are left, i.e. an answer set is produced, or the incoherence of the propositional program is proved, i.e. no answer sets are admitted.

Example 2.2. (Propagation) Consider the propositional rule p₁ reported in Example 2.1 and assume that atoms out(1,1,1) and out(1,1,2) have been heuristically assigned to false. Then, the solver derives out(1,1,3) to true because it is the only way to satisfy rule p₁. ⊲

In presence of weak constraints, modern solvers apply a strategy based on the so-called unsatisfiable cores analysis. In particular, such an algorithm starts by searching an answer set satisfying all weak constraints, which would be therefore optimal. On the other hand, if such an answer set does not exist, a subset of the weak constraints that cannot be jointly satisfied is identified. Such a set is called unsatisfiable core, and essentially evidences that any optimal answer set must sacrifice at least one of the desiderata expressed by the weak constraints. Therefore, the program is modified by replacing the weak constraints in the unsatisfiable core with new weak constraints that essentially express a preference for answer sets satisfying all but one of the original weak constraints, and anyhow the largest number of them, so that the process can be reiterated.

3 Problems description

We start this section by providing a description of the Nurse Scheduling Problem as posed by an Italian hospital (Section 3.1). In the description we identify elements that allow to reuse the proposed solution even if part of the specification given by the hospital will change. After that, we describe the Nurse Rescheduling Problem as posed by the same Italian hospital (Section 3.2).

3.1 Nurse scheduling problem

NSP amounts to the totalization of partial schedules assigning nurses to working and rest days over a predetermined period of time, which is fixed to one year in this paper. Usually, partial schedules to be totalized involve few data concerning already authorized vacations. Admissible schedules must satisfy a set of requirements dictated by the rules of the hospital units. In the following, we report the requirements specified by an Italian hospital.

Hospital requirements. For every working day, nurses can be assigned to exactly one of the following shifts: morning (7 A.M. – 2 P.M.), afternoon (2 P.M. – 9 P.M.), night (9 P.M. – 7 A.M.). Thus, the morning and the afternoon shifts last 7 hours, whereas the night shift lasts 10 hours. In order to ensure the best assistance program for patients, the number of nurses in every shift x ∈ {morning, afternoon, night} must range from $x_{\min}^{nurse}$ to $x_{\max}^{nurse}$ .

Nurses requirements. In order to guarantee a fair workload, each nurse must work a number of hours ranging from work_min to work_max. Additional requirements are also 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 ordinary rest days for every window of fourteen days. In addition, nurses working on two consecutive nights deserve one special rest day in addition to the ordinary rest days.

Balance requirements. The number of morning, afternoon and night shifts assigned to every nurse should range over a set of acceptable values, that is, from $x_{\min}^{day}$ to $x_{\max}^{day}$ for each x ∈ {morning, afternoon, night}.

Optimal balance requirements/ In addition to the above requirements, the hospital reported some further requirements to guarantee a balance in the assignment of shifts. Indeed, the number of morning, afternoon and night shifts assigned to every nurse should be preferably fixed to some desired values, that is, x^day for each x ∈ {morning, afternoon, night}.

3.2 Nurse rescheduling problem

NRP addresses situations where an already computed schedule is not usable because of sudden absences of some nurses. Stated differently, 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. In such cases, the previously computed schedule has to be changed starting from a future day that must not follow any reported absence. The new schedule must clearly satisfy all requirements described in Section 3.1, with the exception that any absence due to health problems must not be rescheduled. Additionally, the new schedule must minimize the differences with the previous schedule, and such a minimization has priority over any other optimality requirements.

4 Problems formalization

The computational problems described in the previous section, namely the Nurse Scheduling Problem and the Nurse Rescheduling Problem, are formalized in Section 4.1 and 4.2, respectively. The formalization takes into account all parameters identified in the previous section, which are properly represented as part of the input.

4.1 Nurse scheduling problem

According to the requirements described in Section 3.1, here we define the decisional problem NSP^d, and the optimization problem NSP^o (which also takes into account the optimal balance requirements). To ease the reading, formulas are reported in Fig. 1.

Fig. 1

Formulas involved in the Nurse (Re)Scheduling Problems.

Let us fix a set S = S^w ∪ {special - rest, rest, vacation} of shifts, where S^w = {morning, afternoon, night} is the set of working shifts. Let us also fix natural numbers work_min, work_max, and $x_{\min}^{nurse}$ , $x_{\max}^{nurse}$ , $x_{\min}^{day}$ , and $x_{\max}^{day}$ for x ∈ S^w, imposing bounds for working hours and nurses per shift.

Hence, given a set N of nurses, and a partial schedule s′ of the form (1), NSP^d amounts at establishing the existence of a schedule s of the form (2) extending s′ and satisfying (3)–(9); NSP^o amounts at computing a schedule s of the form (2) satisfying (3)–(9), and minimizing (10).

4.2 Nurse rescheduling problem

According to the requirements described in Section 3.2, here we define two optimization problems, namely NRP^d and NRP^o, where the second also takes into account the optimal balance requirements.

In addition to sets and natural numbers fixed in the previous section, let us fix a set S^p = {health - problem, personal - problem} of shifts to report impossibility for a nurse to work in a day, and a set S^hp = {x^hp ∣ x ∈ S^w} of working shifts used to keep track of absences due to health problems.

Given a set N of nurses, a (previously computed) schedule s^pre of the form (11), a partial schedule s^req of the form (12) reporting problems, and a day start - date ∈ [1 . .365], NRP^d amounts at computing a new schedule s^new of the form (13) satisfying (3), (5)–(9), (14)–(18), and minimizing (19); NRP^o amounts at computing a new schedule s^new of the form (13) satisfying (3), (5)–(9), (14)–(18), and minimizing (19) and (10), in this order, that is, (19) is minimized first, and ties are possibly broken by minimizing (10).

5 Nurse scheduling via ASP

In this section, after recalling an existing encoding from the literature [24] (Section 5.1), we present the new advanced encoding (Section 5.2).

5.1 Existing encoding

Instances of NSP^d and NSP^o are represented by means of ASP facts and constants. Specifically, the interval [1 . .365] of days is encoded by facts of the form day(d), for all d ∈ [1 . .365], and the number of days is fixed by the fact days(365). The nurses are encoded by facts of the form nurse(n), for all n ∈ N. Available shifts are encoded by facts of the form shift(id_x,x,h), where id_x ∈ [1 . .6] is a numerical identifier of the shift x ∈ {morning, afternoon, night, special - rest, rest, vacation}, and h is the number of working hours associated to the shift. Natural numbers $x_{\min}^{nurse}, x_{\max}^{nurse}$ for x ∈ {morning, afternoon, night} are represented by facts of the form nurseLimits(id_x, $x_{\min}^{nurse}$ , $x_{\max}^{nurse}$ ), where id_x is the identifier of the shift x. Natural numbers $x^{day}, x_{\min}^{day}, x_{\max}^{day}$ for x ∈ {morning, afternoon, night} are represented by dayLimits(id_x, x^day, $x_{\min}^{day}$ , $x_{\max}^{day}$ ), while numbers work_min and work_max are represented by instances of workLimits(work_min, work_max). Hence, according to the specification given by the hospital, the following facts and constants are considered in our setting:

The computed schedule is encoded by atoms of the form assign(n, x, d), representing that nurse n is assigned shift x on day d, that is, s (n, d) = x. The same predicate assign is used to specify the partial schedule s′ in input.

The ASP encoding introduced in [24] is reported in Fig. 2. It implements the Guess&Check programming methodology: Choice rule r₁ is used to guess the schedule s : N × [1 . .365] → [1 . .6] extending s′ and assigning each day of each nurse to exactly one shift, and rules r₂–r₁₃ are used to discard schedules not satisfying some of the desired requirements. Specifically, hospital requirements, formalized as property (3), are enforced by the integrity constraints r₂ and r₃, which filter out assignments exceeding the limits. Regarding nurse requirements, property (4) is enforced by integrity constraints r₄ and r₅, property (5) by integrity constraint r₆, property (6) by integrity constraint r₇, property (7) by integrity constraint r₈, and property (8) by integrity constraint r₉–r₁₁. Note that r₇ takes advantage of the numerical identifiers associated with shifts, and in particular by the fact that morning has id 1, afternoon has id 2, and night has id 3. Concerning balance requirements, formalized as property (9), they are enforced by integrity constraints r₁₂ and r₁₃. Rules r₁–r₁₃ encode NSP^d, while for NSP^o we also need weak constraint r₁₄: It assigns a cost to each admissible schedule measured according to function (10). Optimum schedules are those minimizing such a cost.

Fig. 2

ASP encoding introduced in [24] for NSP^o (and for NSP^d if r₁₄ is removed).

5.2 Advanced encoding

The aim of this section is to introduce a new encoding, shown in Fig. 3, which improves the encoding reported in the previous section. First of all, it has to be noted that many constraints of the encoding in Fig. 2 only involve assignments to working shifts, that is, morning, afternoon and night. The Guess part of the encoding (i.e. rule r₁) can thus be replaced by two different choice rules, $r_{1 a}^{'}$ and $r_{1 b}^{'}$ , where $r_{1 a}^{'}$ guesses among one of the working shifts or otherwise marks nurses as not working, and $r_{1 b}^{'}$ eventually guesses among rest, special-rest and vacation for each nurse marked as not working. To achieve such a behavior, an additional meta-shift is added to the set of facts, namely shift(7,notworking,0).

Fig. 3

Advanced ASP encoding for NSP^o (and for NSP^d if $r_{14}^{'}$ is removed).

A second improvement is obtained by combining the knowledge represented by (4) and (9) with some observations on how rules r₄ and r₅ are evaluated. In fact, during the solving phase, rules obtained by instantiating r₄ and r₅ comprise aggregates with relatively large aggregation sets and few different weights. Specifically to our setting, where morning and afternoon shifts are fixed to 7 hours, and night shifts to 10 hours, each aggregation set contains 365 elements with weight 7, and 365 elements with weight 10. It turns out that several schedules result into exactly the same sum value. The question is now how many of these schedules actually satisfy both (4) and (9). Restricting to the specification given by the hospital, that is, ${morning}_{\min}^{day} = {afternoon}_{\min}^{day} = 74$ , ${morning}_{\max}^{day} = {afternoon}_{\max}^{day} = 82$ , ${night}_{\min}^{day} = 58$ , and ${night}_{\max}^{day} = 61$ , the possible sum values are those reported in Table 1, where we also highlight admissible values in the interval [work_min . . work_max] = [1687 . .1692]. The new encoding therefore determines the admissible pairs of the form (N, M + A), where M, A, N are the number of morning, afternoon and nights assigned to a given nurse, by means of rule $r_{15}^{'}$ . These pairs are then used to check whether the assignment of working shifts is valid for each nurse by means of rules $r_{4}^{'}$ and $r_{5}^{'}$ .

Table 1

Number of working hours assigned to nurse n, that is, 7 · (M + A) +10 · N, where M = | {d ∈ [1 . .365] : s (n, d) = morning} |, A = | {d ∈ [1 . .365] : s (n, d) = afternoon} |, and N = | {d ∈ [1 . .365] : s (n, d) = night} |. Admissible values, that is, those in the interval [1687 . .1692], are emphasized in bold

N	M + A
	148	149	150	151	152	153	154	155	156	157	158	159	160	161	162	163	164
58	1616	1623	1630	1637	1644	1651	1658	1665	1672	1679	1686	1693	1700	1707	1714	1721	1728
59	1626	1633	1640	1647	1654	1661	1668	1675	1682	1689	1696	1703	1710	1717	1724	1731	1738
60	1636	1643	1650	1657	1664	1671	1678	1685	1692	1699	1706	1713	1720	1727	1734	1741	1748
61	1646	1653	1660	1667	1674	1681	1688	1695	1702	1709	1716	1723	1730	1737	1744	1751	1758

Actually, rules $r_{4}^{'}$ and $r_{5}^{'}$ take advantage from a third improvement of the advanced encoding. The number of morning, afternoon and night shifts that can be assigned to a nurse must adhere to (9), and are therefore limited to a few different values. The possible values of these aggregations are therefore encoded by means of atoms of the form countGE(x, n, v), being true whenever $| {days}_{x}^{n} | \geq v$ , where ${days}_{x}^{n} : = {d \in [1 . . 365] : s (n, d) = x}$ . It turns out that any answer set satisfies the following property: For each shift x and for each nurse n, there is exactly one value v such that countGE(x, n, v), notcountGE(x, n, v + 1) is true. In the advanced encoding, predicate countGE is defined by rule $r_{17}^{'}$ . Moreover, rule $r_{18}^{'}$ is used to enforce truth of countGE(x, n, v - 1) whenever countGE(x, n, v) is true; it is not required for correctness, but convenient to prune the search space in case countGE(x, n, v) is assigned to true during the computation even if $| {days}_{x}^{n} | \geq v$ does not yet hold (for example, in case countGE(x, n, v) is selected as a branching literal). In addition, since rules r₁₂–r₁₄ aggregate on sets ${days}_{x}^{n}$ for x ∈ {morning, afternoon, night}, it is convenient to rewrite these rules in terms of predicate countGE, hence obtaining rules $r_{12}^{'}$ – $r_{14}^{'}$ .

In the previous optimization, note that conjunction countGE(x, n, v), not countGE(x, n, v + 1) in rule $r_{4}^{'}$ represents the aggregate #count{D: assign(n,x,D)} = v. A predicate countEQ has not been used because predicate countGE is also used in rules $r_{12}^{'}$ and $r_{13}^{'}$ , where the encoded aggregates are respectively #count{D: assign(n,x,D)} ≤ v_min, and #count{D: assign(n,x,D)} ≥v_max. Moreover, the knowledge encoded by predicate countGE allows for the introduction of rule $r_{18}^{'}$ , which as already explained further prunes the search space; such a rule is similar to the order encoding used by SMT solvers to handle integer constants [1].

Finally, a further improvement is obtained by checking the number of nonworking days assigned to each nurse. For the specification given by the hospital it must range between 149 and 150, and in general the admitted range can be determined by rule $r_{16}^{'}$ . The check itself is then performed by rules $r_{12}^{'}$ and $r_{13}^{'}$ (for X being 7). Note that also this last check is not required to guarantee correctness of the encoding, but instead to further prune the search space.

6 Nurse rescheduling via ASP

The aim of this section is to introduce an encoding, shown on Fig. 4, for updating a given schedule due to a sudden absence of one or more nurses. In particular, the absence of nurses is encoded by atoms of the form unavailable(n, d₁, d₂, t), representing that nurse n is absent from the day d₁ to day d₂ (d₁ ≤ d₂) due to reason t, where t can be health _ problem or personal _ problem. A solution of NSP^d (NSP^o), i.e. the schedule to update, is represented by atoms of the form previous_assign(n, x, d), representing that nurse n was assigned shift x on day d.

Fig. 4

ASP encoding for rescheduling NRP^o (and for NRP^d if $r_{14}^{'}$ is removed).

The idea is to compute a new schedule, taking into account the unavailability of some nurses, such that differences with the previous schedule are minimized. To this end, rules s₂ and s₃ are used to compute the days for which the schedule of an unavailable nurse must be changed, corresponding to all working days between the range of unavailability provided by the nurse. Schedules for the days before starting date are not changed (rule s₄). Then, nurses that are absent due to health problems cannot be assigned to other shifts (rules s₅–s₇), whereas nurses that are absent for personal problems are assigned to the shift rest (rules s₈ and s₉). The differences between the new schedule and the previous one are minimized by means of the weak constraint s₁₀. The correctness of the new schedule is then checked using a slight different variant of the encoding reported in Fig. 3, where the only differences are in rule $r_{1 a}^{'}$ , $r_{1 b}^{'}$ , and $r_{17}^{'}$ , which are substituted with $r_{1 a}^{″}$ , $r_{1 b}^{″}$ , and $r_{17}^{″}$ . The new version takes also into account the days in which a nurse is unavailable due to health problems.

7 Empirical evaluation

In this section the results of the empirical evaluation are reported. The experiments take into account both the problem of generating a schedule, and the problem of repair a schedule to sudden absences. Both experiments were executed on the same computer equipped with four core Intel Xeon CPU X3430 2.4 GHz and 16 GB of RAM, running Debian Linux. Time and memory were limited to 1 hour and 8 GB, respectively. All ASP material can be found at http://www.star.dist.unige.it/∼marco/Data/material.zip.

7.1 Nurse scheduling

The experiments consider real data provided by the Italian hospital unit, which comprises a set of 41 nurses and holidays selected using the preferences of nurses of the year 2015. Moreover, the scalability of the approach has been evaluated by considering different number of nurses. In particular, an additional experiment was run by considering 10, 20, 41, 82 and 164 nurses without fixed holidays. Both the decisional (NSP^d) and the optimization (NSP^o) variants of NSP were considered. Concerning the decisional variant, the ASP-based approaches are compared to solutions based on SAT and on ILP.

The ASP encodings have been tested using the system clingo (version 5.1.0) [33] and the system wasp (version 996bfb3) [6] combined with the grounder gringo [29], both configured with the core-based algorithms [4] for NSP^o. Solvers lingeling (version bbc-9230380-160707) [15], glucose (version 4.1) [9] and clasp (v. 3.2.2) have been executed on the SAT encoding, while the commercial tool gurobi (version 7.0.2) [35] on the ILP encoding. Concerning the optimization variant, the same tools for ASP and ILP have been used, whereas lingeling and glucose have been replaced by the MaxSAT tools mscg [44] and maxino [7], both binaries taken from MaxSAT Competition 2016.

In order to test SAT and ILP solutions, a pseudo-Boolean formula based on the ideas of the advanced ASP encoding is created. The pseudo-Boolean formula was represented using the OPB format, which is parsed by the tool gurobi. Concerning the SAT-based solutions, the state-of-the-art tool pblib [49] has been used to convert the pseudo-Boolean formula into a CNF. The running time of pblib has not been included in the analysis.

Results. The results of the instance with parameters provided by the Italian hospital are reported in Table 2. The best result overall is obtained by clingo executed on the advanced encoding for both NSP^d and NSP^o, which is able to find a schedule in 43 and 70 seconds, respectively. This is a clear improvement with respect to the original encoding. Indeed, clingo executed on the original encoding was able to find a schedule in 22 and 7 minutes for the decisional and optimization variant, respectively. We observed that the better performance is mainly due to the second improvement, which allows the new encoding to avoid materializing aggregates with large aggregation sets (see Section 5.2). However, the advanced encoding does not help the ASP solver wasp : Its bad performance seems related to the branching heuristic, which is not effective on this particular domain. Indeed, wasp often selects atoms which do not appear in the aggregates, and this strategy seems to be ineffective for solving such instances. SAT-based (and MaxSAT-based) approaches are also not able to find a schedule within the allotted time and memory. In this case their performance can be explained by looking at the large size of the formula to evaluate (approximately 65 millions of clauses), which makes the solvers exceed the allotted memory. The tool gurobi obtained good performance on both NSP^d and NSP^o instances. In particular for NSP^dgurobi is faster than clingo executed on the original encoding. On the contrary, gurobi is slower than clingo on the NSP^o instance.

Table 2
Results of the experiment with 41 nurses and fixed holidays

NSP ^d NSP ^o

Solver Time (s) Solver Time (s)

clingo (orig enc) 1352 clingo (orig enc) 431

clingo (adv enc) 43 clingo (adv enc) 70

wasp (orig enc) - wasp (orig enc) -

wasp (adv enc) - wasp (adv enc) -

glucose (sat enc) - mscg (maxsat enc) -

lingeling (sat enc) - maxino (maxsat enc) -

clasp (sat enc) - clasp (maxsat enc) -

gurobi (ilp enc) 1018 gurobi (ilp enc) 1073

NSP ^d	NSP ^o
clingo (orig enc)	1352	clingo (orig enc)	431
clingo (adv enc)	43	clingo (adv enc)	70
wasp (orig enc)	-	wasp (orig enc)	-
wasp (adv enc)	-	wasp (adv enc)	-
glucose (sat enc)	-	mscg (maxsat enc)	-
lingeling (sat enc)	-	maxino (maxsat enc)	-
clasp (sat enc)	-	clasp (maxsat enc)	-
gurobi (ilp enc)	1018	gurobi (ilp enc)	1073

Scalability. A further analysis about the scalability of the encoding, considering different numbers of nurses, is reported in the following. In particular, for both NSP^d and NSP^o, five instances are considered, containing 10, 20, 41, 82 and 164 nurses, respectively. For each instance, the number of working nurses during each shift is proportionally scaled and holidays are randomly generated, whereas other requirements are not modified. Results are reported in Table 3.

Table 3

Scalability of the approach. Solving time (s) for each solver

	Solver	Nurses
		10	20	41	82	164
NSP ^d	clingo (orig enc)	155	117	738	1486	2987
	clingo (adv enc)	4	9	70	351	1291
	wasp (orig enc)	-	-	-	-	-
	wasp (adv enc)	5	20	-	-	-
	glucose (sat enc)	-	-	-	-	-
	lingeling (sat enc)	-	-	-	-	-
	clasp (sat enc)	-	-	-	-	-
	gurobi (ilp enc)	62	172	1018	-	-
NSP ^o	clingo (orig enc)	37	94	339	798	1689
	clingo (adv enc)	4	13	72	482	1590
	wasp (orig enc)	-	-	-	-	-
	wasp (adv enc)	4	-	-	-	-
	mscg (maxsat enc)	-	-	-	-	-
	maxino (maxsat enc)	-	-	-	-	-
	clasp (maxsat enc)	-	-	-	-	-
	gurobi (ilp enc)	113	411	2004	-	-

The best results overall is obtained again by clingo executed on the advanced encoding, which outperforms all other tested approaches. Concerning ASP-based approaches, their performance is much better when they are executed on the advanced encoding. Indeed, the running time of clingo considerably decreases for all tested instances in both NSP^d and NSP^o. As a possible explanation for this behavior, Fig. 5 shows a comparison among the number of conflicts found by clingo executed on the original and on the advanced encodings. The new encoding takes advantage of the better propagations, thus it is able to find a solution with a smaller number of conflicts. Concerning NSP^o, it can also be observed that the performance of clingo executed on the two encodings are comparable on the instance with 164 nurses, even if the number of conflicts are much lower when clingo is executed on the advanced encoding. To explain this discrepancy we analyzed the number of branching choices performed by clingo , which are around 128 millions for the original encoding, and around 300 millions for the advanced encoding. Thus, for this specific instance, the branching heuristic of clingo seems to be more effective when the original encoding is considered. Moreover, wasp executed on the advanced encoding is able to find a schedule for NSP^d when 10 and 20 nurses are considered, whereas wasp executed on the original one does not terminate the computation in 1 hour. The performance of SAT (and MaxSAT) solvers are also in this case not satisfactory since they cannot solve any of the tested instances. In this case, when 10 nurses are considered the size of the formula is not prohibitive (approximately 15 millions of clauses), however all the SAT solvers were not able to find a solution within the allotted time. gurobi can solve instances up to 41 nurses, whereas it is not able to find a schedule when 82 and 164 nurses are considered.

Fig. 5

Comparison of the number of conflicts (in thousands) of clingo executed on the original and on the advanced encodings for both NSP^d and NSP^o with different number of nurses.

7.2 Nurse rescheduling

The experiments for rescheduling consider the schedule computed by clingo on instances with 41 nurses. Then, absences of nurses were randomly generated, considering three different sets of instances, i.e. short, mid and long term absences. For each set, 50 instances were generated.

Absences ranging from 1 to 7 days are considered short; from 8 to 30 days are considered mid and from 30 days to one year are considered long. For each test, a random number of absent nurses is generated and for each nurse a range of unavailability is also randomly generated. In short term instances, the number of absent nurses is limited to 3, while for mid term and long term instances it is limited to 2 and 1, respectively. Moreover, short term instances include both health and personal problems, while mid term and long term include only health problems. An example of a short term instance is the following:

representing that nurses with ids 12 and 9 are not available for 3 days due to personal problems and health problems, respectively.

Since ASP has been shown to be the best solution for NSP, here we consider only this approach. The encodings have been tested using the system clingo (version 5.1.0) [33] and the solver wasp [6] combined with the grounder gringo [29], both configured with the core-based algorithms [4].

Results. The results of the experiments are reported in Table 4. First of all, both clingo and wasp are able to solve all the instances within the time limit. Concerning clingo , its average running time is approximately 7 and 26 seconds for NRP^d and NRP^o, respectively. Concerning wasp , its running time is also satisfactory since it is on average 48 and 65 seconds for NRP^d and NRP^o, respectively. The running time does not depend on the length of the absence, instead we observed that both solvers needed more time to find a solution on instances including absences due to personal problems. As example, short term instance number 14 comprises only absences related to personal problems and it is solved in approximately 4 minutes by clasp and in approximately 6 minutes by wasp. Moreover, we report that clingo is able to find a solution within 10 seconds for the 97% of the considered NRP^d and NRP^o instances.

Table 4
Average solving time (s) for clasp and wasp

Absences NRP ^d NRP ^o

clingo wasp clingo wasp

Short term 14 61 69 87

Mid term 3 10 3 10

Long term 5 73 5 100

Absences	NRP ^d	NRP ^o
Short term	14	61	69	87
Mid term	3	10	3	10
Long term	5	73	5	100

8 Related work

In recent years, several approaches to solve NSP have been proposed. The main differences concern (i) the planning periods; (ii) the different type of shifts; (iii) the requirements related to the coverage of shifts, i.e. the number of personnel needed for every shift; and (iv) other restrictions on the rules of nurses (see [17] for more detailed information). In this paper a one-year window of time has been considered as in [21], where however the same requirements on nurses and hospitals were not reported. Concerning the shifts, we considered three different shifts (morning, afternoon and night) with no overlapping among shifts, whereas in the literature other approaches are based on one single shift only (see e.g. [43]). Other requirements depend on the different policies of the considered hospitals. Thus, this makes the different strategies not directly comparable with each other.

Concerning other solving technologies reported in the literature, they range from mathematical to meta-heuristics approaches, including solutions based on integer programming [10, 12], genetic algorithms [3], fuzzy approaches [51], and ant colony optimization algorithms [36], to mention a few. Detailed and comprehensive surveys on NSP can be found in [17, 22].

As far as the relation between the basic and advanced encodings, the two encodings mainly differ with respect to how the constraints related to hospital and balance requirements are modeled. Indeed, the new encoding takes into account only combinations of parameters values that can lead to a valid schedule.

As argued in two recent surveys [23, 47], NRP is considered strategic in many hospitals, since rescheduling is an almost daily activity and any change to previous schedule usually faces unexpected resistance. Thus, most of the approaches are based on minimizing the changes with the previous schedule as also considered in this paper.

Many solutions have been proposed in the literature [23, 47], including heuristic approaches [38 , 48], genetic algorithms [46], parallel algorithms [14], artificial immune systems [41], and integer multicommodity flow formulations [45].

In [13], authors considered the possibility of hiring temporary staff, called travelers, for dealing with sudden absences of nurses. It turns out that this approach is needed in hospitals facing a chronic nursing shortage, i.e. when permanent nurses cannot fulfill the requirements imposed by the hospital, which is not the case of the hospital considered here.

Finally, ASP encodings have been proposed for scheduling problems other than NSP and NRP: Incremental Scheduling Problem [19], where the goal is to assign jobs to devices such that their executions do not overlap one another; and Team Building Problem [50], where the goal is to allocate the available personnel of a seaport for serving the incoming ships. However, to the best of our knowledge, the only ASP encodings for NSP and NRP are those shown in Sections 5.1, 5.2 and 6.

9 Conclusion

In this paper an advanced ASP encoding for addressing a variant of NSP has been proposed. The new encoding overcomes the limitations of the one proposed in [24] by taking into account intrinsic properties of NSP and internal details of ASP solvers. The new NSP encoding has been used as basis for an ASP-based solution for solving NRP. The ASP-based approach to NSP has been compared with the basic one [24] and with other declarative approaches on real setting provided by an Italian hospital. Results clearly show that clingo executed on the new encoding outperforms all alternatives, being able to solve all instances within 30 minutes, even with more than 100 nurses. Concerning NRP solution, it has been tested by simulating sudden absences for nurses along the year. Results on 150 random scenarios are quite good: clingo and wasp are able to compute a solution for NRP within few seconds.

Moreover, we also observe that the techniques presented in this paper might be also used for similar encodings. In particular, if the problem at hand involves several constraints on aggregated values, a predicate like countGE proposed in Section 5.2 may help ASP solvers to better prune the search space; on the other hand, the programmer should take into account the effective size of the instantiation of such a predicate, and evaluate whether it is affordable or not.

As future work, we plan to extend our ASP encoding in order to take into account also other requirements [47]. In particular, it would be interesting to evaluate the performance of the ASP encodings on the instances of the international nurse scheduling competitions [20, 37].

Footnotes

Acknowledgments

We would like to thank Nextage srl for providing support for this work. Mario Alviano has been partially supported by the Italian Ministry for Economic Development (MISE) under project “PIUCultura – Paradigmi Innovativi per l’Utilizzo della Cultura” (n. F/020016/01-02/X27), and under project “Smarter Solutions in the Big Data World (S2BDW)” (n. F/050389/01-03/X32) funded within the call “HORIZON2020” PON I&C 2014-2020, and by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM).

References

Abío

, Stuckey

P.J.

, Encoding linear constraints into SAT. In O’Sullivan

, editor, CP, volume of LNCS, 2014, pp. 75–91. Springer. https://doi.org/10.1007/978-3-319-10428-7_9

Abseher

, Gebser

, Musliu

, Schaub

and Woltran

, Shift design with answer set programming, Fundam Inform147(1) (2016), 1–25. https://doi.org/10.3233/FI-2016-1396

Aickelin

and Dowsland

K.A.

, An indirect genetic algorithm for a nurse-scheduling problem, Computers & OR31(5) (2004), 761–778. https://doi.org/10.1016/S0305-0548(03)00034-0

Alviano

and Dodaro

, Anytime answer set optimization via unsatisfiable core shrinking, TPLP16(5-6) (2016), 533–551. https://doi.org/10.1017/S147106841600020X

Alviano

, Faber

, The complexity boundary of answer set programming with generalized atoms under the FLP semantics, In LPNMR volume 8148 of LNCS, 2013, pp. 67–72. Springer. http://dx.doiorg/10.1007/978-3-642-40564-8_7

Alviano

, Dodaro

, Leone

, Ricca

, Advances in WASP, In LPNMR volume 9345 of LNCS, 2015, pp. 40–54. Springer. https://doi.org/10.1007/978-3-319-23264-5_5

Alviano

, Dodaro

, Ricca

, A MaxSAT Algorithm Using Cardinality Constraints of Bounded Size, In IJCAI 2015, 2015, pp. 2677–2683. AAAI Press.

Alviano

, Dodaro

and Maratea

, An advanced answer set programming encoding for nurse scheduling, In AI*IA, volume to appear, 2017.

Audemard

, Simon

, Extreme cases in SAT problems. In Creignou

and Berre

D.L.

, editors, SAT, volume 9710 of LNCS, 2016, pp. 87–103. Springer. https://doi.org/10.1007/978-3-319-40970-2_7

10.

Naceur Azaiez

and Al Sharif

S.S.

, A 0-1 goal programming model for nurse scheduling, Computers & OR32 (2005), 491–507. https://doi.org/10.1016/S0305-0548(03)00249-1

11.

Balduccini

, Gelfond

, Watson

, Nogueira

, The USA-advisor: A case study in answer set planning, In LPNMR volume 2173 of LNCS, 2001, pp. 439–442. Springer. https://doi.org/10.1007/3-540-45402-0_39

12.

Bard

J.F.

and Purnomo

H.W.

, Preference scheduling for nurses using column generation, European Journal of Operational Research164(2) (2005), 510–534. https://doi.org/10.1016/j.ejor.2003.06.046

13.

Bard

J.F.

and Purnomo

H.W.

, Incremental changes in the workforce to accommodate changes in demand, Health Care Management Science9(1) (2006), 71–85. https://doi.org/10.1007/s10729-006-6281-y

14.

Bäumelt

, Dvorák

, Sucha

and Hanzálek

, A novel approach for nurse rerostering based on a parallel algorithm, European Journal of Operational Research251(2) (2016), 624–639. https://doi.org/10.1016/j.ejor.2015.11.022

15.

Biere

, Fröhlich

, Evaluating CDCL variable scoring schemes, In SAT volume 9340 of LNCS, 2015, pp. 405–422. Springer. https://doi.org/10.1007/978-3-319-24318-4_29

16.

Brewka

, Eiter

and Truszczynski

, Answer set programming at a glance, Commun ACM54(12) (2011), 92–103. http://doi.acm.org/10.1145/2043174.2043195

17.

Burke

E.K.

, Causmaecker

P.D.

, Berghe

G.V.

and Landeghem

H.V.

, The state of the art of nurse rostering, J Scheduling7(6) (2004), 441–499. https://doi.org/10.1023/B:JOSH.0000046076.75950.0b

18.

Calimeri

, Faber

, Gebser

, Ianni

, Kaminski

, Krennwallner

, Leone

, Ricca

and Schaub

, ASP-Core-2 Input Language Format, 2013. https://www.mat.unical.it/aspcomp/files/ASP-CORE-2.01c.pdf.

19.

Calimeri

, Gebser

, Maratea

and Ricca

, Design and results of the fifth answer set programming competition, Artif Intell231 (2016), 151–181. https://doi.org/10.1016/j.artint.2015.09.008

20.

Ceschia

, Thanh

N.D.T.

, Causmaecker

P.D.

, Haspeslagh

, Schaerf.

, Second international nurse rostering competition (INRC-II) – problem description and rules - . CoRR, abs/1501.04177, 2015. http://arxiv.org/abs/1501.04177

21.

Chan

, Weil

, Cyclical staff scheduling using constraint logic programming, In PATAT volume 2079 of LNCS, 2000, pp. 159–175. Springer. https://doi.org/10.1007/3-540-44629-X_10

22.

Cheang

, Li

, Lim

and Rodrigues

, Nurse rostering problems - a bibliographic survey, European Journal of Operational Research151(3) (2003), 447–460. https://doi.org/10.1016/S0377-2217(03)00021-3

23.

Clark

, Moule

, Topping

and Serpell

, Rescheduling nursing shifts: Scoping the challenge and examining the potential of mathematical model based tools, Journal of Nursing Management23(4) (2015), 411–420. https://dx-doi-org.web.bisu.edu.cn/10.1111/jonm.12158

24.

Dodaro

, Maratea

, Nurse scheduling via answer set programming, In LPNMR volume 10377 of LNCS, 2017, pp. 301–307, Springer. https://doi.org/10.1007/978-3-319-61660-5_27

25.

Dodaro

, Leone

, Nardi

, Ricca

, Allotment problem in travel industry: A solution based on ASP, In RR volume 9209 of LNCS, 2015, pp. 77–92. Springer. https://doi.org/10.1007/978-3-319-22002-4_7

26.

Dodaro

, Gasteiger

, Leone

, Musitsch

, Ricca

and Schekotihin

, Combining answer set programming and domain heuristics for solving hard industrial problems (application paper), TPLP16(5-6) (2016), 653–669. https://doi.org/10.1017/S1471068416000284

27.

Erdem

and Öztok

, Generating explanations for biomedical queries, TPLP15(1) (2015), 35–78. https://doi.org/10.1017/S1471068413000598

28.

Gavanelli

, Nonato

and Peano

, An ASP approach for the valves positioning optimization in a water distribution system, J Log Comput25(6) (2015), 1351–1369. https://doi.org/10.1093/logcom/ext065

29.

Gebser

, Kaminski

, König

, Schaub

, Advances in gringo series 3, In LPNMR volume 6645 of LNCS, 2011, pp. 345–351. Springer. https://doi.org/10.1007/978-3-642-20895-9_39

30.

Gebser

, Kaufmann

, Kaminski

, Ostrowski

, Schaub

and Schneider

M.T.

, Potassco: The potsdam answer set solving collection, AI Commun24(2) (2011), 107–124. https://doi.org/10.3233/AIC-2011-0491

31.

Gebser

, Schaub

, Thiele

and Veber

, Detecting inconsistencies in large biological networks with answer set programming, TPLP11(2-3) (2011), 323–360. https://doi.org/10.1017/S1471068410000554

32.

Gebser

, Kaufmann

and Schaub

, Conflict-driven answer set solving: From theory to practice, Artif Intell187 (2012), 52–89. https://doi.org/10.1016/j.artint.2012.04.001

33.

Gebser

, Kaminski

, Kaufmann

, Ostrowski

, Schaub

, Wanko

, Theory solving made easy with clingo 5, In ICLP TCs volume 52 of OASICS, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, pp. 2:1–2:15. https://doi.org/10.4230/OASIcs.ICLP.2016.2

34.

Gelfond

and Lifschitz

, Classical negation in logic programs and disjunctive databases, New Generation Comput9(3/4) (1991), 365–386.

35.

Gurobi, The website of gurobi, 2017. http://www.gurobi.com.

36.

Gutjahr

W.J.

and Rauner

M.S.

, An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria, Computers & OR34(3) (2007), 642–666. https://doi.org/10.1016/j.cor.2005.03.018

37.

Haspeslagh

, Causmaecker

P.D.

, Schaerf

and Stølevik

, The first international nurse rostering competition 2010, Annals OR218(1) (2014), 221–236. https://doi.org/10.1007/s10479-012-1062-0

38.

Kitada

and Morizawa

, A heuristic method for nurse rerostering problem with a sudden absence for several consecutive days, International Journal of Emerging Technology and Advanced Engineering3(11) (2013), 353–361.

39.

Koponen

, Oikarinen

, Janhunen

and Säilä

, Optimizing phylogenetic supertrees using answer set programming, TPLP15(4-5) (2015), 604–619. https://doi.org/10.1017/S1471068415000265

40.

Maenhout

and Vanhoucke

, An evolutionary approach for the nurse rerostering problem, Computers & OR38(10) (2011), 1400–1411. https://doi.org/10.1016/j.cor.2010.12.012

41.

Maenhout

, Vanhoucke

, An artificial immune system based approach for solving the nurse re-rostering problem, In EvoCOP 2013 volume 7832 of LNCS, 2013, pp. 97–108. Springer. https://doi.org/10.1007/978-3-642-37198-1_9

42.

Marileo

M.C.

and Bertossi

L.E.

, The consistency extractor system: Answer set programs for consistent query answering in databases, Data Knowl Eng69(6) (2010), 545. https://doi.org/10.1016/j.datak.2010.01.005

43.

Miller

H.E.

, Pierskalla

W.P.

and Rath

G.J.

, Nurse scheduling using mathematical programming, Operations Research24(5) (1976), 857–870. https://doi.org/10.1287/opre.24.5.857

44.

Morgado

, Dodaro

, Marques-Silva

, Core-Guided MaxSAT with Soft Cardinality Constraints, In CP volume 8656 of LNCS, 2014, pp. 564–573. Springer. https://doi.org/10.1007/978-3-319-10428-7_41

45.

Moz

and Pato

M.V.

, Solving the problem of rerostering nurse schedules with hard constraints: New multicommodity flow models, Annals OR128(1-4) (2004), 179–197. https://doi.org/10.1023/B:ANOR.0000019104.39239.ed

46.

Moz

and Pato

M.V.

, A genetic algorithm approach to a nurse rerostering problem, Computers & OR34(3) (2007), 667–691. https://doi.org/10.1016/j.cor.2005.03.019

47.

Mutingi

and Mbohwa

, The nurse rerostering problem: An explorative study, In International Conference on Industrial Engineering and Operations Management (IEOM), 2017. http://ieomsociety.org/ieom2017/papers/563.pdf

48.

Pato

M.V.

and Moz

, Solving a biobjective nurse rerostering problem by using a utopic pareto genetic heuristic, J Heuristics14(4) (2008), 359–374. https://doi.org/10.1007/s10732-007-9040-4

49.

Philipp

, Steinke

, Pblib - A library for encoding pseudo-boolean constraints into CNF, , In SAT volume 9340 of LNCS, 2015, pp. 9–16. Springer. https://doi.org/10.1007/978-3-319-24318-4_2

50.

Ricca

, Grasso

, Alviano

, Manna

, Lio

, Iiritano

and Leone

, Team-building with answer set programming in the gioiatauro seaport, TPLP12(3) (2012), 361–381. https://doi.org/10.1017/S147106841100007X

51.

Topaloglu

and Selim

, Nurse scheduling using fuzzy modeling approach, Fuzzy Sets and Systems161(11) (2010), 1543–1563. https://dx-doi-org.web.bisu.edu.cn/10.1016/j.fss.2009.10.003

Nurse (Re)scheduling via answer set programming 1

Abstract

1 Introduction

2 Preliminaries

3 Problems description

3.1 Nurse scheduling problem

3.2 Nurse rescheduling problem

4 Problems formalization

4.1 Nurse scheduling problem

5 Nurse scheduling via ASP

5.1 Existing encoding

7.1 Nurse scheduling

Table 4 Average solving time (s) for clasp and wasp Absences NRP d NRP o clingo wasp clingo wasp Short term 14 61 69 87 Mid term 3 10 3 10 Long term 5 73 5 100

9 Conclusion

Footnotes

Acknowledgments

References

Table 4
Average solving time (s) for clasp and wasp

Absences NRP ^d NRP ^o

clingo wasp clingo wasp

Short term 14 61 69 87

Mid term 3 10 3 10

Long term 5 73 5 100