Carla Juvin
email: carla.juvin@laas.fr

Laurent Houssin
email: laurent.houssin@laas.fr

Pierre Lopez
email: pierre.lopez@laas.fr

Hybrid Methods to Solve the Two-Stage Robust Flexible Job-Shop Scheduling Problem with Budgeted Uncertainty

Keywords: Flexible Job-Shop Scheduling, Robust Optimization, Uncertainty Budget, Mixed Integer Linear Programming, Constraint Programming

This paper addresses the robust flexible job-shop scheduling problem considering uncertain operation processing times associated with an uncertainty budget. Exact solution methods based on mixed integer linear programming and constraint programming are proposed to solve the problem. Such solutions are hybridized in the framework of a two-stage robust optimization, and a column and constraint generation algorithm is used to solve representative instances. The experimental results show the advantages of a two-stage approach where constraint programming and integer programming are mixed to solve a master problem and a subproblem, respectively.

INTRODUCTION

The job-shop scheduling problem is a well studied and NP-hard problem where a set of jobs are to be processed on a set of machines [START_REF] Garey | The complexity of flowshop and jobshop scheduling[END_REF]. Each job is composed of a sequence of operations that must be processed on machines with given processing times in a given job-dependent order, and each machine can process only one operation at a time. The flexible job-shop problem (FJSSP) is a generalization of the job-shop scheduling problem: for each operation, there exists a set of eligible machines. This makes the problem more difficult to solve, as it consists of both a machine allocation and a sequencing problem. The FJSSP has received considerable attention and both metaheuristics and exact methods have been developed to solve the problem, the majority of them with the assumption that the parameters are deterministically known [START_REF] Brandimarte | Routing and scheduling in a flexible job shop by tabu search[END_REF][START_REF] Dauzère-Pérès | An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search[END_REF]. However, in the real world, many sources of uncertainty (processing times variation, machine breakdown, addition of new operations, etc.) can affect the quality and even the feasibility of a schedule.

There exist two major approaches to deal with data uncertainty: stochastic optimization and robust optimization. While stochastic optimization considers probability distribution, robust optimization assumes that uncertain data belong to a given uncertainty set and aims to optimize performance considering the worst-case scenario within that set.

In this paper, we propose exact solution methods to solve the robust flexible job-shop scheduling problem. A two-stage robust optimization is used to deal with processing times uncertainty, where the first stage fixes the assignment and the sequence of operations on machines whilst the second stage sets the operation start times. We provide two robust counterpart models based on mixed-integer linear programming and constraint programming formulations, as well as a column and constraint generation algorithm. A discussion is conducted on the basis of an analysis of experimental results.

PROBLEM DEFINITION

Deterministic Flexible Job-Shop Scheduling Problem

We first introduce the flexible job-shop scheduling problem (FJSSP) with makespan minimization. An instance of the FJSSP implies a set of jobs J and a set of machines M . Each job i ∈ J consists of a sequence of n i operations. The j th operation O i, j ∈ O i of a job i must be performed by one of the machines from the set of eligible machines M i, j ⊆ M . Let p i, j,m denote the processing time of operation O i, j that is processed on machine m ∈ M i, j . Each machine can process at most one operation at a time and preemption is not allowed: once an operation is started, it must be processed without any interruption. The objective is to find an assignment for each operation and a sequence on each machine that minimize the maximum completion time or makespan C max .

Notations and definitions

J

Set of jobs

M Set of machines n i Number of operations in job i (i ∈ J ) O i Set of operations in job i (i ∈ J ) O i, j j th operation of job i (i ∈ J , j ∈ {1, . . . , n i }) M i, j Set of eligible machines for operation O i, j (i ∈ J , O i, j ∈ O i ) p i, j,m Processing time of operation O i, j on machine m (i ∈ J , O i, j ∈ O i , m ∈ M i, j ) I m Set of operations that can be processed by machine m (m ∈ M ) H Big constant

Flexible Job-Shop Scheduling Problem with Uncertain Processing Times

We consider that the processing times of operations are uncertain. Each processing time p i, j,m of an operation O i, j ∈ O i , i ∈ J , on machine m ∈ M i, j , belongs to the interval [ pi, j,m , pi, j,m + pi, j,m ], where pi, j,m is the nominal value and pi, j,m the maximum deviation of the processing time from its nominal value.

Example 1. Consider an FJSSP instance with 3 jobs and 2 machines. The intervals [ pi, j,m , pi, j,m + pi, j,m ] of processing times p i, j,m of operations O i, j ∈ O i , i ∈ J on each eligible machine m ∈ M i, j , are given in Table 1.

Uncertainty Budget

The traditional robust optimization approach [START_REF] Soyster | Convex programming with setinclusive constraints and applications to inexact linear programming[END_REF] consists in protecting against the case when all parameters can deviate at the same time, which makes the solution overly conservative. Indeed, there is a very low probability that all parameters take their worst value all together. To overcome this limitation, [START_REF] Bertsimas | The price of robustness[END_REF]) introduce an uncertainty budget approach that allows a restriction on the number of deviations that can occur simultaneously to a given budget. In order to reach a trade-off between robustness and solution quality, we exploit this approach to define the uncertainty set.

Let Γ be the budget of uncertainty, the maximum number of operations whose processing time deviation can occur simultaneously. The worst-case scenario is always an extremum scenario [START_REF] Ben-Tal | Robust optimization[END_REF]. Thus, for each scenario ξ, the processing time of operation O i, j on machine m is given by: p i, j,m (ξ) = pi, j,m + ξ i, j • pi, j,m where ξ i, j is equal to 1 if the processing time of the operation deviates, 0 otherwise. We define the uncertainty set U Γ as:

U Γ = {(ξ i, j ) i∈J ,1≤ j≤n i | ∑ i∈J n i ∑ j=1 ξ i, j ≤ Γ}

Multi-Stage Robust Optimization

