Lahcene Mezouari
email: lahcene.mezouari@hds.utc.fr

Jean-Paul Boufflet

Aziz Moukrim

Surgery planning for elective patients: a dedicated heuristic and an effective ALNS

Keywords: Surgery planning, project scheduling, adaptive heuristic, operating room management, metaheuristic

Hospital organization, the medical concerns of the patient, surgery resources and the horizon to be considered are all elements that contribute to the variety of problems encountered in surgery planning. In this paper, we address the admission planning problem for which surgical interventions of hundreds of elective patients need to be scheduled months before the date of surgery. The health care surgery organization we consider here is based on a shared management of operating rooms and surgeons. The main issue for hospital planners is to schedule all the interventions under resource availability constraints while considering the patients' health priorities. We propose a two-phase 2PSC-EM randomized heuristic that obtains better results on literature benchmark instances. However, for some instances certain interventions are left unscheduled since straightforward heuristic failed to schedule all interventions. We investigated an effective Adaptive Large Neighborhood Search (ALNS) approach. Better results are obtained for each instance, all the patients' interventions are scheduled which had not been done before. The average improvement is about 11.2% and the processing times are shorter than the timeout fixed in the literature, except for one instance for which we succeeded to schedule all of the patients.

Introduction

Health care systems are facing increasing demands in an environment of difficult budgetary constraints. Access to quality health services has become a major issue [START_REF] Xie | Operations research in healthcare[END_REF]. The surgery department represents an essential activity for the majority of hospitals, generating about two thirds of the surgical interventions [START_REF] Gupta | Surgical suites' operations management[END_REF]. Given the budgetary constraints involved, increasing the number of surgeons and operating rooms, in addition to all of the other related resources, is not the solution to investigated first, but, instead the improved use of existing resources when feasible [START_REF] Fischer | Elhealth: Using internet of things and data prediction for elastic management of human resources in smart hospitals[END_REF]. One way to do this is to build better surgery schedules with the aim of scheduling a maximum number of surgery interventions while taking limited resources with availability constraints into account.

Planning of surgical interventions has been widely studied, and the literature reviews [START_REF] Rahimi | A comprehensive review and analysis of operating room and surgery scheduling[END_REF][START_REF] Samudra | Scheduling operating rooms: achievements, challenges and pitfalls[END_REF][START_REF] Erdogan | Surgery Planning and Scheduling[END_REF][START_REF] May | The surgical scheduling problem: Current research and future opportunities[END_REF][START_REF] Cardoen | Operating room planning and scheduling: A literature review[END_REF][START_REF] Magerlein | Surgical demand scheduling: a review[END_REF] provide an overview of the wide variety of problems encountered. For example, the hospital organization's stakeholders, the care processes, the hospital structure and the work regulations are all elements that contribute to the wide variety of problems. Surgeons may be fee-for-service or hospital employees, or both. In some cases, the hospital may allocate time windows for operating rooms to a department (e.g., a group of orthopedic surgeons) and leave it to the surgeons themselves to divide the time windows. In some other cases, surgeons schedule their own patients in operating rooms that they book a few weeks in advance. In yet other cases, provided that several surgeons have the surgery skills to perform an intervention that can be done in certain operating rooms, rooms and surgeons are viewed as shared renewable resources to be efficiently managed for the hospital organization. These cases can also be hybridized, and, consequently, public-private organizations are widely encountered.

Problems can be classified along several axes, such as patient characteristics or the length of the planning horizon (months, weeks, days). Patients are usually considered to be in one of two main categories: elective patients or non-elective patients. For the first, interventions can be planned months in advance by considering the main medical resource needs over the long term. For the second, interventions are either more urgent or unforeseen since a recent diagnosis for a patient may involve an intervention to be scheduled in the short term (several weeks) or immediately following an accident. In certain hospital organizations, emergency departments have their own operating rooms; if not, the sharing of operating rooms between the two categories of patients has to be considered. A typical way of managing these two types of patients at the same time is to reserve or to dedicate operating rooms either for elective or for non-elective patients, but it may depend on the horizon being considered. Patient admission planning may take only the main medical resource needs for an intervention into account, with the aim being to allocate a date for the surgical intervention for each patient, typically taking the long-term horizon (months) into consideration. Next, a plan for the following one or two weeks is drawn up on the basis of, first, the existing patient admission schedule and, second, the more urgent interventions of new patients that are only known a few weeks ahead of time. Finally, a schedule is drawn up every day for the next day. The weekly-based and dailybased schedules are usually subject to dynamic re-scheduling that should take cancellation or postponement policies for elective patients into account in order to disrupt patient admission planning as little as possible.

The health care surgery organization we consider here is based on a shared management of operating rooms and surgeons that are viewed as renewable resources available within certain time intervals, and, where each resource has a limited, constant, capacity. An intervention can be performed using one of several modes since several couples of operating rooms and surgeons can be used. A mode has a fixed duration that may depend on, for instance, the surgical act specific to the surgeon and to the operating room. [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF] presented the GOSSP model (generalized operational surgery scheduling problem) as an extension of multi-project MRCPSP/Max, a generalization of the classical-resource constrained project scheduling problem (RCPSP), known to be NP-hard in the strong sense. The model proposed by the authors makes it possible to consider parameters that relate to patients (priority level, availability date, due date, hard due date) and resource availabilities, as well as to preferences that aim at scheduling certain interventions early in the morning. A surgeon may prefer to perform complex and long surgeries early in the morning. For some type of patients much more at risk or for children (it is hard for them to stay on an empty stomach) the surgery should be scheduled in the morning. Three planning situations have been modeled: the admission planning, the weekly problem and the daily problem. As the day of surgery approaches, more resources need to be managed and the model is able to integrate the information related to the planning situation. The authors proposed publicly available datasets. These datasets can be used to compare search methods.

For the sake of generality, the authors have proposed an Adaptive Construct and Improve algorithm (ACI) to address all these planning situations without any off-line parameter tuning. To the best of our knowledge no other results have been published on these datasets. For more detailed insights we invite the reader to refer to [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF].

In this paper, we propose an effective approach dedicated to the admission planning problem for which the surgical interventions of hundreds of elective inpatients and outpatients need to be scheduled months before the date of surgery, considering that: (i) the main medical resource needs are the surgeons and the operating rooms; (ii) several surgeons have the surgery skills to perform the intervention that can be done in certain operating rooms; both rooms and surgeons are viewed as renewable resources; and several couples of operating rooms and surgeons can be used to schedule an intervention; (iii) each patient has a priority level, an availability date, a due date and a hard due date, and the surgery may have to be scheduled early in the morning. The contributions of this work are summarized as follows:

• We propose a two-phase 2PSC-EM randomized heuristic based on the ideas of RCPSP constructive heuristics. We obtain better results for all the benchmark instances for which all the interventions can be scheduled by ACI. However, for some instances not all the patients' interventions are scheduled, the same for which the ACI algorithm also obtained unscheduled interventions. A more effective approach is needed.

• We investigate an ALNS based solution approach with the aim of schedul-ing all the patients' interventions. The 2PSC-EM randomized heuristic is used to obtain initial solutions. The ALNS that we propose makes use of adaptive mechanisms for destruction and construction of solutions that have been investigated to deal with the resource limitations and the patients' medical constraints. An adaptive diversification mechanism associated with certain destruction operators permits us to broaden the search around a solution in order to obtain better solutions. We carefully designed the acceptance of a lower-quality solution to obtain a good trade-off with the adaptive diversification mechanism.

• Preliminary experiments were done to tune the parameters of the components of the ALNS to obtain a good trade-off between solution quality and processing time. We conducted computational experiments to investigate the contribution of each component of the ALNS approach to show when each of them are beneficial.

• Better results are obtained for each instance, all the patients' interventions are scheduled which had not been done by the ACI algorithm. The average improvement is about 11.2% and the processing times are shorter than the timeout fixed for the ACI algorithm experiments except for one instance for which the ALNS succeeded to schedule all of the patients. The ALNS is an approach that automatically adapts to the difficulty of the instance. The ALNS takes little time for the majority of the instances, and it schedules all the patients' interventions within a reasonable processing time for more difficult instances. The ALNS approach outperforms the results of a more general approach like ACI.

The remainder of this paper is organized as follows. Section 2 is a review of the literature from the short-term horizon of a day, up to the middle-term horizon of several weeks, which we put into the perspective of the admission planning problem over several months. Section 3 presents the admission problem we address here. Constraints, parameters and objective function related to patients are detailed. Section 4 presents the two-stage 2PSC-EM heuristic that we propose. Our ALNS approach is described in Section 5 and several components are explained in detail. The computational experiments are reported and commented on in Section 6. The conclusion and perspectives for further development are to be found in Section 7.

Literature review

The planning and scheduling of patients for surgical interventions have been widely investigated in the literature. In this study we consider the deterministic case, for non deterministic approaches we invite the reader to refer to recent works as presented in [START_REF] Zhou | Surgical Scheduling with Constrained Patient Waiting Times[END_REF].

Metaheuristic based solution approaches have been extensively reported in literature to address a large variety of optimization problems, for a comprehensive survey we invite the reader to refer to [START_REF] Hussain | Metaheuristic research: a comprehensive survey[END_REF]. Recently, [START_REF] Lan | A survey on the applications of variable neighborhood search algorithm in healthcare management[END_REF] presented a survey on the applications of Variable neighborhood search (VNS) in the health care area. In addition to VNS, the ALNS approach makes use of adaptive mechanisms.

For a more general and recent review on the ALNS metaheuristic framework and its applications, we invite the reader to refer to [START_REF] Mara | A survey of adaptive large neighborhood search algorithms and applications[END_REF].

We review here studies regarding the scheduling of surgical interventions from a scheduling horizon perspective, ranging from the short-term horizon of a day, up to the middle-term horizon of several week. Short-term and middleterm problems have many specific features that depend on the practical cases addressed by the study, as well as aspects that can be viewed in a longer-term perspective.

