Part 10: Disjunctive Scheduling

We ask you not to publish your solutions on a public repository. The instructors interested to get the source-code of the solutions can contact us.

Theoretical questions

Decomposing the Disjunctive Constraint

Your task is to make the disjunctive constraint more efficient than using the cumulative constraint with unary capacity.

  • Implement the constraint IsLessOrEqualVar.java for the reification b iff x <= y. This one will be useful implementing the decomposition for the disjunctive constraint..
  • Test your implementation in IsLessOrEqualVarTest.java.
  • Implement the decompostion with reified constraint for the Disjunctive.java. `
  • Test if (as expected) this decomposition prunes more than the formulation with the TimeTable filtering for the cumulative constraint. Observe on the JobShop.java problem if the number of backtracks is reduced with the decomposition instead of the formulation with the cumulative. Test for instance on the small instance data/jobshop/sascha/jobshop-4-4-2 with 4 jobs, 4 machines, 16 activities.

The Global Disjunctive Constraint (Overload Checker, Detectable Precedence and Not-First-Not-Last

  • Read and make sure you understand the implementation 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.
  • The overlad-checker, detectable precedences, not-first, edge-finding only filter one side of the activities. To get the symmetrical filtering implement the mirroring activities trick similarly to Cumulative.java.
  • Implement the overload-checker in Disjunctive.java
  • The overload-checker should already make a big difference to prune the search tree. Make sure that larger-job-shop instances are now accessible for instance the data/jobshop/sascha/jobshop-6-6-0 should now become easy to solve.
  • Implement the detectable-precedence in Disjunctive.java
  • Implement the not-first-not last in Disjunctive.java
  • Make sure you pass the tests DisjunctiveTest.java
  • (optional for a bonus) Implement the edge-finding in Disjunctive.java (you will also need to implement the ThetaLambdaTree data-structure).