Comparing Mixed-Integer Programming and Constraint Programming Models for the Hybrid Flow Shop Scheduling Problem with Dedicated Machines

In the academic literature, few exact methods have been employed to solve the HFS with dedicated machines.

Riane et al. [8] developed a dynamic program for the case of two stages, where two dedicated machines are in the second stage. The goal is to minimize the maximum completion time. The results show that the developed dynamic program is baffled for problems of more than 15 jobs.

Moseiov and Sarig [9] developed an integer programming model for the two-stage HFS with m dedicated machines and due dates. Besbes et al. [10] considered a two-stage HFS with parallel-dedicated machines in both stages. They proposed a mixed-integer linear programming model to minimize the maximum completion time among all jobs. This model is based on the mathematical formulation of Guinet et al. [11] and is solved by Cplex. The authors proved that Cplex can obtain an optimal solution for only small sizes. With the objective of minimizing the makespan, Hadda et al. [12] also proposed a branch and bound algorithm for the case of m dedicated machines in the second stage. The authors used an elimination rule to improve even more the performance of their algorithm. The experimental results demonstrated that many big size instances are solved, and the elimination rule has contributed to discard up to 50% of the nodes. Chikhi et al. [13] studied the case of the two-stage robotic flow shop scheduling problem with the objective of minimizing the makespan. There are two dedicated machines in stage 1 and only one machine in stage 2. Depending on the job type, each job is firstly processed on a dedicated machine and is then transported by a robot, to be processed on the single machine. The authors developed a mixed-integer programming model, which is using valid inequalities based on a set of lower bounds. Nabli et al. [14] proposed two mixed-integer programming models (M1 and M2) for solving the hybrid flow shop scheduling problem with parallel machines in the first stage and two dedicated machines in the second stage. The first model (M1) is based on time indexed variables, while the second model (M2) is based on ordering variables. In their paper, the authors compared the computational time performances of M1 and M2, and they found that M2 (linear ordering variables) is faster than M1 (time index variables).

Other studies have developed heuristic and metaheuristic approaches for solving the hybrid flow shop with dedicated machines. For example, Lin et al. [3] developed a heuristic approach with combined rules for the two-stage HFS with setup times and due dates in a label sticker manufacturing company. The objective was to minimize the weighted maximum tardiness of jobs. Oguz et al. [15] developed a heuristic approach, which is based on the Johnson’s algorithm [16] for minimizing the makespan.

Yang [17] proposed an optimal solution for the case where the processing times on the common machine are identical. The aim is to minimize the total completion time. Besbes et al. [10] considered respectively s and m dedicated machines in stages one and two. The authors developed two approaches. The first approach is based on the Johnson’s algorithm [16], while the second one consists of a genetic algorithm. Huang and Lin [18] considered the case of two stages with setup time where a single machine is in the first stage and two dedicated machines are in the second stage. Their aim is to obtain a schedule that has the minimum makespan. They investigated the case where the processing schedules of the two types of jobs are fixed. To solve the problem, the authors proposed a polynomial-time dynamic programming algorithm.

Nabli et al. [19] studied a two-stage hybrid flow shop with dedicated machines and release dates. There are two parallel machines in stage one and two dedicated machines in stage two. The objective is to minimize the makespan. To solve the problem, the authors proposed three heuristic and two lower bounds. Harbaoui et al. [20] compared the performance of two metaheuristic: a tabu search and a genetic algorithm for the no-wait hybrid flow shop problem with dedicated machines under makespan minimization. The authors [21] studied a hybrid flow shop with dedicated machines, sequence dependent setup and time lags, and they developed a genetic algorithm to minimize the makespan.

Dealing with the minimization of the makespan for the case of m dedicated machines in the second stage, many heuristics were also developed in the references [22, 23].

For the case of more than two stages, Riane et al. [2] considered a three-stage HFS with two dedicated machines in the second stage and one single machine in stages one and three. They developed a dynamic programming-based heuristic and a branch and bound based heuristic. Ouled Bedhief et al. [1] studied the case of three-stage HFS with dedicated machines in the third stage. The authors studied a set of cases and proposed a heuristic approach for the general problem that is denoted by IH-DP. For the same problem, Ouled Bedhief et al. [24] proposed an improved genetic algorithm. Many computational experiments demonstrated its efficiency with a mean percentage deviation from the lower bound that does not exceed 0.5%, and a very reasonable computational time.

The literature review shows that most of the available studies on the hybrid flow shop with dedicated machines are focused on the development of heuristic approaches. However, few exact methods have been employed to solve this kind of problems.