Daily intervention scheduling problems [START_REF] Park | Operating room scheduling considering surgeons' preferences and cooperative operations[END_REF] proposed a mixed integer program and a heuristic based on the grouping of interventions of the same surgeon for the surgical planning of the daily interventions of a Korean university hospital. Each patient is already assigned to a surgeon. Some operating rooms are reserved for urgent surgeries, beyond the scope of the daily schedule. The surgeons' preferences for operating rooms as well as cooperative surgery constraints, where several surgeons simultaneously or sequentially perform an operation are considered. The aim is to minimize the total number of overtime hours, the number of operating rooms used, the number of surgeries not allocated to preferred rooms and the number of surgeries allocated to unfavorable operating rooms. [START_REF] Wang | Scheduling operating theatres: Mixed integer programming vs. constraint programming[END_REF] proposed two approaches to address the daily surgical intervention scheduling problem of a Belgian university hospital. The interventions to be scheduled per day are known. The authors considered the constraints of operating room and surgeon availability, as well as the limited number of recovery beds. Some interventions should start earlier than others, depending on the priorities related to patient status (e.g., children, diabetics). The first approach uses a mixed integer programming model, whereas the second uses constraint programming. The main aim is to minimize the makespan of the scheduled interventions. [START_REF] Xiang | An ant colony optimization approach for solving an operating room surgery scheduling problem[END_REF] proposed a solution approach based on Ant Colony Optimization (ACO) to address the daily surgical intervention scheduling problem of the MD Anderson Medical Center in Houston, Texas (USA). The surgeries to be scheduled on a daily basis are known. The aim is to minimize makespan considering the limited amount of resources (e.g., surgeon, anesthesiologist, nurse, beds) that are needed to perform a surgery, as well as the pre-surgery and postanesthesia stages. [START_REF] Xiang | A multi-objective ACO for operating room scheduling optimization[END_REF] proposed an extension of the ACO approach considering two additional aims to minimize the variation in the working time of resources and to minimize the total overtime of all resources. [START_REF] Sier | Scheduling surgical procedures[END_REF] proposed a solution for a daily surgical intervention problem based on a simulated annealing algorithm. A mixed integer nonlinear formulation for the studied problem was proposed. The objective function is a weighted sum of all problem constraints. The feasibility of the solution is not guaranteed, the approach aims at minimizing the constraints violations.

The daily surgical intervention scheduling problems have common features that can be observed, regardless of the specific organization. The list of elective patients' interventions to be scheduled is known and all the interventions are scheduled. The makespan or the overtime hours are often considered as an explicit part of the objective function since it is important not to exceed normal working hours. Since all interventions must be scheduled, the uses of the critical resources to make a daily schedule feasible are to be considered since each resource has a limited, and constant, capacity.

Weekly intervention scheduling problems [START_REF] Roshanaei | Solving integrated operating room planning and scheduling: Logic-based benders decomposition versus branch-price-andcut[END_REF] proposed a sequence-based mixed-integer programming model and a constraint programming model to address a problem initially proposed in Hashemi [START_REF] Hashemi Doulabi | A constraintprogramming-based branch-and-price-and-cut approach for operating room planning and scheduling[END_REF] to plan surgical interventions over a week horizon. Patients are managed using two sets (mandatory and optional patients). The patient-to-day allocation, the (patient, day)-tooperating room assignment, the (patient, day, operating room)-to-surgeon, and, finally, the scheduling of the start times of these surgeries are considered in turn. The aim is to maximize the total scheduled surgical time. Given that this problem can be hierarchically structured, the authors investigated Benders decomposition that makes it possible to achieve better results. [START_REF] Akbarzadeh | A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering[END_REF] considered a surgery planning problem over several days with nurse re-rostering. Experiments were conducted on generated data based on real data from the Sina Hospital (Tehran, Iran). The heuristic solution approach proposed first builds an optimal LP solution obtained via a column generation algorithm, after which a diving heuristic is applied to drive fractional solutions to integrality. The aim is to maximize the use of the operating rooms by considering the nurses' needs as well. [START_REF] Oliveira | Assessing the impact of patient prioritization on operating room schedules[END_REF] investigated patient scheduling over two weeks considering their prioritization and available sessions (operating rooms and surgeons) for a Urology Department at a university hospital in Quebec City. A MIP model is used on randomly generated instances based on real data to study the impact of several policies for managing wait-listed patients (four categories of patients are considered by urgency level). [START_REF] Ballestín | Scheduling and rescheduling elective patients in operating rooms to minimise the percentage of tardy patients[END_REF] considered the scheduling and rescheduling of elective patients over two weeks. A tentative schedule is first built, followed by a final schedule that is calculated some days before the start of the planning horizon in order to take new information (change in the waiting list or in the status of the patients) into account. The aims are to minimize the number of tardy patients and to maximize the utilization rate of the operating rooms. A linear model formulation is used to perform simulations on randomly generated instances based on real data from a Spanish hospital. The authors studied the trade-off between the degree of the changes allowed in the tentative schedule and the benefits in relation to the objective function. [START_REF] Zhang | A two-level optimization model for elective surgery scheduling with downstream capacity constraints[END_REF] considered a weekly scheduling single-specialty elective surgery problem. The operating rooms and surgical intensive care unit have a limited capacity. However, the surgeons are not considered in this study. A two-level approach was proposed. By applying a Markov decision process, the first level selects interventions from a waiting list of patients. The second level is based on an approximate dynamic programming approach to assign selected interventions to rooms. [START_REF] Castro | Operating room scheduling with generalized disjunctive programming[END_REF] addressed the problem of planning over a week of elective surgeries of different specialties to be selected from among a large list of elective surgeries on the basis of three priority levels. There is a maximum weekly operating time limit for every surgeon. A two-step decomposition approach that makes use of Generalized Disjunctive Programming (GDP) is proposed. The first step generates a planning model that does not consider the surgeon availability constraints. The second step generates a scheduling model, that aims at determining the start time of the selected interventions by assigning the surgeons to the operating rooms, and taking the types of interventions and the availability of the surgeons into account. Some surgery/surgeon/room assignments cannot be translated into a feasible schedule due to conflicts not considered in the planning model, and some interventions of the subset may consequently be left unscheduled. Room and day assignments do not change but some lower-priority planned surgeries can be moved back to a waiting list. The proposed approach is tested on real data from central and university hospital in Lisbon (Portugal). The aim is to maximize the total surgical time.

The weekly surgical interventions scheduling problems have common features that can be observed, regardless of the specific organization. The main resources to be managed are the surgeons and the operating rooms. Considering a hospital organization and given the relative importance of the stakeholders, the constraints on the allocations of the surgeons and of the operating rooms need to be adequately managed. Not all interventions can be planned because the waiting list exceeds the limit of the considered horizon of a few days, a week or a few weeks.

Mathematical programming approaches are popularly used to address surgical intervention scheduling problems over a day or a week. One reason for their success is that mathematical programming offers a framework that is powerful to express the wide variety of the encountered context dependent constraints. However, as the problems grow in size or in complexity/number of the different constraints, solvers may face difficulties in attaining solutions within reasonable processing times. Heuristic approaches based on mathematical formulations, on dedicated heuristics or on meta-heuristics are used to obtain good solutions.

Regardless of the specific features of the organization of surgery rooms, the common features are the list of patients, each having a priority, and, the main resources that are the surgeons and the operating rooms with their availabilities.

The more the horizon increases, the more the importance of scheduling all patients increases while considering their priority in terms of access to surgery.

Given a large list of patients for whom interventions need to be scheduled, each with his or her own health characteristics, it is an issue for a hospital to know whether it is feasible to have an admission plan where all interventions can be scheduled. Not only can it be useful to determine a day for surgery, but an hour as well, allowing constraints such as scheduling certain interventions in the morning to be taken into account as early as possible. The surgeons and the operating rooms can be considered on a long-term horizon provided that the availability constraints are known. -ORs(Operating Rooms), Surg(Surgeons), Obj(Objective).

-Obj: SO(Single-Objective), MO(Multi-Objective).

-Data: RD(Real Data), BRD(Based on Real Data), TD(Theoretic Data).

-Optimization method: H(Heuristics), MH(Metaheuristics), EA(Exact Algortithm).

-CP(Constraint Programming), MIP(Mixed Integer Program).

-ACO(Ant Colony Optimization), GDP(Generalized Disjunctive Programming).

-S(Simulation), ADP(Approximate Dynamic Programming).

Table 1: Related studies on surgical intervention scheduling problems.

In Table 1 we provide a synthetic overview of the literature that relates to our study by chronological order.

For a more detailed overview of the literature about surgery planning problems, we invite the reader to refer to [START_REF] Rahimi | A comprehensive review and analysis of operating room and surgery scheduling[END_REF], [START_REF] Samudra | Scheduling operating rooms: achievements, challenges and pitfalls[END_REF], [START_REF] Erdogan | Surgery Planning and Scheduling[END_REF], [START_REF] May | The surgical scheduling problem: Current research and future opportunities[END_REF][START_REF] Cardoen | Operating room planning and scheduling: A literature review[END_REF], [START_REF] Magerlein | Surgical demand scheduling: a review[END_REF] who provide reviews on variants of these problems and on solution approaches.

Problem description and MIP model

Hospitals need to create the admission plans for surgical interventions of patients months before the date of surgery in consideration of their most critical resources: the surgeons and the operating rooms. In this paper, we consider elective inpatients and outpatients for whom a surgical intervention is to be scheduled regardless of the events that may arise in shorter time horizon schedules.

We focus on the following admission planning problem: given a set of hundreds of patients for whom surgical interventions need to be scheduled over several months, the main issue is to schedule all the interventions in order to obtain a start date (a day and a time) for each intervention. There may be interventions that cannot be feasibly scheduled, but this should be avoided as much as possible.

We first present the data and parameters that relate to patients (priority level, availability date, due date, hard due date), the resource availabilities, as well as preferences that aim at scheduling certain interventions early in the morning. Next, we report the mathematical formulation of the problem from [START_REF] Riise | The surgery scheduling problem-a general model[END_REF] and [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]. In the following, we use most of the notations introduced in Riise and Mannino (2012) and [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF].

