A Branch-and-Price Algorithm for Scheduling Observations on a Telescope

1 Scheduling observations on a 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, calling for efficient algorithms.

Software solutions exist to cope with scheduling observations. SPIKE, originally designed for the Hubble Space Telescope, addresses specific cases and uses a constraint programming approach, together with a multistart stochastic repair procedure [Johnston and Miller, 1994]. SPOT is a recent integrated tool designed for automating the schedule computation in the case of a search for extra-solar planets: it first analyzes the various constraints and determines the observation windows of each target in each night, and then computes actual schedules using heuristic and meta-heuristic techniques. It is fast (5 minutes for 1000 targets on a modern laptop), provides a friendly user interface and is portable on all major operating systems [Lagrange et al., 2015].

In this paper we investigate alternative, exact methods to cope with the typical kind of instances which are frequently addressed to SPOT and that can be described as a parallel machine scheduling problem with time-windows and the particular constraint that each task has a mandatory instant at which it must be in execution; the problem is formally defined in Section 2, together with notations, a mixed-integer programming formulation and the many links with interval scheduling problems. Then, we prove the NP-completeness of the problem (Section 3) and propose solution procedures and bounds (Section 4). Experimental results on real and realistic datasets are discussed in Section 5.

2 Problem description

We are given a set of allocated nights and a targets list. Each target has a scientific priority and many properties as its coordinates, its angular proximity to the moon, its elevation above the horizon, etc. Each night has also specific properties: its starting and ending times as well as particular conditions (e.g, due to weather) that prevent the observation of some specific directions or target faint objects. Furthermore, in the case of extra-solar planet surveys, a target must be observed when it crosses its meridian and the exposure must ensure a minimum rotation of the field of view. Altogether, this information defines, for every target: an interest, an observation duration, a mandatory instant of observation (the meridian) and an observation window; note that, apart from the interest, all these parameters are night-dependent.

As a consequence, the problem we address is a parallel scheduling problem with an apriori mandatory part known for each task (nights can be seen as machines and targets as tasks). It is precisely defined as follows.

