1. Decomposing the Disjunctive Constraint.

To implement the decomposition of the Disjunctive constraint, you need first to use the constraint IsLessOrEqualVar.java:

IsLessOrEqualVar(BoolVar b, IntVar x, IntVar y) creates a reified is less or equal constraint \(b <=> (x <= y)\).

This constraint is already provided to you. Based on it, implement the decomposition with reified constraints in the file DisjunctiveBinary.java.

Make sure your implementation passes all the tests in DisjunctiveBinaryTest.java.

2. Modeling the JobShop

Once your DisjunctiveBinary constraint is implemented, you can use it to model the JobShop problem. Part of the implementation is already done within JobShop.java. You still need to implemented the TODO1 using DisjunctiveBinary constraint for each pair of activities to have a working model.

You should now be able to solve tiny instances and pass the test testModel within JobShopTest.java.

However, the search procedure is still naive and quite slow. Let's speed things up!

3. First-Fail Branching on precedences for the JobShop

As seen in the course, for the Jobshop problem, one could perform the search either with start variables or precedence variables. Here, you will base your search procedure on the precedence variables. A precedence variable has the following format: b[m][i][j] with \(m\) a given machine and \(i\) and \(j\) two activities to be executed on the machine \(m\).

For the search, you then need criteria to decide :

• which machine \(m\) to consider first;
• on a given machine \(m\), which non-fixed two activities \(i\) and \(j\) to consider first;
• between the chosen activities \(i\) and \(j\), should we try first b[m][i][j] = true or b[m][j][i] = true ?

For the variable selection, it is well known that the first fail principle is one of the most straightforward CP search strategies that provide relatively good results. You will use it here based on the size of the variables.

Your mission: Implement the search strategy described below in the TODO2 of JobShop.java .

Machine variable \(m\).

Select first the machine m that has the smallest sum of size of the domains of the activities to be executed on it. Given a machine \(m\), let \(startOnMachine(m)\) be the set of activities to be executed on \(m\) and let \(start(i)\) be the domain of the variable representing the start time of the activity \(i\).

You will consider first a machine m that contains at least one non-fixed \(start(i)\) (with \(i \in startOnMachine(m)\)) with the minimum:

\(\Sigma_{i \in startOnMachine(m)} start(i).size()\).

Variable selection \(b_{ij}\).

For a given machine \(m\), consider first a non-fixed variable \(b_{ij}\) (\(i\) and \(j\) in \(startOnMachine(m)\)) with the minimum \(start(i).size() * start(j).size()\).

Value selection.

Once the variable is selected, you will decide which decision to take first between \(b_{ij} = true\) and \(b_{ij} = false\). Often, it is better to try first the value that gives the most flexibility in the remaining domains. Let us define \(slackJIfIStartBeforeJ\) as the number of slots available in \(start(j)\) if the activity \(i\) starts before \(j\) on a given machine: The following figure shows an example.

Assuming that the non-fixed variable \(b_{ij}\) is selected: try first \(b_{ij} = true\) if \(slackJIfIStartBeforeJ > slackIIfJStartBeforeI\).

On the example illustrated above, we will have:

Hint1:

DisjunctiveBinary.java constains useful methods for implementing this search, such as slackIfBefore() and slackIfAfter(). Try to use them as much as possible!

Hint2:

when all precedences variables are already fixed, you can fix makespan and all non-fixed start variables to their respective minimum values. You will get an optimal solution for this problem.

Hint3:

The value heuristic looks a bit complicated? You can opt for a simpler (but less efficient) technique: once you have chosen \(b_{ij}\), branch on the left with \(b_{ij} = false\) and on the right with \(b_{ij} = true\). You can check that you are able to solve the first few instances in testFindOptimality within JobShopTest.java. To solve the remaining ones, implement the value selection described above.

You should now be able to solve the medium and big-size instances in data/jobshop and pass almost all instances from the testFindOptimality test within JobShopTest.java.

To find the best solution from the remaining instances, we will implement more efficient filtering algorithms.

4. The Global Disjunctive Constraint: Detectable Precedence and Not-First-Not-Last.

Read and make sure you understand the implementation of the ThetaTree in ThetaTree.java. Some unit tests are implemented in ThetaTreeTest.java. To make sure you understand it, add a unit test with 4 activities and compare the results with a manual computation.

Within the Disjunctive.java constraint, Detectable Precedence and Not-Last only filter one side of the activities. To get the symmetrical filtering (and transform the Not-Last into a Not-First filtering), implement the mirroring activities trick similarly to Cumulative.java.

Once the mirroring trick is implemented, read the overLoadChecker algorithm within the constraint and compare it to the pseudo-code presented in the videos. Look carefuly at how the operations are done with respect to the ThetaTree. Within Disjunctive, you need to:

• Implement detectablePrecedence. You can check that your implementation is correct with the test testDetectablePrecedence from DisjunctiveTest.java.
• Implement notLast. You can check that your implementation is correct with the test testNotLast

Make sure your implementations pass all the tests in DisjunctiveTest.java.

On JobShop.java, test whether, as expected, each of your new implementations (detectable precedences and not-first-not-last) makes a difference to prune the search tree.

Test, for example, on the instance data/jobshop/medium/jobshop-9-9-0 with 9 jobs, 9 machines, and 81 activities. The number of backtracks will be reduced when you add a new filtering rule or a combination of them to the model.

You should be able to solve almost the instances from the testFindOptimality within JobShopTest.java.

Solving the biggest instances is left as a challenge, and will require some extra effort. You can experiment other heuristics or even implement the Edge-Finding rule if you want to find the best solution for them.