Multi-stage robust optimization has been introduced by [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. In some optimization problems, only part of the decision variables have to be fixed before uncertainty is revealed, while the other variables can be chosen after the realization and can thus be adjusted to the scenario. The authors introduce the adjustable robust counterpart; the set of decision variables is split into "here and now" decisions and "wait and see" decisions. The objective is to find a solution for the "here and now" decision variables such that constraints involving uncertain parameters remain feasible for all values of the uncertain parameters, and minimizing the objective value.

In our problem, we consider that the purpose is to find the assignment and sequence on the machines (first stage: here and now), allowing to define a start time for each operation and each scenario (second stage: wait and see), minimizing the makespan in the worst-case scenario considering the budget of uncertainty. Example 2. Considering Example 1, a feasible solution is the assignment of operations O 1,1 , O 3,1 , O 3,2 to machine M 1 , and of operations O 2,1 , O 2,2 , O 1,2 to machine M 2 , following these sequences. Figure 1 represents this solution when all processing times take their nominal value; the makespan is 221. Considering an uncertainty budget Γ = 2, the worst case, for this solution, is that the processing time of operations O 2,1 and O 1,2 deviate and take their greatest value. Figure 2 shows the Gantt chart in this case. The objective function value of this solution for an uncertainty budget Γ = 2 reaches the makespan equal to 429.

Mixed Integer Linear Programming Model

We define a Mixed Integer Linear Programming (MILP) extended robust model, which is directly inspired by the sequence-based model made by [START_REF] Shen | Solving the flexible job shop scheduling problem with sequence-dependent setup times[END_REF]. The first stage decision variables are defined as follows:

x i, j,m =    1 if operation O i, j is processed on machine m; 0 otherwise y i, j,i ′ , j ′ =    1 if operation O i, j is processed before O i ′ , j ′ ; 0 otherwise while the start time t i, j (ξ) ∈ R + of each operation O i, j in scenario ξ is part of the second stage variables.
The MILP model is as follows: minC max (1) s.t.

∑ m∈M i, j x i, j,m = 1 ∀i ∈ J , ∀ j ∈ O i (2) ∑ m∈M i, j-1 x i, j-1,m • p i, j-1,m (ξ) + t i, j-1 (ξ) ≤ t i, j (ξ) ∀i ∈ J , ∀ j ∈ O i , ∀ξ ∈ U Γ (3) t i ′ , j ′ (ξ) + p i ′ , j ′ ,m (ξ) -(2 -x i, j,m -x i ′ , j ′ ,m + y i, j,i ′ , j ′ ) • H ≤ t i, j (ξ) ∀m ∈ M , ∀(O i, j , O i, j ′ ) ∈ I 2 m , ∀ξ ∈ U Γ (4) t i, j (ξ) + p i, j,m (ξ) -(3 -x i, j,m -x i ′ , j ′ ,m -y i, j,i ′ , j ′ ) • H ≤ t i ′ , j ′ (ξ) ∀m ∈ M , ∀(O i, j , O i, j ′ ) ∈ I 2 m , ∀ξ ∈ U Γ (5) t i,n i (ξ) + ∑ m∈M i,n i x i,n i ,m • p i,n i ,m (ξ) ≤ C max ∀i ∈ J , ∀ξ ∈ U Γ (6) x i, j,m ∈ {0, 1} ∀i ∈ J , ∀ j ∈ O i , ∀m ∈ M i, j (7) y i, j,i ′ , j ′ ∈ {0, 1} ∀(i, i ′ ) ∈ J 2 , ∀ j ∈ O i , ∀ j ′ ∈ O i ′ (8)
The objective ( 1) is to minimize the makespan C max . Constraints (2) are assignment constraints and ensure that each operation is assigned to exactly one machine. Constraints (3) ensure the precedence relation between two consecutive operations of the same job. Constraints ( 4) and ( 5) are the disjunctive constraints and avoid overlapping of operations scheduled on the same machine. Note that Constraints (3), ( 4) and ( 5) are duplicated for each feasible scenario. Finally, Constraints (6) allow to compute the greatest makespan among all feasible scenarios and therefore to determine the optimal solution in the worst case. Finally, Constraints ( 7) and ( 8) define the domain of the variables.

Constraint Programming Model

While Constraint Programming (CP) obtains very good results in scheduling, to the best of our knowledge it has been never used in robust multi-stage models. The following model is directly inspired from [START_REF] Kress | Mathematical models for a flexible job shop scheduling problem with machine operator constraints[END_REF] for the deterministic FJSSP with machine operator constraints. It involves the following variables:

• task i, j,ξ : interval variable between the start and the end of the processing of operation O i, j in scenario ξ;

• mode i, j,m,ξ : interval variable between the start and the end of the processing of operation O i, j on machine m in scenario ξ (since the operations have multiple eligible machines and must be executed by exactly one of them, this is an optional variable);

• seqs m,ξ : sequence variable of tasks scheduled on machine m in scenario ξ.

The CP model is as follows:

minC max (9) s.t.

C max ≥ task i,n i ,ξ .end ∀i ∈ J , ∀ξ ∈ U Γ (10) EndBe f oreStart(task i, j,ξ ,task i, j+1,ξ ) ∀i ∈ J , ∀O i, j ∈ O i \ {O i,n i }, ∀ξ ∈ U Γ (11)
Alternative(task i, j,ξ , mode i, j,m,ξ :

∀m ∈ M i, j ) ∀i ∈ J , ∀O i, j ∈ O i , ∀ξ ∈ U Γ (12) NoOverlap(seqs m,ξ ) ∀m ∈ M , ∀ξ ∈ U Γ (13) PresenceO f (mode i, j,m,0 ) ⇒ PresenceO f (mode i, j,m,ξ ) ∀i ∈ J , ∀O i, j ∈ O i , ∀m ∈ M i, j , ∀ξ ∈ U Γ \ {0} (14) SameSequence(seqs m,0 , seqs m,ξ ) ∀m ∈ M , ∀ξ ∈ U Γ \ {0} (15)
Constraints (10) allow the determination of the makespan, which is equal to the end of the last operation. Constraints (11) ensure the precedence relation between two consecutive operations of the same job. Constraints (12) ensure that each operation is assigned to exactly one machine. Constraints (13) ensure that in each scenario each machine performs at most only one operation at the same time. Constraints (10-13) are duplicated for each scenario. Constraints ( 14) and ( 15) ensure that the assignment of each operation and the sequence on each machine are the same in each scenario. For these last two constraints, the first scenario ξ = 0 is used as reference.

COLUMN AND CONSTRAINT GENERATION APPLIED TO THE FJSSP

We present here a column and constraint generation approach to solve the robust flexible job-shop scheduling problem. This method has been introduced by [START_REF] Zeng | Solving two-stage robust optimization problems using a column-and-constraint generation method[END_REF] to solve two-stage robust optimization problems. The procedure splits the problem into a master problem and an adversarial subproblem. The idea is to solve the robust counterpart problem (or master problem), for a limited subset of scenarios, and then to identify which scenarios, if any, make the found solution infeasible, using an adversarial subproblem. Then, these scenarios are included in the master problem by generating the corresponding recourse decision variables on the fly. This process repeats until a solution that is feasible for all scenarios is found [START_REF] Hamaz | The cyclic job shop problem with uncertain processing times[END_REF][START_REF] Duarte | Multi-process production scheduling with variable renewable integration and demand response[END_REF][START_REF] Silva | Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty[END_REF][START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF].

Column and Constraint Algorithm

For the FJSSP, the master problem can be defined as one of the extended models presented in Section 3, for which only a subset of scenarios is considered, i.e. each robust constraint ((3-6) for the MILP model or (10-13) for the CP model) is defined only for a subset of scenarios. An optimal solution for this master problem allows us to obtain a lower bound on the makespan for the global problem. In order to verify the feasibility of this solution, given the assignments and sequences on the machines fixed in the master problem, we check whether one of the possible scenarios leads to a greater makespan than the one found in the master problem. If such a scenario exists, then the variables and constraints associated with it are generated and added to the master problem. In our case, the search for such a scenario can be seen as the search for the scenario that leads to the largest possible makespan. Figure 3 depicts the scheme of the column and constraint generation algorithm, where LB represents the lower bound and UB the upper bound.

Worst-Case Evaluation

Having assigned and sequenced operations on machines via the master problem, we know all precedence relations between operations, both the precedences in the jobs induced by the problem, and the precedences on the machines fixed in the master problem. The resulting problem corresponds to the evaluation of the worst-case scenario: Given an uncertainty budget Γ, the aim is to identify the Γ deviating operations that lead to the greatest makespan.

Mixed Integer Linear Programming

We introduce a MILP model with the following decisions variables:

ξ i, j =    1 if processing time of operation O i, j deviates; 0 otherwise b i, j,i ′ , j ′ =    1 if operation O i, j starts at the end of operation O i ′ , j ′ ; 0 otherwise d i =    1 if the last operation O i,n i of job i is the
last operation among all to be completed; 0 otherwise Let also A i, j be the set of immediate predecessors of operation O i, j . The MILP model developed for the worst-case scenario evaluation is as follows: max C max ( 16)

s.t. ∑ i∈J ∑ j∈O i ξ i, j = Γ (17) t i, j -(t i ′ , j ′ + pi ′ , j ′ + ξ i, ′ j ′ • pi ′ , j ′ ) ≤ H • (1 -b i, j,i ′ , j ′ ) ∀i ∈ J , ∀ j ∈ O i , ∀(i ′ , j ′ ) ∈ A i, j (18)
∑ (i ′ , j ′ )∈A i, j b i, j,i ′ , j ′ ≥ 1 ∀i ∈ J , ∀ j ∈ O i | A i, j ̸ = / 0 (19) t i,1 = 0 ∀i ∈ J | A i,0 = / 0 (20) C max -(t i,n i + pi,n i + ξ i,n i • pi,n i ) ≤ H • (1 -d i ) ∀i ∈ J (21) ξ i, j ∈ {0, 1} ∀i ∈ J , ∀ j ∈ O i (22) b i, j,i ′ , j ′ ∈ {0, 1} ∀i ∈ J , ∀ j ∈ O i , ∀(i ′ , j ′ ) ∈ A i, j (23) d i ∈ {0, 1} ∀i ∈ J (24)
The objective is to find the scenario (the values of ξ i, j for each operation O i, j ) that maximizes the makespan (16). Constraints (17) ensure that exactly Γ operations have their processing time deviating. Constraints ( 18) and ( 19) ensure that each operation, which has at least one predecessor, starts at the maximum time among the completion time of the predecessors. Constraints (20) ensure that operations with no predecessor start at time 0. Constraints (21) ensure that the makespan is equal to the latest completion time among all jobs.

Constraint Programming

We introduce a CP model with optional interval variables dev i, j , which are present only if the processing time of the corresponding operation O i, j takes its maximum value (i.e. the operation deviates from its nominal value). Let us define the decision variables used to model the subproblem as follows:

• task i, j , interval variable associated to operation O i, j of duration pi, j,m ;

• dev i, j , optional interval variable of duration pi, j,m , present if operation O i, j deviates from its nominal value.

We also use function HeightAtStart, which gives the contribution of an interval variable to a cumulative function at its start point, and the cumulative function StepAtStart, which defines the contribution of an interval at its start. maxC max (25)

s.t. task i,1 .start = 0 ∀i ∈ J | A i,1 = / 0 (26) task i, j .start = max({task i ′ , j ′ .end | O i ′ , j ′ ∈ A i, j }) ∀i ∈ J , ∀O i, j ∈ O i (27)
StartAtEnd(dev i, j ,task i, j ) ∀i ∈ J , ∀O i, j ∈ O i (28) ∑ i∈J ∑ j∈O i HeightAtStart(dev i, j , StepAtStart(dev i, j , 1)) = Γ (29)
C max = max(∪ ∀i∈J ({task i,n i .end} ∪ {dev i,n i .end})) (30)
The objective is to find the scenario (by determining which optional interval variables dev i, j are present) that maximizes the makespan (25). Constraints ( 27) and ( 28) ensure that each operation starts as soon as possible, given the assignment and the sequencing determined by the master problem, and the precedence constraints. Constraints (29) ensure that if the interval variable dev i, j is present, meaning that the processing time of the corresponding operation O i, j deviates from its nominal value, this processing time is equal to its maximum value. Constraints (29) ensure that exactly Γ operations take their maximum values for their processing times. Finally, Constraints (30) ensure that the makespan is equal to the latest completion time among all jobs.

For computational tests, all experiments are performed on three cluster nodes with Intel Xeon E5-2695 v4 CPU at 2.1 GHz. All algorithms presented are implemented in C++, using CPLEX 12.10 for the MILP models and CP Optimizer (CPO) 12.10 for the CP models. CPU time and RAM are respectively limited to 1 hour and 16 GB.

Instances and Methods

The instances we used for our tests are small-and medium-size problems instances for the FJSSP taken from [START_REF] Fattahi | Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[END_REF] (whose features are described in Table 2), adapted to the robust problem by randomly generating values for the deviations. Let pmax be the maximum nominal processing time for all operations and all machines. For each operation O i, j and each eligible machine m ∈ M i, j , we randomly generate a value for pi, j,m within a range from 25 % to 100 % of the value of pmax . We repeat this operation three times; we therefore obtain three new instances from one initial deterministic instance. We generate in total 60 instances that we use for our tests. We tested all the models by varying the budget of uncertainty according to four ratios, namely 20 %, 40 %, 60 % and 80 % of the number of operations rounded down to the nearest integer, giving a total of 240 experiments per method.

In addition to the two extended models presented in Section 3, we evaluate four combinations of the column and constraint algorithm presented in Section 4. Table 3 presents the name and configuration of each tested method (ccg stands for column and constraint generation).

Results

Table 4 presents general results comparing the performance of the methods for all instances, by reporting the number of instances that each method is able to solve within the time limit. If we focus on the extended methods, we notice that the CP formulation performs slightly better than the MILP method. Secondly, we note that methods based on column and constraint generation allow to solve considerably more instances than extended methods. More specifically, those using a CP formulation for the master problem are the ones with the best results. Finally, we observe that the resolution of the adversarial subproblem with MILP provides a marginally better performance than with the CP model.

Table 5 reports, for each original instance, the number of robust instances (among the 12) solved to optimality by each method and the average time to achieve it. Not surprisingly, we observe that the more the size of the instances increases the more difficult they are to solve, visible by a decreasing number of solved instances and an increasing CPU time. Extended methods manage to solve all instances up to 4 jobs and 5 machines while 'ccg cp milp' solves all instances up to 6 jobs and 7 machines. Table 6 aims to visualize the performance of the methods according to the given uncertainty budget. We notice that for the extended methods, the resolution is more difficult for medium budget (40 % and 60 %); this is due to the fact that these uncertainty budgets generate a greater number of scenarios and, in these methods, the number of decision variables is directly related to the number of scenarios. However, for methods based on the column and constraint generation algorithm, the number of instances solved to optimality increases with the uncertainty budget. It shows that the number of scenarios has no direct ef-

CONCLUSIONS

In this paper, we consider the two-stage flexible jobshop scheduling problem where the operation processing times are subject to uncertainty. The first stage is devoted to fixing the assignment and sequencing decisions; the second stage determines the start time of the operations. As a main contribution, we introduce two robust counterpart formulations to solve the robust scheduling problem, including one based on constraint programming. We use a column and constraint generation algorithm mixing both integer linear programming and constraint programming. Experimental results show that the best method, among those tested in this study, is the constraint and column generation method using constraint programming in the master problem and an integer linear programming model for the subproblem.

Figure 1 :

 1 Figure 1: A feasible solution for Example 1, when all processing times take their nominal value.

Figure 2 :

 2 Figure 2: From the solution of Figure 1, the worst-case solution with an uncertainty budget of 2.

Figure 3 :

 3 Figure 3: Column and constraint algorithm.

Table 1 :

 1 Numerical example of an instance of the FJSSP: operation processing times.

		M1	M2
	O 1,1	[43; 86]	-
	J1 O 1,2	[87; 170]	[95; 190]
	O 2,1	[63; 142]	[53; 166]
	J2 O 2,2	-	[73; 131]
	O 3,1 [125; 239] [135; 224]
	J3 O 3,2	[43; 73]	[61; 174]

Table 2 :

 2 Characteristics of FJSSP instances.

	Instance #Jobs #Machines #Operations
	SFJS1	2	2	4
	SFJS2	2	2	4
	SFJS3	3	2	6
	SFJS4	3	2	6
	SFJS5	3	2	6
	SFJS6	3	3	9
	SFJS7	3	5	9
	SFJS8	3	4	9
	SFJS9	3	3	9
	SFJS10	4	5	12
	MFJS1	5	6	15
	MFJS2	5	7	15
	MFJS3	6	7	18
	MFJS4	7	7	21
	MFJS5	7	7	21
	MFJS6	8	7	24
	MFJS7	8	7	32
	MFJS8	9	8	36
	MFJS9	11	8	44
	MFJS10	12	8	48

Table 3 :

 3 Methods description.

	Method	Method	Robust	Sub-
	name	type	counterpart problem
	milp	extended	milp	-
	cp	extended	cp	-
	ccg milp	ccg	milp	milp
	ccg milp cp	ccg	milp	cp
	ccg cp	ccg	cp	cp
	ccg cp milp	ccg	cp	milp

Table 4 :

 4 Methods performance comparison (number of instances, out of 240, solved to optimality).

	Method	#Solv.
	milp	130
	cp	133
	ccg milp	167
	ccg milp cp	166
	ccg cp	190
	ccg cp milp	193
	fect on the difficulty of the problem.


Carla Juvin
email: carla.juvin@laas.fr

Laurent Houssin
email: laurent.houssin@laas.fr

Pierre Lopez
email: pierre.lopez@laas.fr

Constraint programming for the robust two-machine flow-shop scheduling problem with budgeted uncertainty

Keywords: Flow-Shop Scheduling, Robust Optimization, Uncertainty Budget, Mixed-Integer Linear Programming, Constraint Programming

This paper addresses the robust two-machine permutation flow-shop scheduling problem considering non-deterministic operation processing times associated with an uncertainty budget. The objective is to minimize the makespan of the schedule. Exact solution methods incorporated within the framework of a twostage robust optimization are proposed to solve the problem. We first prove that under particular conditions the robust two-machine permutation flow-shop scheduling problem can be solved in polynomial time by the well-known Johnson's algorithm usually dedicated to the deterministic version. Then we tackle the general problem, for which we propose a column and constraint generation algorithm. We compare two versions of the algorithm. In the first version, a mixed-integer linear programming formulation is used for the master problem. In the second version, we use a constraint programming model for the master problem. To the best of our knowledge, the use of constraint programming for a master problem in a two-stage robust optimization problem is innovative. The experimental results show the very good performance of the method based on the constraint programming formulation. We also notice that Johnson's algorithm is surprisingly efficient for the robust version of the general problem.

Introduction

The permutation flow-shop scheduling is a well-studied problem where a set of jobs are to be processed on a set of machines. Each job must be processed on every machine, with given processing times, following the same given order of machines. Each machine can process only one job at a time and the processing sequence of jobs is the same on each machine. This problem is strongly NPhard for three or more machines. However, the two-machine flow-shop scheduling problem is solved by the well-known Johnson's algorithm [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF] for the makespan minimization when operation processing times are assumed deterministic. In the real world, many sources of uncertainty (processing times variation, machine breakdown, addition of new operations, etc.) can affect the quality and even the feasibility of a schedule.

There exist two major approaches to deal with data uncertainty: stochastic optimization and robust optimization. While stochastic optimization considers probability distribution, robust optimization assumes that uncertain data belong to a given uncertainty set and aims to optimize performance considering the worst-case scenario within that set. The traditional robust optimization approach [START_REF] Soyster | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF] consists in protecting against the case when all parameters can deviate at the same time, which makes the solution overly conservative. Indeed, there is a very low probability that all parameters take their worst value all together. To overcome this limitation, Bertsimas & Sim introduce an uncertainty budget approach that allows a restriction on the number of deviations that can occur simultaneously to a given budget [START_REF] Bertsimas | The price of robustness[END_REF]. In order to reach a trade-off between robustness and solution quality, we exploit this approach to define the uncertainty set. Multi-stage robust optimization has been introduced by Ben-Tal et al. [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. In some optimization problems, only a part of the decision variables have to be determined before uncertainty is revealed, while the other variables can be chosen after the realization of the uncertainty and can thus be adjusted to the scenario. The authors introduce the adjustable robust counterpart where the set of decision variables is split into "here and now" decisions and "wait and see" decisions. Thus, the objective is to find a solution for the "here and now" decision variables such that there always exists "wait and see" variables meeting the constraints for all values of the uncertain parameters, and minimizing the objective value.

The purpose is to find the sequence on the machines (first stage decision), allowing to define a start time for each operation and each scenario (second stage decision), minimizing the makespan in the worst-case scenario considering the budget of uncertainty.

In this paper, we propose exact solution methods to solve the robust twomachine flow-shop scheduling problem. We first study a particular case of the problem. Next, we provide a robust counterpart model based on constraint programming formulation, that is embedded in a column and constraint generation framework. A discussion is conducted on the basis of an analysis of experimental results.

Problem Statement

An instance of the two-machine flow-shop scheduling problem implies a set of jobs J and two machines M = {M 1 , M 2 }. Each job i ∈ J consists of two operations O i,1 and O i,2 . The first one, O i,1 , must be processed by machine M 1 with a duration of p i,1 and then, O i,2 must be processed by machine M 2 with a duration of p i,2 . Each machine can process only one job at a time and each job can only be processed on one machine at a time. The objective is to find a permutation of jobs, denoted σ, minimizing the makespan.

When processing times are deterministically known, the problem can be solved in polynomial time by means of Johnson's rule [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF], which states that job i must be processed before job j if min(p i,1 , p j,2 ) < min(p j,1 , p i,2 ).

Here, we consider that the processing times of operations are uncertain. Each processing time p i,m of an operation O i,m , i ∈ J , m ∈ {M 1 , M 2 }, belongs to the interval [p i,m , pi,m + pi,m ], where pi,m is the nominal value and pi,m the maximum deviation of the processing time from its nominal value.

Let Γ be the budget of uncertainty, that is the maximum number of operations whose processing time deviation can occur simultaneously. For each scenario ξ in the set of feasible scenarios U Γ , the processing time of operation O i,m is then given by:

p i,m (ξ) = pi,m + ξ i,m • pi,m
where ξ i,m is equal to 1 if the processing time of the operation deviates, 0 otherwise.

In this study we consider two types of uncertainty budget:

1. A global budget Γ which denotes the number of operations that can deviate on both machines combined. In this case, the set of feasible scenarios is expressed as:

U Γ = (ξ i,m ) i∈J ,m∈{M1,M2} | i∈J 2 m=1 ξ i,m ≤ Γ, ξ i,m ∈ {0, 1} 2. A machine-dependent budget Γ = (Γ 1 , Γ 2 )
where Γ 1 and Γ 2 denote the number of operations whose processing time deviation can occur simultaneously on machines M 1 and M 2 , respectively. In this case, the set of feasible scenarios is expressed as:

U Γ = (ξ i,m ) i∈J ,m∈{M1,M2} | i∈J ξ i,1 ≤ Γ 1 , i∈J ξ i,2 ≤ Γ 2 , ξ i,m ∈ {0, 1} 2

.1 Worst-case evaluation

For a given sequence of jobs σ, there exists a worst-case scenario, maximizing the value of the makespan. Levorato et al. [START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF] developed a polynomial-time (O(n 2 )) worst-case determination procedure, using dynamic programming, for machinedependent budget Γ = (Γ 1 , Γ 2 ). The same idea is now used when considering a global budget Γ . Given a machine m ∈ M, and two integer numbers i ∈ [1, |J |] and γ ∈ [0, Γ ], let C γ i,m (σ) be the maximum completion time of the i th job of sequence σ, on machine m, considering at most γ deviations. This value is defined by the following recurrence relations:

C γ i,1 (σ) = max(C γ i-1,1 (σ) + pσ[i],1 , C γ-1 i-1,1 (σ) + pσ[i],1 + pσ[i],1 ) (1)
C γ i,2 (σ) = max(C γ i-1,2 (σ) + pσ[i],2 , C γ i,1 (σ) + pσ[i],2 , C γ-1 i-1,2 (σ) +p σ[i],2 + pσ[i],2 , C γ-1 i,1 (σ) + pσ[i],2 + pσ[i],2 ) (2)
with

C γ i,m (σ) = -∞ if γ < 0, C γ 0,m (σ) = 0 if γ ≥ 0 and C 0 i,2 (σ) = pσ[i],2 + max(C 0 i-1,2 (σ), C 0 i,1 (σ)
) ∈ J 2 , ∀(m, m ′ ) ∈ M 2 , pi,m < pi ′ ,m ′ ⇔ pi,m + pi,m < pi ′ ,m ′ + pi ′ ,m ′ ,
then a schedule following the Johnson's rule is optimal for any global uncertainty budget Γ .

Proof. Suppose that σ is an optimal sequence for a given global uncertainty budget Γ , with four consecutive jobs,

σ[i -1], σ[i] = j, σ[i + 1] = k and σ[i + 2]
meeting one of the following conditions:

(i) pj,1 > pj,2 and pk,1 < pk,2 (ii) pj,1 < pj,2 , pk,1 < pk,2 and pj,1 > pk,1 (iii) pj,1 > pj,2 , pk,1 > pk,2 and pj,2 < pk,2
Note σ ′ the sequence obtained from σ by pairwise interchange jobs j and k.

It suffices to show that under any of the three conditions the makespan of the schedule under σ ′ is not greater than under σ.

The maximal start time of job

σ[i + 2] = σ ′ [i + 2]
, on machine M 1 , considering at most γ deviations, is the same under σ and σ ′ , namely,

C γ i+1,1 (σ) = C γ i+1,1 (σ ′ ) = max(a 1 , a 2 , a 3 ) with: a 1 = C γ i-1,1 (σ) + pj,1 + pk,1 a 2 = C γ-1 i-1,1 (σ) + pj,1 + pk,1 + max(p j,1 , pk,1 ) if γ ≥ 1, 0 otherwise a 3 = C γ-1 i-1,1 (σ) + pj,1 + pj,1 + pk,1 + pk,1 if γ ≥ 2, 0 otherwise
Thus, the rest of the schedule on machine M 1 is not affected by the pairwise interchange. We now study the effect of the change on the schedule on machine M 2 , in particular, the date of availability of machine M 2 to process job σ[i + 2], i.e., C γ i+1,2 (σ) under the original schedule and C γ i+1,2 (σ ′ ) after the interchange. The completion time of job σ Thus under each condition, C γ i+1,2 (σ ′ ) ≤ C γ i+1,2 (σ), and therefore the makespan of the schedule under σ ′ is not greater than under σ. □ Consequently, it is possible to find an optimal sequence for the robust twomachine permutation flow-shop scheduling problem, with global uncertainty budget and preserved order of processing times, in polynomial time.

[i+1] = k under original schedule σ is C γ i+1,2 (σ) = max(b 1 , b 2 , b 3 , b 4 , b 5 , b 6 , b 7 , b 8 , b 9 , b 10 , b 11 ) with: b 1 = C γ i-1,2 + pj,2 + pk,2 b 2 = C γ-1 i-1,2 + pj,2 + pk,2 + max(p j,2 , pk,2 ) if γ ≥ 1, 0 otherwise b 3 = C γ-2 i-1,2 + pj,2 + pj,2 + pk,2 + pk,2 if γ ≥ 2, 0 otherwise b 4 = C γ i-1,1 + pj,1 + pj,2 + pk,2 b 5 = C γ-1 i-1,1 + pj,1 + pj,2 + pk,2 + max(p j,1 , pj,2 , pk,2 ) if γ ≥ 1, 0 otherwise b 6 = C γ-2 i-1,1 + pj,1 + pj,2 + pk,2 + max(p j,1 + pj,2 , pj,1 + pk,2 , pj,2 + pk,2 ) if γ ≥ 2, 0 otherwise b 7 = C γ-3 i-1,1 + pj,1 + pj,1 + pj,2 + pj,2 + pk,2 + pk,2 if γ ≥ 3, 0 otherwise b 8 = C γ i-1,1 + pj,1 + pk,1 + pk,2 b 9 = C γ-1 i-1,1 + pj,1 + pk,1 + pk,2 + max(p j,1 , pk,1 , pk,2 ) if γ ≥ 1, 0 otherwise b 10 = C γ-2 i-1,1 + pj,1 + pk,1 + pk,2 + max(p j,1 + pk,1 , pj,1 + pk,2 , pk,1 + pk,2 ) if γ ≥ 2, 0 otherwise b 11 = C γ-3 i-1,1 + pj,1 + pj,1 + pk,1 + pk,1 + pk,2 + pk,2 if γ ≥ 3, 0 otherwise while the completion time of job σ ′ [i + 1] = j on machine M 2 under sequence σ ′ is C γ i+1,2 (σ ′ ) = max(c 1 , c 2 , c 3 , c 4 , c 5 , c 6 , c 7 , c 8 , c 9 , c 10 , c 11 ), with: c 1 = C γ i-1,2 + pk,2 + pj,2 c 2 = C γ-1 i-1,2 + pk,2 + pj,2 + max(p k,2 , pj,2 ) si γ ≥ 1, 0 otherwise c 3 = C γ-2 i-1,2 + pk,2 + pk,2 + pj,2 + pj,2 if γ ≥ 2, 0 otherwise c 4 = C γ i-1,1 + pk,1 + pk,2 + pj,2 c 5 = C γ-1 i-1,1 + pk,1 + pk,2 + pj,2 + max(p k,1 , pk,2 , pj,2 ) si γ ≥ 1, 0 otherwise c 6 = C γ-2 i-1,1 + pk,1 + pk,2 + pj,2 + max(p k,1 + pk,2 , pk,1 + pj,2 , pk,2 + pj,2 ) if γ ≥ 2, 0 otherwise c 7 = C γ-3 i-1,1 + pk,1 + pk,1 + pk,2 + pk,2 + pj,2 + pj,2 if γ ≥ 3, 0 otherwise c 8 = C γ i-1,1 + pk,1 + pj,1 + pj,2 c 9 = C γ-1 i-1,1 + pk,1 + pj,1 + pj,2 + max(p k,1 , pj,1 , pj,2 ) if γ ≥ 1, 0 otherwise c 10 = C γ-2 i-1,1 + pk,1 + pj,1 + pj,2 + max(p k,1 + pj,1 , pk,1 + pj,2 , pj,1 + pj,2 ) if γ ≥ 2, 0 otherwise c 11 = C γ-3 i-1,1 + pk,1 + pk,1 + pj,1 + pj,1 + pj,2 + pj,2 if γ ≥ 3, 0 otherwise It is clear that b 1 = c 1 , b 2 = c

Machine-dependent budget

Γ = (Γ 1 , Γ 2 )
In general, Johnson's rule does not lead to an optimal robust schedule when considering a machine-dependent uncertainty budget.

Example 1. Consider a robust two-machine flow-shop problem with 3 jobs with machine-dependent uncertainty budget Γ = (1, 2). The intervals [p i,m , pi,m + pi,m ] of processing times p i,m of operations O i,m , i ∈ J , m ∈ M, are given in Table 1. Table 1. Numerical example of an instance of a two-machine flow-shop problem: preserved order of operation processing times.

M1 M2 J1 [6,9] [8,12] J2 [10,15] [4,6] J3 [4,6] [3,5]
Applying Johnson's rule to this instance yields the sequence σ = {J 1 , J 2 , J 3 }. Given the sequence σ, and considering an uncertainty budget Γ = (1, 2), the worst case, for this solution, is that the processing time of job J 2 on machine M 1 and jobs J 2 and J 3 on machine M 2 deviate and take their greatest value. Figure 1 depicts the Gantt chart in this case. The objective function value of this solution reaches a makespan equal to 32. Another possible sequence is σ ′ = {J 3 , J 1 , J 2 }. The worst case for this new solution is such that the processing time of job J 2 on machine M 1 and jobs J 1 and J 2 on machine M 2 deviate from their nominal value. Figure 2 depicts the Gantt chart in this case; it leads to a solution with a worst-case makespan equal to 31. Fig. 2. Example 1 and sequence {J3, J1, J2}: worst case under optimal robust schedule,

J 1 J 2 J 3 J 1 J 2 J 3 M 1 M 2 0 2 4
J 1 J 2 J 3 J 1 J 2 J 3 M 1 M 2 0 2 4
Γ1 = 1, Γ2 = 2.
Although the order of processing times is preserved, Johnson's rule does not allow to obtain the optimal sequence for this instance when considering a machine-dependent uncertainty budget Γ = (1, 2).

Unpreserved order of processing times

In general, Johnson's rule does not lead to an optimal robust schedule when considering an instance with unpreserved order of processing times, even when we consider a global uncertainty budget.

Example 2. Consider a robust two-machine flow-shop problem with 3 jobs with the global uncertainty budget Γ = 3. The intervals [p i,m , pi,m +p i,m ] of processing times p i,m of operations O i,m , i ∈ J , m ∈ M, are given in Table 2. Table 2. Numerical example of an instance of a two-machine flow-shop problem: unpreserved order of operation processing times.

M1 M2 J1 [1,5] [2,3] J2 [2,3] [1,5] J3 [2,20] [4,5]
Applying Johnson's rule to this instance yields the sequence σ = {J 1 , J 3 , J 2 }. Given the sequence σ, and considering an uncertainty budget Γ = 2, the worst case, for this solution, is such that the processing time of job J 3 on machine M 1 and job J 2 on machine M 2 deviate and take their greatest value. Figure 3 depicts the Gantt chart in this case. The objective function value of this solution reaches a makespan equal to 30. Another possible sequence is σ ′ = {J 2 , J 3 , J 1 }. The worst case for this solution is such that the processing time of job J 2 on machine M 1 and job J 1 on machine M 2 deviate from their nominal value. Figure 4 depicts the Gantt chart in this case; it leads to a solution with a worst-case makespan equal to 29. Although the considered uncertainty budget is global, Johnson's rule does not allow to obtain the optimal sequence for this instance whose order of processing times is not preserved.

J 1 J 1 J 3 J 3 J 2 J 2 M 1 M 2 0 2 4
J 2 J 2 J 3 J 3 J 1 J 1 M 1 M 2 0 2 4

General Case

As discussed in the previous section, in the general case, Johnson's rule is not guaranteed to find an optimal robust sequence. However, Mixed-Integer Linear Programming (MILP) or Constraint Programming (CP) allow the development of exact solution methods.

Mixed-integer linear programming robust counterparts

Levorato et al. [START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF] proposed two mixed-integer linear programming robust counterparts for the two-machine permutation flow-shop problem.

The first one is adapted from the integer programming model for the threemachine deterministic flow-shop by Wagner [START_REF] Wagner | An integer linear-programming model for machine scheduling[END_REF]. It uses rank decision binary variables, which determine whether a job is placed at a given position in the sequence. It also uses two types of idle times variables. The first ones represent the time each job waits between the end of its execution on machine M 1 and its starting on machine M 2 . The others represent the time machine M 2 idles between the execution of each pair of consecutive jobs. These idle times variables are duplicated for each considered scenario. Precedence constraints are addressed with job-adjacency and machine-linkage constraints, which exploit the special structure of the problem to describe the relation between idle times, both on machines and jobs, and processing times.

The second robust counterpart proposed by Levorato et al. is based on the formulation presented by Wilson [START_REF] Wilson | Alternative formulations of a flow-shop scheduling problem[END_REF]. It also uses rank decision binary variables to determine whether a job is placed at a given position in the sequence. Precedence constraints are based on start time variables defined for each job operation and each machine.

The numerical experiments in [START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF] highlight the superiority of Wagner's formulation over Wilson's method. Consequently, we only focus on Wagner's formulation and MILP always refers to this formulation in the following.

Constraint programming robust counterparts

Another alternative is to use constraint programming. To present the CP model, we use the IBM CP Optimizer solver, which allows the use of specific decision variables and constraints. In particular, we use interval and sequence variables defined as follows:

task i,m,ξ : interval variable between the start and the end of the processing of job i ∈ J on machine m ∈ {M 1 , M 2 } in scenario ξ ∈ U Γ ; -seqs m,ξ : sequence variable of operations scheduled on machine m ∈ {M 1 , M 2 } in scenario ξ ∈ U Γ .

The CP model developed for the the two-machine robust flow-shop problem is as follows:

min C max (3) s.t. C max ≥ task i,2,ξ .end ∀i ∈ J , ξ ∈ U Γ (4) EndBef oreStart(task i,1,ξ , task i,2,ξ ) ∀i ∈ J , ξ ∈ U Γ (5) N oOverlap(seqs m,ξ ) ∀m ∈ {M 1 , M 2 }, ξ ∈ U Γ (6) SameSequence(seqs 1,1 , seqs m,ξ ) ∀m ∈ {M 1 , M 2 }, ξ ∈ U Γ (7)
Constraints ( 4) allow the determination of the makespan, which is equal to the end of the last job on machine M 2 in the worst-case scenario. Constraints [START_REF] Johnson | Optimal two-and three-stage production schedules with setup times included[END_REF] ensure the precedence relations between the two operations of a same job. Constraints (6) ensure that, in each scenario, each machine performs at most one operation at a time. Constraints [START_REF] Silva | Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty[END_REF] ensure that the sequence is the same on both machines, and the same for each scenario. The first scenario ξ = 1 is used as reference, and the constraint is duplicated for each scenario and each machine.

Column and constraint generation algorithm

The column and constraint generation method has been introduced by Zeng and Zhao [START_REF] Zeng | Solving two-stage robust optimization problems using a columnand-constraint generation method[END_REF] to solve two-stage robust optimization problems. The procedure splits the problem into a master problem and an adversarial subproblem. The idea is to solve the robust counterpart problem (or master problem), for a limited subset of scenarios, that fixes the first stage variables, and then to identify which scenarios, if any, make the solution found in the master problem infeasible, using an adversarial subproblem. Then, these scenarios are included in the master problem by generating the corresponding recourse decision variables on the fly. This process repeats until a solution that is feasible for all scenarios is found [START_REF] Duarte | Multi-process production scheduling with variable renewable integration and demand response[END_REF][START_REF] Hamaz | The cyclic job shop problem with uncertain processing times[END_REF][START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF][START_REF] Silva | Solution algorithms for minimizing the total tardiness with budgeted processing time uncertainty[END_REF]. Figure 5 depicts the scheme of the column and constraint generation algorithm. Levorato et al. [START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF] propose a column and constraint generation framework for the two-machine permutation flow-shop problem. It consists in relaxing one of the MILP formulations presented in Section 4.1 by considering only a subset of scenarios. Then, given a sequence, a polynomial time dynamic algorithm (see Section 2.1) is used to identify the worst-case makespan considering a given uncertainty budget.

Since constraint programming is often very efficient for scheduling problems, we try to improve this framework by replacing the master problem by a relaxed version of the constraint programming model presented in Section 4.2. For this purpose, each robust constraint (4-7) is defined only for a subset of scenarios. The rest of the algorithm remains identical to the version proposed by Levorato et al.

Master Problem

Adversarial subproblem

Optimal

Add scenario : variables and constraints fixed σ all scenarios feasible infeasible scenario Fig. 5. Column and constraint algorithm.

Experimental Results

We evaluate the performance of the column and constraint generation algorithm for both the MILP and the CP models. Experiments are performed on three cluster nodes with Intel Xeon E5-2695 v4 CPU at 2.1 GHz. The algorithms are implemented in C++, CPLEX 12.10 is used as the solver for the MILP master problem and CP Optimizer (CPO) 12.10 for the CP master problem. We limited time to 2 hours, with 4 CPU and a total of 16 GB of RAM, per instance.

Instances from literature

The instances we used in this section are the same as in [START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF], based on instances generated by Ying [START_REF] Ying | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF]. They are composed of six groups of instances of different size, where the number of jobs |J | belongs to {10, 20, 50, 100, 150, 200}.