We consider a set M of m nights and a set T of n targets. Each target i has an interval [rj i ↪ dji [ when it can be observed during night j, and a duration of observation pji ; furthermore each target must be observed at its meridian mji . The telescope can observe only one target at once, and each target i has a weight wi that represents its "interest". The objective is to maximize the total weight of the observed targets by deciding the allocation of the targets to the nights and the schedule of the observations within the nights.

The existence of mandatory instants (meridians) implies a particular structure on both the instances and the solutions:

Property 1 A target i has a mandatory instant during night j if and only if 2pji ≥ dji - rj i .

Proof If mji is a mandatory instant then rj i ≥ mji - pji and dji  mji + pji and thus 2pji ≥ dji - rj i . Conversely, if 2pji ≥ dji - rj i then tji = (rj i + dji )◁2 can be considered as a mandatory instant. 2

Property 2 The observations must be scheduled by nondecreasing mandatory instants (for a given night j).

Proof Consider two targets 1 and 2 such that mj1 < mj2 . Target 2 ends after mj2 (mandatory instant) and thus strictly after mj1 : hence, target 1 cannot respect its mandatory instant mj1 if it is schedule after target 2. 2

Property 2 is a key feature for everything that follows as the order of the observations scheduled during a same night is known in advance. First, it allows for the following mixedinteger linear formulation:

where the decision variables are: zi (binary, 1 if and only if target i is scheduled); zj i (binary, 1 if and only if target i is scheduled during night j); yi1↪i2 (binary, 1 if and only if targets i1 and i2 are scheduled during the same night); and ti (non-negative, the starting time of the observation of target i).

The objective sums up the total interest of the scheduled targets. Constraints (1) ensure that each scheduled target is actually scheduled within some night. Constraints (2) and (3) impose that a target, if scheduled during night j, respects the corresponding observation interval (note: M is a large constant, e.g., the length of the longest night). Constraints (4) and (5) ensure that two observations scheduled during the same night do not overlap; in constraints (5), "i1 ≺j i2" refers to the order induced by Property 2. This mixed-integer formulation allows for a clear statement of the problem, but is improper for a fast solution of large instances.

When interpreted in scheduling terms, the problem, due to Property 1, is described by the notation R♣rj i ↪ 2pji ≥ dji - rj i ♣ P wiUi (see e.g., [Pinedo, 2014] for classical notations and results from scheduling theory). If the observation intervals do not depend on the night (rj i = ri; dji = di; pji = pi), then nights are identical machines, and the problem becomes a special case of the parallel machine scheduling problem with release and due dates where one wants to minimize the weighted number of unscheduled tasks (P♣ri♣ P wiUi). This problem is NP-complete, even for a single night, no release dates and a unique due-date (1♣di = d♣ P wiUi), or with no release dates, no due dates, and no weights (P ♣♣ P Ui), or for one night and no weights (1♣ri♣ P Ui). However, the special case 1♣ri↪ pi = p♣ P wiUi is polynomially solvable [Baptiste, 1999], as is the case for 1♣ri↪ pi = di -ri♣ P wiUi [Chuzhoy et al., 2006].

If the duration of the interval is exactly the processing time but the observation intervals depend on the night (i.e., pji = dji - rj i ), then the problem belongs to interval scheduling (see [Kolen et al., 2007] for a review). If all targets have the same weight, then the problem can be solved in polynomial time by a greedy algorithm [Faigle and Nawijn, 1995; Carlisle and Lloyd, 1995]. If the duration does not depend on the night (pi = di - ri), the problem can be formulated as a minimum cost flow and is solvable in polynomial time [Arkin and Silverberg, 1987; Bouzina and Emmons, 1996]. However, when some targets are not visible some nights, the problem becomes NP-complete, except if the number of nights is fixed [Arkin and Silverberg, 1987].

When a discrete set of k intervals is associated to a target (e.g., one possible interval per night), then the problem of deciding whether all targets can be scheduled is NP-complete if k ≥ 3 [Nakajima and Hakimi, 1982], and is polynomial if k = 2 [Keil, 1992]. However, scheduling a maximum number of targets with discrete intervals is NP-complete if k ≥ 2 [Spieksma, 1999].

To the best of our knowledge, the assumption 2pji ≥ dji -rj i has not been studied before. It implies a particular structure of a feasible solution but nevertheless, as we prove in the next section, the problem remains NP-complete.

3 Complexity analysis

The complexity of various related problems has been discussed above; Table 1 sums up the main results. In this section we prove that, with the assumption that 2pi ≥ di -ri the problem is NP-complete but solvable in pseudo-polynomial time if there is one night (Section 3.1), and is unary NPcomplete for several nights (Section 3.2). Note that NPcompleteness is not straightforward since the problem is polynomial with either equal weights or duration equals to the observation window.

P♣ri↪ 2pi ≥ di - ri♣ P wiUi NP-complete⇤

3.1 The single night problem

The problem reduced to one night is a special case of the one machine scheduling problem with release dates (1♣rj♣ P wjUj, NP-complete). It is indeed a constant relative window size problem, where each task verifies k pi ≥ di - ri (polynomial for k = 1): we consider the case k = 2 and we prove that the weighted problem is NP-complete (Theorem 1) and the unweighted case is polynomial (Proposition 1).

Theorem 1 The single-night observation scheduling problem (1♣ri↪ 2pi ≥ di - ri♣ P wiUi) is NP-complete.

Proof The single-night observation scheduling problem is trivially in NP. We shall reduce a variant of the PARTITION problem to ours.

PARTITION: given n pairs of integers (a2i-1↪ a2i) such that P2n i=1 ai = 2B, is there a set S such that: S contains exactly one element of each pair (a2i-1↪ a2i), and Pi2S ai = B? This problem is NP-complete [Garey and Johnson, 1979].

• ÷ r2i-1 = r2i = 2(i - 1)B + Pi-1 k=1 min(a2k-1↪ a2k),

Consider an instance of PARTITION. For each pair of integers, we create a pair of incompatible targets. More precisely, we consider 2n targets such that wi = pi = 2B + ai and:

• ÷ d2i-1 = d2i = 2iB + Pik=1 max(a2k-1↪ a2k), except for the last two targets: d2n-1 = d2n = 2(n + 1)B.

(Note that the assumption 2pi ≥ di - ri holds, and that the transformation is polynomial.) The question is: is there a schedule of these targets of total interest at least (2n+1)B?

First, assume that PARTITION has a solution S. We build an observation schedule by picking the targets corresponding to the integers in S: they can be scheduled within their timewindow and are done so without idle-time. The total interest of such a schedule is 2(n + 1)B. Hence if PARTITION has a solution, then, there is a schedule of value 2(n+1)B.

Conversely, let assume that there is a feasible schedule of total interest 2(n + 1)B. Such a value implies that this schedule is non-idling, as the value of each observation is equal to its duration. Besides, for a given i, note that no target other than 2(i - 1) or 2i can be scheduled during the interval ]2(i - 1)B + Pi-1 k=1 max(a2k-1; a2k); 2iB + Pik=1 min(a2k-1; a2k)[, and that at most one of them can be scheduled, for they are overlapping. Since the schedule is non-idling, one target from each pair (2(i - 1)↪ 2i) has been selected and the schedule corresponds to a solution of PARTITION. Hence, if there is a schedule of value 2(n+ 1)B, then PARTITION has a solution.

As a consequence, solving the observation scheduling problem solves PARTITION. As the latter is NP-complete, so is the former. 2

Proposition 1 If all targets have the same interest (wi = 1), then the single-night observation scheduling problem (1♣ri↪ 2pi ≥ di - ri♣ P Ui) is polynomially solvable.

1. Set initial solution S = ;

Proof The selected targets must be scheduled in a predefined order (Property 2); we assume that they are numbered accordingly (1 ≺ 2 ≺ ▷ ▷ ▷ ≺ n). Apply the following procedure:

2. For i = 1 to n do

• ÷ if target i is compatible with every observation in S, schedule it as early as possible;
• ÷ otherwise, target i is incompatible with target k, the last target added to S; replace k with i if i ends before k when scheduled as early as possible.

This algorithm runs in polynomial time and, besides, it is optimal. Indeed, let S⇤ be an optimal solution and let k⇤ and k be the first observations to differ respectively in S⇤ and S. By definition of the procedure, k ends before k⇤ and is thus compatible with all the remaining observations of S⇤ : the procedure must have selected them (or alternative observations that, in each case, ends before the corresponding observations in S⇤ ). As a consequence S has as many observations as S⇤ , and is thus optimal. 2

The known order of the observations within a night allows for a procedure based on standard dynamic programming:

Theorem 2 The single-night observation scheduling problem (1♣ri↪ 2pi ≥ di - ri♣ P wiUi) can be solved in pseudopolynomial time.

Proof Consider a set of n targets and a night length T = maxi=1▷▷n di. Let f ⇤ (i↪ t) be the optimal value of a schedule involving targets 1↪ ▷ ▷ ▷ ↪ i and such that i finishes before t. f ⇤ verifies:

Note that, for a target i the last three cases span over the whole night: [0↪ ri + pi[[[ri + pi↪ di][]di↪ T]. We are looking for f ⇤ (n↪ T ) which can be computed in space and time complexity O(nT ). 2

Note that this procedure provides a very efficient algorithm when the time horizon is not too large.

3.2 Several nights problem

If the order of the observations does not depend on the night, then the algorithm of Theorem 2 can be generalized, yielding an O(nT m) algorithm, pseudo-polynomial for a fixed number of nights m. However, in the general case, the problem is unary NP-complete:

Theorem 3 The observation scheduling problem is NPcomplete in the strong sense when there are several nights, even for the unweighted case and if the observation intervals are the same for all the nights (that is: problem P♣2pi ≥ di - ri♣ P Ui is unary NP-complete).

Proof The observation scheduling problem is in NP. We shall prove that the NUMERICAL 3-DIMENSIONAL MATCHING problem reduces to ours.

NUMERICAL 3-DIMENSIONAL MATCHING (3-DM): given 3 sets of n non negative integers X = ¶x1↪ · · · ↪ xn♦, Y = ¶y1↪ ▷ ▷ ▷ ↪ yn♦ and Z = ¶z1↪ · · · ↪ zn♦ such that Pni=1 (xi+yi+zi) = nB, is there a collection S of n subsets Sj = ¶xj1 ↪ yj2 ↪ zj3 ♦ containing exactly one element of each set X, Y and Z such that [nj=1Sj = X [ Y [ Z and such that for each set Sj: xj1 + yj2 + zj3 = B? This problem is NP-complete in the strong sense [Garey and Johnson, 1979].

Now, consider an instance of 3-DM. The reduction is as follows: consider 3 sets of n targets each T X [ T Y [ T Z = T ; the total number of targets is then ♣T ♣ = 3n. The duration of a target i is the same whatever the night and is defined by:

• ÷ 8i 2 T X , pXi = 4B +xi with 0 < xi < B;
• ÷ 8i 2 T Y , pYi = 2B + yi with 0 < yi < B;
• ÷ 8i 2 T Z , pZi = B + zi with 0 < zi < B.

The intervals [ri↪ di] associated with each target i are:

• ÷ [0; 5B] for i 2 T X ;
• ÷ [4B; 8B] for i 2 T Y ;
• ÷ [6B; 8B] for i 2 T Z .

Note that the assumption 2pi ≥ di-ri holds. The weight of a target i is 1. The number of nights is ♣M♣ = n. The question is: is there a schedule of the observations with a total gain of 3n?

The complexity of this reduction is pseudo-polynomial, hence it is a pseudo-polynomial transformation, provided that 3-DM has a "yes" answer if and only if the observation scheduling problem has.

First, consider an instance of 3-DM for which a solution exists. Then, the corresponding instance of the observation scheduling problem admits a solution with a total gain of 3n: each set Sj corresponds to night j, the first observation is scheduled from 0 to 4B+xj1 , the second one from 4B+xj1 to 6B +xj1 + yj2 and the third one from 6B +xj1 + yj2 to 7B+xj1 +yj2 +zj3 = 8B, each respecting its interval, and the total gain is 3n as all the observations are scheduled.

Conversely, assume that the observation scheduling problem admits a schedule of total gain 3n. Such a value is obtained if and only if all the observations are scheduled. As pXi > 4B, exactly one observation i 2 T X must be scheduled first each night. The time remaining each night for the other observations is less than 4B and, as pYi > 2B, exactly one observation i 2 T Y must be scheduled each night. The time remaining each night is less than 2B and, as pZi > B exactly one observation i 2 T Z is scheduled last each night. The total duration of the observations is equal to the available duration of the n nights: Pni=1 (4B + xi + 2B + yi + B + zi) = 7nB + Pni=1 (xi + yi + zi) = 8nB. Consequently there is no idle time, and each night j is such that: 4B + xi1 + 2B + yi2 + B + zi3 = 8B, that is: xi1 + yi2 + zi3 = B, leading to a solution for the instance of the 3-DM.

As a consequence, there exists a pseudo-polynomial transformation from 3-DM to the observation scheduling problem. As the former is NP-complete in the strong sense, so is the latter. 2

4 Solution methods and upper bounds

Various direct formulations of the problem using mixed integer programming, constraint programming and even local search paradigms have been experimented before [Brauner et al., 2015], but the results obtained are completely outperformed by approaches that take advantage of the fact that the single-night problem can be solved in pseudo-polynomial time. We therefore focus on exact and heuristic approaches that rely on the dynamic program proposed for the singlenight case (Theorem 2).

4.1 A column generation procedure

The single-night case is not too hard (see Theorem 2), which allows for a column generation procedure: the set of all possible schedules for every night is considered and a MIP selects an optimal subset of them. The linear relaxation of this MIP is solved iteratively by adding the column (feasible schedule) with maximum reduced cost, which can be computed using the dynamic program for the single-night case.

Let ⌦j be the set of all possible schedules for night j. The k-th schedule for night j is described by a 0/1 vector (sk1↪j ↪ ▷ ▷ ▷ ↪ skn↪j ), where ski↪j is equal to 1 if and only if observation i belongs to the k-th schedule of night j, and the weight of this schedule is equal to wk j = Pi2T wiski↪j .

Let ⇢kj be a binary variable indicating whether the k-th schedule is used for night j. An extended formulation of the observation scheduling problem can be stated as follows:

The sets ⌦j are too large to be enumerated completely, thus the linear relaxation of this model is solved with a column generation procedure. The pricing problem is to identify a variable ⇢kj to enter the basis. Let ↵j and βi denote the dual variables of respectively constraints (1) and (2). The reduced cost of variable ⇢kj is defined as:

So the pricing problem is to identify a valid schedule (ski↪j ) that maximizes Pi2T ski↪j (wi - βi) - ↵j . Such a column of maximum reduced cost can be found with the dynamic program (Theorem 2) by replacing wi with (wi - βi). The sets ⌦j are thus iteratively increased as long as a positive reduced cost schedule can be found. When dropping the constraints that ⇢kj are integers, the procedure yields an upper bound.

4.2 A branch-and-price algorithm

The problem can be formulated as a constraint programming model:

1. NIGHTDISJUNCTIVE([zj1 ↪ ▷ ▷ ▷ ↪ zj ♣T ♣ ]) j 2M

The binary decision variables zi and zj i denote respectively whether target i is scheduled, and if it is scheduled during night j. The starting dates of the observations are not explicitly represented as the model ensures that a feasible schedule for each night can be obtained by scheduling targets as early as possible in the order of their meridians. This is ensured by constraints (2): NIGHTDISJUNCTIVE states that the targets chosen for a night j can be scheduled without overlapping. This disjunctive scheduling problem is easy to solve due to the known ordering of the targets: checking whether a set of targets can be scheduled can be done using a greedy algorithm starting each target as early as possible. Algorithm 1 is thus used as a necessary and sufficient condition for the constraint to be satisfied when applied to the mandatory targets of night j, Mj = ¶i♣zj i = 1♦. It is also used for each remaining ungrounded zja by checking if Mj [¶a♦ can be scheduled and, if not, value 1 is filtered from the domain of zja ; this enforces generalized arc-consistency in O(♣T ♣2 ). This can be seen has a specific case of the unary resource or disjunctive global constraint with optional tasks when the order of the tasks is known.

Algorithm 1 returns whether the set S of targets can be scheduled in night j

Require: Targets S sorted by non-decreasing meridians 1: ctime 0 2: for each target i 2 S do 3: ctime max(ctime↪ rj i ) + pji 4: if ctime > dji then 5: return false; 6: return true

Constraints (3) are a relaxation of the NIGHTDISJUNCTIVE constraints that aims at speeding up the filtering of targets that cannot be scheduled a given night. A simple example would be that two targets i1 and i2 cannot be scheduled in a same night j when their total durations exceeds the available time; that is when pji1 + pji2 > max(dji1 ↪ dji2 ) -min(rj i1 ↪ rj i2 ). The two targets are then said to be incompatible. The incompatibility graph of night j is defined with a vertex for each target and an edge for each pair of incompatible targets. A clique C jk in this graph can provide a constraint stating that at most one of the targets of the clique can fit in night j. The C jk are obtained by computing maximal cliques in the incompatibility graph of night j; and C j simply denotes a set of such maximal cliques.

Constraint (4) considers all variables of the problem and encapsulates the column generation procedure to propagate an upper bound of z. It can be seen as a redundant constraint stating the objective function and the key features for implementing it are:

• ÷ The dynamic program is modified to handle the mandatory/forbidden targets for a night. The domains of the variables are thus taken into account in the sub-problem of the column-generation and do not affect the master.
• ÷ All generated columns are kept and the ones compatible with the current domains are added to the master to
• initialize it whenever the filtering algorithm is called to update the upper bound.
• ÷ When the relaxation turns out to be integer (⇢kj end up being integers), the zj i are grounded to the related values.
• ÷ Finally the zj i are filtered using the optimal reduced costs. Reduced cost based filtering is a traditional filtering technique that can be applied from an optimal solution of the linear relaxation. It can possibly fix to 0 some binary (0/1) variables remaining out of the basis. This technique can also be applied with an extended formulation by taking advantage of the dynamic program.

Search strategy

The search is directed by the global relaxation provided by the column generation procedure. It is performed in two steps that can be seen as best first and first fail types of strategies.

First, a good feasible solution is identified. The branching is performed on a variable zj i that maximizes Pk2⌦⇤j ⇢kj ski↪j , setting value 1 first. In other words, we set to 1 the targets that seem to be favored by the relaxation. This step is backtrack free and the search simply dives to a feasible integer solution.

The search is then restarted from scratch and the branching is performed on a variable zj i that minimizes ♣0▷5 - Pk2⌦⇤j ⇢kj ski↪j ♣ and setting value 1 first. In other words, we select the mostly undecided variables of the relaxation, hopping to decrease the upper bound as much as possible to fail as soon as possible.

4.3 A local search approach

We implemented a local search approach to serve as a baseline. The search space is represented by the possible assignments of the targets to the nights, with an additional fake night for unscheduled targets. The following neighborhood is used for any such assignment (a "night" might be the fake one):

• ÷ shift: move a target from one night to another.
• ÷ swap: swap two targets between two nights.
• ÷ reschedule: considering all targets of a given real night j and those of the fake night, reschedule night j with a set of maximum value (using the dynamic program of Theorem 2).

A move is valid if it leads to a feasible assignment (all nights can be scheduled) and does not degrade the objective function. The moves are explored in a random order and the first valid move found is performed. So the search is performed in the space of feasible assignments only, and can iterate over plateaus of configurations with the same objective value. A simple tabu mechanism is added. This approach can be seen as a large neighborhood search due to the reschedule move which is the core component.

5 Experimentations

Since we only have one real dataset, we generated realistic random datasets. We choose ♣T ♣ 2 ¶400↪ 600↪ 800↪ 1000♦ and ♣M♣ 2 ¶71↪ 107↪ 142♦, respecting the proportion of the real dataset between the number of targets and the number of nights (datasets 1-15) or increasing the number of targets with the same number of nights (datasets 16-20). For all datasets, the horizon is equal to 640 (time is discretized in minutes).

The dataset generator tries to reproduce the real dataset. We first generate random targets that can be observed some time during the year and we compute the visibility window of each target each day of a year. Then we generate a number of random nights of observation, batched into runs (consecutive days), as in the real dataset. As a consequence, the targets of two nights in the same run are almost the same, up to an offset of the visibility windows, due to the rotation of the earth around the sun.

The experiments were performed on an Intel Xeon E52440 v2 @ 1.9 GHz processor and 32 GB of RAM, and ran with a memory limit of 4 GB and a time limit of 2 hours.

Figure 1 provides, from left to right, the dataset name, the size of T and M, and the computational result of each method described: the column generation (Section 4.1), the branch-and-price (Section 4.2), the MIP formulation (Section 2), the local search (Section 4.3) and the SPOT software (Section 1).

• ÷ Column generation: the upper bound rounded down to a multiple of 10 (RUB, wi are multiples of 10), the gap between RUB and the best lower bound found (GAP) and the computation time in seconds (CPU).
• ÷ Branch-and-price: the number of solutions found (NSOL), the computation time to find the first solution (FCPU), the best lower bound (LB), yes (Y) or no (N) depending if optimality has been proved and the total computation time (CPU) in seconds.
• ÷ MIP: the gap between the best known lower bound and the solution obtained by the MIP in 2 hours, "-" if no feasible solution was found within the time limit (GAP2h).
• ÷ Local search: the gap between the best known lower bound and the solution obtained with local search in 2
• minutes (GAP-2m), and the same gap with the solution obtained after 2 hours (GAP-2h).
• ÷ SPOT: the gap between the best known lower bound and the solution obtained with SPOT in 2 minutes (GAP2m), and the same gap with the solution obtained after 2 hours (GAP-2h).

The optimal solution is found and proved by the branchand-price for 18 out of 21 datasets. For the 3 remaining, the gap with the upper bound computed by column generation is smaller than 0▷11%. The best lower bound is always provided by the branch-and-price (the gap is thus not given for this approach). The proof of optimality is achieved when the bound is initially optimum. The heuristic guided by the linear relaxation dives directly to an optimal integer solution in all cases except three (instances 7, 16, 20).

The local search is also relevant because it finds good solutions (with a gap smaller than 2▷22%) within only 2 minutes, whereas the first solution of the branch-and-price requires more computation time for the biggest datasets (with ♣T ♣ ≥ 800). In comparison, on the real dataset, the MIP model (section 2) does not found any solution and SPOT provides a solution of objective 17940 (i.e a gap of 3.65%) using 2 hours of computation time.

6 Conclusion

In this paper, we have studied a parallel machine problem with mandatory instants. We proved the NP-completeness of the problem and proposed a column-generation, a branchand-price and a local-search procedures to solve it. Experimental results show these methods strongly dominates an outof-the-box MIP and a tailored dedicated heuristic. Indeed, optimal (or very near optimal) solutions can be obtained in a very short time (2 hours), with regard to the planning horizons (several months).

Acknowledgments

The authors are grateful to Benoit Cance and Alexandre Le Jean for preliminary studies and their work on the datasets.

We also thank all the students involved in preliminary study of this problem: Cyril Dutrieux, Ily`es Mezghani, Kimia Nadjahi and Lucie Pansart. This work received a grant from the LabEx PERSYVAL-Lab (ANR-11-LABX-0025).