Experiments with the constructive heuristics

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

5.1 Experiments with the constructive heuristics

In this subsection, we evaluate the two constructive heuristics. Tables 3 and 4 show the results. For each instance, the lowest makespan, among the solutions found by the two constructive heuristics, is shown in bold. In all instances, the constructive heuristics take less than 0.001 seconds of CPU time to build a solution. Considering the small-sized instances in Table 3, depending on the instance, there may be a significant difference between the solutions found by one and the other constructive heuristic. However, on average, the two heuristics behave basically indistinguishably. For the large-sized instances in Table 4 the comparison is a bit different: there is a clear advantage of the EST constructive heuristic in the DA-type instances, while on the other hand there is a clear advantage of the ECT constructive heuristic in the Y-type instances. It is worth noting that in the small-sized instances there is no clear differentiation between the sequencing flexibility sparsity measure ω1 of the DA-type and the Y-type instances (see Table 1). On the other hand, in the large-sized instances, Y-type instances have a value of ω1 clearly lower than the value of ω1 of DA-type instances. Summarizing, as mentioned at the end of Section 3, the greedy strategy of ECT of choosing the operation/machine pair that terminates first seems to compensate in situations where, because there is already little sequencing flexibility, the greedy choice does not cause a large decrease of the search space.