The nominal processing time pi,m , i ∈ J , m ∈ {M 1 , M 2 } is generated from the uniform distribution U [10, 50] and the processing time deviation pi,m is a ratio of the nominal processing time αp i,m with α = 10, 20, 30, 40 and 50 %. Thus, the order of processing times is preserved through deviation. Ten sets of values for nominal duration were generated for each size |J |, and all deviations ratios α were applied to each of them, giving a total of 300 test instances. The uncertainty budgets, Γ 1 and Γ 2 , are set to 20 %, 40 %, 60 %, 80 % and 100 % of |J |.

We summarize the results in Table 3 where the performance over instances of different sizes is displayed. We report the percentage of instances solved to optimality before reaching the time limit (Solved (%)). For the instances solved to optimality, we display the average execution time, in seconds, to reach optimality (Avg. time (sec)). Lastly, we display the average percentage gap of non-optimally solved instances (Avg. gap (%)), where the gap is given by:

gap method = U B method -LB method U B method . ( 8
)
We notice that the CP model outperforms the MILP one. Indeed, even for the largest instances (200 jobs) the CP-based method manages to solve almost all (98.83 %) of the instances optimally, while the MILP-based method solves fewer and fewer instances as they grow (down to 68.92 % for 200 jobs). We also observe that the time needed to reach the optimum is much lower for the CP method, whatever the size of the instances. Finally, we can see that for both methods, the gap is quite low (less than 1 %, regardless of instance size). Note that the few differences between the results reported here and those presented in [START_REF] Levorato | Exact solutions for the two-machine robust flow shop with budgeted uncertainty[END_REF] concerning the MILP method is probably due to a difference in the implementation of the method and the tools (software and hardware) used for the tests. However, we obtain very comparable results in terms of number of instances optimally solved.

