Cette thèse n'aurait tout d'abord bien évidemment pas été possible sans mes encadrants Nadia Brauner et Pierre Lemaire. Je les remercie d'avoir cru en moi et de m'avoir soutenu pendant ces trois années, J'ai grâce à eux passé trois superbes années, autant sur le plan scientifique que sur le plan personnel. Je les remercie d'avoir toujours été présents quand j'en avais besoin. Je les remercie également de tout ce qu'ils m'ont apporté au niveau de l'enseignement, de m'avoir laissé participer au challenge EURO/ROADEF et de m'avoir donné l'opportunité de passer quatre mois à Minsk. Je remercie Safia Kedad-Sidhoum et Christophe Rapine d'avoir accepté d'être rapporteurs de ma thèse, et pour Christophe Rapine, également d'avoir participé au Comité de Suivi Individuel pendant ma thèse. Je remercie Christian Artigues d'avoir présidé mon jury de thèse et Anne-Marie Lagrange d'avoir accepté d'être examinatrice de ma thèse. Je remercie encore Anne-Marie Lagrange d'avoir proposé cette collaboration entre les équipes de Recherche Opérationnelle et d'Astrophysique de Grenoble, ainsi que Pascal Rubini, l'ingénieur qui a développé le logiciel SPOT utilisé par les astrohpysiciens et avec qui j'ai régulièrement échangé durant ma thèse. Je remercie bien-sûr Luc Libralesso de s'être inscrit au challenge, Vincent Jost de m'avoir poussé à le rejoindre, et encore Luc d'avoir accepté et de m'avoir appris tant de choses depuis. Я хочу поблагодарить Михаила Ковалева за то, что он принимал меня четыре месяца в Минске. Из Минска я также хочу поблагодарить Максима Баркетова, Якова Шафранского, Александра Ковалева и всю административную команду Объединенного института проблем информатики Национальной академии наук Беларуси за их помощь, в частности Евгения Ефимова. Je remercie tout le personnel du laboratoire G-SCOP, le service informatique, le service financier ainsi que le personnel administratif qui permettent aux doctorants d'effectuer leur thèse dans des conditions optimales ; et l'ensemble des membres du laboratoire, de l'association des doctorants et les autres doctorants qui n'ent font pas partie, qui font de ce lieu un endroit convivial. Pour m'avoir aidé sur les questions techniques en informatique et en mathématiques, je remercie Nicolas, Denis et Amaury. Je remercie également mes amis et ma famille.

Introduction

To a large extent, this thesis is the result of a collaboration between the Operations Research team at G-SCOP laboratory and the IPAG research unit (Institute for Planetary sciences and Astrophysics, Grenoble) of Grenoble's Universe Sciences Observatory (OSUG). Astrophysicists want to schedule observations on a telescope and, for each possible target (star), there exist time-windows when it is visible, a required duration for its observation, and an interest for observing it; the objective is to maximize the total interest of the schedule. The primary goal of this thesis was to improve the algorithms implemented in the software used by the astrophysicists, while integrating additional specific constraints and assessing the potential gains of introducing some flexibility in the model. This flexibility is related to observation duration. Indeed, shortening an observation leads to a picture of lesser quality. However, it would be worth doing if that makes room for another one. More generally an observation remains relevant even if its observation time is slightly less than the required value.

In Chapter I, we study this aspect from a theoretical point of view. We consider scheduling problems where jobs have a variable processing time: one can decide the processing time of each job. The profit for a job then depends on its allocated processing time and the objective is to maximize the total profit of the schedule. Our purpose is to draw the line between P-easiness and NP-hardness for various profit functions and machine environments, with an emphasis on models leading to the practical star scheduling problem.

Then, in Chapter II, we take care of the practical problem resolution. We define the complete model and propose several ways of integrating the flexible observation durations in it. We develop a Large Neighbourhood Search algorithm for each variant. It reaches the required practical criteria from simplicity and adaptability to speed and efficiency. Its performances are compared to previous approaches and the gain from flexibility is estimated.

Chapter III is not related to the star observation scheduling problem. Every other year, the French Operational Research and Decision Support Society (ROADEF) jointly with the European Operational Research Society (EURO) organizes an optimization challenge open to everyone. Each edition is a collaboration with an industrial partner, and the problems and instances submitted correspond to real life industrial optimization problems. Previous challenges have been organized in collaboration with Air Liquide (2016), SNCF (2014), Google (2012), EDF (2010)... The 2018 edition of the challenge was dedicated to a cutting optimization problem in collaboration with Saint-Gobain.

In Chapter III, we present the heuristic Branch and Bound algorithm we submitted for the final phase of the challenge. We describe the Branching scheme including dominance criteria and symmetry breaking strategy; and the anytime Tree search algorithm called MBA* which is inspired from the classical A* and Beam search algorithms.

The three chapters can be read independently. Therefore, Because of the unrelatedness of cited papers between them, we choose to split the bibliography into each chapter. While Chapters I and II have been written with my supervisors Nadia Brauner and Pierre Lemaire, Chapter III has been written together with Luc Libralesso.

Table of Contents

Table of Contents

TABLE OF CONTENTS

IV Conclusion 123 9/127

This page is intentionally left blank.

I Chapter Complexity of processing time dependent profit maximization scheduling problems

In this chapter, we study the complexity of scheduling problems where jobs have a variable processing time: one can decide the processing time of each job. The profit for a job then depends on its allocated processing time.

In our experience, the problem originates from astrophysics and the search for exoplanets (Lagrange et al. 2016). Astrophysicists want to schedule observations on a telescope and, for each possible target (star), there exist time-windows when it is visible, a required duration for its observation, and an interest for observing it; the objective is to maximize the total interest of the schedule. This primary version of the problem has been described and solved by Catusse et al. 2016, but it appears that shortening an observation would be worth doing if that makes room for another one. More generally an observation remains relevant even if its processing time is slightly less than the required value, with an accordingly downgraded interest. Such a situation can be modelled by processing time dependent profits: hence there is a need to study such models and, first of all, their complexity (this chapter); the practical resolution of the complete problem is the subject of Chapter II. Therefore, in this chapter, we first state formally the problem and propose several profit functions (Section I.1) together with a literature review (Section I.2); then, we prove some generic properties (Section I.3) moving on to NP-completeness results (Section I.4) before considering polynomial cases (Section I.5).

I.1 Processing time dependent profit

We consider a scheduling problem with n jobs; each job T j has a deadline d j and a profit function w j (p j ) that depends on the decided processing time p j .

CHAPTER I. PDPS PROBLEMS

The objective is to maximize the total profit:

max n j=1 w j (p j )
with the convention that p j = 0 if T j is not scheduled. Note that, if there are no release dates (all jobs are available at t = 0), a job can always be scheduled with a null processing time at the beginning of the schedule. However, when jobs have different release dates, it may be impossible to schedule all jobs in an optimal solution, even with null processing time. This is illustrated on Figure I.2. In this example, we assume that the profit yielded by J 1 is much greater than the profit that would yield J 2 if it were scheduled and that preemption is not allowed. If one schedules J 2 , then J 1 has to be interrupted, and therefore no optimal solution exists where J 2 is scheduled. However, the feasibility can always be ensured since not scheduling any job is a feasible solution. Also note that the objective function is not a regular criterion and the instance size (as input of a Turing machine) depends on how w j are defined. In the remainder of this chapter, we call this problem and its variants Processing time Dependent Profit Scheduling Problems (PDPSP). We propose now several profit functions that are studied thereafter; to this extent, we adapt the 3-field notation (see e.g. Pinedo 2015) as follows:

α | f, β | - w j (p j )
where, in addition to the classical α and β, parameter f describes the profit function. We note the objective -w j (p j ) as the minimization of the negative profit, since, in scheduling, objectives are usually to be minimized (Pinedo 2015). Also note that deadlines are not explicitely indicated, since they are implied by the objective.

In this chapter, we consider the profit functions presented in Figure I.3. The one corresponding to the original astrophysics problem is the last. The other ones are simplifications that allow to understand the role of each of its components. The mnemonic for the abbreviations is: ST stands for Setup Time, B for Bounded, L for Linear, and IP for Initial Profit. In all cases, the parameter b j is called the growth rate of job T j , w min j its minimum profit, w max j its maximum profit, p min j its minimum processing time and p max j its maximum processing time. Note that these denominations are slightly abusive: indeed, the minimum processing time of any job T j is 0 and the maximum processing time is d j , but there is no use scheduling T j during p j ∈ 0, p min j ∪ p max j , d j . We also define b max = max j b j and d = max j d j . In Section I.5, we present polynomial algorithms that generalize to a Piecewise Linear Profit (PLP) model. In this model, each job T j has K j pieces. A piece is given by an initial processing time p k j , an inital profit w k j and a growth rate b k j :

w j (p) = w k j + b k j (p -p k j ) for p k-1 j ≤ p < p k j
and we assume that:

(1) p 0 j = 0 and w 0 j = 0 (no profit for a null processing time); (2) p K j ≥ d j (profit must be defined at least up to the deadline);

(3) w k+1 [. The assumption that input data are integers holds for every model (and is further discussed later, see Section I.3). For LBP, LBPST and LBPSTIP, we allow growth rates to be rationnal, but such that w max j remain integers. For a PDPSP with a PLP, we note K = max j=1,...,n K j .

A general PDPSP is obviously an NP-complete problem. In this chapter, we study the complexity of the various PDPSP with a focus on the PLP model in order to find easier cases.

I.2 Literature review and applications

From a theoretical point of view, PDPSP can been seen as a combination of job selection (also called scheduling with rejection) and scheduling with controllable processing times. Job selection is a classical class of scheduling problems. A review of these problems can be found in [START_REF] Slotnick | Order acceptance and scheduling: A taxonomy and review[END_REF][START_REF] Shabtay | A survey on offline scheduling with rejection[END_REF]. The most basic variants of job selection problems are the Knapsack Problem and the scheduling problem 1 | | U j . Research focuses on richer variants of the problem. For example, [START_REF] Bartal | Multiprocessor Scheduling with Rejection[END_REF]Zhang et al. 2009 consider a job selection problem of which objective is to minimize the sum of the makespan and the penalties of all rejected jobs while [START_REF] Engels | Techniques for scheduling with rejection[END_REF] minimize the sum of the weighted completion times of the jobs scheduled plus the sum of the penalties of the jobs rejected. Zhang et al. 2010 minimize any regular objective function while bounding the sum of the penalties of the rejected jobs. [START_REF] Shabtay | A bicriteria approach to scheduling a single machine with job rejection and positional penalties[END_REF] propose a bicriteria approach, the first objective being a regular criterion and the second one being the total rejection cost. Lin and Ying 2015 study of permutation flowshop with job rejection. [START_REF] Eun | Maximizing total job value on a single machine with job selection[END_REF] study a completion time dependent profit maximization scheduling problem, while in PDPSP, the profit depends on the processing time. Scheduling problems with controllable processing times have also received great attention (see [START_REF] Shabtay | A survey of scheduling with controllable processing times[END_REF]Shioura et al. 2018 for surveys). In those problems, processing times are controllable by allocating a resource to job operations. The objective is then either related to job completion times, resource consumption cost or a combination of both. When there is no discontinuity in the profit function, algorithms developed for scheduling problems with controllable processing times may also solve PDPSP. For example, the problem 1 | LBP | -w j (p j ) is equivalent to the scheduling problem with controllable processing times subject to deadlines adressed in Janiak and Kovalyov 1996. A variant of PDPSP has been introduced by [START_REF] Cao | On Several Scheduling Problems with Rejection or Discretely Compressible Processing Times[END_REF]. They studied it as a bi-criteria problem, minimizing the weighted number of rejected jobs and minimizing the total cost of compression. They prove the NP-hardness of the problem, and propose a FPTAS, a pseudo-polynomial algorithm and a greedy heuristic. In this chapter, we aggregate both criteria, which allows us to study more accurately and exclusively the complexity of those problems. PDPSP are also related to scheduling problems with late work criteria, noted Y w (see [START_REF] Sterna | A survey of scheduling problems with late work criteria[END_REF] for a survey), in which only the units executed after the due dates are penalized. For example, as used in Section I.9.3, P | LBP, pmtn, r j | -w j (p j ) can be seen as the late job problem P | pmtn, r j | w j Y j , that can be solved with a minimum cost flow model in polynomial time [START_REF] Leung | Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF].

PDPSP appear as subproblems of several applications. As stated in the introduction, the issue arises in astrophysics and the search for exoplanets (Lagrange et al. 2016) in which the picture quality depends on the observation time; even though the current practice does not take advantage of such a possibility, due to the lack of tools to handle it. A similar phenomenon appears in Earth observation scheduling problems. In the problem described by Verfaillie and Lemaître 2001, polygon acquisitions may be only partially satisfied. The gain associated with a partially sat-isfied request is either linearly or convexly dependent of the useful aquired surface. [START_REF] Cordeau | Maximizing the value of an Earth observation satellite orbit[END_REF]Habet et al. 2010;Wang et al. 2011;[START_REF] Tangpattanakul | A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite[END_REF] used the same model for variants of the problem. Yang and Geunes 2007 also introduced a scheduling problem including PDPSP as subproblem. As in PDPSP, the objective is profit maximization, but their model also includes tardiness costs. They propose two heursitics with computational experiments on randomly generated instances.

I.3 Notations and general results

Some notations are used consistently throughout the rest of this chapter. I denotes an instance and |I| is its size (as input of a Turing machine). S denotes a solution, |S| is the number of tasks included in S (possibly with a null processing time). For a task T j ∈ S: p j (S) denotes its processing time, s j (S) its start date and C j (S) its completion time (end date). When there is no ambiguity on the solution, we will just write p j , s j and C j . w(S) denotes the total profit of S (i.e., w(S) = T j ∈S w j (p j )). U denotes a dominant set of solutions, i.e. for any instance, there exists an optimal schedule in U. Furthermore, when considering complexity issues and thus decision problems, we shall add a bound W ∈ N and ask whether there exists a feasible schedule such that j w j (p j ) ≥ W . For all the cases considered in this chapter, providing start dates, processing times and, if needed, processing machines for all tasks completely defines a solution; for each case, such a solution is indeed a polynomial certificate and will be enough to straightforwardly conclude that it belongs to NP.

The first remarkable fact about processing time dependent profit scheduling problems, is that the profit functions proposed in Section I.1 strongly relate one to another, and there is indeed a whole complexity hierarchy that exists among them and is represented by Figure I.5. This hierarchy is useful to exhibit maximally-polynomial or minimally-NP-complete cases. Then, a generic dominance property exists: Lemma I.3.1 For P | | -w j (p j ), the set of solutions for which all tasks are scheduled (possibly with p j = 0) and such that, on each machine, tasks are scheduled in non-decreasing order of their deadlines and without idle time, is dominant.

Proof. In any solution, idle times can always be removed and tasks that are not scheduled can always be added at time 0 with a null processing time, without altering the feasibility nor the value of the solution. Hence, we can consider, without loss of generality, that all tasks are scheduled and without idle time.

Then, the proof relies on a classical exchange argument. Let S be an optimal solution. If there exist unordered pairs of tasks (that is (T j , T k ) such that T j is scheduled after T k on the same machine whereas d j < d k ), then there exists an unordered pair (T * j , T * k ) such that T * j is scheduled immediately after T * k . The solution obtained by exchanging T * j and T * k remains feasible and optimal, while strictly decreasing the number of unordered pairs. Repeating this operation leads to a feasible optimal solution without any unordered pairs, i.e. with tasks scheduled in non-decreasing order of their deadlines. This lemma is very useful but is not enough to directly provide optimal solutions, as one does not know how long each task must be executed. Still, note that for the single machine case, a solution can be characterized by the list of the processing times allocated to each task.

In scheduling, it is quite common that start dates and end dates are integers as soon as input data are integers and there is no preemption. So one could think that similar results could be designed for all but exotic profit functions. This is not that simple and one should be aware that tasks may end at noninteger (even irrational) instants as soon as the profit function is not linear

CHAPTER I. PDPS PROBLEMS 0 1 0 1 p w(p) w 1 (p) w 2 (p) w 3 (p)
Three tasks T 1 , T 2 , T 3 such that :

• w 1 (p) = p • w 2 (p) = √ p/2 • w 3 (p) = 2 -2/(1 + p)
and

d 1 = d 2 = d 3 = 1 Example 1: I = {T 1 , T 2 }.
In an optimal solution: p 1 = 15/16, p 2 = 1/16. Example 2: I = {T 1 , T 3 }. In an optimal solution: (1) all tasks are scheduled (possibly with p j = 0) and on each machine, tasks are scheduled in non-decreasing order of their deadlines without idle time;

p 1 = √ 2 -1, p 3 = 2 - √ 2.
(2) all start dates and processing times are integers, i.e. for all j = 1, . . . , n: s j , p j ∈ {0, . . . , d j } is dominant.

Proof.

(1) has already been proven by Lemma I.3.1. For (2), let us first remind that d j ∈ N and p k j ∈ {0, . . . , d j } for all j = 1, . . . , n and k = 1, . . . , K j . In any solution, idle times can be removed and the last task on a machine can always be extended up to its deadline (possibly with no profit). As a consequence, one can assume without loss of generality that on each machine: the first task starts at time 0, every other task starts as soon as the preceding one ends, and the last task ends at an integer time (its deadline). Clearly, if all processing times are integers, then all start dates and end dates are integers. So, let's prove that there always exists an optimal solution with only integer processing times.

If that is not true, then there exists a solution S which has the above properties, which is optimal, and which is "minimal", in the sense that it has the minimum number of tasks with non-integer processing times. Let T j 1 be the first task such that p j 1 / ∈ N; as the total processing times on a machine sums up to an integer, there exists another task T j 2 , on the same machine, such that p j 2 / ∈ N; we assume T j 2 to be the first such task after T j 1 . There exists

k 1 such that p k 1 j 1 ≤ p j 1 < p j 1 < p j 1 ≤ p k 1 +1 j 1
and there exists k 2 such that

p k 2 j 2 ≤ p j 2 < p j 2 < p j 2 ≤ p k 2 +1 j 2 . If b j 1 = b j 2 ,
then p j 1 can be decreased, and p j 2 increased by the same amount, until either p j 1 or p j 2 is an integer (which then contradicts that S is "minimal"). If b k 1 j 1 < b k 2 j 2 then there exists > 0 such that decreasing p j 1 by and increasing p j 2 by the same amount yields a feasible and strictly better solution, which contradicts the optimality of S; the reverse holds if b k 1 j 1 > b k 2 j 2 . In this case, note that T j 1 and T j 2 being the first two tasks with non-integer durations, none of the tasks in between can end on an integer date, and in particular, none ends at its deadline; hence it is indeed always possible to increase p j 1 by some > 0 and decrease p j 2 by the same amount, without altering the feasibility of the solution.

Lemma I.3.2 still does not provide a direct optimal solution, but we can develop a dynamic programming algorithm on it: Theorem I.3.1 Algorithm 1 returns an optimal solution to P | PLP | -w j (p j ) in time O(n(md m+1 + log n)).

Proof. Algorithm 1 is a standard dynamic-programming algorithm. The value f * (j, C) is the best value that can be obtained by scheduling the first j tasks so that the machines end at the completion times defined by C. By Lemma I.3.2, there exists an optimal solution with tasks ordered as in step 1. Thus, it is enough to consider the tasks in this order and to enumerate, for a task T j , all possible end dates on all machines. This is done by step 3: the base case is straightforward, whereas the two next cases forbid idle time (since there always exists an optimal solution without idle time) and the general case performs the actual enumeration. The complexity of step 1 is O(n log n). Then, the complexity of step 2 is O(nd log K) which is O(nd 2 ) since K ≤ d; this pre-computing enables to get w j (C i -s) in O(1) during step 3. The size of f * is nd m and it takes O(md) to compute a given value in step 3. The overall complexity is thus O(nmd m+1 + n log n).

20/127

CHAPTER I. PDPS PROBLEMS

Algorithm 1 P | PLP | -w j (p j ) INPUTS: an instance I 1: Sort tasks in non-decreasing order of their deadlines 2: Precompute w j (p) for all task T j , j = 1, . . . , n and for all p = 0, . . . , d j 3:

Let C = {C ∈ {0, . . . , d} m , C 1 ≤ • • • ≤ C m }. Return max C∈C f * (n, C)
such that:

f * (j, C) =                                        0 ∀j = 0, . . . , n and C = {0, . . . , 0} -∞ if j = 0 and C = {0, . . . , 0} (idle time at the beginning is never necessary) -∞ if d j < max C i (no task can end at C i ) max 1≤i≤m s∈{0,...,C i } f * (j -1, C -(C i -s)e i ) + w j (C i -s) otherwise
where C is a m-dimensional vector containing the required completion time of the last task scheduled on each machine and e i is the vector such that e i i = 1 and e i k = 0 for all k = i.

Note that Algorithm 1 runs in pseudo-polynomial time if the number of machines is fixed and even in polynomial time if d is also fixed (or more generally if either due-dates or processing times are bounded). That is: Algorithm 1 runs in a reasonable time if the numbers involved are reasonable. This is a standard property for a number-problem (well-known for, e.g., Partition or Subset Sum) which may actually apply in practice. For instance, in the star scheduling problem, the duration of a night is naturally bounded and the duration of an observation is technically limited, providing practical upper bounds on respectively due-dates and processing times.