Data and parameters

Patients, and some related medical and practical issues, are considered using the following data and parameters: H, planning horizon, or planning period length; z, the number of time units in a day; P , set of elective patients for whom a surgical intervention has to be planned, indices p, we denote |P | as its size; X p , earliest start date for the intervention of patient p; D p , due date; patient p should preferably be scheduled before; H p , hard due date; patient p must be scheduled before; otherwise, the intervention is unscheduled;

β p , for a patient, the relative importance to schedule the patient's surgical intervention;

P em ⊂ P , subset of patients for whom the intervention should be planned early in the morning, we denote |P em | as its size;

τ , for all patients p ∈ P em , the time in the morning from which the intervention can be scheduled; γ p , for a patient p ∈ P em , the relative importance to schedule the patient early in the morning;

R s , set of surgeons, indices s; R r , set of operating rooms, indices r; R, set of all resources, R = R s ∪ R r ;
R p , set of resources assigned to the surgical interventions of patient p, through the choice of mode;

K i , set of successive disjoint availability intervals associated with resource i (surgeon or room);

K p i ⊆ K i , set of intervals for which resource i is available to the surgical inter- ventions of patient p; M , set of modes m = (r s , r r ) ∈ R s × R r ,
u m i , if mode m uses resource i then u m i = 1;
ϑ m p , length of the surgical intervention for patient p when using mode m.

Each patient p has an earliest start date X p for the intervention and a due date D p defined to reflect a medical priority. Each patient p has a hard due date H p ≥ D p . The starting date of the intervention should be strictly below this hard due date; otherwise, the surgical intervention is left unscheduled. Parameters X p , D p , and H p are integer numbers of days relative to the beginning of the planning horizon. For a patient p, the value β p is linked to the patient's degree of priority for the surgical intervention.

For some particular patients p ∈ P em , the surgical intervention should be preferably scheduled early in the morning; the parameter τ is the time in the morning from which the surgical intervention can be scheduled. The parameter γ p is the relative importance to schedule the patient's surgical intervention earlier in the morning.

In order to be scheduled, a surgical intervention requires a surgeon and a room. The sets R s , R r , R and R p , are used to manage the resources. The sets K i are useful to take the daily working hours of the teams or the surgeons into consideration, as well as the operating room hours and the maintenance operations of these surgical technical platforms.

For a patient p, the set of feasible modes is M p , depending on the surgical operation to be performed. The medical evaluations during the preoperative consultations make it possible to select surgeons not only in accordance with the needed specialty, but also with the professional experience that is related to the difficulty of the medical case. Usually in such organization, the surgeons themselves, organized by specialty, decide who can perform the surgical operation. Consequently, the length ϑ m p of the surgery depends on the surgeon and on the operating room where it can be done.

One mode m should be chosen to plan the surgical intervention of patient p from among M p . The preemption of surgical interventions is not authorized.

Given that we are scheduling many patients, when using mode m = (r s , r r ) for a patient p, an interval I from among the set of intervals K rs ∩ K rr is to be chosen to make it possible to plan the surgical intervention of length ϑ m p , taking all other surgical interventions that are already scheduled into account.

For a patient p, a surgical intervention is to be scheduled; an intervention corresponds to one patient p. For the sake of simplicity, we use the same indices p for indexing interventions in the sequel.

Mathematical formulation

We introduce the mathematical formulation of the problem from [START_REF] Riise | The surgery scheduling problem-a general model[END_REF] and [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]. The variables are as follows:

x m p = 1, if the surgical intervention of patient p uses mode m ∈ M p , and 0 otherwise;

q k p = 1, if the surgical intervention of patient p uses resource interval k ∈ K i ,
for resource i, and 0 otherwise;

+ W wt 1 1 + λ|P | p∈P o wt(p) (1 -h p ) Owt (1b) + W em 1 z|P em | p∈P em γ p Γ(p)(1 -h p ) Oem (1c)
Subject to:

x m p ∈ {0, 1} ∀p ∈ P, ∀m ∈ M p (2) z pp ∈ {0, 1} ∀p, p ∈ P (3) t p ∈ R + ∀p ∈ P (4) q k p ∈ {0, 1} ∀i ∈ R, ∀k ∈ K p i (5) c p ∈ R + ∀p ∈ P (6) g i p ∈ {0, 1} ∀i ∈ R, ∀p ∈ P (7) c p = t p + m∈Mp ϑ m p x m p ∀p ∈ P (8) g i p = m∈Mp u m i x m p ∀i ∈ R, ∀p ∈ P (9) m∈Mp x m p = 1 -h p ∀p ∈ P (10) k∈K p i q k p = g i p ∀p ∈ P, ∀i ∈ R (11)
z pp + z p p ≤ 1 ∀p, p ∈ P (12) t p -c p ≥ (z pp -1)M ∀p, p ∈ P (13) z pp + z p p ≥ g i p + g i p -1 ∀p, p ∈ P, ∀i ∈ R (14) t p ≥ X p ∀p ∈ P (15) c p ≤ H p ∀p ∈ P (16) t p -ϕ k q k p ≥ 0 ∀p ∈ P, ∀i ∈ R, ∀k ∈ K p i (17) c p -σ k q k p -(1 -q k p )M ≤ 0 ∀p ∈ P, ∀i ∈ R, ∀k ∈ K p i (18)
Constraints ( 2)-( 7) define the variables. Constraint (8) sets the completion times c p . Constraint (9) ensures resource i is used in the chosen mode m for patient p. Constraint (10) ensures that at most one mode m is chosen and set h p accordingly. Constraint (11) ensures that one interval k is used for each resource i of mode m for a patient p. Constraints ( 12), ( 13) and ( 14) ensure precedence constraints when two patients p, p use a same resource i. Constraints ( 15) and ( 16) ensure surgical intervention to be in the required interval [X p , H p ] for patient p. Constraints ( 17) and ( 18) ensure surgical intervention interval [t p , c p ] to be inside interval [ϕ k , σ k ] of resource i. In constraints ( 13) and ( 18), the big-M value is M = H (see [START_REF] Riise | The surgery scheduling problem-a general model[END_REF]).

A feasible solution S is composed of P ⊆ P , a set of elective patients for whom a surgical intervention is scheduled (h p = 0) and a set P \ P of patients for whom a surgical intervention is not scheduled (h p = 1). In the same way, we consider P em and P em \ P em .

The objective function to be minimized is a weighted sum of three normalized terms, see (1a)-(1c). Given a feasible solution, the first term O un of the objective function aims at minimizing the number of elective patients for whom the surgical interventions are left unscheduled. The term is a normalized sum of the β p values, the relative importance to schedule the patient's surgical intervention, for all the elective patients for whom their surgical intervention (p ∈ P \ P ) cannot be scheduled.

The second term of the objective function O wt is a normalized sum of the waiting times for the patients for whom the surgical intervention is scheduled. For a patient p, the waiting time o wt(p) is assessed using the following function:

o wt(p) = cp-Xp Dp-Xp if c p ≤ D p 1 + λ cp-Dp Hp-Dp otherwise. (19)
Overall, for a patient p, this piecewise linear function increases as c p increases relative to the earliest start date X p and relative to the due date D p . Given that we should schedule the surgery before the due date D p , the slope value becomes a steeper value λ when c p > D p . The purpose is to over-penalize the surgical intervention of a patient p that is scheduled after the due date D p .

The third term O em is a normalized sum that evaluates the surgical interventions of patients p ∈ P em whose interventions should be planned early in the morning. Given that τ is known for all patients p ∈ P em , the function Γ(p) computes the difference of time between τ and c p for the chosen planning day; this value is weighted by the relative importance γ p .

The normalized terms are weighted by W un , W wt and W em . We have W un > W wt > W em , which clearly reflects the hierarchy for medical considerations: the priority is to, first, plan as many patients' interventions as possible; second, as close as possible to the due date; and, finally, to schedule in the morning the patients for whom this constraint should be respected.

We denote Obj(S) as the evaluation of a solution S that we compute as presented in equations (1a)-(1c).

The 2PSC-EM heuristic

Given that surgical interventions of the set P of patients can be viewed as projects that require renewable and shared resources, the admission planning problem is presented in [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF] as a multi-project/multi-mode RCPSP with minimum and maximum time lags.

We propose a Two Priorities Scheduling Construction phase (2PSC) based on the ideas of RCPSP constructive heuristics (see [START_REF] Kolisch | Heuristic algorithms for the resourceconstrained project scheduling problem: Classification and computational analysis[END_REF]; [START_REF] Tormos | An efficient multi-pass heuristic for project scheduling with constrained resources[END_REF]; [START_REF] Almeida | Priority-based heuristics for the multi-skill resource constrained project scheduling problem[END_REF]), followed by an improvement phase that focuses on patients that need to be scheduled early in the morning. We denote this heuristic as 2PSC-EM.

The 2PSC construction phase uses two priority lists, one for managing the patients to be scheduled (P ), and the second for managing the execution modes of each patient (M p ). The general idea is to increase the time at each iteration in order to choose the next surgical intervention to be planned by taking all the surgical interventions in progress that are already planned into account (these are assumed to still be in progress) since they cannot be interrupted (no preemption allowed).

Algorithm 1: The construction phase 2PSC The algorithm of the 2PSC construction phase is shown in Algorithm 1.

The iteration i corresponds to the time t i where a surgical intervention can be scheduled; they are initialized at i = 0 and t 0 = 0. The beginning of the planning horizon is 0 and the end is t end .

We denote E p as the End time of intervention p when surgical intervention is scheduled for a patient p with length ϑ m p using a mode m. We denote C i as the set of the surgical interventions of patients that have been Completed at time t i , formally C i = {p ∈ P, E p ≤ t i }. We denote A i as the set of Active surgical interventions of patients at time t i , formally A i = {p ∈ P, E p -ϑ m p ≤ t i < E p }; these surgical interventions are in progress. The surgical interventions that have been planned up to t i belong either to C i or to A i . We denote R i as the set of resources of R s or R r used by the active interventions in the set A i . We denote L i as the list of interventions that can be scheduled at time