We now examine the quality of the solution obtained by applying Johnson's rule on these instances. Table 4 presents the percentage of best known solution

gap method = U B method -LB * U B method (9)
and LB * is the best bound found among the two versions of the column and constraint generation algorithm. We note that the polynomial time algorithm enables to find high quality solutions. Indeed, for almost all the instances (94.46 %), Johnson's rule provides a robust solution with the same objective value as the best known solution, and the optimality gap is very low. In view of these results, we notice that these instances are easy to solve, due to their particular structure that preserves the order of the processing times. To overcome this, we generated new instances and the results obtained are presented in the following section.

New instances

In this section, we generated new instances which are also based on the ones from [START_REF] Ying | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF]. The nominal processing times pi,m , i ∈ J , m ∈ {M 1 , M 2 } remain the same as in the original instances [START_REF] Ying | Scheduling the two-machine flowshop to hedge against processing time uncertainty[END_REF]. However, the processing time deviations pi,m are randomly generated to avoid the order preserving of processing times. Let pmax be the maximum nominal processing time for all operations. For each operation O i,m , i ∈ J , m ∈ {M 1 , M 2 }, we randomly generate a value for pi,m within a range from 25 % to 80 % of the value of pmax . We generate in total 60 instances that we use for our tests. Again, the uncertainty budgets, Γ 1 and Γ 2 , are set to 20 %, 40 %, 60 %, 80 % and 100 % of |J |.

