Simon Caillard
email: simon.caillard@u-picardie.fr

Laure Brisoux Devendeville
email: laure.devendeville@u-picardie.fr

Corinne Lucet
email: corinne.lucet@u-picardie.fr

Laure Brisoux Devendeville

Local Search for a Planning Problem with Resource Constraints in Health Simulation Center

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

In recent years, research into development of scheduling solutions in the healthcare sector has become increasingly important. These works discuss problems related to patient service quality, optimization of resource management and, as in our case, training time for health professionals. The training center SimUSanté located in Amiens, France, is one of the biggest multidisciplinary active pedagogy centers in Europe. This center is used by all kinds of health actors: professionals, students, patients and carers. The aim of this center is to provide a space where all of its actors can meet and train together by simulating medical acts in various fields of healthcare (such as surgical operations, blood sampling, cardiopulmonary resuscitation, etc.), but also attending regular courses. Thus, the number of different variables such as the number of activities, resources, and employees, their skills, and the number of operating rules might come to be important and become a problem when constructing a coherent and effective schedule.

The purpose of our collaboration with the SimUSanté center is to study possible solutions to management and planning problems they encounter in all their activities. First, we presented and formalized the SimUSanté problem and we proposed a mathematical model related to the model presented in [START_REF] Brucker | Resource-Constrained Project Scheduling and Timetabling[END_REF]. A dedicated greedy algorithm SimU G is proposed in order to provide a first suitable and compact solution in a short time. Then, a local search algorithm SimU LS was added to improve solutions obtained by SimU G. It is suited to being used over a short search time (less than 2 hours) and then uses strong diversification operators combined with an isolated tabu system when the regular diversification phase occurs. During intensification phases, it generates several neighborhood solutions from a selected operator and uses random proportionality rules to accept continuing the search from one of these neighbors. Because there is no realistic benchmark to our knowledge of the SimUSanté problems, we have generated adequate instances [START_REF] Caillard | Health Simulation Center Simusanté ® 's Problem Benchmarks[END_REF] inspired by those used in the Curriculum-Based Courses Timetabling problem [START_REF]High School Timetabling Project[END_REF] to train our algorithms. We compared SimU G and SimU LS with the results worked out by our mathematical model implemented in CPLEX.

The paper is organized as follows. Section 2 presents a state-of-the-art related to issues close to the SimUSanté problem. In section 3, we describe and formalize the scheduling problem encountered by SimUSanté. The corresponding mathematical model is presented in section 4. In section 5 we present our greedy algorithm SimU G and give the different selection criteria of the construction process. In section 6, we introduce our local search algorithm SimU LS and describe the movement operators used. Section 7 explains the instance generation and provides computational results. Section 8 concludes this paper with some final remarks.

State of the art

Timetabling is an important field of research which has many applications in real life problems, like hospitals, universities, airports, etc. Most of the time, scheduling is a difficult process that needs to be done in several stages and requires coordination and communication between the different groups involved: students, teachers, administrative department and heads of services for university timetables for example. In this paper, we are concerned with educational timetabling. Historically, these kinds of problems have been grouped into three categories: examination timetabling problems (ETP), school timetabling problems (STP) [START_REF] Pillay | A survey of school timetabling research[END_REF] and university course timetabling problems (UCTP) [START_REF] Babaei | A survey of approaches for university course timetabling problem[END_REF]. All these problems are NP-Hard [START_REF] Cooper | The Complexity of Timetable Construction Problems[END_REF]. They are defined as a classroom assignment [START_REF] Carter | When is the classroom assignment problem hard?[END_REF] or a course assignment problem [START_REF] Carter | Recent developments in practical course timetabling[END_REF]. In recent years, a wide variety of articles related to educational scheduling problems have been published, as shown in many surveys [START_REF] Schaerf | A Survey of Automated Timetabling[END_REF][START_REF] Lewis | A Survey of Metaheuristic-Based techniques for University Timetabling problems[END_REF][START_REF] Mazlan | A Study on Optimization Methods for Solving Course Timetabling Problem in University[END_REF]. The UCTP has been mostly studied [START_REF] Bashab | A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms[END_REF] and considers many constraints [START_REF] Al-Betar | University course timetabling using a hybrid harmony search metaheuristic algorithm[END_REF] that can be classified in two sets. The constraints that must be satisfied are called hard constraints and make the schedule feasible. The soft constraints are optional and their optimization ensures timetables of high quality [START_REF] Akkan | A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem[END_REF]. Although similar in many ways, UCTP can vary from one institution to another, with the addition of specific constraints. With the growing interest in this area, two international competitions have been organized: International Timetabling Competition (ITC-2002 [START_REF] Paechter | International Timetabling Competition 2002[END_REF] and ITC-2007 [START_REF] Mccollum | International Timetabling Competition 2007[END_REF]). The objective of ITC-2002 was to formalize problem definition for the university course timetabling problem, and to generate some instances related to it. In ITC-2007, university course timetabling problems have been split into two subproblems [START_REF] Mccollum | Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition[END_REF]: Post-Enrolment-based Course Timetabling (PE-CTT) and Curriculum-Based Course Timetabling (CB-CTT) and one of the aims of the competition was to reduce the differences between practice and research in educational scheduling problems [START_REF] Mccollum | A perspective on bridging the gap between theory and practice in university timetabling[END_REF]. The SimUSanté problem is an extension of CB-CTT [START_REF] Gaspero | The Second International Timetabling Competition (itc-2007): Curriculum-Based Course Timetabling (track 3)[END_REF]. A curriculum is the set of lectures that students follow and a course is composed by one or many lectures. The problem consists of finding the best weekly assignment for lectures, available rooms, time periods, etc. for a set of curricula while respecting a set of constraints. Even though the hard constraints are roughly the same, the case of SimUSanté differs in some points from the CB-CTT: in SimUSanté, there are no periodic schedules and we do not consider many soft constraints. However we need to consider lectures with room, time and precedence constraints. We also need to take into account different types of resources (rooms have specific characteristics like surgical block, pharmacy, etc.), different types of skills needed to perform lectures, resources with multi-types, scheduling of lunch breaks, etc.

Due to its importance, many approaches have been studied to solve UCTP and its subproblems. Most of them are optimization methods and give optimal or near optimal results. The ITC-2007 instances are often used as UTCP benchmarks to compare proposed methods. These approaches are split into two categories: exact method and metaheuristics. Only a few exact methods exist in the literature to solve UTCP. The Integer Linear Programming (ILP) approach is an exact method which uses a mathematical model to solve an objective function [START_REF] Phillips | Integer programming for minimal perturbation problems in university course timetabling[END_REF][START_REF] Schimmelpfeng | Application of a real-world university-course timetabling model solved by integer programming[END_REF][START_REF] Mirhassani | A computational approach to enhancing course timetabling with integer programming[END_REF]. The ILP given in [START_REF] Burke | Penalising Patterns in Timetables: Novel Integer Programming Formulations[END_REF] is adapted to the CB-CTT and can be used with a generic solver. In [START_REF] Lach | Curriculum Based Course Timetabling: New solutions to Udine benchmark instances[END_REF], a two-step ILP is used to solve the CB-CTT. The first step assigns lectures to time periods, without taking into consideration rooms, minimizing penalties for curriculum compactness and working days. The second one assigns lectures to rooms. A generalized ILP method for the CB-CTT, which is able to handle most of the ITC-2007 instances is presented in [START_REF] Kristiansen | Integer programming for the generalized high school timetabling problem[END_REF]. The graph coloring approach has also been used. In [START_REF] Badoni | A graph edge colouring approach for school timetabling problems[END_REF], they use an edge coloring graph algorithm to first distribute resources to classes and then set time slots for each of them.

