## Solving Flexible Job Shop Scheduling Problems
This benchmark is known as Flexible Job Shop Scheduling Problem (FJSSP) We'll reuse Quintiq description here:
In order to try CP Optimizer on these benchmarks we set up a very simple experimentation protocol that can be reproduced by any user of CP Optimizer 12.6: - we used the simple FJSSP model provided with CP Optimizer since May 2008
- we run this model for each instance of the benchmark, using CP Optimizer's with default settings and 3 different time limits of 15 min, 3 hour, and 24 hour
- the experiments were performed on a Blade-Linux machine HS22 Type 7870, Processor Xeon 4C X5570, 2.93GHz, 12GB RAM with CP Optimizer using 4 parallel workers
The model we use for FJSSP is given below in OPL. We actually used the C++version in our experiment but performance is quite similar whatever API is used (C++, Java, .NET or OPL). using CP;
The benchmark consists of 7 groups of instances and contains 313 instances in all. Among these 313 instances, 119 are referenced as being still open on the Quin
Here is the meaning of the columns: - %Opt: percentage of overall instances for which CP Optimizer 12.6 could prove optimality
- #ImprLB: number of open instances for which CP Optimizer 12.6 improved the makespan lower bound compared with the state-of-the-art (including Quintiq results)
- #ImprUB: number of open instances for which CP Optimizer 12.6 improved the makespan upper bound compared with the state-of-the-art (including Quintiq results)
- #NewClosed: number of open instances in the state-of-the-art (including Quintiq results) that are now closed thanks to CP Optimizer 12.6 results
We see that within a 15mn time limit per instance, CP Optimizer 12.6 manages to close more than one third of the still open instances (52 instances). With a longer time-limit, CP Optimizer 12.6 is able to close more than half of the 119 open instances. These results are achieved using a very basic model distributed with CP Optimizer since 2008, and no parameter tuning. Thus, they are easily reproducible by any of our users. Clearly, CP Optimizer 12.6 performs much better than the previous release (12.5.1) on those benchmarks. The main reason is that version 12.6 uses so called failure-directed search. Failure-directed search is a brand new way to solve scheduling problems and provide optimality proofs. CP Optimizer automatically starts failure-directed search when other search strategies are no longer successful. The goal of the failure-directed search is not to find a solution but to prove optimality by exploring the whole search space. The name "failure-directed search" comes from the fact that it first explores (and eliminates) assignments that are most likely to fail. It is a quite successful strategy, especially for problems where the main complexity comes from cumulative or disjunctive resources. Here is a file with the complete CP Optimizer 12.6 results and the updated best bounds on each instance. We use the same references as in Quintiq's page. We also list below the 69 instances closed thanks to CP Optimizer 12.6 . For each instance we provide the value of the optimal makespan.
Brandimarte Mk02 26
A direct comparison between Quintiq Optimizer and CP Optimizer is difficult to perform because (1) the Quintiq page does not describe the experimental protocol and (2) Quintiq results are only available for the instances that were improved by Quintiq Optimizer. Nevertheless, on these instances improved by Quintiq optimizer, CP Optimizer is worse than Quintiq optimizer on 11 instances and is better on 24 instances.
Philippe Laborie and Petr Vilim |