t i . The interventions in L i are {p ∈ P ∧ p / ∈ A i ∧ p / ∈ C i , X p ≤ t i }.
These lists manage the interventions of patients to be scheduled throughout the algorithm.

An intervention for a patient p from among L i can possibly be performed using mode m from among M p . However, not all these modes are possible at time t i , since resources may already be used by some interventions in A i that are not finished. We denote M p,i as the list of modes that can be used at time

t i . The modes in M p,i are: {m = (r s , r r ) ∈ M p , (r s , r r / ∈ R i ) ∧ (t i + ϑ m p ≤ H p ) ∧ ([t i , t i + ϑ m p ] ∈ K rs ∩ K rr )}.
In the first loop of Algorithm 1, the overall idea is to manage the interventions to be planned by applying the earliest due date rule. We first update t i by selecting the time of the intervention that is in progress with the soonest end in A i , computed at the previous iteration. Next, the new C i , A i , R i and L i that correspond to the new timestep i are computed. The list L i , the interventions that can be scheduled at time t i , is then sorted in increasing order of D p ; the priority given to the earliest due date aims at minimizing the O wt term. The loop ends when all the interventions are scheduled or when no more interventions can be scheduled without exceeding t end .

In the second loop of Algorithm 1, the idea is to schedule as many interventions as possible at time t i by applying the shortest processing time rule. The first intervention p that can be scheduled at time t i is selected. Its usable modes M p,i at time t i are computed and then sorted by increasing length ϑ m p . Next, the mode m with the smallest length is chosen, the intervention p is scheduled, and its end time E p is updated. The sets and the list S, R i , A i and L i are updated. For a scheduled intervention p, we set c p = t i for the intervention start time. The loop ends when no more interventions can be scheduled at time t i . The rule aims at freeing the resources as soon as possible.

We observed that patients may have the same values of due date D p . We can take advantage of this observation by introducing a partial randomization to obtain different solutions when performing several runs. We shuffle the consecutive blocks of L i that correspond to the same value of D p (see lines 9 and 19), and by doing so, the interventions with equal D p are chosen at random.

The 2PSC algorithm computes a solution S, so P is known. The interventions that have been left unscheduled are computed and we return L u . This heuristic approach aims at minimizing the O wt term, but can be improved by considering the O em term.

We propose an improvement phase EM with the aim of improving the number of interventions of patients in P em who are scheduled early in the morning. We try to move interventions p ∈ P em a step backwards to schedule them early in the morning. For each patient p ∈ P em , we obtain the day d where the surgical intervention is scheduled and then we obtain the list of all the scheduled interventions of this day. This list L d is sorted in increasing order of the time element of c p . Given that p is in position i, we try to swap intervention p with each intervention scheduled before. Function Swap(s, i, j) returns True when it is possible to exchange the interventions. Provided that the two modes and the two lengths are the same, the exchange is performed by this function and S is updated. This straightforward condition has a major advantage, i.e., we can obtain an improved solution at small expense by avoiding the computing time necessary to re-schedule part of the solution.

Given a solution S obtained by applying EM, the set P is the same, and for every day d, the set of scheduled interventions is still the same. We recall that parameters X p , D p , H p and the number of days in c p are integer numbers of days relative to the beginning of the planning horizon. Consequently, the first two terms of the objective function do not change. The swap of the modes of execution of the interventions leads to an equivalent solution relative to the constraints of the problem (resource consumption and release). The start time of some interventions of P em may change, which may decrease the third term of the objective function.

The 2PSC-EM that we propose is a fast dedicated heuristic that computes a schedule that complies with the resource usage constraints, while addressing medical considerations that are related to patients. By introducing the shuffling of list L i , it can be run many time to obtain different solutions.

ALNS metaheuristic for the admission planning problem

The 2PSC-EM heuristic may compute a solution of good quality but, some interventions may be left unscheduled. It is of importance for the hospital management to know whether the interventions for all the elective patients can be scheduled.

The ALNS approach was presented for the first time by [START_REF] Ropke | An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[END_REF]. We provide a contextualized overview that consider the planning admission problem addressed here. We then present the general structure of our Adaptive Large Neighborhood Search (ALNS) in Section 5.1 .

For a large-scale neighborhood search, similar solutions are obtained through modifications to the original solution by applying several local search operators. Given that some interventions may be left unscheduled, we explore the neighborhood of a current solution by first applying a destruction operator to free resources. Next, all the interventions that remain to be planned are scheduled by applying a repair operator with the aim of scheduling all the interventions whenever possible. We present the four destruction operators and the three repair operators that we investigate in Sections 5.2 and 5.3. The degree of destruction needs to be tuned since it affects diversification. An adaptive diversification mechanism is used to manage the degree of destruction for some destroy operators. A couple of destruction and repair operators plays the role of a neighborhood for the local search.

The success of operators may vary depending on the problem instance. An adaptive choice generally leads to better results rather than fixing the choice of operators for the entire course of the algorithm. The adaptive mechanism presented in Section 5.4 is based on a roulette wheel principle that we use to manage the success of destruction operators and the success of repair operators. Each operator has a weight that represents its share in a wheel. The weights are updated according to the performance; efficient operators are used more often than less efficient operators.

The ALNS makes use of these destroy/repair operators to explore the neighborhood of a solution. However, that may not be sufficient to allow the search process to avoid or escape local optima. The acceptance method of ALNS has the purpose of deciding to either continue exploring the neighborhood of a current solution or to select a newly created one. A lower-quality solution can be accepted with the aim of escaping from local optima. We present an adaptive acceptance strategy in Section 5.5 based on the record-to-record travel algorithm, originally proposed by [START_REF] Dueck | New optimization heuristics; The great deluge algorithm and the record-to-record travel[END_REF].

The ALNS that we propose makes use of adaptive mechanisms for destruction, construction and acceptance procedures. Several parameters need to be tuned to obtain a good efficiency of these adaptive mechanisms.

General structure of ALNS

Algorithm 2 gives the general structure of the ALNS that we outline here before providing more detailed insights.

Given an initial solution S and the list L u of interventions left unscheduled, both computed by the 2PSC-EM heuristic (see Section 4), the algorithm alternates destruction and repair phases on a current solution S cur to compute an incumbent solution S i (lines 5-10). The incumbent solution is denoted as S i .

However, we do not create a new container for every incumbent solution for each iteration i, where index i is used for explanation purposes. When the incumbent solution S i fulfills the acceptance criteria, it is retained as the new current solution S cur , and, the number of iterations i is reset to zero; otherwise it is incremented (lines 11-15). The best solution found so far within iterations S best is kept (lines 16-18). Provided that a maximum number of iterations Iter max without any improvement is met, the ALNS algorithm stops and then returns S best and L u .

The destruction operator O des is selected from among a set of destruction operators (line 5) that are either day-oriented or intervention/patientoriented (see Section 5.2). For intervention/patient oriented destruction operators (DayDestroy(O des )=false), a random number of k interventions, bounded by D max , are to be removed (line 7). An adaptive diversification mechanism manages D max (line 20), which makes it possible to broaden the search around the best solution found so far, with the intention of finding a better solution (see Section 5.2). The destruction operator is performed using Destruction(S cur , k, O des ) (line 8). This frees resources but an additional list L des of interventions are unscheduled. The repair operator O rep is selected (line 9) from among a set of repair operators (see Section 5.3). Next, it is used in Construction(S i , L des , L u , O rep ) (line 10) to schedule all the unscheduled interventions (L des and L u ), when possible. Given an incumbent solution S i , the order in which the L des and L u interventions are processed has an impact on the number of interventions that can be scheduled. This depends on free resources within intervals. The repair operators that we propose are based on how the interventions of L des and L u are sorted.

In order to escape from local optima, we allow the acceptance of a nonimproving solution (line 11). The main issue to be faced is to avoid selecting a too low-quality solution, leading to a waste of processing time when exploring its neighborhood in the hope of obtaining a better quality solution. We chose to implement an adaptive acceptance strategy, which we detail in Section 5.5, based on the record-to-record travel algorithm proposed in [START_REF] Dueck | New optimization heuristics; The great deluge algorithm and the record-to-record travel[END_REF].

It is important to make the selection of good destruction/constructions op-erators over the iterations possible in order to be able to schedule all the interventions. The adaptive mechanism that we implement is detailed in Section 5.4. The weights of the two roulette wheels are updated using AdaptiveW eightsAdjustment(S best , S cur , S i ).

The number of iterations without any improvement Iter max can be fixed regardless of the instance or computed during the course of the ALNS algorithm according to some characteristics of the processed instance in order to adapt it to the difficulty of the instance during execution.

We chose to formulate Iter max as γ

|P \ P | |R| +1 . | P |
|R| where γ ∈ [1, 10]. We recall that the set of scheduled interventions during the course of the algorithm is P , the set of patients left unscheduled is P \ P , and the set of resources is R.

Therefore, Iter max mainly increases as The γ parameter needs to be tuned to obtain a good trade-off between good quality solutions and processing times.

Destruction operators

We investigated four destruction operators, two that are intervention/patientoriented and two others are day-oriented. All these operators use the current solution S cur as input, and the intervention/patient operators remove a certain number of interventions while the day operators remove all the interventions scheduled in one day. All these destroy operators aim at freeing resources, which allows the repair operators to schedule as many interventions as they can. RR and RDR are pure random destruction operators. They help diversify the search mechanism [START_REF] Hemmati | Evaluating the importance of randomization in adaptive large neighborhood search[END_REF].

By focusing on days, RDR and WDR make it possible to reallocate resources within one day, while aiming at decreasing the cost, especially with regard to the third term O em of the objective function (1c) related to patients for whom the intervention should be planned early in the morning.