Metaheuristics used to solve UTCP can be divided into two groups. The first one concerns local search-based methods [START_REF] Abuhamdah | Population based local search for university course timetabling problems[END_REF][START_REF] Gaspero | Multi-neighbourhood local search with application to course timetabling[END_REF]. They are characterized by the definition of several different neighborhood operators allowing switching from one solution to another (changing the time period assigned to a lecture, or the room assignment for a lecture, etc.). They are often composed of several phases. The first one builds an initial solution and the others explore the neighborhoods to improve it, as shown in [START_REF] Müller | Itc2007 Solver Description: A Hybrid Approach[END_REF]. They use different mechanisms to avoid being trapped in a local minimum. In these kinds of methods, we found simulated annealing (SA) [START_REF] Bellio | Feature-based Tuning of Simulated Annealing Applied to the Curriculum-Based Course Timetabling Problem[END_REF][START_REF] Goh | Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem[END_REF], tabu search (TS) [START_REF] Clark | QuikFix-A Repair-based Timetable Solver[END_REF][START_REF] Islam | University timetable generator using tabu search[END_REF][START_REF] Muklason | Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm[END_REF], great deluge (GD) [START_REF] Kuan | Comparison of simulated annealing and great deluge algorithms for university course timetabling problems (uctp)[END_REF], hill climbing (HC) [START_REF] Yusoff | Evaluation of genetic algorithm and hybrid genetic algorithm-hill climbing with elitist for lecturer university timetabling problem[END_REF], etc. In [START_REF] Abuhamdah | Population based local search for university course timetabling problems[END_REF], authors proposed a local search algorithm that starts from an initial solution and generates a set of neighborhood solutions with the aid of eight classic neighborhood operators stemmed from the literature [START_REF] Abdullah | Heuristic approaches for university timetabling problems[END_REF][START_REF] Thompson | Variants of simulated annealing for the examination timetabling problem[END_REF]. Each of these solutions is compared to the current best solution in order to determine the more promising search space. From this, the best solution is selected and the process is iterated until a new best solution is found or if there is no further improvement. In [START_REF] Gaspero | Multi-neighbourhood local search with application to course timetabling[END_REF], a multi-neighbourhood local search is used. The method starts with the first neighbourhood operator and when it has found its best local optimum, starts the search again with the second neighbourhood operator from this new best local optimum. This procedure is then repeated over many iterations. With limited running time, it seems to be better to use local search with robust diversification operators [START_REF] Lü | Adaptive tabu search for course timetabling[END_REF] like those proposed in [START_REF] Lourenço | Iterated Local Search[END_REF]. In [START_REF] Muklason | Automated course timetabling optimization using tabu-variable neighborhood search based hyper-heuristic algorithm[END_REF], a tabu search hybridized with a variable neighborhood search is used. It starts from an initial solution obtained by a greedy algorithm and generates several neighborhood solutions using shaking operators. A solution is accepted or set in tabu list. A solution is accepted if it is better than the current best one or if it satisfied an acceptance criteria. Then the search continues from here, generating new neighborhood solutions.

The second group is that of population-based methods, which are often bioinspired approaches. They consider many solutions at the same time which are combined to obtain better ones. In these kinds of methods, we found: Ants Colony Optimization (ACO) [START_REF] Mazlan | University course timetabling model using ant colony optimization algorithm approach[END_REF], Genetic Agorithms (GA) [START_REF] Gozali | Solving university course timetabling problem using localized island model genetic algorithm with dual dynamic migration policy[END_REF], Particle Swarm Optimization (PSO) [START_REF] Imran Hossain | Optimization of university course scheduling problem using particle swarm optimization with selective search[END_REF], etc. Local search based and population based algorithms have two disadvantages [START_REF] Blum | Metaheuristics in combinatorial optimization: Overview and conceptual comparison[END_REF][START_REF] Stützle | Stochastic local search-foundations and applications[END_REF]: early convergence and being stuck in a local optimum, so hybrid approaches which combine the two procedures have often been used [START_REF] Blum | Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison[END_REF][START_REF] Kenekayoro | Greedy Ants Colony Optimization Strategy for Solving the Curriculum Based University Course Timetabling Problem[END_REF][START_REF] Matias | Examining Genetic Algorithm with Guided Search and Self-Adaptive Neighborhood Strategies for Curriculum-Based Course Timetable Problem[END_REF].

We also propose a local search algorithm to solve the SimUSanté problem. Indeed, this kind of algorithm is adapted to real problems and gives good results in a short time. Nevertheless the quality of the solutions mainly relies on the quality of the neighborhood operators. In this sense, we have developped several operators dedicated to the SimUSanté problem, whose principles nevertheless remain applicable to similar planning problems.

SimUSanté: a planning problem with resource constraints

In such a large center of multidisciplinary active pedagogy as SimUSanté, there are a lot of activities, grouped into training sessions, with some precedence constraints, specific skill requirements and specific room equipment. Moreover, because SimUSanté is a simulation center, the room facilities are both varied and flexible. Planning all activities while respecting the various constraints is an issue of primary importance for the proper functioning and success of such a center. It is important to schedule as many activities as possible in sessions and that session timetables are compact. This minimizes the number of days for learners and teachers. First let's formally define the data problem: We denote Λ = Λ r ∪ Λ e . Each resource can have more than one associated type. For example, a room may be equipped with artificial arms for the simulation of taking blood, but also with artificial vertebral columns for the simulation of lumbar punctures. We denote R λ i = the set of resources of type λ i , and qtav t λ i the quantity of resource λ i available at time slot t. All activities scheduled at time slot t cannot use more than the available resources. Each employee e ∈ R e is associated with a set of types Λ e and their availability at each time slot is taken into account by isavailable t e which is equal to 1 if employee e is available at time slot t and 0 otherwise. Activities: Let A be the set of activities and s a the session to which a belongs.

Each activity a ∈ A is characterized by a duration duration a , an earliest starting date ES a and latest starting date LS a . qtreq a λ i is the quantity of resources of type λ i , ∀i = 1, .., |Λ| required by activity a, and Λ a = {λ i ∈ Λ / qtreq a λ i = 0}, the set of resource types required by a. iseligible t a is equal to 1 if there are enough resources for scheduling activity a at time slot t (i.e. ∀λ i ∈ Λ a , qtreq a λ i ≤ qtav t λ i ), 0 otherwise. A precedence relation is defined between the activities and we denote pred a the set of activities that must be planned before activity a. Training session: Let S be the set of training sessions to schedule over horizon H. Each training session s ∈ S is composed of a set of activities A s and has a total duration duration s = a∈A s duration a . We denote Λ s = a∈A s Λ a , the set of resource types required per training session s.

Mathematical model