Lemma I.3.2 provides a first overview of the structure of solutions with a PLP function. Still, we can have better results: most tasks can be scheduled during a p k j , and only a few will not. If two consecutive tasks are not scheduled during a p k j , one of them can have its processing time decreased for the benefit of the other one (the increase of the first task may be limited by its deadline).

We get even stronger results if we only consider "interesting" processing times instead of all p k j . We define P j the set of "interesting" processing times of task T j as follows:

P j = ρ 1 j , . . . , ρ K ρ j j = ρ, ∃k, ρ = p k j and w k j (ρ -1) < w k j (ρ) with ρ 1 j ≤ • • • ≤ ρ K ρ j j
and we call T j a regular task if p j ∈ P j and a singular task if p j / ∈ P j (note that K ρ j ≤ K j ). An "interesting" processing time corresponds to a p k j except when the previous piece has a null growth rate and there is no discontinuity between them. The need to define P j is illustrated in Figure I.7; for instance, p min j is "interesting" for LPSTIP or LBPSTIP, but it is not for LPST and LBPST. The following lemma indicates what makes those processing times "interesting": Lemma I.3.3 For P | PLP | -w j (p j ), the set of solutions such that:

(1) all tasks are scheduled (possibly with p j = 0) and, on each machine, tasks are scheduled in non-decreasing order of their deadlines without idle time;

(2) for all pairs of singular tasks T j 1 , T j 2 scheduled on the same machine, there exists at least one task T k scheduled on the same machine between T j 1 and T j 2 and ending at its deadline is dominant. Furthermore, there exists a polynomial time algorithm that, given any optimal solution, returns an optimal solution satisfying those properties.

Proof.

(1) has already been proven in Lemma I.3.1.

Let S be an optimal solution such that all tasks are scheduled without idle time and in non-decreasing order of their deadlines, and which is "minimal", in the sense that it has the minimum number x of pairs of singular tasks scheduled on the same machine without any task ending at its deadline in between. If x = 0 then the Lemma is proven.

Otherwise, let T j 1 , T j 2 be such a consecutive pair. Let k 1 , k 2 be such that

p k 1 j 1 ≤ p j 1 < p k 1 +1 j 1 and p k 2 j 2 ≤ p j 2 < p k 2 +1 j 2
, and let k ρ 1 , k ρ 2 be such that ρ

k ρ 1 j 1 < p j 1 < ρ k ρ 1 +1 j 1 and ρ k ρ 2 j 2 < p j 2 < ρ k ρ 2 +1 j 2
. Remark that:

(1) There may be many processing times (p k 1 -1

j 1 , p k 1 -2 j 1 . . . ) between ρ k ρ 1 j 1
and p k 1 j 1 , but they are all not interesting processing times, meaning null growth rate and no discontinuity. As a consequence, decreasing p j 1 to any value in [ρ

k ρ 1 j 1 , p k 1 j 1 ] yields a loss of profit of only b k 1 j 1 (p j 1 -p k 1 j 1 ). (2) If b k 2 j 2 > 0 then p k 2 +1 j 2
is an interesting processing time. As a consequence, increasing p j 2 to the next interesting processing time yields a gain of profit of b k 2 j 2 (ρ

k ρ 2 +1 j 2 -p j 2 ). If b k 1 j 1 = 0, then we can set p j 1 = ρ k ρ 1 j
1 and shift all the jobs scheduled after to the left. The solution value is not downgraded (remark (1)) and x stricly decreases. Therefore, S was not minimal. The case b k 2 j 2 = 0 is similar.

If 0 < b k 1 j 1 ≤ b k 2 j 2
, we can reduce the processing time of T j 1 by min{p j 1ρ

k ρ 1 j 1 , ρ k ρ 2 +1 j 2
-p j 2 }, shift all the regular tasks scheduled between T j 1 and T j 2 toward T j and increase the processing time of T j 2 by the same quantity. In the process the profit is not downgraded (remarks (1) and (2), with b k 1 j 1 ≤ b k 2 j 2 ) and thus the solution remains optimal, but either T j 1 or T j 2 is now a regular task, and x strictly decreases. Therefore, S was not minimal. If b k 1 j 1 > b k 2 j 2 > 0, we can increase the processing time of T j 1 by min{ρ

k ρ 1 +1 j 1 - p j 1 , {d l -C l } s j 1 ≤s l <s j 2 , p j 2 -ρ k ρ 2 j 2 } (
with l restricted to tasks on the same machine as T j 1 and T j 2 ), shift all the tasks scheduled between T j 1 and T j 2 toward T j 2 and decrease the processing time of T j 2 by that quantity; this is valid and the solution remains optimal, but either T j 1 is now a regular task, or T j 2 is now a regular task, or there exists a task T l such that C l = d l between T j 1 and T j 2 : in any case, x stricly decreases and therefore S was not minimal. In all cases, there is a contradiction, so x = 0. Furthermore, the operations described above can be used to strictly decrease x in an optimal solution with x > 0. Then, after a polynomial number of polynomial iterations, we can tranform any optimal solution in an optimal solution belonging to the dominant set.

A direct corollary from Lemma I.3.3 is that when all tasks have the same deadline, there will be at most one singular task on each machine: Corollary I.3.1 For P | PLP, d j =d | -w j (p j ), the set of solutions such that:

(1) all tasks are scheduled (possibly with p j = 0) and, on each machine, tasks are scheduled without idle time;

(2) on each machine, there is at most one singular task is dominant. Furthermore, there exists a polynomial time algorithm that, given any optimal solution, returns an optimal solution satisfying these properties.

I.4 NP-complete cases

Intuitively, some problems are NP-complete since several profit functions can be shaped to fit with the profit function of classical scheduling problems (for example LP ST IP , b j =0). Then, reductions from P | | C max , P m | | C max or the Knapsack Problem will be straightforward. In the former case, the problems will be proven to be strongly NP-complete. In the latter cases, with fixed m, the problems will be only weakly NP-complete as we already know a pseudo-polynomial algorithm to solve them (Theorem I.3.1).

For one machine problems, we have:

Theorem I.4.1 1 | d j =d | -w j (p j
) is weakly NP-complete with the following profit functions:

(

1) LPSTIP, b j =b (2) LBPST, b j =b (3) LBPSTIP, b j =b, w max j =w max (4) LBPSTIP, p max j =p max , w max j =w max
Proof. As remarked before, those problems clearly belong to NP. Furthermore, they have already been proven to be solvable in pseudo-polynomial time (Theorem I.3.1). We prove their NP-completeness using reductions from Knapsack, known to be NP-complete [START_REF] Garey | Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite[END_REF] and defined as follows.

Let I be an instance of Knapsack: given a finite set A of items and for each item j ∈ A a size a j ∈ N and a value v j ∈ N, and given bounds B ∈ N and V ∈ N; the question is: is there a subset S ⊂ A such that j∈S a j ≤ B and j∈S v j ≥ V ?

(1): Knapsack happens to be the particular case with b j = 0: there are as many tasks as there are items, and for task T j we set w min j = v j , p min j = a j and we use B as the common due-date d.

(2) the idea is to set the growth rate to 1 and to stretch the minimum processing times and common deadline. The maximum processing time of a task is then relatively close to its minimum processing time, and every task scheduled, will necessarily be executed during its maximum processing time. Technically, let v = n(max k v k + 1) and let I be an instance of 1 | LBPST, b j =b, d j =d | -w j (p j ) with n tasks T j , j = 1, . . . , n, such that w max j = v j , b = 1, p max j = va j , p min j = va j -v j (note that p min j ≥ 0) and d = vB; the question is: is there a schedule S such that w(S) ≥ V ? If I has a "yes" answer, then clearly, I has a "yes" answer too. If I has a "yes" answer, then let S be an optimal solution of I . Corollary I.3.1 provides a polynomial time algorithm to transform S such that it contains at most one task that is not scheduled during its maximum processing time (all tasks have the same deadline). Suppose that there is one such task T j . The schedule is full (otherwise p j could be increased and the solution value improved). Thus,

p(S) = T k ∈S p k = d = vB. Furthermore, p(S) = T k ∈S p k = v T k ∈S a k - (p max j -p j ). However p max j -p min j < v, therefore, p(S)
is not a multiple of v, which contradicts p(S) = vB. As a consequence, all tasks in S are scheduled during their maximum processing time and it is clearly possible to build the corresponding solution for Knapsack. Therefore, I has a "yes" answer.

For LBPSTIP, one could use the fact that LBPSTIP generalizes LPSTIP: hence a consequence of the first case (LPSTIP, b j = b) is that LBPSTIP is NP-complete even if b j = b. However, the proof relies on b j = 0 and thus one must add the additional requirement that w min j = w max j ; with such restrictions, LBPSTIP and LPSTIP are indeed the same problem and so there is nothing new. The two particular cases of LBPSTIP considered are different; we nevertheless use the same general idea.

(3): we set growth rates to 1 and the minimum profits large enough so that processing a task beyond its minimum processing time always yields a negligible profit, mimicking a classical scheduling problem.

Let I be an instance of Knapsack. Let I be an instance of 1 | LBPSTIP, b j =b, w max j =w max , d j =d | -w j (p j ) with n tasks T j , j = 1, . . . , n, such that b = 1, p min j = a j , w min j = (B + 1)v j , w max = (B + 1)(max k v k + 1), p max j = a j + (B + 1)(max k v k + 1 -v j ) and d = B; the question is: is there a schedule S such that w(S) ≥ (B + 1)V ? If I has a "yes" answer, then clearly, I has a "yes" answer too. If I has a "yes" answer, then let S be an optimal solution for I . Corollary I.3.1 provides a polynomial algorithm to transform S such that it contains at most one task that is not scheduled during its minimum processing time in polynomial time (no task can be scheduled during its maximum processing time since they are all greater than the deadline). If there is no such task, then S directly provides an optimal solution to I. Otherwise, let T j be this task. Let S be a solution identical to S except that T j is only scheduled during p min j . Then w(S ) = T k ∈S (B + 1)v k and it is therefore a multiple of B + 1. However, w(S) ≥ (B + 1)V and w(S ) -w(S) ≤ d < B + 1. Therefore, w(S ) ≥ (B + 1)V , and it is possible to build the corresponding solution for Knapsack. Therefore, I has a "yes" answer.

(4): we set the maximum processing time large enough so that processing a task beyond its minimum processing time always yield a negligible profit, mimicking a classical scheduling problem. Let I be an instance of 1 | LBPSTIP, p max j =p max , w max j =w max , d j =d | -w j (p j ) with n tasks T j , j = 1, . . . , n, such that p min j = a j , p max = B(max

k v k + 2), x = n j=1 (B(max k v k + 2) -a j ), b j = x max v k +1-v j B(max k v k +2
)-a j , w min j = xv j , w max = x(max k v k + 1) and d = B; the question is: is there a schedule S such that w(S) ≥ xV ? Note that all parameters are integers and all maximum profits are equal. If I has a "yes" answer, then clearly, I has a "yes" answer too. If I has a "yes" answer, then let S be an optimal solution of I . Corollary I.3.1 provides a polynomial algorithm to transform S such that it contains at most one task that is not scheduled during its minimum processing time in polynomial time (no task can be scheduled during its maximum processing time since they are all greater than the deadline). If there is no such task, then S directly provides an optimal solution to I. Otherwise Let T j be this task. Let S be a solution identical to S except that T j is only scheduled during p min j . Then w(S ) = T k ∈S xv k and it is therefore a multiple of x. However, w(S) ≥ xV and w(S ) -w(S) ≤ b j d < x. Therefore, w(S ) ≥ xV , and it is possible to build the corresponding solution for Knapsack. Therefore, I has a "yes" answer.

Note that the proofs for the LBPSTIP cases do not hold if, for all T j , we Proof. As remarked before, these problems clearly belong to NP. Furthermore, the cases with a fixed number of machines have already been proven solvable in pseudo-polynomial time (Theorem I.3.1 as special cases of PLP). We prove their NP-completeness using reductions from P m | | C max and P | | C max , respectively known to be NP-complete [START_REF] Garey | Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite[END_REF] and strongly NP-complete [START_REF] Garey | Strong " NP-Completeness Results: Motivation, Examples, and Implications[END_REF].

Let I be an instance of P m | | C max : n tasks T j , j = 1, . . . , n, processing times x j ∈ N, j = 1, . . . , n and a deadline δ ∈ N; the question is: is there a m-processor schedule, m ∈ N, for {T j } j=1,...,n that meets the overall deadline δ?

(1): P m | | C max happens to be a particular case of P m | LPSTIP, w min j =w min , b j =b, d j = d | -w j (p j ) with b j = 0: there are as many tasks, and for task T j we set w min = 1, p min j = x j and d = δ.

(2): let I be an instance of P m | LBP, w max j =w max , d j =d | -w j (p j ), with n tasks T j , j = 1, . . . , n, such that p max j = x j , w max = n k=1 x k and d = δ; the question is: is there a schedule S such that w(S) ≥ n n k=1 x k ? Note that for all j = 1, . . . , n, b j = w max p max j = n k=1,k =j x k is an integer. I responds "yes" if and only if each task T j is scheduled during x j before δ, yielding a solution to I . Conversely, I responds "yes" if and only if each task is scheduled during its maximum processing time, yielding a solution to I.

27/127

CHAPTER I. PDPS PROBLEMS

(3): we choose d = δ and b = 1 and w max j = x j and thus p max j = x j ; the question is: is there a schedule S such that w(S) ≥ n j=1 x j ? The reasonning is the same.

(4): let I be an instance of 1 | LBPST, b j =b, w max j =w max , d j =d | -w j (p j ) with n tasks T j , j = 1, . . . , n, such that w max = 1, b = 1, p max j = x j , p min j = x j -1 and d = δ; the question is: is there a schedule S such that w(S) ≥ n? I responds "yes" if and only if each task T j is scheduled during x j before δ, yielding a solution to I . Conversely, I responds "yes" if and only if each task is scheduled during its maximum processing time, yielding a solution to I.

(5): let I be an instance of 1 | LBPSTIP, p min j =p min , b j =b, w max j =w max , d j =d | -w j (p j ) with n tasks T j , j = 1, . . . , n, such that p min =1, p max j = x j , b = 1, w max = max j x j + 1, w min j = w max + 1 -p max j and d = δ; the question is: is there a schedule S such that w(S) ≥ nw max ? Note that w min j ≥ 0. I responds "yes" if and only if each task T j is scheduled during x j before δ, yielding a solution to I . Conversely, I responds "yes" if and only if each task is scheduled during its maximum processing time, yielding a solution to I.

In all cases, the transformations are not only polynomial but even strongly polynomial; hence the strong NP-completeness of the concerned cases.

I.5 Polynomial cases solved with dynamic programming

In this section, we propose three new algorithms for PDPSP with a PLP function, that return optimal solutions in polynomial time for several profit functions.

I.5.1

P m | PLP, |{p k j }| ≤ κ | -w j (p j )
The first algorithm is an adaptation of Algorithm 1 where instead of considering all instants {0, . . . , d}, we only consider a polynomial subset of relevant instants, thus reducing the number of states to a polynomial number. From Lemma I.3.3, we can deduce the dominant set of possible start dates and end dates (we assume the tasks are sorted in non-decreasing order of their deadlines):

Θ 0 =    d j + n l=j+1 ρ l       j=0,...,n-1 ρ j+1 ∈P j+1 . . . ρn∈Pn    ∪    d j - j l=1 ρ l       j=1,...,n ρ 1 ∈P 1 . . . ρ j ∈P j   
The size of this set is a priori exponential. However, it can be rewritten as follows. Let P = ∪ j=1,...,n P j and let ...,n lρ=0,...,j lρ≤j Clearly: Θ 0 ⊂ Θ, and

Θ =    d j + ρ∈P l ρ ρ    j=0,...,n-1 lρ=0,...,n-j lρ≤n-j ∪    d j - ρ∈P l ρ ρ    j=1,
|Θ| = O n |P|+1
In the general case, |P| = O (nK), but if |P| is independent of the instance size, |Θ| is polynomial in the instance size. For example, for LBPSTIP, p min j =p min , p max j =p max : |P| = 2. More generally, we note |{p k j }| ≤ κ to specify problems for which the number of different values for p k j is bounded by a integer κ independent of the input. Let us also remind that P m in the first field of the three fields notation implies that m is also independent of the input. Then we can adapt Algorithm 1 to run on instants of Θ instead of {0, . . . , d}: Theorem I.5.1.1 Algorithm 2 returns an optimal solution to P m | PLP, |{p k j }| ≤ κ | -w j (p j ) in polynomial time.

Proof. The proof is similar to the one of Theorem I.3.1 in combination with Lemma I.3.3 which ensures that the problem is solved optimally. The complexity of step 1 is

O(n log n). The size of f * is n|Θ| m , that is O(n m(|P|+1)+1
), and since O(m log |Θ|) is required to retrieve a value of f * , it takes O(mn |P|+1 (m|P| log n + log K) to compute a given value in step 2. The overall complexity is thus polynomial in the size of the input.

The complexity hierarchy among models allows to derive the following particular cases:

Algorithm 2 P m | PLP | -w j (p j ) INPUTS: an instance I 1: Sort tasks in non-decreasing order of their deadlines

2: Let C = {C ∈ Θ m , C 1 ≤ • • • ≤ C m }. Return max C∈C f * (n, C) such that: f * (j, C) =                                        0 ∀j = 0, . . . , n and C = {0, . . . , 0}
-∞ if j = 0 and C = {0, . . . , 0} (idle time at the beginning is never necessary)

-∞ if d j < max C i (no task can end at C i ) max 1≤i≤m s∈Θ,s≤C i f * (j -1, C -(C i -s)e i ) + w j (C i -s) otherwise
where C is a m-dimensional vector containing the required completion time of the last task scheduled on each machine and e i is the vector such that e i i = 1 and e i k = 0 for all k = i.

Corollary I.5.1.1 P m | | -w j (p j ) can be solved in polynomial time with the following profit functions:

• LPST (and thus LP)

• LBPST, |{p max j }|≤κ (and thus LBP, |{p max j }|≤κ)

• LBPSTIP, |{p min j , p max j }|≤κ (and thus LPSTIP, |{p min j }|≤κ)

Besides, for PLP, if the pieces are all of the same duration (or more precisely, if there exists ρ 0 such that for all ρ ∈ P, there exists k ≤ K: ρ = kρ 0 ), then:

Θ = {d j + lρ 0 } j=0,...,n l=-jK,...,(n-j)K is a dominant set of instants of size |Θ | = O n 2 K
Furthermore, a value f * (j, C) can be retrieved in O(1) and w j (p) can be computed in O(1). Therefore the complexity of the algorithm is dramatically reduced to O(mn 2m+3 K m+1 + n log n).

I.5.2 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b} | -w j (p j )
Algorithm 2 is handy when there is some regularity among the p k j , as that allows to enumerate all possible end dates. When there is no such regularity, the problem remains polynomial in some cases, provided some regularity on the profit. Again, the trick is to use dynamic programming schemes, but now the recursive functions do not represent a maximum profit for given completion times, but required time to achieve a given profit. We will exhibit a polynomial algorithm for 1 | PLP, |{w k j }|≤κ, b k j ∈{0, b} | -w j (p j ). First, consider the following dominant set:

Lemma I.5.2.1 For 1 | PLP, b k j ∈{0, b} | -w j (p j
), the set of solutions U 1 such that:

(1) all tasks are scheduled (possibly with p j = 0) and on each machine, tasks are scheduled in non-decreasing order of their deadlines without idle time;

(2) there exists at most one singular task is dominant.

Proof.

(1) has already been proven in Lemma I.3.1.

Let S be an optimal solution such that all tasks are scheduled without idle time and in non-decreasing order of their deadlines, and which is "minimal", in the sense that it has the minimum number x of singular tasks. If x ≤ 1 then the Lemma is proven.

Otherwise, let T j 1 , T j 2 be two singular tasks. Let k 1 , k 2 be such that

p k 1 j 1 ≤ p j 1 < p k 1 +1 j 1 and p k 2 j 2 ≤ p j 2 < p k 2 +1 j 2
, and let

k ρ 1 , k ρ 2 such that ρ k ρ 1 j 1 < p j 1 < ρ k ρ 1 +1 j 1 and ρ k ρ 2 j 2 < p j 2 < ρ k ρ 2 +1 j 2 . If b k 1 j 1 = 0, then we can set p j 1 = ρ k ρ
1 j 1 and shift all the tasks scheduled after to the left. The solution value is not downgraded and x stricly decreases. Therefore, S was not minimal. The case b k

2 j 2 = 0 is similar. If 0 < b k 1 j 1 = b k 2 j 2 , we can reduce the processing time of T j 1 by min{p j 1 - ρ k ρ 1 j 1 , ρ k ρ 2 +1 j 2
-p j 2 }, shift all the regular tasks scheduled between T j 1 and T j 2 toward T j 1 and increase the processing time of T j 2 by the same quantity. In the process the profit is not downgraded and thus the solution remains optimal, but either T j 1 or T j 2 is now a regular task, and x strictly decreases. Therefore, S was not minimal.

Even though dominant, U 1 remains too large for an exhaustive search. We restrict it to another dominant set of smaller size. Among the solutions with exactly one singular task T l such that the tasks scheduled before T l yield a profit w C and the tasks scheduled after a profit w S , we will only consider solutions such that T l starts as early as possible and ends as late as possible. Therefore, we define the function C * (j, w) (resp. s * (j, w)) that computes the earliest makespan (resp. the latest possible start date) to schedule tasks T 1 , . . . , T j (resp. T j , . . . , T n ) in this order with a profit w and such that all tasks are regular:

C * (j, w) =                  0 if w = 0 +∞ if j = 0 and w = 0 min k=1,...,K w k j ≤w C * (j-1,w-w k j )+p k j ≤d j C * (j -1, w -w k j ) + p k j otherwise s * (j, w) =                d n if w = 0 -∞ if j = n + 1 and w = 0 max k=1,...,K w k j ≤w s * (j+1,w-w k j )≤d j s * (j + 1, w -w k j ) -p k j otherwise Lemma I.5.2.2 For 1 | PLP, b k j ∈{0, b} | -w j (p j )
, the set of solutions U 2 such that, for all S ∈ U 2 :

(1) S ∈ U 1 ;

(2) if S contains a singular task T l , then for all S ∈ U 1 such that

• l-1 j=1 w j (p j (S )) = l-1 j=1 w j (p j (S)) • n j=l+1 w j (p j (S )) = n j=l+1 w j (p j (S)) then C l-1 (S) ≤ C l-1 (S ) and s l+1 (S) ≥ s l+1 (S )
is dominant.

Proof.

(1) has already been proven by Lemma I.5.2.1. Let S ∈ U 1 be an optimal solution. If S contains no singular task, then S ∈ U 2 . If S contains a singular task T l , then let

S c = arg min S ∈U 1 l-1 j=1 w j (p j (S ))= l-1 j=1 w j (p j (S)) n j=l+1 w j (p j (S ))= n j=l+1 w j (p j (S)) C l-1 (S ) S s = arg max S ∈U 1 l-1 j=1 w j (p j (S ))= l-1 j=1 w j (p j (S)) n j=l+1 w j (p j (S ))= n j=l+1 w j (p j (S)) s l-1 (S )
and let S be the solution of U 1 such that:

p j (S ) =      p j (S c ) if j < l p l (S) if j = l p j (S s ) if j > l
Since S, S c , and S s are feasible, S is also feasible. Furthermore, w(S ) = w(S) and thus S is optimal. Eventually, by construction, S ∈ U 2 .

Let

Ω 0 =    n j=1 w j       w 1 ∈{w k 1 } k=1,...,K 1 . . . wn∈{w k n} k=1,...,Kn   
For all j = 1, . . . , n, for all w / ∈ Ω 0 : C * (j, w) = +∞ and s * (j, w) = -∞. Thus, we only need to compute C * (j, w) and s * (j, w) when w ∈ Ω 0 . As for Θ 0 , the size of this set is a priori exponential. However, it can be rewritten as follows. Let W = ∪ j=1,...,n k=1,...,K j In the general case, |W| = O (nK), but if |W| is independent of the instance size, |Ω| is polynomial in the instance size. For example, for LBPSTIP, w min j =w min , w max j =w max : |W| = 2. We can therefore deduce a polynomial algorithm for the problem when the number of w k j is bounded:

Theorem I.5.2.1 Algorithm 3 returns an optimal solution to 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b} | -w j (p j ) in polynomial time. Algorithm 3 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b} | -w j (p j ) INPUTS: an instance I 1:
Sort tasks in non-decreasing order of their deadlines 2: Compute C * (j, w) and s * (j, w) for all (j, w) ∈ ({0, . . . , n} × Ω)

3: return max                      max w∈Ω C * (n,w)<+∞ w (no singular task) max (l,w C ,ws) ∈({1,...,n}×Ω×Ω), C * (l-1,w C ) ≤s * (l+1,ws) w C + w s + w l (s * (l + 1, w s ) -C * (l -1, w C )) (one
• LPSTIP, |{w min j }| ≤ κ, b j =b • LBPST, b j =b, |{w max j }| ≤ κ • LBPSTIP, |{w min j , w max j }| ≤ κ, b j =b
One may remark that the dominance property from Lemma I.5.2.2 can be generalized to the case of parallel machines. However, this will not lead to a polynomial algorithm (unless P = NP) as was proved by Theorem I.4.2.

I.5.3 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b j }, d j =d | -w j (p j )
We will now propose our last algorithm, based on similar ideas. Tasks are now allowed to have different growth rates (still b k j =b j ), but they should have a common deadline. Since all deadlines are equal, Corollary I.3.1 directly provides a dominant set U 3 such that:

(1) all tasks are scheduled (possibly with p j = 0) in non-decreasing order of their deadlines and without idle time;

(2) for all S ∈ U 3 , S contains at most one singular task.

Once again, this set is too large for an exhaustive search and we restrict this set to another dominant set of smaller size. We now define C * (j, w, l) that computes the earliest makespan to schedule tasks T 1 , . . . , T j but not T l with a profit of w such that all tasks are regular:

C * (j, w, l) =                C * (j -1, w, l) if j = l 0 if w = 0 +∞ if j = 0 and w = 0 min k=1,...,K w k j ≤w C * (j -1, w -w k j , l) + p k j otherwise Lemma I.5.3.1 For 1 | PLP, b k j ∈{0, b j }, d j =d | -w j (p j ) , the set of solutions U 4 such that, for all S ∈ U 4 : (1) S ∈ U 3 (2) if S contains a singular task T l , then for all S ∈ U 3 such that n j=1,j =l w j (p j (S )) = n j=1,j =l w j (p j (S)), then n j=1,j =l p j (S) ≤ n j=1,j =l p j (S )
is dominant.

Proof.

(1) has already been proven by Corollary I.3.1.

Let S ∈ U 3 be an optimal solution. If S contains no singular task, then S ∈ U 4 . If S contains a singular task T l , then let

S C = arg min S ∈U 3 n j=1,j =l w j (p j (S ))= n j=1,j =l w j (p j (S)) n j=1,j =l p j (S )
and let S be the solution of U 3 such that:

p j (S ) = p j (S C ) if j = l p l (S) if j = l
Since S is feasible, S is also feasible. Furthermore, w(S ) = w(S) and thus S is optimal. Eventually, by construction, S ∈ U 4 .

We can therefore deduce a polynomial algorithm for the problem when the number of w k j is bounded:

Theorem I.5.3.1 Algorithm 4 returns the optimal value of 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b j }, d j =d | -w j (p j ) in polynomial time. Algorithm 4 1 | PLP, |{w k j }|≤κ, b k j ∈{0, b j }, d j =d | -w j (p j ) INPUTS: an instance I 1:
Compute C * (j, w) for all (j, w) ∈ ({0, . . . , n} × {1, . . . , n}) and C * (j, w, l) for all (j, w, l) ∈ ({0, . . . , n} × Ω × {1, . . . , n})