For the Worst Removal, we assess the individual contribution for each scheduled intervention p ∈ S cur . This allows us to remove the k interventions with the highest cost. The WDR destroy operator also assesses the individual contributions. WR and WDR both work at the expense of more processing time but this make it possible to reduce the overall cost Obj(S i ) using repair operators.

At each iteration, function SelectDestructionOperator() (see Algorithm 2) selects one destruction operator O des that is chosen from among the four described above using an adaptive mechanism based on a roulette wheel selection algorithm (see Section 5.4).

The Destruction(S cur , k, O des ) function requires a degree of destruction k, the number of interventions to be removed, that is used by RR and WR. Note that parameter k = 1 when a day-oriented operator is chosen since one day has to be selected. The degree of destruction k affects diversification, and, consequently, the quality of solutions. It can be fixed, chosen at random from a range depending on the size of some characteristics of the instance, or gradually varied at run-time according to a strategy. We chose to implement an adaptive strategy for managing k for RR and WR that uses the number of modes and the number of scheduled interventions that we obtain during the course of the ALNS algorithm.

In Algorithm 2, the value k is chosen at random as k ← rand(1, D max ). Provided that an intervention/patient-oriented destroy operator has been chosen, k is bounded by D max . We define D max as the degree of diversification. This value is initialized to 3 and then incremented after each non-improving iteration as D max ← min(D max + 1, D limit ), when the D limit value is not attained. As soon as an improvement is found, we reset D max to 3 in order to entirely explore the neighborhood of the new best solution S best . The choice of the D limit value is important because it makes it possible to broaden the search around a solution to find a better solution. However, a too large value will possibly generate an unnecessary expenditure of processing time because a better solution could be found in another part of the search space starting from a solution of lower quality that could be selected thanks to the acceptance mechanism (see Section 5.5). We chose to formulate D limit as α. The size of P is larger than the size of M , and processing time increases as the number of removed interventions increases. We chose to select α ∈ [0, 1]. The α parameter needs to be tuned to obtain good-quality solutions.

Over the iterations of the ALNS, the adaptive mechanism makes it possible to choose from among the four destruction operators to explore the neighborhood of a solution. The destruction operators shake up the current solution that makes it possible to explore the neighborhood of this solution.

Repair operators

In the literature, the Best Insertion Algorithm is often used for solution repair. Overall, the idea is to insert items in an incumbent solution at a place chosen as the best one according to specific criteria [START_REF] Amarouche | Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows[END_REF][START_REF] Ben-Said | A variable space search heuristic for the capacitated team orienteering problem[END_REF].

Based on the general principle, we proposed the dedicated algorithm as shown in Algorithm 3. Given an incumbent solution S i , we compute the set that contains triplets of surgeon, room and time interval that can be used to schedule an intervention. We obtain all the free (s, r, I) relative to S i (modes and intervals). We denote this set as S sr(ti) , indexed by sr(ti) for surgeon, room and time interval. this intervention. We then assess the related cost, denoted as cost p , of inserting the intervention p in S i . We therefore obtain the set of quadruplet S p,sr(ti)c (surgeon, room, interval and cost). Provided that S p,sr(ti)c is not empty, we select the best insertion quadruplet with minimum cost and we schedule intervention p using the associated mode m and interval I. The set S sr(ti) is then updated for the next iteration since the resource has been used. If the set S p,sr(ti)c is empty, the intervention p cannot be scheduled and is added to the list L u .

The adapted insertion algorithm and the ordered/prioritized list L itbs together play the role of a repair operator. We can have different solutions using different priority lists. Given the two lists L u and L des , we first append list L des Overall, the idea behind the NRM repair operator is to first schedule the interventions with the least number of modes, assuming that we will have more possibilities to schedule the others as things progress when we schedule the interventions.

More generally, it may be interesting to consider all the elements related to the scheduling of a patient's intervention. We must not lose sight of the fact that the medical constraints of hard due date H p and of due date D p should also be taken into consideration. The modes for scheduling the intervention of a patient as well as the resources may have an impact.

We propose to investigate a strategy for the third repair operator based on the aggregation of the criteria related to the patient's level of urgency (H p and D p ) and those related to modes and resources. Let n mode be the number of different modes that can be used for a patient and let n res be the number of different resources that we count over the different modes. We first compute H p . D p . n res . n mode , and then sort L itbs in ascending order of these values. A low value indicates that the patient is urgent, that a resource is critical, and that there are few modes for the patient's intervention.

The idea behind the AC repair operator is to first schedule the patients' interventions with low values, assuming that we will have more possibilities to schedule the others as things progress when we schedule the interventions.

Over the iterations of the ALNS, the adaptive mechanism makes it possible to choose from among the three repair operators to explore the neighborhood of a solution.

Adaptive mechanism for destruction/repair

The idea is to promote future choices of successful operators by modifying the weights used in a roulette wheel algorithm that selects operators. The weights for the roulette wheel used for destruction operators and the weights for the other roulette wheel used for repair operators are updated using the AdaptiveW eightsAdjustment procedure according to the obtained performance.

The proposed ALNS algorithm uses four destruction and three repair operators. Operator success may vary depending on the problem instance. The adjustment of the roulette wheel weights is necessary to increase the probability that efficient operators are used more often than less efficient operators. Dynamic adjustment is the only way to ensure a permanent re-evaluation of operators' weights.

Two approaches can be used for updating the weights: at each iteration or periodically after a certain number of iterations. The advantage of the first one is that weights are up-to-date at all times but at the expense of processing time since the weights and the operator probabilities for the next iteration have to be calculated at each iteration. On the contrary, by periodically updating the weights after a certain number of p u iterations, we save processing time. However, this implies determining a good value for p u . A large value saves processing time but does not allow the adaptive mechanism to fully play its role, which can result in poor-quality solutions. To save processing time, we chose the second approach. Hence, the tuning of p u is needed to obtain a good trade-off between saved computing time and good-quality solutions.

The adaptive mechanism is the same for destruction or repair operator selection. We denote O as either a destruction or a repair operator. The number of times the operator O has been used during p u iterations is denoted as u(O). The success of operator O is denoted as s(O), set to zero at the beginning of the period of p u iterations. Given the incumbent solution S i , the current solution S cur , and the best solution found so far S best , the value of s(O) is increased at each iteration as:

s(O) + σ i where σ i is either      σ 1 if Obj(S i ) ≤ Obj(S best ) σ 2 if Obj(S i ) ≤ Obj(S cur ) σ 3 otherwise
In the first case, the operator O improves or equals the best solution found so far, while in the second case it improves or equals the current solution. In the last case, we reward the operator when a new solution is worse but accepted according to the acceptance strategy (see Section 5.5). We have σ 1 > σ 2 > σ 3 . This promotes the operator as the relative or absolute solution quality increases. These parameters need to be tuned because they have an impact on the solution quality. We chose to formulate σ 2 as σ 2 = θ.σ 1 and σ 3 as σ 3 = φ.σ 2 where θ, φ ∈ [0, 1]. Provided that an initial value is set for σ 1 , the parameter tuning of σ 1 , σ 2 , σ 3 can be performed by varying the couple of parameters (θ, φ).

The weights for the forthcoming iterations are calculated as:

w(O) = (1 -l)w(O) + l s(O) u(O) , if u(O) > 0 (1 -l)w(O), if u(O) = 0
The reaction factor l ∈ [0, 1] is a parameter that controls the influence of the recent success of an operator on its weight.

The four destruction and the three repair operators together make large changes possible from one solution to its neighbors, which may prevent the search process from being stuck in local optima. However, since operator success may vary depending on the problem instance, the adaptive mechanism plays an important role by rewarding efficient operators throughout iterations. To make the adaptive mechanism efficient, the parameters presented above need to be tuned.

Adaptive acceptance strategy

We chose to implement an adaptive acceptance strategy based on the recordto-record travel algorithm. Originally proposed by [START_REF] Dueck | New optimization heuristics; The great deluge algorithm and the record-to-record travel[END_REF], it is a deterministic variant of simulated annealing. A low-quality solution is accepted based on the difference between the incumbent solution cost Obj(S i ) and the best solution cost Obj(S best ) relative to a value denoted as record-deviation, which is a threshold-based strategy. This straightforward but efficient mechanism has the advantage that it depends only on one parameter, which is the value of the record-deviation, denoted here as Dev (see [START_REF] Dueck | New optimization heuristics; The great deluge algorithm and the record-to-record travel[END_REF]).

The record-deviation parameter Dev plays a central role in controlling the acceptance of low-quality solutions. In the general scheme of the algorithm presented in [START_REF] Dueck | New optimization heuristics; The great deluge algorithm and the record-to-record travel[END_REF], the record-deviation parameter is fixed and originally used as Dev ≤ Obj(S i ) -Obj(S best ). We chose to implement it relative to a percentage as Obj(S i ) ≤ (1+Dev).Obj(S best ) because the unscheduled interventions (postponed from a surgical standpoint) strongly contribute to the overall cost of the objective function (1a)-(1c). It is preferable to use this percentage rather than an absolute difference value for comparison purposes between instances for which all interventions are scheduled and those for which all interventions are not scheduled.

However, the larger this parameter is, the more we unnecessarily explore lowquality solutions because the record-to-record-based mechanism is activated too early.

To have the opportunity to first explore the neighborhood of a current solution using the destroy/repair operators we propose an adaptive acceptance strategy that we manage in procedure Accept(S best , S i ) (see Algorithm 2). Thus, the value of Dev is not fixed, it can increase or decrease throughout the search space exploration process.

However, the increase of Dev may be at the expense of the adaptive diversification mechanism that also increases D max , the maximum number of interventions that can be removed from S i , when a lower quality solution is met. In Algorithm 2, we update D max ← min(D max + 1, D limit ) when Obj(S i ) ≥ Obj(S best ) for some destroy operators. A good trade-off between these two mechanisms must be found to prioritize local searches.