Table 5 presents the same performance indicators as Table 3 for the new generated instances.

By comparing these two tables, it can be seen that the new instances are more difficult to solve than the ones from literature. Indeed, there is a lower proportion of instances solved optimally, a higher average time needed to reach the optimum, as well as a higher average gap for the unsolved instances, for both methods. However, focusing on the information provided by Table 5, it is noticeable that the CP model still outperforms the MILP one, for all observed indicators. Tables 6 and7 detail the percentage of solved instances according to uncertainty budget Γ = (Γ 1 , Γ 2 ) for the CP-based and the MILP-based column and constraint generation method, respectively. By comparison of these two tables with each other, we notice that, for all combinations of Γ 1 and Γ 2 , except one (Γ 1 = 40 %, Γ 2 = 20 %), the CP model outperforms the MILP one. We also see that the problem is more difficult to solve for medium uncertainty budgets (40 % or 60 %), for both methods. This can be explained by the fact that these uncertainty budgets generate a greater number of scenarios. However, the number of scenarios is not the only difficulty factor, as we can see, the methods are more efficient in solving instances with a large uncertainty budget. For example, instances with an uncertainty budget of 80 % are better solved than those with a budget of 20 %, while the number of possible scenarios are the same.

Conclusion

In this paper, we investigate the robust two-machine flow-shop scheduling problem where the operation processing times are subject to uncertainty. A two-stage robust optimization is used to deal with this uncertainty, where the first stage is devoted to fixing the sequencing decisions whilst the second stage determines the start time of the operations. As a main contribution, we show that under specific conditions the problem can be solved in polynomial time. For the general case, we introduce a constraint programming formulation, which we embed in a column and constraint generation decomposition scheme. This method provides the best results compared to a literature algorithm based on a MILP formulation.