Furthermore, most of these exact methods are mixed-integer linear programming models. To the best of our knowledge, there is no report on constraint programming (CP) models for the HFS scheduling problem with dedicated machines.

Based on logic programming, the constraint programming is, also, an efficient exact method that has been widely used for solving industrial scheduling problems [25-27].

It is further applied for solving many other types of scheduling problems such as: scheduling problems in operating theatres [28] or medical resident scheduling problems [29].

In this paper, we compare a constraint programming model (CP) to a mixed-integer programming model (MIP) for the $2 F H D\left|1,2, r_{j}\right| C_{\max }$ scheduling problem.

In this section, we propose a mixed-integer programming model for the $2 F H D\left|1,2, r_{j}\right| C_{\max }$ problem. This MIP model is composed only of linear equations. The goal is to minimize the makespan (i.e. maximum completion time of jobs).

At the beginning, we define the decision variables of our MIP model as follows:

Binary variables:

• X_0j=1 if j is the first job processed on M_c, 0 otherwise; $j \in J$;
• X_ij=1 if job i is scheduled before job j on M_c, 0 otherwise; $i, j \in J$ and $i \neq j$;
• $X_{0 j}^{(k)}=1$ if j is the first job processed on D_k, 0 otherwise; $j \in J_{k}, k=\{1,2\}$;
• $X_{i j}^{(k)}=1$ if job i is scheduled before job j on D_k, 0 otherwise; $i, j \in J_{k}, k=\{1,2\}$ and $i \neq j$;

Continuous variables:

• C_j: Completion time of job j on $M_{c}, j \in J$;
• $C_{j}^{(k)}$: Completion time of job j on $D_{k}, j \in J_{k}, k=\{1,2\}$;

Our proposed MIP model can now be given as:

Objective function: minC_max.

Subject to:

$\sum_{i=1}^{n} X_{0 j}=1 j \in J$               (1)

$\sum_{i=0, i \neq j}^{n} X_{i j}=1 \quad j \in J$               (2)

$\sum_{i=1, i \neq j}^{n} X_{j i} \leq 1 j \in J$                 (3)

$\sum_{j=1}^{n_{k}} X_{0 j}^{(k)}=1 j \in J_{k} ; k \in\{1,2\}$                (4)

$\sum_{i=0, i \neq j}^{n_{k}} X_{i j}^{(k)}=1 j \in J_{k} ; k \in\{1,2\}$               (5)

$\sum_{i=1, i \neq i}^{n_{k}} X_{j i}^{(k)} \leq 1 j \in J_{k} ; k \in\{1,2\}$                    (6)

$C_{j} \geq r_{j}+a_{j} j \in J$                 (7)

$C_{i}+a_{j}+\left(X_{i j}-1\right) M \leq C_{j} j \in J$                     (8)

$C_{j}^{(k)} \geq C_{j}+b_{j k} j \in J_{k} ; k \in\{1,2\}$                   (9)

$C_{i}^{(k)}+b_{j k}+\left(X_{i j}^{(k)}-1\right) M \leq C_{j}^{(k)} i, j \in J_{k} ; i \neq$$j ; k \in\{1,2\}$                 (10)

$C_{i} \leq C_{j}+M\left(1-X_{i j}^{(k)}\right) i, j \in J_{k} ; k \in\{1,2\}$                 (11)

$C_{\max } \geq C_{j}^{(k)} j \in J_{k} ; k \in\{1,2\}$                    (12)

$C_{j} \geq 0 j \in J$                                         (13)

$C_{j}^{(k)} \geq 0 j \in J_{k} ; k \in\{1,2\}$                             (14)

$X_{i j} \in\{0,1\} i, j \in J$                        (15)

$X_{i j}^{(k)} \in\{0,1\} i, j \in J_{k} ; k \in\{1,2\}$                         (16)

$X_{0 j} \in\{0,1\} j \in J$                          (17)

$X_{0 j}^{(k)} \in\{0,1\}$                                (18)

In this mixed-integer programming model, the objective function is to minimize the maximum completion time C_max among all jobs.