In procedure Accept(S best , S i ), we implement an adaptive mechanism that increases the value of Dev by a constant value ∆ Dev when no improvement is met throughout a defined number of iterations Iter D . The record-deviation parameter is equal to zero at the beginning (Dev = 0). When the defined number of iterations Iter D without improvement has been performed, Dev is increased by the record-deviation increment ∆ Dev to permit the diversification mechanism to play its role. Low-quality solutions are more often accepted, which allows the search to jump out from local optima. The Dev value increases by ∆ Dev as long as destroy/repair operators fail to find a better solution. We reset the record-deviation parameter Dev to zero if a local or global improvement occurs.

Therefore, the two parameters to be tuned to make this adaptive acceptance strategy efficient are ∆ Dev , the record-deviation increment, and, Iter D the number of iterations without improvement that induces the incrementation of Dev.

Computational experiments

In our experiments, our objectives were: (i) to show the effectiveness of the 2PSC-EM heuristic compared to the literature results; (ii) to provide a summary and insights into how to conduct the tuning of the ALNS so that it can be used in other situations where planning of elective patients has to be done over a period of several months; (iii) to evaluate the effectiveness of the destruction/repair operators and the adaptive mechanism for destruction/repair and to discuss the results to show whether a component contributes to obtaining good solutions by also considering the processing time; and (iv) to assess the quality of the solutions computed by the ALNS on benchmark instances compared to the literature results. Tests were done using C++ and Standard Template Library (STL), compiled with GCC under Linux, on a machine with an Intel(R) Xeon(R) Gold 6138 CPU @ 2.00 GHz.

Benchmark overview and experimental protocol

We tested the 2PSC-EM heuristic and the ALNS meta-heuristic on the admission set of the benchmark proposed by [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]. The authors designed an instance generator based on the real resources of a surgery department (Baerum Sykehus, Norway). For confidentiality reasons, the patients are generated. The test data are available on-line in XML format (SINTEF, 2013).

In this paper we focus on building the scheduling of surgical interventions, i.e. admission planning, for which it is of interest for the hospital organization to know whether it is possible to schedule the interventions of elective patients regardless of whether they are outpatients or inpatients. Each of the ten instances of the benchmark test consists of 728 patients to be scheduled over a planning horizon of between 65 and 71 days (about 3 months). In all instances, there are seven surgeons and four operating rooms.

In [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF], the authors decided to run the ACI algorithm ten times for each instance and a time limit of 600 s has been chosen for each run. They reported the minimum, maximum and average solution values at the chosen time limit of 600 s. In [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF], the best solution value, denoted as UB, is also reported for each instance. This UB value corresponds to the best value obtained on all the runs performed by the authors. The processing times for obtaining the UB values are not reported in the paper. The authors indicated that they are obtained using considerably longer running times than the 600 s time limit.

Comparison of 2PSC-EM heuristic with the literature

In Table 2, for each instance under the ACI heading, the UB column shows the best known value, or upper bound, the Min column shows the minimum value obtained by ACI (see [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]), the Mi2UB column shows the percentage (U B -M in)/U B, and the t(s) column shows the processing time. Given that the weight W un is set to 1,000 (see term (1a)), values larger than a thousand indicate that some interventions are left unscheduled. The results that are better than UB are shown in bold print.

Since our algorithm is also a randomized one like ACI, we chose to initially perform 100 runs to show whether the heuristic can obtain better results. A run of the 2PSC-EM heuristic takes about ten seconds. Under the 2PSC-EM (100) heading, we show the minimum value we obtain and the percentage (U B -M in)/U B in the Min and Mi2UB columns, respectively.

In eight out of ten instances the 2PSC-EM heuristic obtains better results. For the eight instances for which all the interventions are scheduled using the ACI approach and the proposed 2PSC-EM heuristic, we improve UB up to 16% and 9% on average. Except for the a_05 and the a_08 instances for which neither the ACI nor the 2PSC-EM heuristic succeeded in scheduling all the interventions, the 2PSC-EM heuristic that we propose provides better results. These preliminary results using the 2PSC-EM heuristic show that better results are achieved. However, in some cases, some interventions are still left unscheduled. A more effective approach is to be investigated with the aim of scheduling all the interventions, when possible.

The 2PSC-EM heuristic can potentially provide good initial solutions to the ALNS approach that we propose to study here. However, we cannot spend too much processing time to obtain these solutions. We therefore perform another series of experiments where we limit the number of runs to show whether good initial solutions can be obtained using the heuristic using a limited amount of time, while not significantly worsening the quality of the solutions. Since the heuristic is a randomized method, we performed several experiments of k runs. We experimentally observed that k = 3 runs seems to be a good trade-off between solution quality and processing time.

In Table 2 under the heading 2PSC-EM (3), we show the best results obtained using the 2PSC-EM heuristic when performing three runs of the heuristic ten times. In seven out of ten instances, the 2PSC-EM heuristic still obtains better results. A small degradation is observed for the instance a_01 compared to UB. For the eight instances for which all the interventions can be scheduled, the proposed 2PSC-EM heuristic still improves UB up to 14% and 7.1% on average. As can be shown, slightly better results can be achieved using 100 runs of the 2PSC-EM heuristic compared to three runs, but it takes a while to obtain them. We experimentally observed that three runs are sufficient to obtain adequate solutions within a short processing time.

We propose the ALNS approach with the aim of scheduling all the interventions and improving the results of the 2PSC-EM heuristic. As initial solutions of the ALNS approach, we use the best solution computed using three runs of the 2PSC-EM heuristic below.

Parameter tuning

We present the experiments we carried out to find the parameter values that were used to test our ALNS approach. As described in Section 5.1, the ALNS that we propose has four sets of parameters:

• D limit , the maximum number of patients removed by the destroy operators;

• ∆ Dev and Iter D , the record-deviation increment and the number of iterations without improvement before increasing the deviation;

• σ 1 , σ 2 , σ 3 , p u , and l, the first three are the added scores after using a destroy or repair operator, p u is the number of iterations before adjusting the weights of operators, and l is the reaction factor;

• Iter max , the maximum number of iterations without improvements.

Some of these parameters are computed during the course of the ALNS algorithm according to some characteristics of the instance being processed or are relative to other parameters. For these parameters, the first column in Table 3 shows the parameters as presented in Section 5.1. The second column describes how they are computed and the related parameters that need to be tuned.

Computed as, and parameters to be tuned To calibrate all the parameters, we carried out preliminary experiments on a subset of five instances that are randomly selected from the eight benchmark instances for which all the interventions can be scheduled. Since ALNS is a randomized search method, the experiments were repeated five times with a different random seed. To tune the parameters, we evaluate the results using the Relative Percentage Error (RPE). We define the RPE as follows:

RP E = 100 × Z best -Zmax Z best
where Z best denotes the best result we achieved over all the runs we performed for an instance, and Z max denotes the best result we obtained among the five performed runs. Next, the RPE values are averaged for the five instances chosen at random, and this average is shown as a percentage in the figures we present and that we comment on below.

We start by tuning the first D limit , and we then tune each parameter, one after the other, considering the four sets of parameters presented. The initial values we use to first tune D limit are ∆ Dev = 0.2, δ = 0.2, σ 1 = 50, θ = 0.3, φ = 0.1, p u = 60, l = 0.5 and γ = 10. Then, to tune a parameter, we retain the best setting of the other parameters found before proceeding to tune it.

The maximum number of patients to be removed D limit

We performed the tuning experiments by varying α from 0.1 to 1.0 with a step of 0.05. In Figure 1, we show that when α is lower than 0.2, the number of interventions removed from the solution is too small, so the neighborhood exploration is insufficient. When α is larger than 0.35, the number of interventions removed from a current solution increases. The diversification increases so the quality of the solutions is worsened, as can be seen by the average RPE values. As could be expected, the processing time increases with the α value, so we do not show a curve of CPU time vs α. The larger the values of α are, the larger the processing times are, which is ineffective. We chose α = 0.3, which is a good trade-off between solution quality and processing time.

Record-to-record-based adaptive acceptance strategy; tuning of ∆ Dev and Iter D

To calibrate the value of ∆ Dev we varied it between 0.0% and 2.5% with increments of 0.02%. In Figure 2, we show that when ∆ Dev varies between zero and 0.1%, the RPE decreases. We then reach a plateau of the curve for three values that give the smallest value of RPE. Next, the average RPE values increase as ∆ Dev increases. We observe this same phenomenon for values of ∆ Dev larger than 0.4%; consequently, values larger than 0.4% have not been shown in Figure 2. We fix the value of ∆ Dev = 0.1% for the record-deviation increment. It is the smallest value for which the average RPE value is minimum.

We then proceed to the tuning of δ for Iter D , the number of iterations without improvement before the deviation increase. In Figure 3, three good values of δ can be chosen; the first is 0.12. If Iter D is small, the allowed solution S i , the current solution S cur , and the best solution found so far, S best , we chose to first set σ 1 to 50 and we compute σ 2 = θ.σ1 and σ 3 = φ.σ 2 such that θ, φ ∈ [0, 1].

Figure 4 shows the beginning of the curve that we obtain to better focus on the interesting values. We chose θ = 0.3 and φ = 0.2, the first value giving the best performance relative to the average RPE.

To tune p u , the number of iterations before adjusting the weights of operators, we vary it between 0 and 200 iterations with a step of 5. Figure 5 shows that the RPE is better when p u is between 70 and 85, and we chose to set p u to 70.

To find the best value of l, the reaction factor that controls the influence of the recent success of an operator on its weight, we vary it between 0 and 1 with an increment of 0.1. The average RP E values shown in Figure 6 reveal that good solutions are achieved when l is between 0.6 and 0.8. The previous iteration seems to have a little influence on the weight calculation. We chose to fix l at 0.7.

Maximum number of iterations without improvement; tuning of Iter max