2: return max              max w∈Ω C * (n,
• LPSTIP, |{w min j }|≤κ • LBPST, |{w max j }|≤κ • LBPSTIP, |{w min j , w max j }|≤κ
One may remark that the dominance property from Lemma I.5.3.1 can be generalized to the case of parallel machines. However, this will not lead to a polynomial algorithm (unless P = N P ) as was proved by Theorem I.4.2.

In this section, we proposed several algorithms to solve different flavors of PLP functions. Even though polynomial, the proposed complexities may appear discouraging. However they are tremendously reduced when the algorithms are applied to particular cases, e.g., those presented in the corollaries. For example, Algorithm 5 is directly derived from Algorithm 4 to solve 1 | LPSTIP, w min j =w min , d j =d | -w j (p j ) in O(n 2 ).

Algorithm 5 1 | LPSTIP, w min j =w min , d j =d | -w j (p j ) INPUTS: an instance I 1: Sort tasks in non-decreasing order of their minimum processing time 2: OPT ← 0 3: for l from 1 to n do 4:

w ← w min , C ← p min l 5: OPT ← max {OPT, w + b l (d -C)} 6: for j from 1 to n, j = l do 7: w ← w + w min , C ← C + p min j 8: if C > d then 9: break 10: OPT ← max {OPT, w + b l (d -C)} 11: return OPT

I.6 Polynomial cases solved with list algorithms

In this section, we present polynomial list algorithms for several particular cases.

I.6.1 P

| LP | -w j (p j )
On a single machine and without additional constraint, scheduling jobs in non-increasing order of their growth rates, from the previous scheduled job end date until their deadline (when possible, i.e. when the previous scheduled job end date is before the current job deadline), leads to an optimal solution that generalizes to parallel machines:

Theorem I.6.1.1 Algorithm 6 returns an optimal solution of P | LP | -w j (p j ) in poly- nomial time O(n log n). Algorithm 6 P | LP | -w j (p j ) 1: if m ≥ n then 2:
for j from 1 to n do 3:

Schedule T j on machine j on [0, d j [.

4: else

5:

Sort jobs in non-increasing order of their growth rates b j .

6:

Let q be a priority queue initialized such that element i has cost 0 for i = 1, . . . , m.

7:

q contains the current completion time on each machine.

8:

for j from 1 to n do 9:

Get element i with minimum cost C from q. 10:

if d j > C then 11: Schedule T j on machine i on [C, d j [. 12:
Update the cost of i in q to d j .

I.6.2 1 | LBP | -w j (p j )
We already showed that the case with parallel machines is NP-complete even with a common deadline and either identical growth rates b j =b or identical maximum processing-times p max j =p max (see Theorem I.4.2). On the other hand, with a single machine and common deadlines (d j = d), this problem corresponds to the well-known fractionnal knapsack problem. This problem has been first solved by Dantzig 1957: it suffices to fill the knapsack with the items with the largest ratio value over weight until the knapsack is full. A O(n) implementation is even possible (Kellerer et al. 2004). In this section, we prove that, with arbitrary deadlines, the problem can still be solved in polynomial time. A first approach uses linear programming and is once again based on Lemma I.3.1. The whole procedure is summed-up in Algorithm 7. However, more efficient algorithms can be designed.

Algorithm 7 1 | LBP | -w j (p j )
1: Sort jobs in non-decreasing order of their deadlines. 2: Solve the following linear program:

     max n j=1 b j p j s.t. j k=1 p k ≤ d j ∀j = 1, . . . , n p j ≤ p max j ∀j = 1, . . . , n
Indeed, the problem can be seen as the linear relaxation of the well-known 1|| w j U j where it is allowed to schedule only fractions of jobs. 1|| w j U j is NP-complete and solvable in pseudo-polynomial time [START_REF] Lawler | Sequencing to Minimize the Weighted Number of Tardy Jobs[END_REF]. For the linear relaxation, Potts and Van Wassenhove 1988 proposed an explicit algorithm that schedules jobs by non-increasing order of deadlines for an overall complexity of O(n log n). The problem is also equivalent to the scheduling problem with controllable processing-times presented by Janiak and Kovalyov 1996; the problem is to schedule on one machine n jobs, the processing-times of which can be decreased by allocating a continuously divisible resource. Janiak and Kovalyov 1996 proposed a polynomial time algorithm that schedules jobs by non-decreasing order of their deadlines and that also runs in O(n log n) time. This algorithm can be adapted to 1 | LBP | -w j (p j ) as follows: schedule jobs in non-decreasing order of their deadlines; whenever a job T j cannot be scheduled during p max j , make room for it by reducing the processing time of less profitable jobs already scheduled. As it generalizes to broader cases, the precise algorithm is presented later in this chapter; the impatient reader will find it as Algorithm 10 by setting p min j = 0 for all j = 1, . . . , n (this assumption insures that the returned solution is feasible). Note that such a procedure builds, at iteration k, the optimal solution of the instance that only contains the first k jobs. Whatever algorithm one prefers, the conclusion is:

Theorem I.6.2.1 Problem 1 | LBP | -w j (p j ) can be solved in polynomial time O(n log n). I.6.3 1 | LBPST, p min j =p min , b j =b | -w j (p j ) The problem 1 | LBPST, b j =b | -w j (p j ) is already NP-complete (see Theorem I.4.2).
In this section, we propose a polynomial algorithm for the case with identical minimum processing-times and identical growth rates. Another polynomial case with parallel machines, based on a completely different approach, is presented in Section I.7.3. As in the previous section, the set of solutions such that every job is scheduled and in non-decreasing order of their deadlines, is dominant. Thus, the problem can be reformulated as:

max n j=1 max{0, b(p j -p min )} s.t. p j ≤ p max j , ∀j = 1, . . . , n j k=1 p k ≤ d j , ∀j = 1, . . . , n (I.1)
but, as the objective is not linear, that does not prove that the problem is polynomial.

We nevertheless use this dominance property and implement it as a similar scheme as that proposed in Janiak and Kovalyov 1996, to get Algorithm 8. The remaining of this section is dedicated to prove the correctness of this algorithm. Roughly speaking: schedule jobs in non-decreasing order of their deadlines; whenever a job T j cannot be scheduled during p max j , make room for it by reducing the processing time of jobs with the smallest non null processing time. The proof of correctness of such a scheme is inspired by the proof proposed by Janiak and Kovalyov 1996 but requires major technical adjustments. It relies on reducing the instance by updating deadlines. After the update, jobs may not be sorted in non-decreasing order of their deadlines anymore, but jobs are not reordered. Therefore, we consider Problem ( P ) defined as follows:

max

n j=1 max{0, b(p j -p min )} s.t. p j ≤ p max j , ∀j = 1, . . . , n j k=1 p k ≤ d j or p j = 0 ∀j = 1, . . . , n ( P )
Problem ( P ) is similar to Formulation (I.1). The input and output are the same. However, in Formulation (I.1), the order was deduced from a dominance property; whereas in Problem ( P ), the order is part of the instance,

40/127 CHAPTER I. PDPS PROBLEMS

Algorithm 8 1 | LBPST, p min j =p min , b j =b | -w j (p j ) 1: Sort jobs in non-decreasing order of their deadlines d j . 2: C ← 0 Current completion time. 3: Let q be a priority queue 4: q will contain jobs currently scheduled and with non-null processing time; the cost of a job in q will be its processing time in the current solution. 5: p j ← p max j for all j = 1, . . . , n 6: for k from 1 to n do 7:

C ← C + p max k 8: Add element k with cost p max k in q. 9: while C > d k do 10:
Let j be the minimal cost element of q.

11:

if p j ≤ C -d k then 12: C ← C -p j 13: p j ← 0 14:
Remove element j from q.

15: else 16:

p j ← p j -(C -d k ) 17: C ← d k 18: return {p j } j=1,...,n
i.e. jobs cannot be reordered. Furthermore, jobs may not be sorted in nondecreasing order of deadlines in ( P ). This has two consequences. First, a job may not be scheduled at all; this corresponds to p j = 0 in Problem ( P ). Second, if p j = p max j , the solution may not be feasible because of the deadlines of the following jobs. Hence the need to define ρ k j and ρ j :

ρ k j = min p max j , min u,j≤u≤k d u ρ j = ρ n j
ρ j can be interpreted as the effective maximum processing time of job T j in any feasible solution. ρ k j can be defined equivalently recursively:

ρ 0 j = p max j ρ k j = min ρ k-1 j , d k
From these definitions, one can derive several properties. If, for some k < n, there exists

l k such that ρ k l k ≥ ρ k j for all j = 1, . . . , k, then ρ k+1 l k ≥ ρ k+1 j . If k 2 ≥ k 1 , then ρ k 2 j ≤ ρ k 1 j . If j 2 ≥ j 1 and ρ k j 1 < p max j 2 , then ρ k j 2 ≤ ρ k j 1 .
Besides, remark that if I is an instance of 1 | LBPST, p min j =p min , b j =b | -w j (p j ) and Ī an instance of Problem ( P ) with the same input provided such that d j are sorted in non-decreasing order, then an optimal solution of Ī is clearly an optimal solution of I. Now let us start with the following dominance property: Lemma I.6.3.1 Let ρ max = max j=1..n ρ j . For a given job T l such that ρ l = ρ max , there exists an optimal solution to ( P ) in which p l = ρ l .

Algorithm 9

1: procedure INCREASEBEST({p j } j=1,...,n , l) 2:
p j ← p j for all j = 1, . . . , n Proof. Let S be an optimal solution. We prove that Algorithm 9 applied to S returns a solution S which remains optimal and such that p l = ρ max . First, note that the solution value is never degraded: n k=0 p k is constant throughout the algorithm and the number of scheduled jobs is non-increasing. Second, the algorithm stops either at line 4 or line 14. Otherwise, after the for loop, p k = 0 for all k = l and p l < ρ max , corresponding to a sub-optimal solution. As the solution value is never degraded that would contradict that S was optimal. If the algorithm stops at line 4, then the initial solution S was as expected. Otherwise, it stops at the end of iteration k and p j = 0 for all j ≤ k, j = l; therefore constraint j of P is satisfied for all j ≤ k, j = l. Furthermore, for all j > k, j = l, C j = C j ; therefore, constraint j is also satisfied for j > k, 42/127 CHAPTER I. PDPS PROBLEMS j = l. Finally, if k ≤ l, C l = C l , and if k > l, p j = 0 for all j < l; therefore constraint l is also satisfied.

Lemma I.6.3.2 Let I be an instance of Problem ( P ). There exists a job T l such that ρ l = ρ max and such that Algorithm 8 executed on I sets p l at ρ l . (NOTE: Since jobs are not allowed to be reordered in Problem P , the first step of Algorithm 8 is skipped, whenever applied to an instance of Problem P .)

Proof. Let ρ k max = max j=1,...,k ρ k j be the maximum effective processing time at iteration k. We show that at each iteration k, there exists T l k such that p k l k = ρ k max . T l k is therefore necessarily at the end of the queue. In the case where there are several jobs at ρ k max , we consider T l k to be the last one in the queue. It is clearly true at the end of iteration 1. Let us suppose the property true for some k < n. Then, at iteration k + 1, job T k+1 is added to the queue with processing time p max k+1 (in what follows, p k j is the processing time of job T j at the end of iteration k):

• Case p max k+1 < p k l k . Then ρ k+1 k+1 < ρ k max . Therefore ρ k+1 max = ρ k+1 l k .
T l k stays at the end of the queue and p k+1

l k = ρ k+1 l k . • Case p max k+1 ≥ p k l k . Then ρ k+1 k+1 ≥ ρ k+1 l k ≥ ρ k+1 j
for all j = 1, . . . , k. T k+1 takes the last position in the queue and p k+1 k+1 = ρ k+1 k+1 and ρ max k+1 = ρ k+1 k+1 .

Let I be an instance of Problem ( P ). From Lemma I.6.3.2, we know that there exists a job that Algorithm 8 sets at ρ max . Let T l be such a job. We now define the following reduced instance I (of Problem ( P )):

• d k = d k for all k = 1, . . . , l -2 • d l-1 = min{d l-1 , d l -ρ l l } (if l > 1) • d k = d k -ρ k l for all k = l + 1, . . . , n (ensuring d k ≥ 0) • T l
is removed from I Note that the jobs may not be sorted in non-decreasing order of deadlines anymore.

Lemma I.6.3.3

Let I be an instance of P and I (one of) its reduced instance. If S is an optimal solution of I , then S = {p 1 , . . . , p l-1 , ρ l , p l+1 , . . . , p n } is an optimal solution of I.

Proof. First, we prove that S is feasible.

If ρ l = p max l : For k < l -1, k j=1 p j = k j=1 p j ≤ d k = d k . For k = l -1, l-1 j=1 p j = l-1 j=1 p j ≤ d l-1 = d l -p max l ≤ d l-1 + p max l -p max l = d l-1 . For k ≥ l + 1, k j=1 p j = k j=1,j =l p j + ρ l ≤ d k + p max l = d k -p max l + p max l = d k . Therefore, all constraints are satisfied. If ρ l < p max l , then there exists a last k * ≥ l such that d k * = ρ l = ρ k *
l and therefore d k * = 0 and for all j ≤ k * , j = l: p j = 0. Therefore, constraints 1 to k * are satisfied. Furthermore, for k

≥ k * + 1: k j=1 p j = k j=k * +1 p j + ρ l ≤ d k + ρ k * l = d k -ρ k l + ρ k * l ≤ d k .
Therefore, all constraints are satisfied. Now, let suppose that S is not optimal, i.e. there exists an optimal solution S * of I such that w(S * ) > w(S). From Lemma I.6.3.1, we can consider a

S * such that p * l = ρ l . Let S * = {p * 1 , . . . , p * l-1 , p * l+1 , . . . , p * n } be a solution of I . w(S * ) = w(S * ) -w l (ρ l ) > w(S) -w l (ρ l ) = w(S ). Therefore, if S * is feasible, it contradicts S optimal. Let us show that S * is feasible. For k < l: k j=1 p j * = k j=1 p * j ≤ d k = d k . For k > l: k j=1,j =l p j * = k j=1 p * j -ρ l ≤ d k -ρ l = d k +ρ k l -ρ l ≤ d k .
Therefore, all constraints are satisfied. • Case ρ l = p max l : let k = l. Clearly, for all k < l -1, for all j = 1, . . . , k:

p k j = p j k . At iteration l -1 for I, C l-2 + p max l-1 -C l-1 units of processing time are removed from q. -if C l-2 + p l-1 ≤ d l-1 and C l-1 + p max l ≤ d l ,
then no unit of processing time is removed from q, neither for I at iterations l -1 and l, nor for I at iteration l -1.

-if C l-2 + p l-1 > d l-1 and C l-1 + p max l ≤ d l :
no other unit of processing time are removed from q at iteration l. Furthermore, d l-1 = d l-1 and therefore the same number of units of processing time is removed at iteration l -1 for I .

-if C l-1 + p max l > d l (which implies C l = d l ): C l-1 + p max l -C l
units of processing time are removed from q at iteration l on I. The total number of units of processing time removed from q at iteration l and l -

1 for I is therefore C l-2 + p max l-1 + p max l -d l . Furthermore C l-1 = d l-1 = d l -p max l and therefore C l-2 + p max l-1 -C l-1 = C l-2 + p max l-1 + p max l
-d l units of processing time are removed at iteration l -1 for I .

The same amount of processing time is removed for both instances and since by definition of T l , p l is not modified, both queue are identical after iteration l except for p l .

• Case ρ l < p max l : let k be the first iteration such that p k l = ρ l . Then for all j = 1, . . . , k, j = l, p k j = 0. Furthermore d k = 0, and thus p j k = 0.

In both cases, for the remaining iterations, Algorithm 8 clearly behaves the same on I and I since: q and q are the same (except for p l ); on I, by definition of T l , p l will not be modified; and on I ,

d k = d k -ρ l for all k = k + 1, . . . , n.
We now can prove the correctness of Algorithm 8:

Theorem I.6.3.1 Algorithm 8 returns an optimal solution of problem 1 | LBPST, p min j =p min , b j =b | -w j (p j ) in polynomial time O(n log n).
Proof. Algorithm 8 returns an optimal solution on any instance of Problem ( P ) with 0 job. Let suppose that it returns an optimal solution on any instance of Problem ( P ) with n -1 jobs, and let us show that it then returns an optimal solution on any instance of Problem ( P ) with n jobs. Let I be an instance with n jobs and I (one of) its reduced instance. Using the induction hypothesis, the solution S returned by the algorithm on I is optimal. From Lemma I.6.3.3 and Lemma I.6.3.4, the solution returned by the algorithm on I is also optimal. Therefore, the algorithm returns the optimal solution for any instance of Problem ( P ), and consequently of Problem 1 | LBPST,

p min j =p min , b j =b | -w j (p j ). Furthermore, it runs in O(n log n). I.6.4 1 | LBPSTIP | -w j (p j )
This problem is very close to the scheduling problem with controllable processing times where the processing time is a linear decreasing function of the amount of a common resource allocated to the job. The difference is that, in our problem, we may not schedule a job. Therefore we adapt from Janiak and Kovalyov 1996 the following property:

Lemma I.6.4.1 Let V be a set of tasks such that there exists an optimal solution S which set of scheduled jobs is V , i.e. V = T j ∈ S, p j (S) ≥ p min j . If we know such a set V , then Algorithm 10 returns an optimal solution to 1

| LBPSTIP | -w j (p j ) in polynomial time O(n log n).
Algorithm 10

1: procedure Schedule(V ) 2:
Sort jobs in non-decreasing order of their deadlines d j .

3:

C ← 0
Current completion time.

4:

for k from 1 to |V | do 5: C ← p min k 6: if C > d k then 7:
return No feasible solution.

8:

C ← 0 9:
Let q be a priority queue 10:

q will contain scheduled jobs sorted in non-decreasing order of their growth rates. Let j be the minimal cost element of q. 17:

if p j -p min j ≤ C -d k then 18: C ← C -(p j -p min j )
19:

p j ← p min j 20:
Remove element j from q.

21: else 22:

p j ← p j -(C -d k ) 23: C ← d k 24: return |V | j=1 b j p j
Unfortunately, in the general case, finding such a set V has been shown to be NP-complete. Therefore, we will look for special cases for which one can be found in polynomial time.

For a given instance, let T be the set of jobs and let T j 1 , T j 2 ∈ T . We say that T j 1 dominates T j 2 if for any optimal solution S such that T j 2 ∈ S and T j 1 / ∈ S, there exists an optimal solution S containing all the tasks of S except T j 2 and containing T j 1 . For example, if p min j 1 ≤ p min j 2 and p max

j 1 ≤ p max j 2
and w min j 1 ≥ w min j 2 and w max

j 1 ≥ w max j 2
and d j 1 ≤ d j 2 then T j 1 dominates T j 2 . This dominance defines a partial order of T . Thus, in an optimal solution, there is no reason to schedule a task if another task that dominates it has not been scheduled either: Lemma I.6.4.2 Let U 2 be the set of solutions such that for all S ∈ U 2 , for all T j 1 ∈ S and

T j 2 / ∈ S, T j 1 does not dominate T j 2 . U 2 is dominant.
In order to evaluate the size of this set, we show that any of its solutions can be characterized only by its "worst tasks":

Lemma I.6.4.3 For all V ∈ U 2 , let f : U 2 → the set of antichains of T V → {T j , ∀T q ∈ V, q = j, T j does not dominate T q } f is bijective. Proof. Clearly, for all V ∈ U 2 , f (V )
is indeed an antichain of T . Therefore, f is well defined. First, we show that f is surjective: if A is an antichain of T , f -1 (A) is then obtained recursively by adding all tasks dominating tasks of A. Note that this computation can be achieved in polynomial time. Now, we show that f is injective

: let V 1 , V 2 ∈ U 2 such that f (V 1 ) = f (V 2 ). Then • every task of f (V 1 ) = f (V 2 ) belongs to V 1 and V 2 ;
• therefore, by definition of U 2 , every task that dominates a job of f

(V 1 ) = f (V 2 ) belongs to V 1 and V 2 ; • furthermore, every task outside f (V 1 ) = f (V 2 ) that does not dominate a task of f (V 1 ) = f (V 2 ) does not belong to V 1 nor V 2 . Therefore V 1 = V 2 .
S ← SCHEDULE(f -1 (A))
SCHEDULE is Algorithm 10

I.7 Polynomial cases solved with maximum weight b-matching

In this section, we exhibit polynomial algorithms for three processing time dependent profit maximization scheduling problems with parallel machines. Those algorithms use as subproblem the maximum weight b-matching which can be solved in polynomial time [START_REF] Schrijver | Combinatorial optimization: polyhedra and efficiency[END_REF]. Given a graph G(V, E), a demand/supply b v for each vertex v ∈ V , and a weight w e for each edge e ∈ E, a b-matching of G is a vector The algorithm consists in solving a polynomial number of maximum weight b-matching problems which rely on the dominant set described below.

x ∈ N E such that x(δ v ) ≤ b v for all v ∈ V (
We consider the case d = qp min + r, with q, r ∈ N, q ≥ 2, 0 < r < p min . However, with a similar reasoning, the results can be adapted for the case d = qp min , q ∈ N, q ≥ 2. The case d < 2p min is trivial.

Lemma I.7.1.1 Let U be the set of solutions such that for all S ∈ U:

• for all T j ∈ S, p j ≥ p min ;

• there exists at most one job T j ∈ S such that p j / ∈ {d, p min , p min + r}.

U is dominant.

. . . . . . Thus, U is the set of solutions for which each scheduled job is at least executed during the minimum processing time and with at most one special job. Note that a special job is also a break job, and if a job T j is the only special job scheduled on a machine, then p j = tp min + r, t ∈ N, t > 1 and the other jobs scheduled on this machine have processing time p min . Let S / ∈ U be an optimal solution. Let us build another solution S ∈ U from S without degrading its value. First, we can remove all jobs with an allocated execution time strictly shorter than p min without degrading the solution value.

Then we ensure that for each machine, there is only one break job. If it is not the case, let T j and T k (b j ≥ b k ) be two break jobs scheduled on the same machine. Let's transfer p k -p min processing time from T k to T j . The value of the solution is not degraded and the number of break jobs on this machine strictly decreases. Thus, by repeating this operation, we get a solution as good as S with at most one break job per machine. Finally, we ensure that there is only one special job in the solution. If it is not the case, let T j and T k (b j ≥ b k ) be two special jobs of S. From the previous step, we know that T j and T k are not scheduled on the same machine (let's call M i j and M i k the machine on which T j and T k are respectively scheduled), but they are the only special jobs on their machine. This implies that the other jobs scheduled on those machines all have processing time p min and that p j = t j p min + r and p k = t k p min + r, with t j , t k ∈ N, t j , t k > 1. Now, while T j and T k remain special jobs, we move a job (different from T j ) from M i j to M i k , increase processing time of T j by p min and decrease processing time of T k by p min . Thus, in a finite number of steps, we have either p j = d or p k = p min + r and the number of special jobs have strictly decreased. Therefore, we can repeat the operation till there remains only one special job in the solution. Now we can prove the theorem:

Theorem I.7.1.1

There exists an algorithm that solves P | LPSTIP, p min j =p min , d j =d | -w j (p j ) in polynomial time.

Proof. Following Lemma I.7.1.1, we only focus on solutions of U. Thus, we can partition the jobs of a solution S ∈ U into 4 subsets depending on their processing time (and one more for the non scheduled jobs):

U 1 (S) = {T j ∈ S, p j = d} U 2 (S) = {T j ∈ S, T j is a special job} U 3 (S) = T j ∈ S, p j = p min + r U 4 (S) = T j ∈ S, p j = p min U 0 (S) = {T j / ∈ S} ∀k ∈ {0, . . . , 4}, n k (S) = |U k (S)| t(S) = 0, if U 2 (S) = ∅ d-p j p min , if U 2 (S) = {T j }

50/127

CHAPTER I. PDPS PROBLEMS t(S) represents the number of jobs scheduled on the same machine as the job of U 2 . Note that, if U 2 (S) = {T j }, then p j = d -t(S)p min . Furthermore, for all S ∈ U

0 ≤ n 1 (S) ≤ m 0 ≤ t(S) ≤ n -1 n 2 (S) = 0, if t(S) = 0 1, otherwise n 3 (S) = m -n 1 (S) -n 2 (S) n 4 (S) = (q -1)n 3 (S) + t(S) (remember that q = d/p min ) n 0 (S) = n -n 1 (S) -n 2 (S) -n 3 (S) -n 4 (S)
Therefore, if n 1 (S) and t(S) are fixed, we can determine n 2 (S), n 3 (S), n 4 (S) and n 0 (S). Thus, the optimal value is the best optimal value of the O(n 2 ) problems with those parameters fixed:

OPT = max (n 1 ,t)∈({0,...,m}×{0,...,n-1}) OPT(n 1 , t)
Now, we show that for all (n 1 , t) ∈ {1, . . . , m} × {0, . . . , n -1}, a maximum weight b-matching problem model can compute OPT(n 1 , t). We create n nodes T j , j = 1, . . . , n with supply 1, and a 5 nodes U i , i = 0, . . . , 4 with demand n i such that n 2 = 0 if t ≤ 1, 1 otherwise;

n 3 = m -n 1 -n 2 , n 4 = (q -1)n 3 + t, n 0 = n -n 1 -n 2 -n 3 -n 4 .
Then for all j = 1, . . . , n, for all i = 0, . . . , 4, we add the arc (T j , U i ) with capacity u ji = 1 and cost:

c ji =                w j (d) i = 1 w j (d -tp min ) i = 2 w j (p min + r) i = 3 w min j i = 4 0 i = 0
A part of the graph including only one job is represented in Figure I.9. The size of the graph is polynomial compared to the size of the instance. Furthermore, the number of problems that we have to solve is O(n 2 ). Therefore, the problem can be solved in polynomial time.

I.7.2 P | LPSTIP, p min j =p min , b j =b | -w j (p j )
Compared to the previous case, we relax the property that all deadlines are equal, which is replaced by equal growth rates.

51/127

CHAPTER I. PDPS PROBLEMS Let S be an optimal solution. By Lemma I.3.1, we already proved that S can be modified to satisfy and (1).

T j 1 U 3 n 3 U 2 n 2 U 1 n 1 U 4 n 4 U 0 n 0 w j ( d ) wj ( ( t + 1 ) p m in + r ) w j (p min + r) w j ( p m
(2) is also clear: if a job is scheduled during strictly less than p min , it can be removed without degrading the solution value, and if it is scheduled during strictly more than p min , its processing time can be reduced to p min , all the 52/127 following jobs on the machine are shifted toward the beginning and the last job processing time can be increased by the same quantity. Since b j = b, the solution value is not degraded. The solution is still without idle time and the order does not change.

To prove (3), let s i last denote the start date of the last job scheduled on machine M i . Now let M i 1 and M i 2 be two machines such that

s i 1 last = min i s i last and s i 2 last = max i s i last . If s i 2 last -s i 1 last ≤ p min , then (3)
is satisfied. Otherwise, let T j be the last job scheduled on M i 1 and T k be the job scheduled on M i 2 on time interval s i 1 last + p min , s i 1 last + 2p min . Let S be the solution identical to S except that T k is moved from M i 1 to M i 2 and these two machines are rescheduled as illustrated in Figure I.11. Thus, w(

M i 1 ) = w(M i 1 ) - b(d j -(s i 1 last + p min )) + w min k + b(max (d j , d k ) -(s i 1 last + 2p min )) and w(M i 2 ) = w(M i 2 ) -w min k + bp min .
Therefore, the value of the new solution is not degraded, the previous conditions are still satisfied, and the operation can be repeated till the condition is satisfied.

Case d j ≥ d k j k j k Case d k ≥ d j j k j k

.2.1

There exists an algorithm that solves P | LPSTIP, p min j =p min , b j =b | -w j (p j ) in polynomial time.

Proof. Using Lemma I.7.2.1, we only consider solutions with x machines with k jobs and m -x machines with k + 1 jobs. All jobs scheduled on a machine have a processing time of p min , except the last job of each machine which is scheduled till its deadline. If the number η of scheduled jobs is known, then k and x can be determined as the quotient and remainder from the euclidean division of η by m. When k and x are fixed, the problem can be model as a maximum weight b-matching problem: each job is associated to a node, as well as each possible position for a job and there is an arc between a job and a position if the job can be scheduled at this position (according to its deadline). The flow unit denotes wether or not a job is scheduled at a position. A part of the graph including only one job is represented in Figure I.12. The size of the graph is polynomial compared to the size of the instance. Furthermore, n maximum weight b-matching problems have to be solved. Therefore, the problem can be solved in polynomial time. Proof. We consider d = qp max + r, with q, r ∈ N, 0 ≤ r < p max . Let U be the set of solutions such that:

• if n ≤ qm, all n jobs are scheduled during p max ;

• if qm < n ≤ (q + 1)m, all n jobs are scheduled; qm during p max and n -qm during r;

• if n > (q + 1)m, (q + 1)m jobs are scheduled; qm during p max and m during r.

54/127

CHAPTER I. PDPS PROBLEMS

T j 1 [0, p min ] m . . . [(k -2)p min , (k -1)p min ] m [(k -1)p min , d]
x Using similar arguments as before, one can prove that U is dominant. Figure I.13 illustrates the structure of the solutions of U when n > (q + 1)m. Jobs with diagonal stripes are scheduled during p max . Now, if n < qm, all n jobs can be scheduled during p max and this is an optimal solution. Otherwise we use a maximum weight b-matching model to solve the problem. We only present the case n > (q + 1)m, but the model is similar for the case qm < n ≤ (q + 1)m. The model includes two groups of nodes: the nodes T j , j = 1, . . . , n, associated with jobs and the nodes U 1 , U 2 and U 0 representing the state of a job in the solution (scheduled during p max , scheduled during r, or not scheduled). A part of the graph including only . . . For LBP, all one machine cases are polynomial as well as some cases with parallel machines. The case with parallel machines and identical maximum processing-times is still open and interesting since it lies between P | p j =p | w j U j and P | p j =p, pmtn | w j U j that were proved to be respectively solvable in polynomial time and NP-complete (Brucker and Kravchenko 1999). For LPSTIP, most cases with identical minimum processing times are polynomial, whereas having identical growth rates or minimum profits generally keeps the problem NP-complete. Three cases remain open. For LBPST, many cases with identical maximum processing times are polynomial. Nine cases are still open. Finally, for LBPSTIP, most cases are NP-complete and several problems remain open.

[(k -1)p min , kp min ] m -x [kp min , d] m -x ∅ n -(km + x) w m i n j w m in j w min j + b(dj -(k -1)p min ) w min j w m in j + b ( d j -k p m in

I.9 With release dates and preemption

In the previous sections, we looked at PDPS problems under various machine environments and with various profit functions, but without additional I.2 -LBPSTIP constraints. In this section, we briefly glance at some cases where jobs have release dates or where preemption is allowed.

P | b j =b, d j =d P | w max j =w max , d j =d P | p max j =p max P m | P m | b j =b, d j =d P m | w max j =w max , d j =d 1 | P m | p max j =p max P | p max j =p max ,

I.9.1 Preliminary results and notations

First, the following proposition rules out the interest of preemption for some 1-machine problems:

Proposition I.9.1.1 For 1 | pmtn | -w j (p j ), non preemptive solutions are dominant.

Note that this does not hold with parallel machines or with release dates. If release dates are present but deadlines are identical, the problem is equivalent to the one without release dates and with deadlines d j = d -r j .

When there are distinct release dates and distinct deadlines, as illustrated in Figure I.2 of Section I.1, we remind that solutions containing all jobs are not dominant (without preemption). In this case, we define the ordered set A = {α 1 , α 2 , . . . , α 2n } as the union of all release dates {r j } j=1...n and all deadlines {d j } j=1...n , sorted in non-decreasing order; we then derive the ordered set J of intervals as:

J = {[α t , α t+1 ]} t=1...2n-1

I.9.2 Linear profits (LP)

For the linear model, all cases were polynomial. If release dates are present and preemption is allowed, then scheduling the best job at each instant leads to an optimal solution (this even allows for multiple time-windows). This can be achieved by scheduling jobs in non-increasing order of their growth rates on their whole remaining time-windows as described in Algorithm 12, and it is a special case of Theorem I.9.3.2.

Algorithm 12 1 | LP, r j , pmtn | -w j (p j )

1: Sort jobs in non-increasing order of b j .

2: for j from 1 to n do 3:

for J ∈ J do 4:

if J ⊆ [r j , d j [ and no job is yet scheduled on J then 5:

Schedule T j on J However, without preemption, the problem is still open, even if some special cases are easy.

First, note that the set of solutions for which the start date and the end date of each task belong to A is dominant. More precisely, the set of solutions such that for each j = 1, . . . , n, T j starts either at r j or at the deadline d k of the previous job T k without idle time (if it exists), and ends either at d j or at the release date r k of the following job T k without idle time (if it exists), is dominant. With identical growth rates, the problem becomes an uptime maximization and it is enough to schedule jobs as soon as they are available as long as possible:

Theorem I.9.2.1 Scheduling jobs in non-decreasing order of their release dates, and until their deadlines (when possible), leads to an optimal solution of 1 | LP, r j , b j =b | -w j (p j ) in polynomial time.

If no job time-window is strictly included in the time-windows of another job with a strictly greater growth rate, then Algorithm 12 used when preemption is allowed will schedule each job on consecutive intervals, and thus lead to a feasible and therefore optimal solution.

Theorem I.9.2.2 Let us call T j a splitting job iff there exists T k such that r j > r k , d j < d k and b j > b k . If there is no splitting jobs, then Algorithm 12 returns a feasible optimal solution for 1 | LP, r j | -w j (p j ).

For the general case, we know that a job which is the best on its time-window will either be scheduled on its whole time-window or not be scheduled at all, i.e. if for all k

= j, [r j , d j [ ∩ [r k , d k [ = ∅ =⇒ b j ≥ b k
, then there exists an optimal solution for which T j is either scheduled on its whole time-window or not scheduled at all. This dominance property gives a possibility for a branch-and-bound algorithm scheduling jobs in non-decreasing order of their growth rates. Note that a job may then have multiple time-windows. The algorithm runs in exponential time, but if the number of splitting jobs k is bounded, then it runs in polynomial time O((nk) k ).

I.9.3 Linear bounded profits (LBP)

Adding release dates makes the problem NP-complete:

Theorem I.9.3.1 1 | r j | -w j (p j ) is strongly NP-complete with the following profit functions:

CHAPTER I. PDPS PROBLEMS

(1) LBP, b j =b (2) LBP, w max j =w max Proof. First, note that the problem clearly belongs to NP. Then, we shall prove that 3-partition, which is known to be strongly NP-complete [START_REF] Garey | Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite[END_REF], reduces to the decision version. Let I be an instance of 3-partition: a finite set A of 3m elements, a bound B ∈ Z + , and a size s(a) ∈ Z + for each a ∈ A, such that each s(a) satisfies B/4 < s(a) < B/2 and such that a∈A s(a) = mB; the question is: can A be partitioned into m disjoint sets S 1 , . . . , S m , such that for 1 ≤ i ≤ m,

a∈S i s(a) = B? (1): Let I be an instance of 1 | LBP, b j =b, r j | -w j (p j ) with 3m "real" jobs T 1 a , a ∈ A, such that r 1 a = 0, d 1 a = d (with d = mB + (m -1)), b 1 a = b, p max1 a = s(a), and m -1 "dummy" jobs T 0 j , 1 ≤ j ≤ m -1, such that r 0 j = j(B + 1) -1, d 0 j = j(B + 1), p max0 j = 1, b 0 j = b;
the question is: is there a schedule S such that w(S) = bd? I responds "yes" clearly implies a "yes" answer to I . Conversely, I responds "yes" means that there is a schedule with no idle time in which each job is scheduled and executed till its maximum processing-time. In particular, each job T 0 j , 1 ≤ j ≤ m -1 is scheduled on [j(B + 1) -1, j(B + 1)[, which means that they partition the other jobs into sets with processing-time B.

(2): for the case with identical maximum profit w max j =w max , we consider the same reduction, but the maximum profit of the jobs of I is w max and b j are set accordingly; the question is: Is there a schedule S such that w(S) = (3m + (m -1))w?

In all cases, the transformations are not only polynomial but even strongly polynomial; hence the strong NP-completeness of the concerned cases.

However, if preemption is allowed, the problem becomes polynomially solvable, even with parallel machines. Indeed, the problem can be seen as the scheduling problem with late jobs P | pmtn, r j | w j Y j . This problem can be solved with a minimum cost flow model in polynomial time [START_REF] Leung | Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF]):

Theorem I.9.3.2

Algorithm 13 returns an optimal solution for P | LBP, r j , pmtn | -w j (p j ) in polynomial time.

Proof. Algorithm 13 illustrates the flow model with the notations of our problem. Let us recall that J is the set of ordered time-intervals defined by release dates and deadlines.

There is a node t j , j = 1, . . . , n, for each job T j and a node J i t , t = 1, . . . , 2n-1, i = 1, . . . , m, for each element of J × {1, . . . , m}. There is an arc from the source s to each t j , j = 1, . . . , n with capacity p max j and cost -b j , an arc from each t j , j = 1, . . . , n, to each

J i t if [α t , α t+1 [ ⊆ [r j , d j
[ with an infinite capacity and no cost, and an arc between each J i t , t = 1, . . . , 2n -1, i = 1, . . . , m, and the sink t with capacity α t+1 -α t and no cost.

Algorithm 13 1 | LBP, r j , pmtn | -w j (p j ) 1: Solve the following minimum-cost flow problem (the pairs on the edges correspond to capacities and costs):

s t 1 t 2 . . . t N J 1 1 . . . J m 1 J 1 2 . . . J m 2 . . . . . . J 1 2n-1 . . . J m 2n-1 t ( p m a x 1 , -b 1 ) (p ma x 2 , -b 2 ) ( p m a x N , -b N ) ( ∞ , 0 ) (∞ , 0) ( ∞ , 0 ) ( ∞ , 0 ) ( ∞ , 0 ) (∞ , 0) (∞, 0) ( ∞ , 0 ) ( α 2 - α 1 , 0 ) ( α 2 -α 1 , 0 ) ( α 3 -α 2 , 0 ) (α 3 -α 2 , 0) ( α 2 N - α 2 N -1 , 0 ) ( α 2 N - α 2 N -1 , 0 )
2: Use a wrap around to convert the flow solution into a feasible schedule.

Note that with only few changes, this flow model can be adapted to jobs with disjoint time-windows and to any concave piecewise profit function.

I.9.4 Linear profits with setup times (LPST)

The general cases with release dates and with or without preemption are still open. However, a dynamic programming algorithm solves the problem if growth rates are identical. This algorithm is similar to Algorithm 1 except that only the release dates are considered for start dates:

Theorem I.9.4.1 Dynamic programming Algorithm 14 returns the optimal value of P m | LPST, b j =b, r j | -w j (p j ) in polynomial time O(n log n + m 2 n m ).

Algorithm 14 P | LPST, b j =b, r j | -w j (p j )

1: Sort tasks in non-decreasing order of their deadlines

2: Return f * (n, (d n , d n-1 , . . . , d n-m+1 )) with f * (j, C) =                    0 if j = 0 max        f * (j -1, C) max 1≤i≤m C i ≥r j } f * (j -1, C -(C i -r j )e i ) +w j (min{C i , d j } -r j ) otherwise
where C is a m-dimensional vector containing the required completion time of the last task scheduled on each machine and e i is the vector such that e i i = 1 and e i k = 0 for all k = i.

Proof. This proof being very similar to the previous proofs of this chapter, we will be more concise. Even though Lemma I.3.1 does not apply with release dates, scheduling jobs in non-decreasing order of their deadlines remains dominant: indeed with LPST with identical growth rates, it is dominant to end jobs by order of their deadlines and therefore to schedule them in this order. As a consequence, Algorithm 1 would return the optimal value of the problem. To have an efficient algorithm, we consider the set U of solutions such that all scheduled jobs are executed in non-increasing order of their deadlines and start at their release date; this set is dominant. Thus, for each job, only one start date is considered in Algorithm 14 and the size of C is n m . The overall complexity is thus O(n log n + m 2 n m ).

Note that even if preemption is allowed, non preemptive schedules are dominant. Therefore, the optimal value is the same as in the non preemptive case.

I.10 Conclusions

In this chapter, we studied a category of scheduling problems which are of theoretical and practical interest: processing time dependent profit maximization scheduling problems. We discussed some unusual properties and we proposed several piecewise-linear models as references. Then we underlined the complexity hierarchy that exists among those models. We proved NP-completeness of most general cases. Using various technics, we proposed dedicated polynomial algorithms for many particular cases; drawing a first map of these territories.

In the process, the complexity of many cases, including that of an original astrophysics application, have been derived. However, we merely laid some foundations, and many cases remain open or incomplete, and new models of profit functions or other constraints are still to be studied.

II

Chapter A fast, efficient, simple and versatile Large Neighborhood Search algorithm to schedule star observations on the Very Large Telescope

Large telescopes are few and observing time is a precious resource subject to a strong pressure from a competitive community. Besides, a growing number of astronomical projects require surveying a large number of targets during discontinuous runs spread over few months or years. An important example in today astronomy is the imaging surveys to discover and study extra-solar planets, which require to observe hundreds of targets to get a chance of imaging a few planets. There are many targets to be selected as actual observations and the total demand of observing time far exceeds the supply. Furthermore, the optimization must occur on different scales: prior to each year or semester, the requested targets list must fit the projected calendar, leading to adjust both; then the schedule is optimized again prior to each run (roughly, every week) and re-optimized prior to each night, to take into account priority changes and to reschedule failed observations. Even during one night, unexpected conditions such as bad weather might indeed require quasi real time adjustments. Therefore, efficient and both short-term and long-term (i.e. anytime) algorithms need to be designed.1

II.1 Problem description

The first part of this work has been conducted by Catusse et al. 2016. They studied a simplified model, its complexity, and developed algorithms to solve it. We first introduce their model: let M be a set of m nights and T be a set of n targets. Each target T j ∈ T has a profit w j and is visible during a set of nights M j , and for each night i ∈ M j , T j has a time-window [r i j , d i j [ and a duration p i j such that 2p j ≥ d i j -r i j (for almost all targets, there is a compulsory observation instant, the meridian). The objective is to maximize the total profit of the observed targets, such that each scheduled target T j must be observed within one of its time-windows during the corresponding observation time, and only one target can be observed at a time. Usually, a target is not visible in all nights, but rather in few sets of consecutive nights, and the time-window is slightly shifted at each night. Real instances include up to 1000 targets to schedule in about 100 nights. Eventually, between four and eight observations are scheduled in a night. The profit of an observation lies between 10 and 40. In the remaining of the chapter, we call this problem the Pure Star Observation Scheduling Problem (Pure SOSP). To solve this problem, Catusse et al. 2016 propose a branch-and-price algorithm combined with constraint programming, and a local search algorithm. They evaluated the performances of these algorithms on a dataset including one real instance and other generated instances of different sizes built to reproduce the properties of the real one. The branch-and-price algorithm is able to solve to optimality almost all tested instances within two hours whereas the local search algorithm provides solutions of good quality within a few minutes. The limited time-window size (2p i j ≥ d i j -r i j ) is a key feature of the problem resolution and is compulsory for the kind of images taken. It is equivalent for observations to having a "mandatory" instant, and therefore, it imposes the order for the observations scheduled within a night. Even if the model described above is only a simplified version of the actual practical problem, the work carried by Catusse et al. 2016 shows that the problem can be handled and therefore it is worth refining the model to get more realistic solutions. It also gives bounds that can be used to evaluate the performances of algorithms developed for richer models. From the users point of view, it also helped the astrophysicists to understand how operations research can be of great help and how to model more efficiently the problem.

In this chapter, we therefore consider a more accurate version of the model. The refinements are the following:

• The duration of an observation actually depends on its start date. Usually, the duration is the smallest around the middle of the time window and slightly increases if it is done before or after.

• Furthermore, observation durations are flexible. If an observation is slightly shorter, then the picture will be of lesser quality, but shortening an observation may be worth if it makes room for other ones. Note that due to telescope calibration, the observation always needs at least some time before a first valuable picture can be obtained; and beyond a certain duration, the picture quality stops increasing. This model (without the start date dependence) has been studied in Chapter I (see Figure I.3).

• Some observations called calibration observations are mandatory. They typically represent between 3% and 10% of the total number of observations scheduled.

• The mandatory instant property remains true for most observations, but some of them do not satisfy it. This may be for example due to the flexibility of observation durations, but also, calibration observations usually have very large time windows.

• In a few cases, a target might have several time windows during the same night. In the case of calibration observations, these time windows can even overlap.

• Besides scientific interests, targets also have emergencies. Some targets might be important to observe earlier in the schedule.

Currently, the astrophysicists schedule their observations using a software named SPOT (Lagrange et al. 2016). This software takes as input a list of stars with their astronomical properties, computes the astrophysical parameters (observation times, visiblity windows...), and does the optimization. The optimization part is achieved by an algorithm based on Simulated Annealing. It returns rather good solutions, but its convergence is rather slow. The goal of the present work is to propose to the astrophysicists a fast and efficient algorithm than can handle real problems, and to implement it in the software SPOT. As a consequence, the following practical constraints are also to be taken into account:

• As explained in the first paragraph, the algorithm should be anytime, providing good solutions in a few seconds or minutes, but still improving them if run several hours. Typically, astrophysicists want to have a good idea of the solution quality in order to, for example, adjust the profits. But then they will let the algorithm run during the whole day to improve the solutions. Quick solutions of good quality are also important to handle unexpected events during the night (clouds, rain, earthquakes...) that require modifiying the schedule. Furthermore, some artefacts from the software (observation time computing, visualization, etc.), significatively slows the algorithm. Therefore, quickly finding good solutions is even more crucial.

• Despite this, the optimal solution is not the absolute goal, and good industrial solutions may be sufficient. Profits are actually not perfectly accurate and astrophysicists will update them if they want to. However, the problem changes quickly, either because the constraints change, or because the astrophysicists may propose better models (for example the inclusion of emergencies). Therefore, it should be easy to update the algorithm to handle those changes.

• Eventually, the proposed algorithm should be simple: a developer with only little knowledge in operations research should be able to understand it, implement it and maintain it. This also implies avoiding the use of external solvers.

The branch-and-price proposed by Catusse et al. 2016, although highly effective, does not meet the above requirements. First, it is not anytime: the column generation procedure takes time and on some instances, several dozens of minutes are necessary to output the first solution. Second, it is not easy to adapt if the new model breaks the separable structure. Finally, it requires too many knowledge in discrete optimization and the use of a linear solver and a constraint programming solver.

Most papers published on related problems (see Section II.2) focus on a very specific variant of a problem and try to develop the best possible algorithms. This approach does not fit with our need of versatility and simplicity. Furthermore, it makes it difficult to really evaluate the performance of the algorithms. Therefore, we choose a different approach: our goal here is to design an efficient algorithm that can be applied to any variant of SOSP, such that little adaptation is required for each variant. We implemented and evaluated our algorithm on five variants of the problem:

• The Pure Star Observation Scheduling Problem (Pure SOSP)

• The Pure SOSP with discrete flexible observation times (Pure df-SOSP)

• The Pure SOSP with continuous flexible observation times (Pure cf-SOSP)

• IPAG SOSP

• IPAG SOSP with discrete flexible observation times (IPAG df-SOSP)

Pure SOSP has already been presented at the begninning of the section. Thanks to the bounds computed by Catusse et al. 2016, we may evaluate the performances of our algorithms and compare them with their Local Search. Among all additional constraints cited above, only the flexible duration constraint is not currently implement in SPOT and is a new request from the astrophysicists. We wanted to evaluate the effect of this property on the solutions. Therefore, we considered two variants of Pure SOSP where the processing time can be reduced by a factor x. If p j (S) is the duration of observation T j during night i in solution S, then, in the discrete variant (Pure df-SOSP), p j (S) ∈ xp i j , p i j , and in the continuous version (Pure cf-SOSP), p j (S) ∈ xp i j , p i j . Then the profit returned by the observation is w j (S) = w j p j (S)/p i j . Note that all solutions of Pure SOSP are feasible solutions of Pure df-SOSP, and all solutions of Pure df-SOSP are feasible solutions of Pure cf-SOSP. Therefore, we expect to get solutions with greater values in those cases. IPAG SOSP is the current problem solved by the software SPOT (IPAG, "Institut de Planétologie et d'Astrophysique de Grenoble", is the name of the astrophysicists' research unit). It includes all constraints except the flexible durations. By evaluating the performances of our algorithms on this problem, we can compare the results with the algorithm currently implemented and show the astrophysicists if we manage to get better solutions. Since a target may have several time-windows in the same nights, we note K j the number of time-windows of target T j , and for each time-window TW k j , k = 1, . . . , K j , we note r k j its release date, d k j its deadline, m jk its night, w jk its profit and p k j (s) the require observation time when starting it at time s. Finally, IPAG df-SOSP is the problem including all constraints, i.e. all constraints implemented in SPOT and the discrete flexible observation times. Similarly as above, if p j (S) is the duration of observation T j in time-window k starting at time s in solution S, then p j (S) ∈ xp k j (s), p k j (s) . Then the profit returned by the observation is w j (S) = p j (S)/p k j (s) * w k j . We do not look at the continuous version of IPAG df-SOSP. Indeed, it is a bit more complicated to handle and in Section II.4, we observe that our algorithm returns equivalent solution values for both cf-SOSP and df-SOSP.

II.2 Literature review

Besides the work published by Catusse et al. 2016, star observation scheduling problems have not receive a lot of attention. Johnston 1990 presents Spike, a software for scheduling observations on Hubble Space Telescope based on Constraint Programming. The constraints for a space telescope are not the same as the ones for an Earth telescope. Still, Johnston 1993 introduced the problem of scheduling star observations on the Very Large Telescope and states that Spike may be used to solve the problem. Unfortunately, no computational experiments are presented. On the other hand, many papers have been published on Agile Earth Observation Satellites (AEOS) scheduling problems, looking in the opposite direction from the sky towards the Earth (whereas we look from the Earth to the sky). Still, the problems share many similarities. The idea behind AEOS scheduling problem is to schedule projects on a satellite orbiting around the Earth. Each possible project has a time-window and returns a profit. The objective is to maximize the total profit of the schedule. The problem was introduced by Hall and Magazine 1994 in a single machine version. Wolfe and Sorensen 2000 improved the model, considering that an observation is better when it is centered in the time window. This property is similar to the start date dependent observation duration of our problem. Then Verfaillie and Lemaître 2001 considered a model with observation time dependent profit. This property is also one that we added in our model. The first model considering several machines was introduced by Dilkina and Havens 2005, by considering a fleet of satellites. Interestingly, having multiple satellites following each other implies that the time-windows will be shifted on each machine. A similar phenomenon happens with star observations: the time-windows of observations of a night are shifted in the next night. [START_REF] Bianchessi | A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites[END_REF], Wang et al. 2011[START_REF] Xu | Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization[END_REF][START_REF] He | An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling[END_REF][START_REF] Peng | Agile Earth Observation Satellite Scheduling: an Orienteering Problem with Time-Dependent Profits and Travel Times[END_REF] also considered multi-machine versions of the problem, either by considering multiple satellites, multiple orbits, or both. Some papers also consider additional constraints that are not related to our problem such as download, energy consumption, transition times, uncertainties (Verfaillie and Lemaître 2001;[START_REF] Lemaître | Selecting and scheduling observations of agile satellites[END_REF][START_REF] Dilkina | Agile satellite scheduling via permutation search with constraint propagation[END_REF]Li et al. 2007 etc.). Note that, as stated in the previous section, there are uncertainties in our problem, such as weather or earthquakes. Those uncertainties are managed by relaunching the algorithm, since the robustness of the schedule does not matter for the astrophysicists. This is one of the reason why it is crucial to be able to get good solution very rapidly. Unfortunately, algorithms developed for AEOS scheduling problems cannot be used for SOSP. Indeed, in multi-machines AEOS scheduling problems, the number of machines is small, i.e. lesser than five. In our problem, the number of machines, i.e. the number of nights is at least several dozens and can overcome a hundred. Furthermore, the telescope only observes at night, whereas satellites observe continuously and star observations are longer than earth observations. Therefore, even if the two families of problems are similar, AEOS scheduling problems include few machines but many jobs per machine, whereas star observation scheduling problems include many machines but few jobs per machine. It follows that algorithms developed for AEOS scheduling problems are not adequate for star observation scheduling problems.

II.3 Large neighborhood search

We propose a Large Neighorhood Search (LNS) to solve the problem. LNS is a well-known meta-heuristic that has been widely used in Operations Research (see [START_REF] Pisinger | Large neighborhood search[END_REF]. In LNS, an initial solution is iteratively improved by destroying and repairing it. Here, we implemented it by emptying and rescheduling several nights together. The repair is performed with a heuristic greedy algorithm. In the algorithm, a solution S consists of m single night schedules S i , i = 1, . . . , m. For a night i ∈ M, S i is defined by a list of tuples (j, k, τ, s, p), where T j is the corresponding target, TW k j the corresponding time-window, s is the observation start date and p the observation duration. Tuples are sorted and the corresponding observations are scheduled in non-decreasing order of τ .

II.3.1 Single Night Timing Problem

A major interest of the proposed architecture is that in order to handle the different variants of SOSP considered, one just needs to implement an algorithm (exact or heuristic) for a sub-problem called the Single Night Timing Problem (SNTP). SNTP takes as input a list of observations belonging to the same night and computes whether it is possible to schedule all of them in the given order, and if yes, returns the corresponding profit and schedule. Algorithm 15 solves SNTP for Pure SOSP. It is rather straightforward. Since the order is imposed, one just needs to schedule the observations as early as possible. Solving the feasibility problem is actually equivalent for all variants: one just needs to schedule the observations as early as possible at their smallest possible duration. Therefore, in the remaining of the section, we only describe the algorithms that compute the schedule and its profit. for (j, k, τ, ., .) w ← w + w j 16:

C ← C + p 17:
return w that it requires a priority queue. However, this priority queue is actually implemented with an array instead of a binary heap; since the number of observations in a night is less than 10, the array implementation happens to be faster.

For Pure df-SOSP, SNTP can be solved using Dynamic Programming based on the following recursive function:

w(j, t) = max      w(j -1, min{t, d i j } -p i j ) + w j if min{t, d i j } -p i j ) ≥ r i j w(j -1, min{t, d i j } -xp i j ) + xw j if min{t, d i j } -xp i j ) ≥ r i j -∞
The optimal value is then w(|S i |, d) where s is the deadline of the last observation of S i . It is implemented by states and the solution is retrieved by storing the observations scheduled in an additional integer in each state: if bit j = 0, then the jth observation is scheduled during its minimum duration, otherwise, it is scheduled during its maximum duration (see Kellerer et al. 2004 for more details on efficient Dynamic Programming implementations)

Interestingly, SNTP for Pure SOSP is equivalent to SNTP for IPAG SOSP. Indeed, all the additional constraints do not change the sub-problem. Therefore, Algorithm 15 can be straightforwardly adapted. Likewise, SNTP for for (j, k, τ, s, p) in S i do 5:

C ← max{C, r i j } 6: s ← C 7: p ← p i j 8: C ← C + p 9:
while C > d i j do 10:

Let pos min be the position of the first observation starting at its release date.

11:

Let (j , k , τ , s , p ) be the observation at position pos of S i such that pos min ≤ pos ≤ pos that maximizes w j /p i j .

12:

Let p max be the maximum duration at which observation at position pos can be reduced and all observations at position pos , pos < pos ≤ pos can be shifted to the left without violating their release dates.

II.3.2 Greedy algorithm

Algorithm 17 is a greedy algorithm that solves the full star observation scheduling problem. It uses SNTP and relies on the feasible function described in the previous section.

Algorithm 17 Greedy algorithm

1: procedure greedy(NightSet, TWList)

2:
time-windows from TWList all belong to nights of NightSet Remove (j, k, τ, ., .) from S m jk 14:

return {S i } i∈NightSet
Algorithm 17 simply inserts time-windows in the order they are given. If the current solution becomes infeasible, the last added observation is removed. τ is drawn randomly with a uniform distribution between min e min jk , s max jk and max e min jk , s max jk where e min jk and s max jk are respectively the earliest possible end date and the lastest possible start date of target T j in time-window TW k j . This choice of τ ensures that if the order of two observations can be deduced a priori, then the two values of τ will be sorted accordingly. For example, if a time-window has mandatory instants, then τ will be one of them. Therefore if two time-windows have distinct mandatory instants, which imposes the order, the corresponding observations will be scheduled in the correct one (if they have one common mandatory instant, then they are not compatible). If two time-windows TW k 1 j 1 and TW k 2 j 2 satisfy s max j 1 k 1 ≤ e min j 2 k 2 , then T j 1 cannot be scheduled after T j 2 and values of τ will again be sorted accordingly. Algorithm 17 may actually run on a limited number of nights defined by the input parameter NightSet, as well as it does not necessarily process all time-windows, but only those contained in TWList. Note that it does not call the schedule function, as it may be significatively slower than feasible. This way, we ensure that Algorithm 17 runs very fast whatever the variant of problem.

II.3.3 Local search

Based of the Greedy algorithm described in the previous section, we developed a simple Large Neighorhood Search algorithm. Algorithm 18 generates a first solution by running the Greedy algorithm on the whole instance. Then the solution is improved by continuously rescheduling a set of nights Ī with the Greedy algorithm. The number of nights | Ī| is drawn randomly such that P (| Ī| = z) = 1/2 z-1 with z ≥ 2. Then | Ī| nights are drawn uniformly among all nights. In the initial stage of the algorithm, time-windows are considered by efficiency. The efficiency is a heuristic measure of the interest of a time-window. We use the ratio between the profit of the time-window and the typical processingtime. More formally, for Pure SOSP, Pure cf-SOSP and Pure df-SOSP, we choose:

efficiency(TW k j ) = w j p k j and for IPAG SOSP and IPAG df-SOSP, we choose:

efficiency(TW k j ) = w k j p k j s min jk -e max jk 2
For the improvment phase, we need to increase the diversity of the solution and to this extend we use a disturbed efficency: we add a random term, uniformly drawn in [-0.001E max ; 0.0001E max ], where E max is the maximum efficiency among all time-windows. Finally, a simple mechanism is implemented to get out of local optima: a solution is accepted if its absolute gap with the best known solution is not greater than y = 1.1 (the profit of a full observation lies between 10 and 40). TWList ← TW k j for all j = 1, . . . , n, k = 1, . . . , K j 3:

II.4 Computational experiments

Sort TWList by efficiency 4:

S ← greedy(M, TWList) 5:

S best ← S 6:

while true do 7:

Draw a set of random nights Ī 8:

Let TWList be the set of time-windows belonging to nights of Ī from unscheduled targets and targets scheduled in nights of Ī S best ← S on the comparisons. Experiments on Pure SOSP, Pure df-SOSP and Pure cf-SOSP have been performed on an Intel R Core TM i5-8500 CPU @ 3.00GHz × 6. Experiments on IPAG SOSP and IPAG df-SOSP have been performed on an Intel R Core TM i5-6300U CPU @ 2.40GHz × 4.

II.4.1 Pure Star Observation scheduling problem

We used the 21 instances from Catusse et al. 2016 (a real instance and 20 generated ones), with time limits of 2 minutes (120 seconds) and 2 hours (7200 seconds). The best known upper bounds (UB) are the solutions provided by the Branch-and-Price from the same article. Table II.1 compares the result of the Local Search from Catusse et al. 2016 (LS) with the proposed Large Neighorhood Search (LNS). Note that the comparison is not completely fair since the processor used for LNS is much faster. However, LNS clearly outperforms LS as it returns better solutions in 2 minutes than LS in 2 hours. LNS usually fails to find an optimal solution (last column), but nevertheless provides very quickly good solutions and quickly very good ones. Indeed, the worst gap is below 2% and in 2 minutes, it is below 1%. Instances of size 1000 have been generated to be larger than real instances. If we only consider instances of size 400, 600 and 800, then the gap goes below 1% in a dozen of seconds. Therefore, LNS provides very good industrial solutions in a very short time.

From a theoretical point of view, we note that even if LNS keeps improving solutions all along the search, it is not able to provide optimal solutions within the time the Branch-and-price from Catusse et al. 2016 took to find them. Therefore, further research could focus on improving LNS on long runs.

II.4.2 Pure Flexible Star Observation scheduling problems

In this section, we try to assess the effect of including flexible observation duration in the model. We used the same instances as in the previous section. Our interests are: do we get better solutions with LNS when allow- ing continous or discrete flexible observation durations? In this case, is the value of these solutions greater than the best known solutions for the original problem? do we get better results when possible observation durations are continuous? and how does the value of x influence the quality of the solutions? Table II.2 compares the results obtained with LNS on Pure SOSP, Pure df-SOSP and Pure cf-SOSP with x = 0.95. First we note that LNS always returns better solutions on Pure df-SOSP compared to Pure SOSP within 2 minutes (column 6, "-LNS 120") and 2 hours (column 8, "-LNS 7200"). Allowing observation duration flexibility indeed improves the solution value. However, the additional profit is rather moderate, on average 50 (0.3%) and a max of 100 (0.5%) on the instances of the dataset (let us remind that the profit of an observation lies between 10 and 40).

Then, from a more theoretical point of view, we note that on 9 instances, the value found by LNS on Pure df-SOSP is greater than the best-known upper bound for Pure SOSP (column 9, "-UB").

We also compare the solutions obtained on the discrete and the continuous models. Even though solutions of Pure df-SOSP are all feasible solutions of cf-SOSP, the values returned by the algorithm are equivalent for both models. Indeed, the mean difference between the discrete and the continous solution values is 1.83 with a standard deviation of 5.57 (for comparison, the mean difference between the discrete version and the non-flexible version is 49.48 with a standard deviation of 18.97). Since the discrete version is simpler, it should be prefered. Finally, Figure II.2 shows the value returned by LNS for several values of x on two typical instances. The more the duration can be reduced, the greater the additional profit is, until x = 0.85. Then, the profit does not increase anymore.

II.4.3 IPAG Star Observation Scheduling Problems

On the more realistic version of the problem, we tested our LNS algorithm on four new real instances provided by the astrophysicists.

To this extend, LNS was integrated within SPOT, the software developed for the astrophysicists, and compared to the Simulated Annealing algorithm (SA) they currently use. solutions than SA. Furthermore, it finds them much quicker. When flexible observation duration is allowed, we observe the same behaviour as for Pure df-SOSP: the total profit is slightly greater.

II.5 Conclusion

We proposed a simple and general Large Neighborhood Search scheme for star observation scheduling problems. The algorithm reduced the resolution of a specific variant to the resolution of a Single Night Timing Problem for which algorithms are much easier to develop and adapt. We illustrated this by implementing several algorithms solving SNTP for different variants of star observation scheduling problems. Our Large Neighborhood Search algorithm is relevant because it clearly outperforms both the previous Local Search algorithm on literature instances for the pure problem, and the currently used SA algorithms on real instances. Besides, it is simpler and more easily adaptable than both. Compared to the Branch-and-Price algorithm, it provides solutions within 2% of optimality in less than 2 seconds, while the Branch-and-Price will need about 10 minutes to find its first solution on real sized instances. However, even if the Large Neighborhood Search continues improving the solution over time, the solution found by the Branch-and-Price is almost always the optimal one and the Large Neighborhood Search cannot find it within the same In this chapter, we present the heuristic Branch and Bound algorithm we submitted for the final phase of the challenge. The resulting program was ranked first over 20 qualified submissions. The code is free (GPL-3.0) and available online2 .

In the AI community, solving problems often involves exploring a search tree, either exhaustively, using methods similar to Branch and Bound, or using heuristic procedures that only explore the most promising parts of the search tree. In the latter case, they are called Anytime Tree Searches because they can be stopped at any time and provide good solutions in the allowed computation time. Such methods have the same objective as metaheuristics. Anytime Tree Searches usually start by the most promising regions of the search tree, providing good solutions first. Then they explore the least promising regions if time permits it. Possibly, the tree search will explore the whole tree and thus it will provide the optimal solution. To the best of our knowledge, Anytime Tree Searches are hardly present in Operations Research.

For the ROADEF/EURO challenge 2018, we took the bet that one can combine Branch and Bounds from Operations Research and Tree Search Algorithms from AI to get a simple method that is competitive with classical meta-heuristics. We designed a Branch and Bound, with pseudo-dominance properties, symmetry breaking rules, bounds and heuristic guides as people usually do in Operations Research. We changed the search strategy by a custom iterative tree search algorithm inspired from AI. It starts its first iteration by performing very aggressive heuristic cuts and behaves like a greedy algorithm finding a good solution fast. At the second iteration, it performs less aggressive heuristic cuts, taking more time, finding even better solutions.

If the algorithm runs for long enough, no heuristic cut will be performed and it behaves like an exact Branch and Bound. The resulting method obtained the best results compared to the other submitted approaches during the final phase.

We also extracted a general framework that can be applied to many other industrial problems. Indeed, the method can be divided into two parts. First, one designs the Branching Scheme which is a definition of the implicit search tree (i.e. root node, how to generate children of a given node, lower bounds etc.). This implicit search tree is usually too big to be entirely explored. Thus, we also need to design a strategy to explore the tree starting from promising regions. This decomposition allows rapid prototyping of both search trees definitions and tree searches. We believe that many tree search techniques from AI can be applied with success on many Operations Research problems. The chapter is organized as follows: Section III.1 contains the problem description; Section III.2 describes the branching scheme (i.e. implicit search tree definition) that we implemented; Section III.3 presents an overview of the most significant tree search algorithms in AI and the algorithm Memory Bounded A* (MBA*) that we designed for the challenge. Eventually, Section III.5 is dedicated to computational experiments on the challenge instances.

III.1 Problem definition

The ROADEF/EURO challenge 2018 was proposed by the company Saint-Gobain. The challenge consists in packing rectangular glass items into standardized bins called jumbos. Each jumbo has a fixed size H × W (6m × 3.21m). The goal is to produce all items while minimizing the total surface of waste (surface not used by items). For the last jumbo used, we allow a special cut creating a remaining part that will not be counted as waste. A more detailed description of the problem and examples can be found on the challenge website3 . Formally, the objective can be formulated as:

min nHW -Hw - i∈I w i h i
where n is the number of jumbos used; W and H the standardized width and height of jumbos; w the position of the most right cut of the last jumbo; and I the set of produced items of height h i and weight w i , i ∈ I. Note that the last term is constant but necessary to interpret the objective as the total waste of the solution. The problem is a variant of the classical two-dimensional orthogonal (rectangular items and cuts parallel to the border of the jumbo) packing problem. However, it contains several additional constraints that makes it more difficult to solve:

• Cuts must be guillotine (i.e. traversing all the jumbo). Figure III.1 shows an example of a non-guillotine solution and a guillotine one. The vertical cuts traversing the whole jumbo are called 1-cuts. Each horizontal cut separating regions within a 1-cut is called a 2-cut. The same principle applies for 3-cuts and 4-cuts.

• Items are subject to chain precedence constraints. Each item belongs to exactly one chain. Some instances have a few chains, some have no precedence constraint (i.e. there are |I| chains). When extracted from left to right and bottom to top, the items in a chain need to be in the right order.

• Jumbos can contain defects (between 0 to 8 rectangles about 1-2cm wide). For quality reasons, those defects should not be present in items and cuts cannot be performed on such defects. One needs to pack those defects in the waste.

• Only 4 levels of cuts are available. Moreover, it is possible to perform at most one 4-cut in a sub-plate obtained after a 3-cut. Thus, after a 3-cut, the sub-plate can contain waste, one item without waste, one item and some waste or two items without waste. This is illustrated on Figure III.2.

• Cuts, depending on their level are subject to minimum and maximum size constraint. The distance between two consecutive 1-cuts must be between w 1 min = 100 and w 1 max = 3500. The distance between two consecutive 2-cuts must be at least w 2 min = 100. Finally, the width and the height of any waste area must be at least w min = 20. The consequence of this last constraint is not straightforward and is illustrated on Figure III.3.

J 1 J 2 J 3 J 4 J 5 J 6 J 1 J 2 J 3 J 4 J 5 J 6
Figure III.2 -Only one 4-cut is allowed. Therefore, the first solution is feasible but the second is not.

III.2 Branching scheme

In this section, we describe the branching scheme used by our Tree Search Algorithms. The first part provides several theoretical dominance properties that justify the heuristic choices that we made. Then we describe the general scheme. Finally, we describe a pseudo-dominance rule and a symmetry breaking strategy.

In this section, S denotes a solution (items and cuts with their positions) or a partial solution (not all items may be placed), J an item (or a defect) and D a defect. For all item J ∈ S, x 1 (J, S), x 2 (J, S), y 1 (J, S) and y 2 (J, S) denote respectively the positions of its left cut, right cut, bottom cut and top cut. S is omitted when there is no ambiguity. For a defect D, x 1 (D), x 2 (D), y 1 (D) and y 2 (D) denote respectively its left border, right border, bottom border and top border (that do not depend on a solution). For a k-cut C ∈ S, k odd, x(C) denotes its x coordinate and y 1 (C) < y 2 (C) denote its starting and ending positions. For a k-cut C ∈ S, k even, y(C) denotes its y coordinate and x 1 (C) < x 2 (C) denote its starting and ending positions.

Let S be a partial solution. Let n(S) denote the number of plates used by S and for k ∈ {1, 2, 3}, let x curr k (S) (resp. x prec k ) be the position of the last k-cut (resp. the previous k-cut) of the last plate of S. If there is only one 1-cut on the last plate, then x prec 1 = 0. And if, for k ∈ {2, 3}, there is only one k-cut between the x prec k-1 and x curr k-1 , then x prec

III.2.1 Dominance results

Ideally, a branching scheme should make any solution reachable while limiting the number of equivalent or dominated ones. For this problem, it is not straightforward. Therefore, in this section, we derive several dominance properties to help us decide which branching scheme to implement.

In this section, "as late as possible" for cuts refers to the order in which they are performed. First note that the border of an item corresponds to one unique cut, as illustrated on Figure III.5.

J 1 J 1 Figure III
.5 -The second pattern cannot be obtained with guillotine cuts.

Therefore, if C ∈ S is a k-cut, k odd, and J an item of S or a defect such that x 2 (J) = x(C). Then either y 1 (J) ≥ y 2 (C), or y 2 (J) ≤ y 1 (C), or y 1 (C) ≤ y 1 (J) and y 2 (J) ≤ y 2 (C). The equivalent holds if k is even.

In the pure two-dimensional orthogonal packing problem, it is dominant to pack the items in a corner. When adding some constraints of the current packing problem, this remains true:

Proposition III.2.1.1 For the guillotine two-dimensional orthogonal packing problem with defects and precedences, the set of solutions U such that for all S ∈ U:

• if k+1 is odd, there exists either an item J such that y 1 (C) ≤ y 1 (J) ≤ y 2 (J) ≤ y 2 (C) and x 2 (J) = x(C), or two items J 1 and J 2 such that

y 1 (C) ≤ y 1 (J 1 ) ≤ y 2 (J 1 ) ≤ y 2 (C), y 1 (C) ≤ y 1 (J 2 ) ≤ y 2 (J 2 ) ≤ y 2 (C), x 2 (J 1 ) = x(C) -w min and x(C) -2w min < x 2 (J 2 ) < x(C) -w min .
is dominant.

Proof. Let S be an optimal solution where the condition is not satisfied as late as possible. Let C and C be the first pair of cuts violating the conditions, i.e. the first item or border before the cut is at strictly more than w min . C can be shifted backward as well as all the items placed between C and C until C satisfies the condition (Figure III.7). The new solution is feasible and either it belongs to U , or it violates the condition later than S. Hence a contradiction. Proposition III.2.1.2 For the guillotine two-dimensional orthogonal packing problem with minimum waste, the set of solutions U 2 such that for all S ∈ U 2 :

J 1 J 2 J 3 J 4 J 5 C C C 1 C 2 ↓ -→ > w min > w min J 1 J 2 J 3 J 4 J 5 C C C 1 C 2 = w min > w min
• for all k-cut C, k odd, there exists either an item J such that y 1 (C) ≤ y 1 (J) ≤ y 2 (J) ≤ y 2 (C) and x 2 (J) = x(C), or two items J 1 and J 2 such that y

1 (C) ≤ y 1 (J 1 ) ≤ y 2 (J 1 ) ≤ y 2 (C), y 1 (C) ≤ y 1 (J 2 ) ≤ y 2 (J 2 ) ≤ y 2 (C), x 2 (J 1 ) = x(C) -w min and x(C) -2w min < x 2 (J 2 ) < x(C) -w min .
• for all k-cut C, k even, there exists either an item J such that x 1 (C) ≤ x 1 (J) ≤ x 2 (J) ≤ x 2 (C) and y 2 (J) = y(C), or two items

J 1 and J 2 such that x 1 (C) ≤ x 1 (J 1 ) ≤ x 2 (J 1 ) ≤ x 2 (C), x 1 (C) ≤ 100/127
CHAPTER III. ROADEF/EURO CHALLENGE 2018

x 1 (J 2 ) ≤ x 2 (J 2 ) ≤ x 2 (C), y 2 (J 1 ) = y(C) -w min and y(C) -2w min < y 2 (J 2 ) < y(C) -w min .

is dominant.

Proof. Let S ∈ U be an optimal solution such that it contains a k-cut C violating the condition (i.e. the first item or border before the cut is at strictly more than w min ), k = 1 or there is no (k -1)-cuts violating the condition, and C is the first such cut. Let C 1 and C 2 be the previous and the next (k -2)-cuts or border of C. The blocks between C 1 and C and between C and C 2 can be exchanged. The new solution is feasible and the extra waste is now either before a border or before a (k -2)-cut. Hence a contradiction. However, with the minimum waste constraint and precedences, or with the minimum waste constraint and defects, the property does not hold. Counterexamples are illustrated on Figure III.9. Both instances contain three items J 1 , J 2 and J 3 . In the first instance, J 1 precedes J 3 . In the second instance, there is a defect on the plate. Item J 1 is higher than item J 2 by strictly less than the minimum waste. This imposes the next 2-cut to be placed after y 2 (J 1 ) + w min . However if this cut is placed exactly at y 2 (J 1 ) + w min , then the distance between the top of item J 3 and the top border of the plate would be strictly smaller than the minimum waste. The optimal solution can be obtained by placing J 3 right on top of the plate. In the proof of Proposition III.2.1.2, items J 1 and J 2 are exchanged with items J 3 . However, because of the precedence constraint in the first case and the defect in the second, this is not possible and the presented solutions are the only optimal solutions for each instance.

J 1 J 2 J 3 J 4 J 5 C 1 C C 2 -→ > w min J 1 J 2 J 3 J 4 J 5 C 1 C 2 > w min
J 1 J 2 J 3 J 1 J 2 J 3

III.2.2 General scheme

In the previous section, we showed that in most situations, packing items "in a corner" is dominant. Besides, more general dominance properties we could think of all increase the number of children of a partial solution beyond what is practically tractable. As we are looking for efficient heuristics, we assumed that this "in the corner"'-rule is a good compromise on which our tree generation can be based. Thus, we insert items in the order they are produced, ensuring that the precedence constraint is always satisfied. The root node is the empty solution. Then we define the children of a node. Due to the 4-cut constraint, if we look at a solution rectangle defined by (1) the bottom of the plate or a 2-cut and (2) the next 2-cut (or the top of the plate if there is none) and (3) the left of the plate or a 1-cut or a 3-cut and (4) the next 3-cut (or 1-cut if there is none, or the right of the plate if there is no 1-cut), then this rectangle may contain either only waste, or an item without waste, or an item with waste above, or waste with an item above, or two items without waste. Therefore, our tree generation consists in packing the next such rectangle of the solution. This implies four types of insertions illustrated on Figure III.10 (current and previous cuts have been defined at the beginning of Section III.2; remember Figure III.4, page 98):

• inserting an item such that its bottom is the new previous 2-cut. These are the most common insertions. If there is one, the 4-cut will be the top of the item. This is how items 231, 334, 335, 232, etc. have been inserted.

• inserting an item such that its top is the new current 2-cut. This happens when the first type of insertion is not possible because the item would contain a defect. In this case, there will necessarily be a 4-cut for the bottom of the item. This is how items 6 and 56 have been inserted.

• inserting two items one above the other. Then the bottom of the first 102/127

CHAPTER III. ROADEF/EURO CHALLENGE 2018

item is the new previous 2-cut and the top of the second item is the new current 2-cut. There will be a 4-cut between the two items. Since no 5-cut is allowed, the two items must necessarily have the same length. This is how items 409 and 410 have been inserted.

• inserting a defect. This corresponds to the insertions before item 232, items 409 and 410, and item 247. Note that the defect on the right of item 8 does not need to be inserted.

Figure III.10 -A plate of a solution

An insertion can be done at different depths:

• depth 0: the insertion is done on a new plate. This is how item 231 has been inserted.

• depth 1: the current 1-cut becomes the previous 1-cut and a new current 1-cut is created. This item is then at the bottom of the plate. This is how items 8, 244, 193 and 104 have been inserted.

• depth 2: the current 2-cut becomes the previous 2-cut and a new current 2-cut is created. This is how items 334, 159, 5, 191, 9, etc. have been inserted.

• depth 3: the current 3-cut becomes the previous 3-cut and a new current 3-cut is created. This is how items 335, 6, 7, 192, etc. have been inserted.

Finally, each item may be rotated.

III.2.3 Computing new current cut positions

When doing an insertion, the positions of the new current 1-cut, 2-cut and 3-cut need to be computed. The other cuts will not change. Here, we give some insights on how it is implemented. For an exhaustive explanation, please refer directly to the code4 . In both cases, item J 1 is first inserted and then J 2 .

J 1 J 2 (a) J 1 J 2 → (b)
In the first case, the length of item J 2 is small enough so that the current 1-cut remains valid. In the second case, the length of item J 2 differs by less than the minimum waste from the length of item J 1 : if the current 1cut stayed the same, then the minimum waste constraint would be violated. Therefore, the current 1-cut needs to be moved to the right so that neither J 2 nor J 1 violate the minimum waste constraint; that is: its new position is x 2 (J 1 ) + w min . This example illustrates the need for the following definitions. Let z 1 (S) be such that

• z 1 (S) = 0 iff to move the current 1-cut to the right, it should be moved by at least the minimum waste in order to respect the minimum waste constraint. This is the case in Figure III.11 after inserting item J 1 . More generally, this happens when the current 1-cut is the right cut of an item.

• z 1 (S) = 1 iff the current 1-cut can be moved to the right by any value without violating the minimum waste constraint. This is the case in solution (b) of Figure III.11 after inserting J 2 . This may also happen because of defect insertions. In the solution represented on Figure III.14, if the current 1-cut is placed at x 2 (J 1 ), then it intersects a defect. Therefore, it must be shifted to the right. Note that it must be shifted enough so that the minimum waste constraint is satisfied between the 3-cut at x 2 (J 1 ) and the current 1-cut. Furthermore, the 3-cut at x 2 (J 1 ) may also later intersect the defect if the current 2-cut is moved too high. Therefore, we also introduce and compute y max 2 (S) the maximum height of the current 2-cut in S. Avoiding intersections between 2-cuts and defects is handled a bit differently.

In the first solution of Figure III.15, the current 2-cut does not intersect the algorithm to compare children of a node, and for all generated nodes in the algorithm dedicated to instances with only one or two chains.

J 1 J 2 J 3 J 4 J 1 J 2 Figure III.18 -Illustration of the front of two partial solutions J 1 J 2 J 3 J 1 J 2 J 3

III.2.6 Breaking symmetries

Most instances of the challenge (i.e. 27 over 30) have more than 5 chains. Thus, they have too many sub-problems for a dynamic programming strategy. Therefore, we only use the pseudo-dominance rule between the children of a node, and not between nodes with different fathers. To compensate, we use some rules to avoid exploring equivalent nodes several times instead. A node is cut if a "k-block" (the items between two consecutive k-cuts) can be exchanged with the previous "k-block", i.e. without violating neither the defect constraint nor the precedence constraint, and if the minimum index of its items is lesser. Since the algorithm is constructive, we only need to check the penultimate and the antepenultimate "k-blocks". The current ones cannot be compared since they may still change later. Symmetry breaking is illustrated on Figures III.21 and III.22.

J 1 J 2 (a) J 1 J 2 (b) J 1 J 2 J 3 J 4 (c) J 1 J 2 J 3 J 4 (d)
Figure III.20 -Consider an instance with 4 items and 1 chain. In solution (b), the defect has been inserted before J 2 . The pseudo-dominance rule states that solution (a) dominates the second one. However, the solution (a) cannot lead to the optimal solution, since solution (c) violates the 4-cut constraint, whereas solution (b) can lead to solution (d) which is optimal.

III.3 Tree search

It is common in Operations Research to encode the search space as a tree.

For instance Branch and Bound/Cut fully explores a tree where each node is a partial solution. Branch and Bound algorithms are complete tree searches designed to provide a guaranteed optimal value. But this is usually done at the price of storing a lot of information and not focusing on finding good solutions fast. On the other hand, greedy algorithms can be seen as a special kind of tree-search. They only look at the best next node until reaching a leaf, providing reasonable solutions very fast but without any guarantees. Both methods have their quality and drawbacks. Once again, we opted for a compromise. Some tree searches, at the beginning, behave like greedy algorithms, then, as time goes, behave more and more like a Branch and Bound.

J 2 J 1 J 3 J 2 J 1 J 3 Figure III.
21 -Illustration of symmetry breaking. In the first solution, items J 1 and J 2 can be exchanged. Therefore, the corresponding node is pruned. However, in the second solution, the two items cannot be exchanged because of the defect. Therefore, the solution is kept.

J 3 J 2 J 1 J 3 J 2 J 1 Figure III.
22 -Illustration of symmetry breaking. In the first solution, before inserting item J 1 , items J 2 and J 3 can be exchanged. However, the solution is not cut since the 2-block is not finished yet as item J 1 will be inserted after. However, item J 1 cannot be inserted at depth 2 as in the second solution.

communities. Also, we can note that ant colony optimization is a form of anytime tree search [START_REF] Blum | Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling[END_REF]. However, many more anytime tree searchs exist in AI. To the best of our knowledge, many of them are seldom used in Operations Research. We believed that importing anytime tree searches into Operations Research can lead to competitive methods. We did so, and the resulting method was ranked first in the final phase of the challenge.

In the previous section, we have presented how we generate a search tree encoding the glass cutting challenge. In this section, we present several classical anytime tree search algorithms from the AI community. Then we present a new anytime algorithm we used during the challenge, which is inspired by the AI tree search. for all v ∈ children(n) do 7:

III.3.1 Anytime tree searches

fringe ← fringe ∪ {v}

In this section, we give a brief overview of the most popular anytime tree search algorithms that, we believe, can obtain good results in Operations Research problems. We implemented and compared those algorithms on the challenge instances. Most anytime tree searches (including the methods presented below) are based on one of the 3 classical searches. They modify the base search in order to make it anytime.

Beam Search (BS) was originally proposed by Rubin and Reddy 1977, first as LOCUS Search. Indeed, instead of considering all the nodes at a given depth, it only keeps the D best nodes within a given level. D is usually called the beam size. Beam Search is a generalization of both the greedy algorithm (when D = 1) and BFS (when D = ∞). Several variants of the Beam Search start with a small beam and run again the algorithm with a bigger beam size until the time limit. This process allows to provide good solutions fast and improve them in the later stages of the search. We also note that Beam Search is probably the most popular anytime tree search algorithm in Operations Research. It is present in several popular methods (see for instance Blum 2005, Ow and[START_REF] Ow | Filtered beam search in scheduling[END_REF]. fringe ← fringe \ {n} two chains, there is at most 350 2 = 122, 500 sub-problems and DPA* solves it optimally in a few seconds.

If there is strictly more than two chains, we do not use dynamic programming since it would cost too much in memory. Instead, we run 4 threads in parallel, each one running a restarting MBA* with a given growth factor and guide function. Restarting means that, initially, the maximum size of the fringe is small (3 for example), and each time MBA* terminates, it is restarted with a greater maximal size (multiplied by the growth factor). If the growth factor is 2, the maximal size doubles at each iteration. We use growth factors 1.33 and 1.5 and the two guide functions described in Section III.3.3.

All the threads share the information of the best solution found. If one finds a better solution, the others can exploit this information to perform more cuts and globally perform better together than alone.

III.5 Computational experiments

We now present computational experiments of our algorithm on the challenge instances. They have been performed on a computer with an Intel Core i7-4790 CPU @ 3.60 GHz × 8 processor with 32 Go of RAM. This configuration is similar to the one of the challenge. The instances are separated into three datasets. Dataset A was published during the qualification phase. It contains three trivial instances, some instances of moderate size containing between 30 and 130 items and three larger ones containing about 300 items. Dataset B was published after the qualification phase and was used for the evaluation during the final phase, along with dataset X which was unknown until the results were announced. They both include larger instances containing on average 300 items. Most instances contain between 10 and 15 chains. Three instances have exactly two chains and five instances have no precedence constaints. Since the challenge, a few adjustments have been made (the version presented in this chapter is the current one). Therefore, the results presented here slightly differ from the results obtained during the final phase. Compared to the challenge version, the current version performs better: the total waste on datasets B and X decreases from 493 600 549 for the challenge version to 469 910 749 for the current one. Figures III.23, III.24 and III.25 sum up computational experiments. Columns "Final phase best 180s" and "Final phase best 3600s" contain the values of the best solutions found by any team during the final phase (note that dataset A was not used in the final phase). A result annotated with a star indicates that this solution was found by our algorithm during the final phase of the challenge. Column "MBA*/DPA* 3600" contains the solution values found by the current version of our algorithm in 3600 seconds. Finally, column "Best known" contains the values of the best solutions up to our knowledge. They may have been found during the development of the algorithm, when the execution time is longer than 3600s or by other teams.

In 180 seconds, the algorithm we submitted was ranked first on 17 and second on 10 out of the 30 instances used for the evaluation. In 3600 seconds, it was ranked first on 20 and second on 7. The current version finds the best known solutions on 14 instances of dataset A in less than 3600 seconds. It also finds the best known solutions on instances with exactly two chains in less than 180 seconds, showing the effectiveness of DPA*. Finally, even if it is not indicated in the table, on most of the instances, if the algorithm is run longer, for example 2 hours, the solutions will still be improved.

III.6 Conclusions and perspectives

We have proposed in this chapter an anytime tree search algorithm called MBA*. It performs successive iterations and restarts when the search tree is emptied. During the first iterations, it performs aggressive cuts and behaves like a greedy algorithm. As iterations go, the algorithm performs less heuristic cuts, enabling it to find better solutions. Possibly, the algorithm will perform an iteration with no heuristic cut, finding the best solution available in the branching scheme.

We also provide a framework to design anytime tree search algorithms. The algorithm design can be split into two parts:

Search tree design: Implicit definition of the search tree. It provides the root, how to generate children of a given node, cuts, lower bounds and guides.

Search tree exploration:

A generic anytime tree search that explores the search tree previously defined. Those tree searches are well known in AI and we used them in the challenge.

This framework allowed us to design separate parts, consequently, helping us to do quick prototyping. We implemented 5 different branching schemes to encode the search tree until we found a good compromise in terms of speed and quality. We also implemented many search algorithms (Beam Search, Beam Backtrack, A*, MBA*, SMA*) and kept the one giving the best results. We do not want to draw prematured conclusion, but we tried to understand the success of the algorithm: • When branching, there does not seem to be eliminatory choices. If a move is good locally, it should not be very bad globally. Even if the choice is not optimal, the very high number of possible children makes it possible to find a solution with similar cost anyway. This is true under the condition that all those children are implemented, i.e. that the branching scheme allows to reach the maximum number of configurations (while breaking symmetries). As shown in Section III.2, we gave a lot of attention to this part.

• The problem has natural guide functions to compare solutions at different depths of the tree. Therefore, MBA* seems more suited than Beam Search.

• The two parts design makes the code easier to write and to debug. In the context of an industrial problem with many complex constraints to satifsy, this may be crucial.

The results of the challenge prove that anytime tree searches can be competitive with local search based methods. We believe that they can be suited for other Operations Research problems, and particularly industrial ones with more complex constraints. Indeed, those constraints can weaken the locality property of solutions whereas they might be easily handled by a tree search approach. It should be worth experimenting such methods, especially MBA*, on those problems.

IV

Chapter Conclusion

In Chapter I, we studied a category of scheduling problems which are of theoretical and practical interest: processing time dependent profit maximization scheduling problems. We discussed some unusual properties and we proposed several piecewise-linear models as references. Then we underlined the complexity hierarchy that exists among those models. We =p max | -w j (p j ) lies between P | p j =p | w j U j and P | p j =p, pmtn | w j U j that were proved to be respectively solvable in polynomial time and NP-complete (Brucker and Kravchenko 1999). Finally, 1 | LP, r j | -w j (p j ) is also a very simple and yet open problem. In processing time dependent profit maximization scheduling problems, the non-linearities in the profit functions avoid linear programming formulations, and the controllable processing times make it difficult to design reductions to NP-complete problems. Also, several cases have been proven to be polynomial when the number of parallel machines is fixed (P m) or when all deadlines are equal (d j =d), but the algorithms do not generalize to the cases with an unbounded number of parallel machines (P ) or when deadlines are distinct.

In Chapter II, we studied a practical star observation scheduling problem. We continued the work started by Catusse et al. 2016 by integrating all practical constraints and designing and implementing algorithms more suited for industrial contexts (simpler, anytime and more flexible). We proposed a simple and general Large Neighborhood Search (LNS) scheme for star observation scheduling problems. The algorithm reduced the resolution of a specific variant to the resolution of a Single Night Timing Problem (SNTP) for which algorithms are much easier to develop and adapt. We illustrated this by implementing several algorithms solving SNTP for different variants of star observation scheduling problems. Our Large Neighborhood Search algorithm is relevant because it clearly outperforms both the previous Local Search algorithm on literature instances for the pure problem, and the currently used Simulated Annealing algorithms on real instances. Besides, it is simpler and more easily adaptable than both. Compared to the Branch-and-Price algorithm, it provides solutions within 2% of optimality in less than 2 seconds, while the Branch-and-Price will need about 10 minutes to find its first solution on real sized instances. However, even if the Large Neighborhood Search continues improving the solution over time, the solution found by the Branch-and-Price is almost always the optimal one and the Large Neighborhood Search cannot find it within the same amount of time. Further research could for example focus on diversification techniques to improve this aspect. Theoretically, allowing flexible observation durations necessarily improves the value of the optimal solution. In practice, on the given instances, LNS indeed finds better solutions in theses cases. However, the additional gain is rather moderate. The algorithm is now implemented in the software used by the astrophysicists, and we hope it will be used in production very soon.

In Chapter III, we described the algorithm we submitted for the final phase of the ROADEF/EURO challenge 2018. This edition of the challenge was dedicated to a cutting optimization problem in collaboration with Saint-Gobain We proposed an anytime tree search algorithm called MBA*. It performs successive iterations and restarts when the search tree is emptied. During the first iterations, it performs aggressive cuts and behaves like a greedy algorithm. As iterations go, the algorithm performs less heuristic cuts, enabling it to find better solutions. Possibly, the algorithm will perform an iteration with no heuristic cut, finding the best solution available in the branching scheme. The results of the challenge prove that anytime tree searches can be competitive with local search based methods. We believe that they can be suited for other Operations Research problems, and particularly industrial ones with more complex constraints. Indeed, those constraints can weaken the locality 124/127 CHAPTER IV. CONCLUSION property of solutions whereas they might be easily handled by a tree search approach. It should be worth experimenting such methods, especially MBA*, on those problems. The problem of the challenge is also interesting in itself. It is close to twodimensional packing problems from the literature, but it adds several constraints that makes it harder to solve. The gap between the solutions returned by our algorithm in 1 hour and the best known solutions (not the optimal ones!) is more than 7%, which is high for an optimization problem. The objective is also interesting. Traditionally, in bin packing problems, the objective is only to minimize the number of bins. Thus, unless the instance is intentionnaly built to avoid it, the lower bound obtained by column generation usually matches the optimal value and large problems are solved exactly. The bin packing problem is one of the NP-complete problem with the smallest input size and therefore can be deeply and almost exhaustively studied. The bin packing problems with leftovers offers a problem with the same input, but harder to solve. Some variants of this problem have been studied (see [START_REF] Cherri | The onedimensional cutting stock problem with usable leftovers -A survey[END_REF] for a review).

As stated in the introduction of the manuscript, the three chapters can be read independently. However, looking at them together gives some interesting perspectives.

In Chapter I we studied the complexity of a sub-problem of the real life application presented in Chapter II. The main conclusion of Chapter I can be stated as follows: "those problems are hard". Indeed, even when cases can be solved in polynomial time, the complexity is often deterrent and not suited for practical use. That is why, in Chapter II, we did not tackle this sub-problem directly, as it were before, but rather reduced the problem to one without the job selection property. And thus, it becomes much easier to solve. It is also interesting to compare Chapter II and III as they show two ways of doing practical Operations Research. In both chapters, the goal was to design algorithms for a real world problem. However, in Chapter III, the problem and the instances are well defined and the objective is to develop the best possible algorithm for them, whereas in Chapter II, the problem is evolving, changing, and the objective is to design an efficient enough algorithm that can be easily adapted. But still, the algorithm developed in Chapter III remains rather simple and easily adaptable, and the one developed in Chapter II has been proven to be competitive with previous state of the art methods.

Summary

Large telescopes are few and observing time is a precious resource subject to a strong pressure from a competitive community. Besides, a growing number of astronomical projects require surveying a large number of targets during discontinuous runs spread over few months or years. This thesis is the result of a collaboration between operations researchers from G-SCOP laboratory and astrophysicists from IPAG research unit. Its goal was to optimize the schedule of star observations on telescopes, in particular, on the Very Large Telescope. The first chapter contains a theoretical study of the complexity of several variants of processing time dependent profit maximization scheduling problems. Those problems appear inter alia as sub-problem of the real life star observation scheduling problem studied in the second chapter, for which we developed a fast and efficient Large Neighborhood Search algorithm. The third chapter is not related to the star observation scheduling problem. It describes the Tree Search based algorithm we developed for the glass cutting problem raised by the company Saint-Gobain for the ROADEF/EURO challenge 2018.

Résumé

Il existe peu de grands télescopes et le temps d'observation est une ressource précieuse sujette à une forte pression de la part d'une communauté concurrentielle. En outre, un nombre croissant de projets astronomiques nécessitent l'observation d'un grand nombre d'objets célestes pendant des runs discontinus répartis sur plusieurs mois ou années. Cette thèse est le fruit d'une collaboration entre des chercheurs en recherche opérationnelle du laboratoire G-SCOP et des astrophysiciens de l'unité de recherche IPAG. Son but était d'optimiser l'ordonnancement d'observations d'étoiles sur les télescopes, en particulier, sur le Très Grand Télescope. Le premier chapitre contient une étude théorique de la complexité de plusieurs variantes de problèmes d'ordonnancement de maximisation de profits dépendants du temps d'exécution. Ces problèmes apparaissent entre autres comme sous-problèmes du problème réel d'ordonnancement d'observations d'étoiles étudié dans le deuxième chapitre, pour lequel nous avons développé une recherche locale à voisinage large rapide et efficace. Le troisième chapitre ne concerne pas le problème d'ordonnancement d'observations d'étoiles. Il décrit l'algorithme de recherche arborescente que nous avons développé pour le problème de découpe de verre posé par l'entreprise Saint-Gobain pour le challenge ROADEF/EURO 2018.

  Complexity of processing time dependent profit maximization scheduling problems I.1 Processing time dependent profit . . . . . . . . . . . . . . . . I.2 Literature review and applications . . . . . . . . . . . . . . . . I.3 Notations and general results . . . . . . . . . . . . . . . . . . I.4 NP-complete cases . . . . . . . . . . . . . . . . . . . . . . . . I.5 Polynomial cases solved with dynamic programming . . . . . .I.5.1 P m | PLP, |{p k j }| ≤ κ | -w j (p j ) . . . . . . . . . . . I.5.2 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b} | -w j (p j ) . . . . . . . I.5.3 1 | PLP, |{w k j }| ≤ κ, b k j ∈{0, b j }, d j =d | -w j (p j ) .. . I.6 Polynomial cases solved with list algorithms . . . . . . . . . . I.6.1 P | LP | -w j (p j ) . . . . . . . . . . . . . . . . . . . . I.6.2 1 | LBP | -w j (p j ) . . . . . . . . . . . . . . . . . . . I.6.3 1 | LBPST, p min j =p min , b j =b | -w j (p j ) . . . . . . . . I.6.4 1 | LBPSTIP | -w j (p j ) . . . . . . . . . . . . . . . . I.7 Polynomial cases solved with maximum weight b-matching . . I.7.1 P | LPSTIP, p min j =p min , d j =d | -w j (p j ) . . . . . . . I.7.2 P | LPSTIP, p min j =p min , b j =b | -w j (p j ) . . . . . . . . I.7.3 P | LBPST, p max j =p max , d j =d | -w j (p j ) . . . . . . . . I.8 Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.9 With release dates and preemption . . . . . . . . . . . . . . . I.9.1 Preliminary results and notations . . . . . . . . . . . . I.9.2 Linear profits (LP) . . . . . . . . . . . . . . . . . . . . I.9.3 Linear bounded profits (LBP) . . . . . . . . . . . . . . I.9.4 Linear profits with setup times (LPST) . . . . . . . . . I.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Figure I.1 -Examples of profit functions of: (a) a classical scheduling problem (w j (p) = w j if p ≥ p j , 0 otherwise); (b) basic (linear profit) problem; (c) the star observation problem

Figure I. 2 -

 2 Figure I.2 -Example of an instance where all jobs cannot be scheduled in an optimal solution

j+

  Figure I.3 -Profit functions

  Figure I.5 -Complexity hierarchy of PDPSP problems. An arc from A to B means that A is a special case of B, and a label indicates the particular settings of B that corresponds to A. P LP (K) is the particular case when the number of pieces is bounded by K.

Figure I. 6 -

 6 Figure I.6 -Two simple examples of non-linear PDPSP for which an optimal solution must have some tasks with non-integer start or end dates.

Figure

  Figure I.7 -Examples of "interesting" and not "interesting" processing times.

  reduction from P | | C max and P m | | C max , we have: Theorem I.4.2 P | d j =d | -w j (p j ) is strongly NP-complete and P m | d j =d | -w j (p j ) is weakly NP-complete with the following profit functions: (1) LPSTIP, w min j =w min , b j =b (2) LBP, w max j =w max (3) LBP, b j =b (4) LBPST, b j =b, w max j =w max (5) LBPSTIP, p min j =p min , b j =b, w max j =w max

  | -w j (p j ) is strongly NP-complete. P m | PLP | -w j (p j ) is weakly NP-complete.

  0 ⊂ Ω, and |Ω| = O n |W|

  singular task T l ) Proof. Algorithm 3 searches exhaustively the dominant set U 2 and therefore returns an optimal solution. The complexity of step 1 is O(n log n). The sizes of C * (resp. s * ) is n|Ω| = n |W|+1 and since O(log |Ω|) time is required to retrieve an already computed value of C * (resp. s * ), it takes O(K|W| log n) to compute a given value. Therefore, the complexity of step 2 is O(K|W|n |W|+1 log n). The complexity of computing the first max in step 3 is O(|W|n |W| log n) and the complexity of computing the second one is O(n 2|W|+1 (|W| log n + log K)). The overall complexity is thus polynomial in the size of the input. Corollary I.5.2.1 1 | | -w j (p j ) can be solved by Algorithm 3 in polynomial time with the following profit functions:

  n,w,l)≤d w + w l (d -C * (n, w, l)) (one singular task T l ) Proof. Algorithm 4 searches exhaustively the dominant set U 4 and therefore returns an optimal solution. The complexity of step 1 is dominated by the computation of C * . The size of C * is n 2 |Ω| = n |W|+2 and since O(log |Ω|) time is required to retrieve an already computed value of C * , it takes O(K|W| log n) to compute a given value. Therefore, the complexity of step 1 is O(K|W|n |W|+2 log n). The complexity of computing the first max in step 2 is O(|W |n |W| log n) and the complexity of computing the second one is O(n |W|+1 (|W | log n+log K)). The overall complexity is thus polynomial in the size of the input. Corollary I.5.3.1 1 | d j =d | -w j (p j ) can be solved by Algorithm 4 in polynomial time with the following profit functions:

  3:if p l = ρ max then 4: return p j j=1,...,n 5:for k from 0 to n do 6: if p k = 0 or k = l then 7: continue 8: if p k < ρ max -p l then 9: p l ← p l + p k p l < ρ max k ← p k + p l -ρ max 13:p l ← ρ max 14:return p j j=1,...,n

  Let I be an instance of Problem ( P ) and I (one of) its reduced instance. Let S and S be the solutions returned by Algorithm 8 respectively on instance I and I . Then for all k = 1, . . . , n, k = l: p k = p k Proof. In what follows, C k denotes the completion time of the current solution at the end of iteration k.

  11: p j ← p max j for all j = 1, . . . , |V | 12: for k from 1 to |V | do 13: C ← C + p max k 14: Add element k with cost b k in q. 15: while C > d k do 16:

  Algorithm 11 returns an optimal solution to 1 | LBPSTIP | -w j (p j ). If four parameters among {p min j , p max j , b j , w min j , w max j , d j } can only take a fixed number of possible values, then Algorithm 11 returns an optimal 47/127 CHAPTER I. PDPS PROBLEMS solution to 1 | LBPSTIP | -w j (p j ) in polynomial time. Algorithm 11 1 | LBPSTIP | -w j (p j ) 1: for every antichain A of T do 2:

  where δ v is the set of edges incident to v). The weight of a b-matching x ∈ N E is defined as e∈E w e x e . The maximum weight b-matching problem is then the problem of finding a b-matching of maximum weight in G. I.7.1 P | LPSTIP, p min j =p min , d j =d | -w j (p j )

Figure I. 8 -

 8 Figure I.8 -Illustration of the structure of the solutions in U

in ) 0 Figure

 0 Figure I.9 -A part of the graph including only one job given as input of the maximum weight b-matching problem which resolution returns an optimal solution of P | LPSTIP, p min j =p min , d j =d | -w j (p j ) when n 1 and t are fixed

Figure I. 10 -

 10 Figure I.10 -Illustration of the structure of the solutions of U

Figure I. 11 -

 11 Figure I.11 -Operation which is repeated to make a solution satisfy (3)

I. 7

 7 .3 P | LBPST, p max j =p max , d j =d | -w j (p j ) With the same idea, we have: Theorem I.7.3.1 There exists an algorithm that solves P | LBPST, p max j =p max , d j =d | -w j (p j ) in polynomial time.

  Figure I.12 -A part of the graph including only one job given as input of the maximum weight b-matching problem which resolution returns an optimal solution of P | LPSTIP, p min j =p min , b j =b | -w j (p j ) when the number of scheduled jobs is fixed

Figure I. 13 -

 13 Figure I.13 -Illustration of the structure of the solutions of U when n > (q + 1)m

1Figure

  Figure I.20 -LPSTIP

  SNTP for Pure cf-SOSP is similar to the problem presented byJaniak and Kovalyov 1996. They studied the case without release dates and proposed a O(n log n) exact algorithm. Algorithm 16 is an adaptation of this algorithm in order to take into account the release dates. It is similar to Algorithm 10 presented in Chapter I page 46. Its complexity increases to O(n 2 ). Note 77/127 CHAPTER II. STAR OBSERVATION SCHEDULING Algorithm 15 feasible and schedule for Pure SOSP 1: procedure feasible(S i )

  IPAG df-SOSP can be solved by Dynamic Programming as explained for Pure df-SOSP.

  ] ← false, for all j = 1, . . . , n 4:S i = ∅ for all i ∈ NightSet

S

  Ī ← greedy Ī, TWList 11: w = w(S) -w(SĪ) + w(S Ī ) 12:if w ≥ w(S best ) -y then

  Figure II.1 depicts the maximum relative gap between LNS and the best known upper bound on Pure SOSP for each size of instances. It gives an experimental guarantee of the solution quality for the user. At each instant, the largest gap always comes from an instance of size 1000. In 2 seconds, of LNS after 2 minutes (LNS120) and 2 hours (LNS7200) compared to best-known upper bounds (UB) and local search from Catusse et al. 2016 (LS120, LS7200).

Figure II. 1 -

 1 Figure II.1 -Maximum gap of LNS on Pure SOSP for each size of instances

  Figure II.3 shows the schedule returned by LNS for one of them. Since there are only four instances, we directly show the graphs for each one.

  Figure II.2 -Comparison between the values of the solutions returned by LNS for several values of x on two typical instances.

Figure II. 3 -

 3 Figure II.3 -Visualisation of a schedule found by LNS in SPOT. Each column corresponds to a night, each rectangle to an observation. The height of a rectangle corresponds to the duration and its color to the profit of the corresponding observation.

Figure II. 5 -

 5 Figure II.5 -Comparison between the values of the solutions returned by the algorithms implemented in SPOT on instances p100apr13 and p101may05.

Figure

  Figure III.1 -Illustration of a not valid guillotine cut (a) and a valid one (b). Fig (b) shows in light gray possible waste areas and in dark gray the possible remaining area that can serve other uses.

Figure

  Figure III.3 -Illustration of the consequence of the minimum waste constraint on a plate of the best known solution of instance B1: additional waste must be added before the first 1-cut. Otherwise either the waste on the right of item 1 or the waste on the right of item 23 would violate the minimum waste constraint.

Figure

  Figure III.4 -Examples of current (plain) and previous (dotted) cuts

Figure III. 7 -

 7 Figure III.7 -Illustration of Proof of Lemma III.2.1.1. The new solution is feasible since there are no defects.

Figure III. 8 -

 8 Figure III.8 -Illustration of Proof of Proposition III.2.1.2. The new solution is feasible since there are neither defects nor precedences.

Figure

  Figure III.9 -Counter-examples for the dominant set

Figure III. 11 -

 11 Figure III.11 -Computing the new current 1-cut

Figure

  Figure III.13 -Updating the current 2-cut when items have been inserted above a defect

Figure

  Figure III.15 -Avoiding cutting through defect with 2-cuts

Figure III. 19 -

 19 Figure III.19 -The first partial solution dominates the second one.

•

  Figure III.24 -Computational experiments -Dataset B

  proved NPcompleteness of most general cases based on reductions to the Knapsack Problem and to P m | | C max . We also proposed Dynamic Programming algorithms, list algorithms and b-matching formulation based algorithms running in polynomial time for many special cases. Still, several other cases remain open; we give here some noticeable examples. P | LPST | -w j (p j ) and P | LPST, p min j =p min | -w j (p j ) seem really simple and yet, we could not find polynomial algorithms that solve them. 1 | LBPST, p min =p min | -w j (p j ) corresponds to a fractional knapsack with a fixed setup cost. It seems related to the Cardinality Constrained Knapsack Problem which Farias Jr and Nemhauser 2003 proved to be NPcomplete. P | LBP, p max j

  in S i do

	4:	C ← max{C, r k j } + p k j
	5:	if C > d k j then
	6:	return false
	7:	return true
	8: procedure schedule(S i )
	9:	C ← 0	Current time
	10:	w ← 0	Total profit
	11:
	12:	C ← max{C, r k j }
	13:	s ← C
	14:	p ← p k j
	15:

for

(j, k, τ, s, p)

in S i do

  Comparison of the values of the solutions returned by LNS on Pure SOSP, Pure df-SOSP and Pure cf-SOSP.

	-1.90	-6.06	-7.67	9.12	6.69	-1.36	-0.01	-0.01	-10.00	0.00	10.00	-11.77	-22.60	0.00	-10.26	0.00	-0.90
		14 347.44	14 108.33	14 753.12	14 041.69	13 605.64	19 449.49	19 588.99	19 900.00	19 080.00	18 730.00	23 390.73	23 343.90	23 630.00	22 939.74	22 650.00	18 677.10
		13.5	-4	4	15	7	-0.5	-41	-30	-30	-50	-7.5	-23.5	-80	-70	-60	58
		53.5	46	24	55	47	39.5	59	30	30	30	82.5	86.5	60	80	70	98
		14 354	14 116	14 744	14 035	13 607	19 450	19 589	19 910	19 080	18 720	23 403	23 367	23 630	22 950	22 650	18 678
		53	54.5	33.5	55	56.5	59.5	59	40	50	50	88	113.5	99	85.5	74.5	106
		6 14 340 14 280 14 300 14 333.00	7 14 120 14 050 14 070 14 104.50	8 14 740 14 700 14 720 14 733.50	9 14 020 13 970 13 980 14 025.00	10 13 600 13 540 13 560 13 596.50	11 19 450 19 370 19 410 19 429.50	12 19 630 19 510 19 530 19 569.00	13 19 940 19 850 19 880 19 890.00	14 19 110 19 020 19 050 19 070.00	15 18 770 18 650 18 690 18 700.00	16 23 410 23 270 23 320 23 358.00	17 23 390 23 200 23 280 23 313.50	18 23 710 23 470 23 570 23 569.00	19 23 020 22 800 22 870 22 885.50	20 22 710 22 520 22 580 22 594.50	real 18 620 18 550 18 580 18 656.00	Table II.2 -

110/127 CHAPTER III. ROADEF/EURO CHALLENGE 2018

  Methods with this property are called in AI communities anytime algorithms because they can be stopped at any time and still provide good solutions. Some anytime algorithms are known in Operations Research. Indeed, Beam Search, an anytime method from AI, is popular in scheduling and packing

  Anytime tree searches are usually based on 3 classical searches: Breadth First Search (BFS), Depth First Search (DFS) and A*. For more information about BFS and DFS, we refer the reader to Russell and Norvig 2016. We quickly present A*. A* is guided by a lower bound (for a minimization problem) of a node f (n) = g(n) + h(n) where g(n) is the prefix cost and h(n) an optimist estimate cost. A* considers a list of open nodes called fringe. At the beginning, the fringe contains only the root. At each iteration of the algorithm, A* extracts the node with the smallest lower bound, removes it from the fringe, and adds all its children into the fringe. It continues until it finds a feasible solution n (which is also optimal since the value of n is better than any other remaining node lower bound) or the fringe is empty (in this case, there is no feasible solution in the search tree). A* may take a lot of time and memory, however, the first solution it provides is optimal. It is summed-up in Algorithm 19 (see Russell and Norvig 2016 for more details).

	Algorithm 19 A* algorithm

1: fringe ← {root} 2: while fringe = ∅ do 3: n ← extractSmallestLowerBound(fringe) 4: if n is feasible then return n 5: fringe ← fringe \ {n} 6:

  Simplified Memory-bounded A* (SMA*) was originally proposed by[START_REF] Russell | E cient memory-bounded search methods[END_REF] To the best of our knowledge, SMA* is not popular in Operations Research. It consists in exploring the search tree as A*, opening the node n with the smallest lower bound. It adds to the fringe the child of n which has the smallest lower bound (and which is then removed from the list of children of n), and updates the lower bound of n and its ancestors if needed. n is discarded if it does not have any children left, otherwise, it is kept into the fringe with an updated lower bound. Like Beam Search, it considers a maximum fringe size D. If the fringe contains more than D nodes, SMA* discards the nodes which have the biggest lower bound. As Beam Search, SMA* generalizes the greedy algorithm if D = 1, and, SMA* generalizes A* if D = ∞. MBA* outperformed the other procedures presented before on the challenge instances given the branching scheme described in Section III.2. The main difference between MBA* and SMA* is that MBA* never opens partially a node. Indeed, SMA* stores partially explored nodes which makes the algorithm more difficult to implement. MBA* adds all the children of the selected node at once and then discards it.

	III.3.2 The proposed anytime tree search: Memory
		Bounded A* (MBA*)
	Algorithm 20 Memory Bounded A* (MBA*)
	1: fringe ← {root}
	2: while fringe = ∅ ∧ time < time limit do
	3:	n ← extractBest(fringe)
	4:	fringe ← fringe \ {n}
	5:	for all v ∈ children(n) do
	6:	fringe ← fringe ∪ {v}
	7:	while |fringe| > D do
	8:	n ← extractW orst(fringe)

A* is known to minimize the cost estimate on nodes it opens. However it suffers from a large memory requirement since it has to store a large amount of nodes in the fringe. We propose a simple but yet powerful heuristic variant of A* that cuts less promising nodes if the fringe has more than D nodes. We call this new tree search algorithm Memory Bounded A* (MBA*). Like Beam Search, it takes a parameter D. Like SMA*, if D = 1 it corresponds to a greedy algorithm and corresponds to A* if D = ∞. 9:

Introductory paragraph from Catusse et al.

written by my supervisors.

Figure II.4 -Comparison between the values of the solutions returned by the algorithms implemented in SPOT on instances p100mar27 and p101apr12.

http://www.roadef.org/challenge/2018/en/

https://github.com/fontanf/roadef2018

http://www.roadef.org/challenge/2018/en/index.php

https://github.com/fontanf/roadef2018

Remerciements

 Computers & Industrial Engineering 53.3, pp. 420-432. doi: 10.1016/j. cie.2007.02.005. Zhang, Lu, and Yuan (2009). "Single machine scheduling with release dates and rejection". In: European Journal of Operational Research 198.3, pp. 975-978. doi: 10.1016Research 198.3, pp. 975-978. doi: 10. /j.ejor.2008Research 198.3, pp. 975-978. doi: 10. .10.006. -(2010)). "Single-machine scheduling under the job rejection constraint". In:

Theoretical Computer Science 411.16, pp. 1877-1882. doi: 10.1016/j. tcs.2010.02.006.

amount of time. Further research could for example focus on diversification techniques to improve this aspect. Theoretically, allowing flexible observation durations necessarily improves the value of the optimal solution. In practice, on the given instances, LNS indeed finds better solutions in theses cases. However, the additional gain is rather moderate.

The algorithm is now implemented in the software used by the astrophysicists, and we hope it will be used in production very soon.

CHAPTER III. ROADEF/EURO CHALLENGE 2018

• for all k-cut C, k odd, there exists either an item or a defect J such that y 1 (J) ≥ y 1 (C) and y 2 (J) ≤ y 2 (C) and x 2 (J) = x(C)

• for all k-cut C, k even, there exists either an item or a defect J such that x 1 (J) ≥ x 1 (C) and x 2 (J) ≤ x 2 (C) and y 2 (J) = y(C) is dominant.

Proof. Let S be an optimal solution violating one of the conditions as late as possible. We prove the odd case, however the proof is identical for the even case. Let C be the first k-cut of S, k odd, such that for all items and defects J: y 1 (J) > y 2 (C) or y 2 (J) < y 1 (C) or x 2 (J) = x(C). C can be moved to the left with all items of S which left cut is C until it encounters an item, a defect, another cut, or the border of the plate (in the last two cases, the cut C is removed). The new solution remains optimal and either it violates the property later than S or not at all; in both cases, that contradicts the choice of S. The property holds with the minimum waste constraint if we remove the precedences and the defects:

For the guillotine two-dimensional orthogonal packing problem with minimum waste, the set of solutions U such that for all S ∈ U , for all consecutive k-cuts C 1 , C 2 (that may be a plate border), there exists at most one (k + 1)-cut C that does not satisfy the following properties

Similarly, we define z 2 (S) for the current 2-cut; it can however take three different values. Figure III.12 illustrates two solutions where the first insertion is a 2 items insertion. Because of the 4-cut constraint, the top of item J 2 must necessarily be a 2-cut and cannot be a 4-cut. Therefore, in solution (a), the insertion of J 3 at depth 3 leads to a feasible solution, but in the second solution, the insertion of J 3 at depth 3 leads to an infeasible solution. In other words: once two items have been inserted, the position of the current 2-cut is fixed. Therefore, let z 2 (S) be such that

• z 2 (S) = 2 iff the current 2-cut cannot be moved without violating the 4-cut constraint.

• otherwise:

z 2 (S) = 0 iff to move the current 2-cut to the top, it should be moved by at least the minimum waste in order to respect the minimum waste constraint.

z 2 (S) = 1 iff the current 2-cut can be move to the top by any value without violating the minimum waste constraint.

The value of z 1 (S) and z 2 (S) must be taken into account when computing the position of the new current cuts in order to insure generating feasible partial solutions.

When updating the position of the new current 2-cut, items inserted above a defect must also be taken into account. Indeed, if the position of the cut increases, then those items will also be moved. This is illustrated by Figure III.13. Initially,in (a), item J 1 is inserted above the first defect.

When inserting item J 2 , if the current 2-cut were moved to y 2 (J 2 ), then item J 1 would be moved on a defect, generating an infeasible solution. Therefore, the current 2-cut must be moved higher.

CHAPTER III. ROADEF/EURO CHALLENGE 2018

defect yet. However, depending on the following insertions, that may happen later, as illustrated by the second solution. Therefore, we introduce x max 1 as the maximum position of the current 1-cut. Note that x max 1 cannot be computed right after inserting J 1 since the position of the current 2-cut is not fixed yet: an item higher than J 1 could be inserted at depth 3 and the 2-cut would be shifted higher and would not intersect the defect. Therefore, x max 1 is computed when the current 2-cut gets fixed. In the example, this corresponds to the insertion of J 2 . is also used to handle the maximum 1-cut size constraint. The branching scheme described in this section generates a high number a children for each node. Hence the need to cut dominated nodes or break symmetries.

III.2.4 Depth based cuts

Some rules illustrated on Figure III.17 are applied to avoid generating unpromising nodes:

• if an item can be inserted on the current plate, then the insertion in a new plate, i.e. with depth 0 is not considered;

• if an item can be inserted at depth 2 or 3 without increasing the current 1-cut, then the insertion with depth 1 is not considered;

• if an item can be inserted at depth 3 without increasing neither the current 1-cut nor the current 2-cut, then the insertions at lower depths are not considered.

Some other rules make it possible to avoid generating identical solutions:

Figure III.17 -In solution (a), item J 3 can be inserted at depth 2 without increasing the current 1-cut. Therefore, solution (b) where it is inserted at depth 1 is not considered. In solution (c), J 3 can be inserted at depth 2, however, this increases the current 1-cut. Therefore, solution (d) where it is inserted at depth 1 is considered anyway.

• if the last insertion is a defect at depth d, then the next insertion must also happen at depth d;

• if the last insertion is a 2-item insertion at depth d = 3, then the next insertion must be at depth 3 (unless some tricky conditions that will not be described here are met).

III.2.5 Pseudo-dominance rule

When looking at a partial solution, we see a "front" defined by the previous 1-cut, the current 2-cut, the current 3-cut, the previous 2-cut and the current 1-cut (see Figure III.18). The idea is that if the front of a partial solution S 1 is "before" the front of another partial solution S 2 that contains the same items, then we assume that

III.3.3 Guide functions

Tree search methods are dependent on well crafted guide functions. In the literature on tree search, many use lower bounds as guides since the first found solution is known to be optimal. However, for this problem, the search space is too big to prove optimality and using a lower bound may not be the best choice to find good solutions. Indeed, during the development, we started by using the waste area, which is a lower bound, as a guide. We noticed that the resulting solutions packed small items on the first plates and big items on the last plates. These solutions had small waste area in the beginning but a lot in the last plates which made the solutions globally bad. Another issue with using lower bounds is that it may not be relevant to compare two nodes from different depths of the tree. For example, a solution with only few items will always be considered more interesting than a solution containing almost all items. We designed some "heuristic" guides to overcome these issues and obtained better solutions. We studied and use the two following guide functions:

• waste percentage: nodes containing big items become more interesting if they do not generate too much waste with respect of their own size;

• waste percentage/average item area packed: nodes containing big items are even more appealing.

We also tried several combinations of the above guides. The results were not promising and we only used those two on separate processors.

III.4 Complete algorithm

In the previous sections, we described the branching scheme and tree search algorithms. We now explain how we assemble these components together. Note that we take advantage of the multi-core architecture of the computer used for evaluating algorithms in the challenge. First, we distinguish the case where the instance has two chains or less. In this case, we run the A* algorithm with dynamic programming based on the pseudo-dominance rule described in Section III.2.5 (we call it DPA*). If an instance is only composed of one chain, and the instance contains less than 700 items (this information was given on the challenge description), then the algorithm solves it optimally according to the branching scheme and the pseudo-dominance rule in less than a second. If the instance is composed of