The model proposed for the SimUSanté problem is based on [START_REF] Brucker | Resource-Constrained Project Scheduling and Timetabling[END_REF], that considers CB-CTT as an extension of the Resources Constrained Project Scheduling Problem (RCPSP). The two 0 -1 decision variables used in our model are:

x t a = 1 if activity a starts at time slot t, 0 otherwise, ∀a ∈ A and ∀t ∈ T . y e,λ a = 1 if activity a is assigned to employee e with type λ, 0 otherwise, ∀a ∈ A, ∀e ∈ E and ∀λ ∈ Λ e .

The objective is to plan as many activities as possible while minimizing the completion time (makespan) of each session. This objective is represented by function in equation [START_REF] Abdullah | Heuristic approaches for university timetabling problems[END_REF] where the first term tends to minimize the session makespans and the second one tends to minimize the number of unscheduled activities. Coefficient α is penalty applied to unscheduled activities. starts s and end s are two fictitious activities with duration zero, that respectively represent the beginning and the end of session s. minimize s∈S t∈T

(x t end s × t -x t start s × t) + a∈A (1 - t∈T x t a ) × α (1)
This objective function (see equation ( 1)) must be minimized while respecting all time and resource constraints that are represented by the following linear constraints:

t∈[ES a ,LS a ] x t a ≤ 1 ∀a ∈ A (2) t∈T \[ES a ,LS a ] x t a = 0 ∀a ∈ A (3) t∈T x t a ≤ 1 ∀s ∈ S, ∀a ∈ {start s , end s } (4)
Equations ( 2) and ( 3) ensure that each activity a is scheduled once at most, and in [ES a , LS a ]. Equation ( 4) checks that fictitious activities are scheduled once at most.

t∈T t.(x t a -x t b ) ≥ duration b , ∀s ∈ S, ∀a ∈ A s ∪ {end s }, ∀b ∈ pred a (5) e∈R λ y e,λ a = qtreq a λ , ∀a ∈ A, ∀λ ∈ Λ E (6) t t =end d -duration a +1 x t a + t t =start d+1 -duration a +1 x t a ≤ 1, ∀a ∈ A, ∀d ∈ D \ { d} (7)
a∈A

(qtreq a λ × t t =t-duration a +1 x t a ) ≤ qtav t λ , ∀t ∈ T, ∀λ ∈ Λ R (8)
Equations ( 5), ( 6), ( 7) and ( 8) correspond to constraints related to activities. Equation [START_REF] Babaei | A survey of approaches for university course timetabling problem[END_REF] ensures that activity a cannot start before all its predecessors. Equation (6) ensures, for each activity that the required quantity of employees with type λ is assigned to it. Equation [START_REF] Bashab | A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms[END_REF] ensures that each activity is not split and scheduled on two distinct days. Finally, equation [START_REF] Bellio | Feature-based Tuning of Simulated Annealing Applied to the Curriculum-Based Course Timetabling Problem[END_REF] verifies that the number of scheduled activities on time slot t, requiring rooms of type λ does not exceed the number of available rooms of this type.

t t =t-duration a +1 x t a + b∈A s \{a} t t =t-duration b +1 x t b ≤ 1, ∀t ∈ T, ∀s ∈ S, ∀a ∈ A s ( 9
)
a∈A s t∈break d t t =t-duration a +1 x t a ≤ 1 ∀s ∈ S, ∀d ∈ D (10)
Equations ( 9) and ( 10) are related to session constraints. Equation ( 9) verifies that all activities in the session are serial scheduled and equation [START_REF] Blum | Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison[END_REF] ensures that each session has one lunch break per day if necessary.

duration a .

λ∈Λ e y e,λ a -x t a .

t+duration a -1

q=t isavailable q e ≤ (1 -x t a ) × max a∈A {duration a } ∀e ∈ E, ∀a ∈ A, ∀t ∈ T ( 11
)
λ∈Λ e y e,λ a ≤ 1 ∀e ∈ E, ∀a ∈ A ( 12
) t t =t-duration a +1 x t a + t t =t-duration b +1 x t b + ( λ∈Λ e y e,λ a + y e,λ b ) ≤ 3 ∀e ∈ E, ∀t ∈ T, ∀a ∈ A, ∀b ∈ A \ {a} ( 13
) t t =t-duration a +1 x t a + t t =t-duration b +1 x t b + λ∈Λ e y e,λ a + λ∈Λ e y e,λ b ≤ 3 ∀e ∈ E, ∀d ∈ D, ∀t ∈ break d , a ∈ A, b ∈ A \ {a} (14)
All equations ( 11), ( 12), ( 13) and ( 14) concern the employee constraints. Equation [START_REF] Brucker | Resource-Constrained Project Scheduling and Timetabling[END_REF] ensures that there is no activity assigned to employee e when they are not available. Equation [START_REF] Burke | Penalising Patterns in Timetables: Novel Integer Programming Formulations[END_REF] verifies that employees are assigned to one type at most per activity. Equation [START_REF] Caillard | Health Simulation Center Simusanté ® 's Problem Benchmarks[END_REF] ensures that employee e is assigned at most to one activity per time slot t. Equation ( 14) guarantees that each employee has a lunch break each day.

CPLEX solver (version 12.6) was used to solve this 0-1 linear program. It provides optimal solutions for small instances, but cannot process larger ones in a limited run time of 24 hours. However, thanks to the optimal solutions provided, we were able to measure the efficiency of our heuristic algorithms, SimU G and SimU LS added in sections 5 and 6.

5 SimU G: a greedy algorithm for the SimUSanté problem Because the real life instances are most often large and consequently unsolvable by exact methods, we propose a constructive greedy algorithm named SimU G. The strengths of a greedy algorithm are the simplicity and speed of execution. At each iteration of the construction process, it is necessary to make choices according to local optimality criteria, without guarantee of the global optimality. These selection criteria must therefore be relevant to the SimUSanté problem. In order to design them, we mainly focused on making a schedule compact. The training offered by the SimUSanté center must satisfy their customers, while monopolizing the learners as few as possible. We explain in this section how these criteria were constructed for SimU G.

Solution formulation

Constructing a solution is to assign a start date t a (a time slot) to activity a, and a set of resources R a , such that all the constraints of resources (number and type) of precedence and of operating rules are respected. A solution is represented by a set Sol of triplets (a, t a , R a ), with a ∈ A, ES a ≤ t a ≤ LS a and R a ⊆ R r ∪ R e . R a is a set of available resources assigned to a, which exactly matches the resources required to execute a. Let SA ⊆ A, SA = {a|(a, t a , R a ) ∈ Sol} be the set of scheduled activities and U A = A \ SA, the set of unscheduled ones. For session s ∈ S, Sol s ⊆ Sol, represents the set of triplets of the solution related to s, with Sol s = {(a, t a , R a ) ∈ Sol|a ∈ A s }. SA s = SA∩A s , is the set of scheduled activities of s, and U A s = A s \ SA s , the set of unscheduled activities of s.

For a given session s ∈ S, if at least one activity has been scheduled (SA s = ∅), then the start date t start s = min (a,t a ,R a )∈Sol s {t a } and the end date t end s = max (a,t a ,R a )∈Sol s {t a + duration a }, otherwise t start s = t end s = 0. The makespan of session s is denoted mk s = t end s -t start s .