M is a sufficiently large number (an upper bound on the completion time on both stage 1 (Constraint set (8)) and stage 2 (Constraint set (10)). 

Constraint set (1) (resp. (4)) ensures that every job-sequence on M_c (resp. D_k) begins with exactly one job. Constraint set (2) (resp. (5)) assures that every job should have a predecessor, otherwise, it is the first job processed on M_c (resp. D_k). Constraint sets (3) and (6) state that every job must have at most only one direct successor. Constraint set (7) insures the respect of the release dates of jobs. Constraint set (8) (resp. (10)) states that no job can be processed on M_c (resp. D_k) before the completion time of the current job. Constraint set (9) ensures that the second operation can only begin when the first one is completed.

Constraint set (11) guarantees the obtaining of permutation solutions. In fact, a permutation schedule is defined when the processing order of jobs on the machines is the same.

The maximum completion time is defined through constraint set (12). Finally, constraint sets from (13) … to (18) define the decision variables of our model.

In general, the efficiency of mixed-integer programming is ostensibly not guaranteed, especially, when the problem size increases. However, constraint programming (CP) provides suitable modeling techniques to optimize several complex problems, which are most often qualified by logical and non-linear constraints.

Table 1. Results analysis for MIP model (Cplex solver)

$\boldsymbol{r}_{j} \in[\mathbf{0}, \mathbf{1 0 0}]$
	n=5	n=6	n=7	n=8	n=9	n=10
CLASS 1	0.02	2.94	4.54	4.66	7200	-
CLASS 2	0.03	3.66	5.90	7.27	7920	-
CLASS 3	2.00	2.49	5.71	9.04	-	-
CLASS 4	3.70	4.74	4.90	8.60	-	-
$\boldsymbol{r}_{j} \in[\mathbf{0}, \boldsymbol{n} * \mathbf{1 0}]$
	n=5	n=6	n=7	n=8	n=9	n=10
CLASS 1	0.02	0.32	1.53	2.90	10800	-
CLASS 2	0.04	0.90	2.42	3.06	11520	-
CLASS 3	0.03	0.95	1.30	3.37	-	-
CLASS 4	0.34	1.22	4.59	9.03	-	-

1.png

Figure 1. Average CPU time of Cplex for $r_{j} \in[0,100]$

2.png

Figure 2. Average CPU time of CP Optimizer for $r_{j} \in[0 . n * 10]$

Table 2. Results analysis for CP model (CP Optimizer)

$r_{j} \in[\mathbf{0 . 1 0 0}]$
	n=50	n=100	n=150	n=250	n=350	n=450
CLASS 1	0.03	1.50	4.37	19.1	59.9	201
CLASS 2	0.04	1.57	4.71	18.6	64.3	196
CLASS 3	0.03	1.28	4.11	15.6	112	204
CLASS 4	0.03	1.60	4.96	22.3	163	-
$\boldsymbol{r}_{j} \in[\mathbf{0} . \boldsymbol{n} * \mathbf{1 0}]$
	n=50	n=100	n=150	n=250	n=350	n=450
CLASS 1	0.02	0.75	1.54	3.40	17.2	45.6
CLASS 2	0.02	0.63	1.07	3.15	19.9	57.8
CLASS 3	0.03	0.71	1.53	4.52	25.5	80.7
CLASS 4	0.02	0.83	1.42	7.56	16.3	61.9

3.png

Figure 3. Average CPU time of CP Optimizer for $r_{j} \in[0,100]$

4.png

Figure 4. Average CPU time of CP Optimizer for $r_{j} \in[0 . n * 10]$

Considering the results per problem class, we can see from Table 2 and from Figures 3 and 4 that average CPU time of CP Optimizer increases with the problem size. But it is, on average, similar from one problem class to another. This is to say that the performance of CP Optimizer for obtaining an optimal solution for the HFS with dedicated machines is not very sensitive to data variations and their influences on machine workloads.

These results may be explained by two factors:

- The first factor is that the number of variables in MIP model increases more quickly than in CP model.

- The second factor consists in constraint propagation along with domain filtering, which are fundamental in constraint programming strategy. Indeed, the propagation phase can reduce the size of the search space and avoid exploring an exponential size space. In the initial constraint propagation stage, the CP engine uses domain filtering techniques to eliminate infeasible values from the domains of variables. A filtering algorithm is applied to make the CP model arc consistent. This means, for any value of a given variable in a constraint, there exists at least a value for the other variables to satisfy this constraint. All constraints must be filtered, and filtering is repeated until no domain is changed. This reduces considerably the search space.

Consequently, as an advantage, CP model allows various constraints to be taken into consideration, because the solver takes parcels out of the search space. Contrariwise, the MIP model does not let many complicated constraints which are found in real life to be integrated without convoluting the model since it becomes difficult to build, generalize and solve.

However, constraint programming remains a tree-based searching method. On some large problem sizes, this tree traversal becomes very combinatorial and penalizing in terms of execution time.