Finally, we proceed to the tuning of Iter max , the maximum number of iterations without improvement. The processing time needed to find a good quality solution varies according to the instances and this parameter has an important impact. We chose to formulate Iter max as γ As would be expected, the average RPE decreases as γ increases, and, the processing time increases with the γ value. Therefore, for the sake of compactness, we do not show curves for the γ tuning. For RPE, the shape of the curve has an asymptotic behavior like a 1/x one. The larger the values of γ are, the greater the processing times are, which is ineffective. We chose γ = 11, which is a good trade-off between solution quality and processing time and that generally remains lower than 250 s.

The final calibration results are α = 0.3, ∆ Dev = 0.1%, δ = 0.1, σ 1 = 50, θ = 0.5, φ = 0.2, p u = 70, l = 0.7 and γ = 11. The values of the parameters are used in the sequel for our experiments on all the benchmark instances. They were chosen to obtain a good trade-off between solution quality and processing time.

Evaluation of the ALNS components

We evaluate here the effectiveness of the destruction/repair operators and of the adaptive mechanism for destruction/repair by disabling each of them one at a time. This allows us to discuss the results to show whether a component contributes to obtaining good solutions by also considering the processing time.

In Table 4, we show the results for the four destruction operators (see Section 5.2). Under each heading, we show the minimum values (Min column) and the average processing times in seconds (t(s) column) that we obtain within 10 runs.

For comparison purposes, we tabulate under the ALNS heading the values that we obtain running the ALNS with all of components activated (also in Table 5). The ALNS without Random Removal (No RR column) obtains results that are below those of ALNS using all of the components. The RR destruction operator is necessary, and the patients' interventions chosen at random make it possible to avoid being stuck in a local optimum. This is especially the case for the instances a_05 and a_08 for which we cannot schedule all the interventions if RR is disabled. The processing times are shorter but we experimentally observe that the ALNS with no RR stops because we perform Iter max iterations without any improvement.

ALNS

The ALNS without Worst Removal (No WR column) obtains results that are below those of ALNS using all of the components. For all instances, all the interventions can be scheduled but at the expense of larger processing times. The WR destruction operator is necessary. It is a performance-oriented destruction operator that aims at minimizing the objective function, which is necessary to obtain better overall performances.

The Random Day Removal (RDR) and Worst Day Removal (WDR) are day oriented destruction operators that make it possible to reallocate resources within one day. The ALNS without Random Day Removal (No RDR column) obtains results that are below those of ALNS using all of the components except for instances a_04 and a_07 for which we attain the same best results. The RDR destruction operator is necessary, although for all instances for which all the interventions can be scheduled we, observe that it is at the expense of larger processing times.

The ALNS without Worst Day Removal (No WDR column) obtains results that are below those of ALNS using all components except for instance a_09 for which we attain the same best result. For all instances, all the interventions can be scheduled but at the expense of larger processing times, so WDR is necessary too.

To summarize, the four destruction operators are necessary. They are beneficial for exploring the neighborhood of a solution either by obtaining better results or by shortening the processing time. .64 116.25 20.70 226.27 20.76 141.14 20.75 149.44 20.85 238.43 a_02 19.41 119.86 19.42 259.44 19.49 117.86 19.45 120.27 19.59 240.48 a_03 22.13 117.25 22.43 363.59 22.18 256.03 22.21 284.99 22.27 216.09 a_04 20.37 129.81 20.41 187.91 20.38 144.80 20.43 161.11 20.37 532.06 a_05 23.77 1109.92 24.35 3777.95 24.28 3680.23 24.55 4328.10 28.37 .33 20.34 188.63 20.35 115.90 20.37 104.35 20.35 236.90 Table 5: Impact of repair operators UIF, NRM and AC, and, impact of adaptive mechanism.

In Table 5, we show the results for the three repair operators (see Section 5.3) and for the adaptive mechanism (see Section 5.4) that manages the choice of destruction and repair operators.

Overall, for the three repair operators, Unscheduled Interventions First (UIF), Number of Requested Modes (NRM) and Aggregation of Criteria (AC), we first observe that none succeeded in attaining the results of the ALNS approach using all of the components, and, second, that processing times are generally larger. This is especially the case for the instances a_05 and a_08.

To summarize, the three repair operators are necessary, and are beneficial for exploring the neighborhood of a solution either by obtaining better results or by shortening the processing time.

The last experiment was conducted to highlight how efficient the adaptive mechanism is. We disabled this mechanism by fixing the same probability for every destruction operator (1/4) and the same probability for every repair operator (1/3).

As can be seen in No Adaptive column, we obtain results that are below those of ALNS that uses this component, and the processing times are greater. This is particularly evident for instances a_05 and a_08 for which without this adaptive mechanism we obtain the worst processing times of these series of experiments. The adaptive mechanism that manages the choice of destruction and repair operators during the course of the ALNS is necessary to achieve good results within good processing time for the elective patient admission planning problem that we address here.

Comparison of ALNS with the literature

In Table 6, for each instance under the ACI heading, we show the results obtained by ACI (see [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]). Column UB shows the best known value, or upper bound, and columns Min, Max, Avg show the minimum value, the maximum value and the average value. Under the ALNS heading, we also show the Min, Max and Avg values that we obtained. Column t(s) shows the average processing times in seconds. We show the results that are better than UB in bold print. For comparison purposes, we use (M in-Avg)/Avg denoted in column headings as Mi2Av and (U B -M in)/U B denoted in column headings as Mi2UB.

The Mi2Mi column shows the (M in(ACI) -M in(ALN S))/M in(ACI) values. The first allows us to show how close to the minimum the average results of ACI or of ALNS (for ten runs) are for each instance, whereas the second shows how far the results are from the best known UB value. The first is only really significant for instances for which all interventions can be scheduled. As a matter of fact, the objective function (see Equation ( 1a)-( 1c)) is a weighted sum of normalized terms. The weight W un used for the term that assesses the interventions left unscheduled is the largest compared to the others. This clearly shows that unscheduled interventions are a key issue of great concern. It is not fair to compare the results of instances for which all interventions are scheduled to those for which some are left unscheduled because the highest term is null in the first case. We added an asterisk to the instance names for which both ACI and ALNS succeeded in scheduling all the interventions. For these instances, the last row then shows the average values of Mi2Av, Mi2UB and Mi2Mi, and the average value of processing time of ALNS.

For the eight instances in which both ACI and ALNS succeeded in scheduling all the interventions, the ALNS outperforms the ACI approach. The averaged Mi2Av is about halved, the Mi2UB is improved by about 10.2%, and the Mi2Mi is improved by about 11.2%. The processing times are shorter than the timeout fixed in [START_REF] Riise | Modelling and solving generalised operational surgery scheduling problems[END_REF]. For the two instances for which the ACI approach failed to schedule all the interventions the ALNS succeeded. For the a_08 instance, it takes about five minutes and, for the a_05 instance, it takes about 20 minutes. Better results are obtained for each instance, all the patients' interventions are scheduled which had not been done using the ACI algorithm.

Conclusions and future work

In this paper, we address the patient admission problem for which surgical interventions of hundreds of patients have to be scheduled within a horizon based on several months. The issue faced by hospital planners is to schedule all the interventions while considering operating room and surgeon availability, in addition to the constraints related to each patient's surgical intervention. We introduce a two-phase 2PSC-EM heuristic and an Adaptive Large Neighborhood Search (ALNS) approach, both dedicated to the patient admission problem. The ALNS makes use of the adaptive mechanisms for destruction, construction and acceptance procedures that we investigate for the patient admission problem. A good trade-off between an adaptive diversification mechanism and an adaptive acceptance mechanism is needed so as not to waste processing time by exploring unnecessary low quality solutions.

Computational experiments are conducted on benchmark instances from the literature. Computational results show that the 2PSC-EM heuristic achieved better results than a general purpose approach not dedicated to the admission problem, whereas both heuristics fail in scheduling all interventions for some instances. The experiments concerning the parameter tuning of the ALNS approach can be easily conducted to obtain a good trade-off between solution quality and processing time. Computational experiments are to evaluate the effectiveness of each component of the ALNS approach, and all the components are necessary to obtain good solutions within good processing times.

The ALNS approach obtains better results for each instance, i.e, all the interventions are scheduled and the patients' health constraints for interventions are better respected.