The evaluation of Sol, denoted M akespan(Sol), corresponds to the objective function presented by equation [START_REF] Abdullah | Heuristic approaches for university timetabling problems[END_REF]. It is the sum of the makespans of all sessions, plus the amount of unplanned activities multiplied by penalty α (see equation [START_REF] Carter | When is the classroom assignment problem hard?[END_REF]. The objective is to find a valid solution with a minimum M akespan.

M akespan(Sol)

= s∈S mk s + |U A| × α (15)

Principle of SimUG

SimU G, described in algorithm 1, consists of scheduling one by one the sessions in S, using selection criteria that tend to minimize the objective function presented in equation [START_REF] Abdullah | Heuristic approaches for university timetabling problems[END_REF]. These selected criteria aim to compact the schedule obtained rather than planning as many activities as possible. Two criteria are used to select the session s * to plan -sessionChoice() -and its better starting date t * -betterStart() -. Once s * and t * are fixed, the criterion activityChoice() allows the sequential scheduling of activities of s * from time slot t * . In SimU G, EligibleActivities() simply returns all unplanned activities of s * , whose resource demands can all be satisfied at a given time slot t.

Criterion sessionChoice(S)

The aim of sessionChoice() is to choose among unscheduled sessions in S the next to schedule. It selects the training session with the lowest difficulty score dif s computed by equation ( 16). This score represents the difficulty of planning a session. dif s estimates the total number of required resources over duration s . The lower the dif s of session s is, the more compact the schedule of s will be since s doesn't need many resources or not for a long time. In case of equal dif s , a random choice is made.

dif s = a∈A s λ∈Λ a duration a × qtreq a λ s * = argmin s∈S {dif s } (16)
5.4 Criterion betterStart(s * ) betterStart(s * ) selects the start date t * for previously chosen session s * . This selection is made according to equation [START_REF] Cooper | The Complexity of Timetable Construction Problems[END_REF] which is based on three indicators that characterize each time slot t ∈ H: the resource deficiencies D t s * , the resource availability avail t s * and the underestimated makespan underspan t s * of previously chosen session s * . The chosen time slot is then the one with the lowest resource deficiencies and in case of equality between two time slots, those that have the higher resources availability and finally those that have the lowest underestimation of makespan. The computation of these indicators is described above.

t * = [ argmin t∈T {D t s * }; argmax t∈T {avail t s * }; argmin t∈T {underspan t s * } ] (17)
To calculate these three indicators, we define for each time slot t, the earliest end of session s * denoted end t s * described in equation ( 18). end t s * takes into account the total duration of the activities of s * and the mandatory lunch breaks computed by the function breaks. Lowerbound of chosen session underspan t s * is an underestimation of the makespan of s * if it starts at t and is computed by equation ( 19).

underspan t s * = end t s * -t + 1 (19)
The previous example in figure 1 shows that the earliest ends for time slots 1 and 4 are respectively end

overeq s * λ i = max a∈A s * λ i ∈Λ s * {qtreq a λ i } (20)
So the overestimation of resource deficiencies for each time slot t is the sum of the differences between the over requirement of s * , overeq s * λ i and the available resource at time slot t, qtav t λ i , for each resource type λ i , as shown in equation [START_REF] Goh | Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem[END_REF]. Figure 2 illustrates the over requirement and considers the following requirements for the previous set of activities A s * : activity a needs two rooms of type λ 1 (qtreq a λ 1 = 2) and one employee of type λ 2 (qtreq a λ 2 = 1). The over requirements for session s * is then overeq s * λ 1 = max(2, 1) = 2 ; overeq s * λ 2 = max(1, 1) = 1 ; overeq s * λ 3 = max(0, 2) = 2. Resource availability avail t s * is the average of available resources over [t, end t ]. The more resources left, the more opportunities to schedule remaining activities left. The available resources score of time slot t is given by equation ( 21).

avail t s * = end t s * t =t λ i ∈Λ s (qtav t λ i ) underspan t s * (21)
With our previous example, using s * presented in figure 2 and the resource availabilities shown in figure 3, for time slot 1, the resource availability is the average of the white blocks inside the dashed rectangle, and then avail 1

s * = ((1 + 1 + 2) + (1 + 1 + 2) + (1 + 2 + 2) + (1 + 2 + 3))/4 = 19/4.

Criterion activityChoice(EA s * , t)

Among the set of eligible activities criterion activityChoice() chooses which activity a * ∈ EA s * , with its pre-assigned resources R a * , will be scheduled. Its start date t a * is set to t and resource availabilities are updated by function updateAvailability (a * , t, R a * ).

a * is activity a such that (a, R a ) ∈ EA s * with the lowest score a (see equation ( 22)). score a overestimates the number of times a could be scheduled in [t, end t s * ], thanks to iseligible t a which is equal to 1 when a can start at t. The lower the score, the fewer possibilities there are to program a at a time slot greater than t. Note that if score a = 0, there is no possibility of planning a after t.

Let ∆ = min a|(a,R a )∈EA S * {duration a } be the smallest duration of the activities in EA s * . activityChoice() selects a * according to equation [START_REF] Imran Hossain | Optimization of university course scheduling problem using particle swarm optimization with selective search[END_REF]. If several activities have the same score a , one is randomly chosen.

score a = d∈D t ∈T d ∩[t+∆;end t s * ]        t +duration a -1 t =t iseligible t a duration a        a * = argmin a|(a,R a )∈EA s * {score a } (22)
5.6 Function updateAvailability(a * , t, R a * ) When activity a * is scheduled on t, all resources in R a * are set unavailable over the period [t, t + duration a * -1]. Let us note that precedence constraints are also updated for all activities linked to a * .

SimU LS: a local search algorithm

As mentioned in 5, the strengths of a greedy algorithm like SimU G are the simplicity of implementation and the very short run time. They also enable valid solutions to be built while not violating any constraints of the problem. However, despite the relevance of criteria exposed in section 5, the resulting solutions remain with some unscheduled activities and/or with some idle time slots that damage the session makespans. To improve the SimU G solutions, we have developed a local search algorithm SimU LS that explores the solution space by applying neighborhood operators, starting from a solution provided by greedy algorithm SimU G.

From a given valid solution Sol, SimU LS operator generates a set of possible movements. Each of them corresponds to a neighbor solution of Sol. The process consists of choosing one of these neighbor solutions as the current solution and continues, with the expectation of meeting a near optimal solution. The effectiveness of this method depends on the relevance of the operators and the strategy of their application. Movements and operators are respectively detailed further in sections 6.2 and 6.3.

Principle of SimU LS

SimU LS proposes the following operators : saturator, intra, extra, extra + and diversif icator. saturator tries to complete the current solution by inserting unplanned activities into consecutive time slots with sufficient resources available. intra, extra and extra + are applied when no movement stemmed from saturator is possible. They try to insert unplanned activities by removing one or more scheduled activities from the current solution. diversif icator is applied as a diversification way in order to escape a local minimum.

SimU LS principle, described in algorithm 2, is the following: until a maximum preset limitCounter iterations is reached, SimuLS relies on saturator to plan unscheduled activities. If saturator fails to plan all the unscheduled activities, SimU LS calls function selectOperator to choose one of the following operators: intra, extra or extra + , in order to plan a randomly selected unscheduled activity. Each of these operators removes triplets from the current solution according to some criteria and thus frees resources and unsets time slots associated with these triplets. Finally, if the best solution ever met is not improved after a preset noImprov iterations, a dynamic β% of the solution is randomly destroyed by the destructor operator.

Movement description

As mentioned in section 5.1, a solution is a set of triplets, so a movement m will be characterized by a couple m =< (a, t a , R a ) ; Υ >. (a, t a , R a ) represents a triplet that will be added to the current solution, with a ∈ U A, an unscheduled activity, t a ∈ T , a time slot from which a could be started, and R a , the set of resources assigned to a that exactly matches its resource requirement. In order to plan a, we need to remove a set Υ of triplets from the solution.

Υ = {(b 1 , t b 1 , R b 1 ), . . . , (b n , t b n , R b n )}, n ∈ {1, . . . |Sol|}.
The set of resources R a can be composed of resources directly available over H, plus those released by cancelling all activities of Υ . A movement respects all operational rules and resource constraints. Note that Υ can be an empty set if triplet (a, t a , R a ) can be added to the solution without removing any activities. Movements and their scores are described in the following paragraph.

Algorithm 2 : SimuLS

Require: Sol (the current solution), S (set of sessions), ∀s ∈ S, U As (set of unscheduled activities for session s), U A = s∈S U As (the set of unscheduled activities), noImprov, limitCounter, β min , lim βmax Ensure: bestSol (the best solution met during the process) Each movement m has a score, score m , computed by equation 23. This score allows operators to determine which movement to apply, as show in equation 27. The higher the score associated with m, the greater the probability that m is applied. This score measures the potential improvement of the solution if this move is applied. It is composed of 3 indicators: the makespan variation ∆ m , the number of idle time slots idle m generated and the number of removed activities |Υ m |. The last indicator is considered in order to limit the number of activities to plan next.

noBest ← 0 counter ← 0 bestSol ← Sol β ← β min βmax ← β min for all a ∈ U A do m ← saturator(a) if m = m N U LL then (Sol, U A) ← applyM ove(m, Sol, U A) end if end for bestSol ← Sol while counter < limitCounter do if (noBest = noImprov) or (U A = ∅) then β ← randomInterval(β min , βmax) (Sol, U A) ← diversif icator(Sol, U A, β) noBest ← 0 if βmax < lim βmax then βmax ← βmax + 1 end if end if if U A = ∅ then a ← random(U A) m ← selectOperator({intra, extra, extra + }, a) if m = m N U LL then (Sol, U A) ← applyM ove(m, Sol, U A) end if end if for all a ∈ U A do m ← saturator(a) if m = m N U LL then (Sol, U A) ←
score m = 1 (1 + ∆ m ) × (1 + idle m ) × (1 + |Υ m |) (23)
In details:

∆ m computes (see equation ( 24)) the difference between the new makespan N mk m of session s a , if a is scheduled, and the estimated minimum makespan lb m of session s a .

∆ m = 0 if N mk m ≤ lb m N mk m -lb m otherwise ( 24
)
This estimated makespan is obtained by relaxing all resource constraints and considering lunch-breaks computed by function breaks(). N mk m and lb m are detailed in equations 25.

N mk m = max Υ m is the set of activities that m envisages to remove from the solution, freeing up resources to plan a. The larger |Υ | m is, the more the unplanned activities could weigh negatively on the objective function M akespan(Sol).

t
Each of our operators, described in the next section, builds a set of movements according to different criteria, and selects one of them (see equation 27) to be applied to the current solution Sol.

Description of scheduling operators

As mentioned previously, operators generate a set of movements M . Each movement m ∈ M , with m =< (a, t a , R a ); Υ >, is composed of (a, t a , R a ) the activity to plan at t a with resource consumption R a , and Υ the set of activities to remove from the current solution.The main difference between the four scheduling operators saturator, intra, extra, and extra + is the composition of Υ . Note that if there is no possible movement for an operator (M = ∅), it returns the empty movement m N U LL . This paragraph formally details these four operators.

saturator a : This operator tends to place activity a ∈ U A without changing the current solution. It builds a set of movements M ={< (a, t 1 a , R 1 a ); ∅ >, . . . , < (a, t k a , R k a ); ∅ >}. Because all activities of a same session must be planned in series, for each movement < (a, t i a , R i a ) ; ∅ >∈ M , with i = 1, . . . , k, the following property must be respected:

-[t i a ; t i a + duration a [∩[t b ; t b + duration b [= ∅ ∀(b, t b , R b ) ∈ Sol s(a)
. intra a : This operator removes one or more scheduled activities from s(a) in order to plan activity a ∈ U A. It builds a set of movements M ={< (a, t 1 a , R 1 a ); Υ 1 > , . . . , < (a, t k a , R k a ); Υ k >}, where Υ i are the sets of activities belonging to session s(a) to be removed from the solution. In addition to the seriality constraint, it is clear that only the activities of s(a) scheduled on the time slots of [t i a ; t i a + duration a [ must be deleted. So, for each movement < (a, t i a , R i a ); Υ i > ∈ M , with i = 1, . . . , k, and Υ i ⊆ SA s(a) , the following properties are verified:

-[t i a ; t i a + duration a [∩[t b ; t b + duration b [ = ∅, ∀(b, t b , R b ) ∈ Υ i -[t i a ; t i a + duration a [∩[t b ; t b + duration b [= ∅, ∀(b, t b , R b ) ∈ {Sol s(a) \ Υ i } extra a :
The principle of this operator is based on that of intra(a). To schedule activity a, it builds a set of movements M for which each set Υ i of removed activities belongs to the same randomly selected session s = s(a). For each movement < (a, t i a , R i a ); Υ i >∈ M , with i ∈ [1; k] and Υ i ⊆ SA s , the following properties are verified:

-[t i a ; t i a + duration a [∩[t b ; t b + duration b [ = ∅, ∀(b, t b , R b ) ∈ Υ i -[t i a ; t i a + duration a [∩[t b ; t b + duration b [= ∅, ∀(b, t b , R b ) ∈ Sol s(a) extra +
a : This operator differs from intra and extra because canceled activities come from different sessions. For each movement, the removed activities belong to S. It builds a set of movements M ={< (a, t 1 a , R 1 a ); Υ 1 >, . . . , < (a, t k a , R k a ); Υ k > } in order to plan activity a ∈ U A. For each movement < (a, t i a , R i a ); Υ i >∈ M , with i ∈ [1; k] and Υ i ⊆ SA, the properties below are verified :

-[t i a ; t i a + duration a [∩[t b ; t b + duration b [ = ∅, ∀(b, t b , R b ) ∈ Υ i -[t i a ; t i a + duration a [∩[t b ; t b + duration b [= ∅, ∀(b, t b , R b ) ∈ {Sol s(a) \ Υ i }
So, each operator defined above, first generates a set M of movements, then chooses one of them to apply to the current solution, according to the rule of random proportionality. This rule is built on probability p m , associated with each movement and computed by equation 27.

p m = score m m ∈M score m (27)
The strategy of scheduling operator selection during the iterative process of algorithm 2 still remains to be defined. This is provided by the function selectOperator described in section 6.5.

Diversification operator

diversif icator is the diversification operator. Its purpose is to partially modify the solution in order to escape from a local minimum. diversif icator has two operating modes depending on U A, because the latter could be empty when diversif icator is called. The first mode schedules all the activities in U A. The second one is used when U A = ∅ and moves some scheduled activities to other time slots. Both of these operating modes use extra + operator to schedule or move activities. Below, the details of these modes:

if U A = ∅: it selects a set {(a 1 , t a 1 , R a 1 ), . . . , a β , t a β , R a β )} of triplets to remove from the current solution. For each canceled triplet (a i , t a i , R a i ), with i ∈ [1; β],
it uses operator extra + to plan activity a i . Note that t a i , the previous time slot where a i was scheduled, is considered as tabu and cannot be used by extra + at this step. This restriction was made to prevent diversif icator from scheduling a i on the time slot t a i where it was previously planned.

if U A = ∅: in this mode, there is no need to remove triplets from the solution. For each unscheduled activity a ∈ U A, extra + operator is used to schedule it.

Note that whatever the mode used, each time extra + is used and then a movement m is applied, the canceled activities belonging to Υ m are added to U A and are not yet considered by diversif icator.

β represents the number of removed activities and is randomly generated between limits β min and β max which represent respectively the minimum and the maximum quantity of triplets canceled. β max evolves according to the number of times destructor has been applied without an improvement of the solution. Each time the solution is improved, β max is set to its initial value β min , otherwise β max increases by 1 each time destructor is used, until it reaches its preset limit lim β max .

Function : selectOperator()

Function selectOperator is used when saturator can't schedule all activities, as shown in algorithm 2. Its purpose is to determine which operator will be the most suitable to plan unscheduled activity a. In order to choose which operator to apply between intra, extra, extra + , SelectOperator function uses two specific counters: c s extra counts the number of times where intra has been consecutively applied to session s. When it reaches its associated limit, it activates operator extra to schedule a. c a extra + determines how many iteration activities a remained consecutively unscheduled. When its limit is reached, it uses extra + to plan a.

By default, selectOperator uses intra, except if the counters reach their limits. Note that in case of equality between the two counters, extra + is always used first.

Instances & Computational results

Instances

In order to test our algorithms, we needed instances close to the SimUSanté problem. However, the current operation of the training center does not provide real instances. For this reason, we have generated new instances [START_REF] Caillard | Health Simulation Center Simusanté ® 's Problem Benchmarks[END_REF], from the classic instances of the CB-CTT problem [START_REF]High School Timetabling Project[END_REF]. These generated instances include characteristics inherent to the SimUSanté problem, and are accessible on the website [START_REF] Caillard | Health Simulation Center Simusanté ® 's Problem Benchmarks[END_REF]. Their construction process is now briefly described.

We generate an initial instance D 0 T 0 C 0 A 0 which has as many employees (the teachers), rooms, time slots, sessions (the curricula) and activities (the lectures) as the original CB-CTT instance, and ensure that all the characteristics described in section 3 are present: An employee-type matches to a single employee. So there are as many employee-types as employees. Each employee is available over the horizon and their employee-type is associated with activities that correspond to the lectures the relative teacher/employee was performing on the original CB-CTT instance. All rooms have the same unique room-type. Because such an instance represents a 'too special' case of the SimUSanté instances, we have extended it and thus made it more general using the following criteria:

-Criterion C1 adds one random employee-type to a set of randomly chosen employees. -Criterion D1 halves the availabilities to a set of randomly selected employees.

-Criterion T 1 adds one or two new room-types, distributes the rooms into all these existing types and sets activity requirements accordingly. -Criterion T 2 allows the rooms to have more than one type and then adds to each randomly chosen room one existing room-type. -Criterion A1 selects a set of randomly chosen activities and for each of them increases by 1 the quantity required in a randomly selected room-type. Some activities then require more than one room-type or two rooms of the same type. -Criterion A2 uses the same set of activities considered by criterion A 1 and increases by 1 the quantity required in a randomly selected employee-type.

These criteria are combined to provide different instances. As an illustration,

D 0 T 1 C 0 A 1 + D 1 provides a new instance D 1 T 1 C 0 A 1 .
Because the criteria involve random choices, it is possible to generate several different instances from a single variant criterion.

To test SimU G and SimU LS we use 6 new instances derived from those of the CB-CTT: Brazil1, Italy1, Brazil2, Brazil6, Finland1 and StPaul. The characteristics of the new generated instances are presented in table 1:

Results

The mathemathical model presented in section 4 was implemented with the CPLEX solver 12.8. SimU G and SimU LS were written in Java, and tested on an Intel I7 7500U processor. The tests of CPLEX, SimU G and SimU LS are reported on tables 2 to 7. Column Instancename corresponds to the label associated with CPLEX provided optimal solutions only for the smaller instance families such as Italy1, Brazil1 and Brazil2 (see tables 2, 3 and 4). Note that in the optimal solution, all activities are scheduled. For the others, the optimal solutions are not attained because of the prohibitive execution time of the solver.

The greedy algorithm SimU G worked out valid but non optimal solutions in less than one second. SimU G schedules all activities for only 4 of the 60 tested instances and schedules on average 93.55% of the activities with a standard deviation of 4.96 over all instances. The differences in number of scheduled activities between the tested instances are caused partly by criteria betterStart and ActivityChoice(). The first one returns a time slot t * from which a session s * can start to be planned and then time slots before t * are never considered by SimU G in order to plan s * . As an example, in the solution proposed by SimU G The restricted horizon mainly generates the differences in results observed between the instances. However, although the criteria betterStart and activityChoice() lead sometimes to solutions that have more unscheduled activities than others, they provide compact timetables. Indeed, without penalty pen added to the score of SimU G in equation 15 which have few idle time slots, than others with more scheduled activities but a lot of idle time slots. That is why we used SimU G solutions as initial solutions for SimU LS.

The running time limit for SimU LS has been set at two hours. SimU LS always schedules all activities and always improves results of SimU G. We note an average divergence of 9.97% between SimU LS and the optimal solution when it exists, with a standard deviation of 2.68. Moreover, considering the column SD, we observe for each instance that the standard deviation remains less than 2, which means that SimU LS always provides solutions of equivalent quality. Futhermore for each table, the results obtained are roughly the same (except for D 0 T 0 C 0 A 0 and D 1 T 0 C 0 A 0 ), which means that SimU LS is efficient in most cases.

For small instances, like Brazil1, Italy1, Brazil2 (cf. table 2, 3, 4), the main difference between the optimal solutions and that of SimU LS is that the number of lunch breaks is not minimized. Indeed, to obtain the optimal solution, it is necessary to start the sessions from specific time slots that allow lunch breaks to be minimized. For example: start a session on the first afternoon time slot and end it on the last morning time slot of the following day. Nevertheless the schedules obtained by SimU LS, in all instances, are compact and quite revelant for SimUSanté. Table 8 shows the average use rate of each operator compared to the total number of iterations. The results have been grouped into instances that have been generated from the same CB-CTT instance. We note nb it the total number of iterations made by SimU LS in a running time of two hours and nb intra , nb extra , nb extra + , nb diversif icator respectively the number of iterations where intra, extra, extra + and diversif icator have been used . Column selectOperator gives the percentage of use for the set of operators: nb operator /nb it × 100. They have been grouped together because they are only called by function selectOperator which is called at each iteration. Column diversif icator is the percentage of use for diversif icator operator. Note that the rate of saturator is always 100% because it is called at each iteration.

We observe that the larger the size of the instance, the less the diversificator is used. Indeed, on the smaller and easier instances, once diversif icator has been used, SimU LS succeeds very quickly in planning all the activities and therefore in using diversif icator again. Likewise, we note that the larger and more difficult the instances, the more extra + is used to obtain a solution without unscheduled activities. This is mainly because SimU LS needs several iterations to successfully plan all the activities once diversif icator has been used, and therefore some activities remain unscheduled for quite a long time.

Conclusion

In this paper we have presented a study of a planning problem with resource constraints, for the health training center SimUSanté. We proposed a mathematical model and greedy algorithm SimU G, based on a set of choice criteria aimed at reducing the overall Makespan of training sessions, while respecting all resource and time constraints. SimU G is interesting for SimuSanté because it allows immediat solutions to be obtained, in particular on easier instances. To improve the results obtained by SimU G, we have developed SimU LS, a local search algorithm based on 5 movement operators, in order to plan all the activities, while minimizing the general Makespan. We experimented SimU G and SimU LS on new instances, generated from those of CB-CTT, and integrating the SimUSanté problem characteristics. The results obtained were compared to the optimal solutions provided by the CPLEX solver. SimU G schedules on average 93.55% of the activities and produced a suitable and compact basic solution in a very short time. SimU LS always schedules all activities, enhances results of SimU G in all cases and has an average divergfence of 9.97% from optimal solutions. SimU LS is a good compromise because it obtains good results quickly thanks to our operators which efficiently explore the search space.

Fig. 1

 1 Fig. 1 Computation of the earliest end of session s * for each time slot.

Figure 1

 1 Figure 1 considers the set of activities A s * = {a, b}, with respective duration duration a = 2 and duration b = 2, and shows that if s * starts at time slot 1 or at time slot 4, the earliest end is respectively end 1 s * = 4 and end 4 s * = 8, because a lunch break is required for the latter.

Fig. 2

 2 Fig. 2 Description of session s * and its over requirement

Fig. 3

 3 Fig. 3 Resource availabilities for time slots 1 to 9

U

  A (with pen = |U A| × α and α = |H| on equation (15)), and column SD represents the standard deviation over 20 runs from column M akespan (SimU LS).

  Horizon: Horizon H corresponds to one week decomposed into working days. Let D be the set of these working days. So, ∀d ∈ D, we denote T d the set of time slots of day d and T = d∈D T d . start d = min t∈T d {t} represents the first time slot of day d and end d = max t∈T d {t}, the last one. d is the last day of H. Each time slot represents one hour and a day is composed of 9 time slots. Let break d be a subset of slots identified as potential time breaks, for day d. One at least of these time slots should be idle to ensure the existence of a daily lunch break for any sessions and employees. Resources: We have a finite set of resources R = R r ∪ R e with R r the set of rooms and R e the set of employees. To R e is associated a set of types Λ e = {λ 1 , ..., λ |Λ e | } which corresponds to the skills of employees. To R r is also associated a set of types Λ r = {λ |Λ e |+1 , ..., λ |Λ e |+|Λ r | } which corresponds to specific room equipment.

  Algorithm 1 SimU G Require: S (set of unscheduled training sessions), T (set of time slots) Ensure: Sol (a feasible solution), U A (set of unscheduled activities)

	1: Sol ← ∅
	2: U A ← ∅
	3: while S = ∅ do
	4:	s * ← sessionChoice(S)
	5:	S ← S \ {s * }
	6:	t * ← betterStart(s * , T )
	7:	t ← t *
	8: U A s 10: EA s * ← eligibleActivities(U A s * , t)
	11: 12: 13: 14: 15:	if EA s * = ∅ then (a * , R a * ) ← activityChoice(EA s * , t) Sol ← Sol ∪ (a * , t, R a * ) updateAvalaibility(a * , t, R a * ) U A s * ← U A s * \ {a * }
	16:	t ← t + duration a *
	17:	else
	18:	t ← t + 1
	19:	end if
	20:	end while
	21:	U A ← U A ∪ U A s *
	22: end while
	23: return (Sol, U A)

* ← A s * 9: while (t ≤ |T |) and (U A s * = ∅) do

  1 s * = 4 and end4 s * = 8. The underestimation of corresponding makespans to these time slots is then underspan 1 s We then consider that session s * requires during its progress the maximum resource quantity over A s * , for all resource types λ i ∈ Λ s * .

	end s *
	D t s * =

* = 4-1+ 1 = 4 and underspan 4 s * = 8 -4 + 1 = 5. Resource deficiencies D t s * scores any time slot t by overestimating resource deficiencies over [t, end t s * ] if s * starts at t. t t =t λ i ∈Λ s max(overeq s * λ i -qtav t λ i , 0)

Table 1

 1 Characteristics of the tested instances

	Instance name	Sessions	Employees	Rooms	Activities	Time slots
	Brazil1	3	8	3	27	36
	Italy1	3	13	3	36	45
	Brazil2	6	14	, 6	57	36
	Finland1	10	18	13	139	45
	Brazil6	14	30	14	126	36
	StPaul	67	68	67	589	36

Table 2

 2 Results for Brazil1 -average gap from CPLEX -SimU G: 37.52%, SimU LS: 7.10%

	Instance name	CPLEX	SimU G M akespan |U A|%	pen	M akespan	SimU LS |U A|%	pen	SD
	D 0 T 0 C 0 A 0	83	89	0	0	84.2	0	0	1.62
	D 0 T 1 C 0 A 1	84	124	3.70	36	91.1	0	0	1.67
	D 0 T 1 C 1 A 1	84	124	3.70	36	90.3	0	0	2.01
	D 0 T 1 C 1 A 2	84	124	3.70	36	91.3	0	0	1.71
	D 0 T 2 C 0 A 1	83	159	7.41	72	91.5	0	0	1.63
	D 1 T 0 C 0 A 0	83	86	0	0	84.3	0	0	1.68
	D 1 T 1 C 0 A 1	84	132	3.70	36	91.5	0	0	1.59
	D 1 T 1 C 1 A 1	84	168	7.41	72	90.5	0	0	1.73
	D 1 T 1 C 1 A 2	84	168	7.41	72	90.9	0	0	1.62
	D 1 T 2 C 0 A 1	83	164	7.41	72	91.4	0	0	1.67
	average	83.6	133.8	4.44	43.2	89.99	0	0	1.69

Table 3

 3 Results for Italy1 -average gap from CPLEX -SimU G: 63.09%, SimU LS: 9.99% the criteria used in the generating instance process, as explained before. Column CP LEX gives the optimal solution when attainable in the running time limits of 24 hours. na specifies a non available result. For SimU G and SimU LS, the results are respectively decomposed into 3 and 4 parts: column M akepsan is the value for SimU G and the average over 20 runs for SimU LS of the objective function (equation 1), column |U A| is the percentage (SimU G) and the average percentage (SimU LS) of unscheduled activities, column pen is the penalization induced by

	Instance name	CPLEX	SimU G M akespan |U A|%	pen	M akespan	SimU LS |U A|%	pen	SD
	D 0 T 0 C 0 A 0	101	109	0	0	104.9	0	0	1.38
	D 0 T 1 C 0 A 1	103	199	5.56	90	113.8	0	0	1.65
	D 0 T 1 C 1 A 1	103	245	8.33	135	114.4	0	0	1.41
	D 0 T 1 C 1 A 2	103	244	8.33	135	114.3	0	0	1.64
	D 0 T 2 C 0 A 1	103	474	22.22	360	113.9	0	0	2.03
	D 1 T 0 C 0 A 0	101	107	0	0	105.1	0	0	1.87
	D 1 T 1 C 0 A 1	103	248	8.33	135	116.1	0	0	1.76
	D 1 T 1 C 1 A 1	103	294	11.11	180	117	0	0	1.73
	D 1 T 1 C 1 A 2	103	294	11.11	180	118.4	0	0	1.74
	D 1 T 2 C 0 A 1	103	566	27.78	450	118.2	0	0	1.69
	average	102.6	278	10.28	177.4	113.99	0	0	1.69

Table 4

 4 Results for Brazil2 -average gap from CPLEX -SimU G: 46.88%, SimU LS: 10.96%

	Instance name	CPLEX	SimU G M akespan |U A|%	pen	M akespan	SimU LS |U A|%	pen	SD
	D 0 T 0 C 0 A 0	163	288	5.28	108	174.4	0	0	1.72
	D 0 T 1 C 0 A 1	166	395	10.53	216	188.1	0	0	1.70
	D 0 T 1 C 1 A 1	166	431	12.28	252	186.9	0	0	1.75
	D 0 T 1 C 1 A 2	166	431	12.28	252	188.3	0	0	1.12
	D 0 T 2 C 0 A 1	164	259	8.77	180	186.6	0	0	1.75
	D 1 T 0 C 0 A 0	163	220	1.75	36	175.8	0	0	1.33
	D 1 T 1 C 0 A 1	166	260	3.51	72	188.7	0	0	1.68
	D 1 T 1 C 1 A 1	166	264	3.51	72	188.1	0	0	1.56
	D 1 T 1 C 1 A 2	166	301	5.26	108	188.4	0	0	1.95
	D 1 T 2 C 0 A 1	164	257	3.51	72	187.8	0	0	1.64
	average	165	310.6	6.67	136.8	185.31	0	0	1.71
	Table 5 Results for Finland1
	Instance name	CPLEX	SimU G M akespan |U A|%	pen M akespan	SimU LS |U A|%	pen	SD
	D 0 T 0 C 0 A 0	na	525	2.88	180	345.9	0	0	1.62
	D 0 T 1 C 0 A 1	na	619	4.32	270	367.8	0	0	1.59
	D 0 T 1 C 1 A 1	na	575	3.60	225	368.4	0	0	0.98
	D 0 T 1 C 1 A 2	na	489	2.16	135	367.9	0	0	1.24
	D 0 T 2 C 0 A 1	na	619	4.32	270	366.5	0	0	1.29
	D 1 T 0 C 0 A 0	na	720	5.76	360	346.7	0	0	1.48
	D 1 T 1 C 0 A 1	na	770	6.47	405	368.3	0	0	1.41
	D 1 T 1 C 1 A 1	na	720	5.76	360	370.3	0	0	1.23
	D 1 T 1 C 1 A 2	na	715	5.76	360	370.1	0	0	1.31
	D 1 T 2 C 0 A 1	na	770	6.47	405	369.5	0	0	1.27
	average	na	652.2	4.75	297	364.14	0	0	1.34

Table 6

 6 Results for Brazil6 T 1 C 0 A 1 instance, each session starts at, or after, 1/6 of the horizon. The second one schedules the unplanned activities of s * based on their remaining planning possibilities. These are computed from a restricted interval of time slots: the current time slot t, with t * ≤ t and the earliest end end t s * of s * . The time slots after end t s * are then not considered for these computations and lead activityChoice to misplace activities.

	Instance name	CPLEX	SimU G M akespan |U A|%	pen	M akespan	SimU LS |U A|%	pen	SD
	D 0 T 0 C 0 A 0	383	710	6.35	288	428.5	0	0	1.03
	D 0 T 1 C 0 A 1	390	1030	13.49	612	435.3	0	0	0.86
	D 0 T 1 C 1 A 1	390	958	11.90	540	437.6	0	0	0.65
	D 0 T 1 C 1 A 2	na	1031	13.49	612	437.8	0	0	0.98
	D 0 T 2 C 0 A 1	na	886	10.32	468	437.3	0	0	0.91
	D 1 T 0 C 0 A 0	na	584	4.76	216	429.2	0	0	0.92
	D 1 T 1 C 0 A 1	na	841	8.73	396	438.2	0	0	0.89
	D 1 T 1 C 1 A 1	na	760	7.14	324	438.9	0	0	0.85
	D 1 T 1 C 1 A 2	na	873	9.52	432	438.5	0	0	0.94
	D 1 T 2 C 0 A 1	na	841	8.73	396	438.1	0	0	0.93
	average	na	851.4	9.44	428.4	435.94	0	0	0.90
	Table 7 Results for StPaul
	Instance name	CPLEX	SimU G M akespan |U A|%	pen	M akespan	SimU LS |U A|%	pen	SD
	D 0 T 0 C 0 A 0	na	1591	1.02	216	1433.2	0	0	0.82
	D 0 T 1 C 0 A 1	na	1639	1.19	252	1458.7	0	0	0.89
	D 0 T 1 C 1 A 1	na	1587	1.02	216	1458.7	0	0	0.84
	D 0 T 1 C 1 A 2	na	2125	3.40	720	1462.5	0	0	0.92
	D 0 T 2 C 0 A 1	na	1639	1.19	252	1463.4	0	0	0.85
	D 1 T 0 C 0 A 0	na	2401	4.41	936	1438.1	0	0	0.92
	D 1 T 1 C 0 A 1	na	2331	4.07	864	1468.6	0	0	0.98
	D 1 T 1 C 1 A 1	na	2334	4.07	864	1468.6	0	0	0.95
	D 1 T 1 C 1 A 2	na	2785	6.11	1296	1470.2	0	0	1.01
	D 1 T 2 C 0 A 1	na	2331	4.07	864	1469.5	0	0	0.96
	average	na	2076.3	3.06	648	1459.1	0	0	0.92
	on Brazil1-D 0

Table 8

 8 Operator use rate

	Instance name	diversif icator	selectOperator intra extra extra +
	Brazil1	23.36	89.26	8.33	2.41
	Italy1	16.37	86.09	8.10	5.81
	Brazil2	17.74	88.17	8.55	3.28
	Finland1	13.38	84.70	7.97	7.33
	Brazil6	15.64	85.95	8.32	5.73
	StPaul	10.12	82.84	8.81	8.55