2 and b 3 = c 3 .

 33 Under condition (i): with pj,1 > pj,2 we get c 4 ≤ b 8 , c 5 ≤ b 9 , c 6 ≤ b 10 and c 7 ≤ b 11 ; with pk,1 < pk,2 we get c 8 ≤ b 4 , c 9 ≤ b 5 , c 10 ≤ b 6 and c 11 ≤ b 7 . Under condition (ii): with pk,1 < pj,1 we get c 4 ≤ b 4 , c 5 ≤ b 5 , c 6 ≤ b 6 and c 7 ≤ b 7 ; with pk,1 < pk,2 we get c 8 ≤ b 4 , c 9 ≤ b 5 , c 10 ≤ b 6 and c 11 ≤ b 7 . Under condition (iii): with pj,1 > pj,2 we get c 4 ≤ b 8 , c 5 ≤ b 9 , c 6 ≤ b 10 and c 7 ≤ b 11 ; with pk,2 > pj,2 we get c 8 ≤ b 8 , c 9 ≤ b 9 , c 10 ≤ b 10 and c 11 ≤ b 11 .

Fig. 1 .

 1 Fig. 1. Example 1 and sequence {J1, J2, J3}: worst case under Johnson's schedule, Γ1 = 1, Γ2 = 2.

Table 3 .

 3 Methods performance comparison grouping by instance sizes.

	|J |		CP			MILP
		Solved (%) Avg. time (sec) Avg. gap (%) Solved (%) Avg. time (sec) Avg. gap (%)
	10	100	0.42	-	100	14.7	-
	20	100	0.76	-	100	191.59	-
	50	100	1.47	-	98.75	194.9	0.44
	100	99.58	0.99	0.09	85.5	319.17	0.64
	150	98.92	3.12	0.03	74.67	341.65	0.77
	200	98.83	8.49	0.1	68.92	390.73	0.74
	found (Best known sol. (%)) and the average percentage gap (Avg. gap (%)) of
	non-optimally solved instances (U B method > LB * ), where the gap is computed
	as follows:

Table 4 .

 4 Johnson's rule performance (instances from literature grouping by size).

	|J | Best known sol. (%) Avg. gap (%)
	10	92.58	1.13
	20	92.67	0.4
	50	98.5	0.29
	100	97.67	0.04
	150	89.67	0.04
	200	95.67	0.04

Table 5 .

 5 Methods performance comparison grouping by instance sizes (new instances).

	|J |		CP			MILP
		Solved (%) Avg. time (sec) Avg. gap (%) Solved (%) Avg. time (sec) Avg. gap (%)
	10	100	12.3553	-	100	46.7694	-
	20	80	167.114	2.16398	75	1002.05	2.67698
	50	60	86.8549	2.65432	49	902.686	4.06579
	100	56	310.299	2.49723	45	600.667	5.57048
	150	48	271.321	2.32075	32	667.885	5.97788
	200	54	99.5653	2.68595	30	827.082	6.03535

Table 6 .

 6 Percentage of solved instances according to uncertainty budget Γ = (Γ1, Γ2) for the CP-based column and constraint generation method.

	Γ2	Γ1 20 % 40 % 60 % 80 % 100 %
	20 % 28.33 25 41.67 70	100
	40 % 35 21.67 26.67 81.67 100
	60 % 36.67 28.33 28.33 83.33 100
	80 % 60 71.67 75 88.33 100
	100 % 100	100	100	100	-

Table 7 .

 7 Percentage of solved instances according to uncertainty budget Γ = (Γ1, Γ2) for the MILP-based column and constraint generation method.

	Γ2	Γ1 20 % 40 % 60 % 80 % 100 %
	20 % 26.67 26.67 33.33 58.33 100
	40 % 23.33 18.33 23.33 65	100
	60 % 23.33 21.67 26.67 65	98.33
	80 % 35	35	40	60	100
	100 % 76.67 83.33 91.67 98.33	-