One instance required about 20 minutes, all other instances are processed in A future research direction would be to consider additional objectives and constraints on minimum and/or maximum workloads for surgeons or on operating rooms use to obtain balanced schedules with regard to the use of resources. Fairness between surgeons is a sensitive issue for a hospital organization and load balancing of the rooms may also be useful.

  r s indice of a surgeon and r r indice of a room; these are all the combinations of surgeons and operating rooms; M p , set of feasible modes m for the surgical intervention of patient p; ϕ k , fixed starting time of resource interval k; σ k , latest end time of resource interval k;

  t p , the non-negative starting time of the surgical interventions of patient p; z pp = 1, if the surgical intervention of patient p precedes the surgical interventions of patient p , and 0 otherwise; c p , completion time of the surgical interventions of patient p; g i p = 1, if the surgical intervention of patient p uses resource i in the chosen mode, and 0 otherwise; h p = 1, if the surgical intervention of patient p is unscheduled, and 0 otherwise.

  Given a destroy operator O des , the function Destruction(S cur , k, O des ) (see Algorithm 2) returns S i , the incumbent solution with the removed interventions, and L des the list of removed interventions. The destruction operators we investigated are: RR Random Removal (intervention/patient-oriented); WR Worst Removal (intervention/patient-oriented); RDR Random Day Removal (day-oriented); WDR Worst Day Removal (day-oriented). Random Removal removes k surgical interventions at random from the solution and inserts them one after the other in L des . This can be done in constant time. Worst Removal first assesses then sorts the interventions in decreasing order of cost; see equations (1a)-(1c). This can be done in O(|P | • ln(|P |)). Next, the k surgical interventions with the highest planning cost are removed. The planning cost of a patient p is assessed by the cost difference, assuming the withdrawal of the patient's intervention in the solution. This aims at decreasing the cost. Random Day Removal selects one day in the planning horizon at random. Next, all the interventions scheduled for this day are removed from the solution. At most this can be done in O(|P |). Worst Day Removal first assesses all the scheduled interventions for each day, and then sorts the days in decreasing order of cost. Next, all the interventions for the day having the highest planning cost are removed from the solution. This can be done in O(|P | • ln(|P |)).

  | P | |M | where P is the set of interventions (i.e., patients) already scheduled and M is the possible modes that can be used. It is mainly proportional to the average number of scheduled interventions per mode that are used by the instance. Since | P | ≤ |P | when a number of interventions are left unscheduled in solutions, this favors the adaptive acceptance strategy of low-quality solutions in order to find solutions where all interventions are scheduled. Since it increases as the number of scheduled interventions increases, it then makes it possible to better explore the neighborhood of solutions.

  Initially computing S sr(ti) takes O(H • |P |) iterations, next S sr(ti) is updated in constant time during the course of the ALNS algorithm. The objective is to schedule as many interventions as possible while minimizing the cost. The algorithm uses the incumbent solution S i and an ordered/prioritized list of interventions to be scheduled, denoted as L itbs . The list L itbs contains the interventions left unscheduled of L u and the interventions of L des that have been removed by applying one of the four destruction operators. Given an initial L itbs list, the BIA takes O(H • |P |).The way that interventions are ordered in L itbs has an impact on how many interventions can be scheduled using the set S sr(ti) of available resources within intervals. We propose and look into three different ways of building the order of interventions in L itbs . They are presented below.Algorithm 3 first resets L u to obtain the list of interventions left unscheduled for the forthcoming iteration of ALNS. Given a prioritized list L itbs , we attempt to insert the interventions one by one in the incumbent solution S i . For an intervention p, we first determine the modes m = (s, r) ∈ M p and the associated intervals I from among the set of triplet S sr(ti) that can be used to schedule

  behind list L u to obtain the initial list L itbs . We then propose three ways of ordering/prioritizing interventions in L itbs : UIF Unscheduled Interventions First; NRM sorted in ascending order of the Number of Requested Modes; AC sorted in ascending order of an Aggregation of Criteria. Computing the list L itbs takes at most O(|P | • ln(|P |)). The first repair operator UIF aims at giving priority to the unscheduled interventions remaining in L u . The idea is to free resources by applying a destruction operator to first schedule the interventions of L u , we then schedule the interventions of L des .

  parameter α to be tuned σ1, σ2, σ3 σ1 fixed, next σ2 = θ.σ1 and σ3 = φ.σ2 parameters (θ, φ) to be tuned Iter D δ.Itermax, parameter δ to be tuned Itermax γ |P \ P | |R| +1 . | P | |R| , parameter γ to be tuned

Figure 1 :

 1 Figure 1: Tuning of D limit , effect of α on RPE.

Figure 2 :

 2 Figure 2: Tuning of ∆ Dev , effect of on RPE.

Figure 3 :

 3 Figure 3: Tuning of Iter D , effect of δ on RPE.

Figure 4 :

 4 Figure 4: Tuning of σ 2 and σ 3 relative to σ 1 , effect of θ and φ on RPE.

|P

  / P | |R| +1 • | P | |R| where α ∈ [1, 10], | P | is the number of scheduled interventions, |P/ P | is the number of unscheduled ones and |R| is the number of resources.

a

  hundred seconds. It would be interesting to investigate new solution methods to reduce processing time. One possible research trail is to experiment other approaches based on other metaheuristics or by integrating learning methods as overviewed in Karimi-Mamaghan et al. (2022), Bengio et al. (2021) and Queiroz dos Santos et al. (2014).

  Algorithm 2: Adaptive Large Neighborhood Search (ALNS) algorithm Input : S0 initial solution, Lu list of interventions left unscheduled Output : S best the best solution found, Lu list of interventions left unscheduled Parameters: D limit limit for diversification degree Itermax maximum number of iterations without any improvement Variables : Scur current solution, i number of iterations Dmax maximum number of interventions to remove on several days O des selected destruction operator, Orep selected repair operator k number of interventions to remove on several days Si incumbent solution 1 S best , Scur ← S0 // Initialize best and current solution 2 i ← 0 3 Dmax ← 3 4 while i < Itermax do des ) then k ← rand(1, Dmax) // remove k interventions on several days, or all interventions of a day 8 (Si, L des ) ← Destruction(Scur, k, O des ) Construction(Si, L des , Lu, Orep) // insert as many interventions as possible // Acceptance procedure on Si, incumbent solution

	5	O des ← SelectDestructionOperator() // select a destruction operator
	6	k ← 1

7 if ¬DayDestroy(O 9 Orep ← SelectRepairOperator() // select a repair operator 10 Si ← 11 if Accept(S best , Si) then 12 Scur ← Si // Si is accepted as the new current solution 13 i ← 0 14 else 15 i ← i + 1 16 if Obj(Si) < Obj(S best ) then 17 S best ← Si // A new best solution is found 18 Dmax ← 3 19 else // Update maximum adaptive diversification degree 20 if ¬DayDestroy(O des ) then Dmax ← min(Dmax + 1, D limit ) // Update weights of the two roulette wheels (Destruction/Repair) 21 AdaptiveW eightsAdjustment(S best , Scur, Si) 22 return S best , Lu

  | P | |R| increases, the average number of scheduled interventions per resource. This allows us to spend more processing time when all interventions are scheduled to better improve the terms O wt and O em of the objective function. However, we also need to have a larger number of iterations when interventions are left unscheduled in order to schedule all interventions. The term γ

|P \ P | |R| +1 is equal to the value of parameter γ when all interventions are scheduled since |P \ P | is zero because the set of interventions left unscheduled is empty, but it is larger when many interventions are left unscheduled.

Table 2 :

 2 2PSC-EM heuristic, 100 runs and three runs, compared to ACI.

			ACI			2PSC-EM (100)		2PSC-EM (3)
		UB	Min	Mi2UB% t(s)	Min	Mi2UB% t(s)	Min	Mi2UB% t(s)
	a_01	21.58	21.85	-1.27	600	21.15	1.97	1319	22.00	-1.94	42.0
	a_02	22.83	23.25	-1.83	600	19.72	13.63	1335	20.32	11.01	40.0
	a_03	24.52	24.58	-0.26	600	22.55	8.02	918	22.66	7.81	31.2
	a_04	21.97	22.28	-1.40	600	20.43	7.02	958	20.62	6.16	29.7
	a_05	5113.88 6341.84	-24.01	600	11025.10 -115.59	934	13025.30 -154.71 28.2
	a_06	23.55	23.55	0.03	600	22.15	5.97	991	22.68	3.72	31.6
	a_07	22.73	23.25	-2.28	600	21.98	3.31	1026	22.44	1.28	30.0
	a_08	2086.32 3148.49	-50.91	600	5024.88 -140.85	797	10024.70 -380.50 23.9
	a_09	24.83	24.99	-0.64	600	20.75	16.43	926	21.23	14.50	29.2
	a_10	24.48	24.74	-1.08	600	20.61	15.83	935	20.92	14.53	25.9

Table 3 :

 3 Parameters α, θ, φ, δ and γ to be tuned.

Table 4 :

 4 Impact of destruction operators RR, WR, RDR and WDR.

Table 6 :

 6 ALNS compared to ACI

					ACI				ALNS
		UB	Min	Max	Avg Mi2Av% Mi2UB% t(s) Min	Max	Avg Mi2Av% Mi2UB% Mi2Mi% t(s)
	a_01 *	21.58 21.85 22.23 22.06 0.95	-1.25 600 20.64	20.94 20.77 0.63	4.36	5.54	116.25
	a_02 *	22.83 23.25 23.56	23.4 0.64	-1.84 600 19.41	19.60 19.53 0.61	14.98	16.52	119.86
	a_03 *	24.52 24.58 24.88 24.74 0.65	-0.24 600 22.13	22.49 22.28 0.67	9.75	9.97	117.25
	a_04 *	21.97 22.28 22.66 22.48 0.89	-1.41 600 20.37	20.48 20.45 0.39	7.28	8.57	129.81
	a_05	5113.88 6341.85 9397.78 7987.31 20.60	-24.01 600 23.77 4024.46 1425.0 98.33	99.54	99.63 1109.92
	a_06 *	23.56 23.56 24.03 23.82 1.09	0.00	600 22.30	22.44 22.41 0.49	5.35	5.35	72.59
	a_07 *	22.73 23.26 23.57 23.39 0.56	-2.33 600 21.44	21.62 21.54 0.46	5.68	7.82	93.54
	a_08	2086.32 3148.49 4244.57 3407.31 7.60	-50.91 600 22.59	4023.4 423.21 94.66	98.92	99.28	548.21
	a_09 *	24.83 24.99 25.98 25.37 1.50	-0.64 600 20.52	20.64 20.60 0.39	17.36	17.89	77.80
	a_10 *	24.47 24.75	25.1	24.9 0.60	-1.14 600 20.33	20.42 20.36 0.15	16.92	17.86	78.33
	for '*'				0.86	-1.11			0.47	10.21	11.19	100.67

Acknowledgements

This work was supported by the OIILH project (Optimisation Inter et Intra Logistique Hospitalière) managed by the National Agency for Research (Reference ANR-18-CE19-0019). It was also supported by the Labex MS2T, funded by the French Government, via the program "Investments for the future" managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02).

Data availability statement

The data that support the findings of this study are openly available in "Generalised Surgery Scheduling Data" at http://www.sintef.no/projectweb/health-

deviation rapidly increases and the algorithm accepts poor quality solutions. On the other hand, if Iter D is large, the deviation does not increase as much and the algorithm will be trapped in a local optimum. We chose δ = 0.12. Adaptive weight adjustment parameters; tuning of σ 1 , σ 2 , σ 3 , p u and l We first tune the weight adjustment parameters σ 1 , σ 2 , σ 3 , the scores added 1015 after the use of a destruction or repair operator. Given that σ 1 > σ 2 > σ 3 according to the usual reward of operators relative to the quality of the incumbent

Disclosure statement

The authors report there are no competing interests to declare.