Benchmark instances

Abstract and 1. Introduction

2. Mixed integer and constraint programming models

   2.1 Mixed-integer linear programming model

   2.2 Constraint Programming model

3. Constructive Heuristics

4. Benchmark instances

5. Numerical experiments

   5.1 Experiments with the constructive heuristics

   5.2 Solving the proposed models with a commercial solver

6. Conclusions and References

4 Benchmark instances

Tractability of the introduced models and performance of the proposed constructive heuristics will be evaluated with the 50 large-sized instances proposed in [4], that were introduced for the FJS scheduling problem with sequence flexibility but without learning effect. In addition to these large-sized instances, a new set with 60 smaller instances, using the generator described in [4], was generated. Instances whose name starts with “Y” correspond to instances in which DAGs that represent the operations’ precedences are Y-shaped (like the DAG in the top of

Figure 1); while instances whose name starts with “DA” correspond to instances in which DAGs that represent the operations precedences are arbitrary DAGs (like the DAG in the bottom of Figure 1). The former will be called instances of Y-type and the latter will be called instances of DA-type from now on.

is also between 0 and 1 and represent the degree of the instance sequencing flexibility. The larger ω1, the larger the search space and, therefore, the more difficult the instance. (Of course, any other type of average could be used in the definition of ω1.)

is between 0 and 1. The closer to 1, the larger the search space and, therefore, the harder the instance.

In the small-sized instances of Table 1, the number of binary variables of the MILP models and the number of interval variables of the CP models go up to almost 1,000; while in both models the number of constraints goes up to 13,000. On the other hand, in the large-sized instances of Table 2, the number of binary variables of the MILP models and the number of interval variables of the CP models go up to almost 73,000; while in both models the number of constraints goes up to 4,000,000. Moreover, for each instance, the number of binary variables in its MILP model is very similar to the number of interval variables in its CP model and the two models also have a very similar number of constraints.