0. Assignment Instructions

Before starting with your Java implementation, read the assignment instructions and grading rules on the course web page: https://user.it.uu.se/~pierref/courses/COCP/assignments/assignment6/assignment6.pdf .

This part of the assignment is on the programming tasks of Modules 6 to 9 of the MiniCP on-line teaching materials.

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, the rules 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 lecture. 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 from DisjunctiveTest.java.

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.

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

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

Before submitting, remember to fetch the latest changes from upstream (the MiniCP GitHub repository).

Note that the original tests of the MiniCP GitHub repository will be run.