[Module8 Theory] Disjunctive Scheduling

Disjunctive scheduling.

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Internal error {} has not a valid extension. {} is too heavy.

Question 1: Decomposition

Which approach yields the strongest filtering for \(n\) activities on a disjunctive resource?

Use a (cumulative) time-table filtering with capacity 1.

Use \(n^2\) reified precedence constraints of the type i << j or i >> j for all pairs i, j of activities (where "<<" is the precedence relation).

Question 2: Earliest completion time

Consider a set of activities {A,B,C} where:

A has a duration of 2 and the domain of start(A) is [2..3],
B has a duration of 3 and the domain of start(B) is [4..10], and
C has a duration of 4 and the domain of start(C) is [2..5].

What is ect({A,B,C})?

Question 3: Latest completion time

Consider a set of activities {A,B,C} where:

A has a duration of 2 and the domain of start(A) is [2..3],
B has a duration of 3 and the domain of start(B) is [4..10], and
C has a duration of 4 and the domain of start(C) is [2..5].

What is lct({A,B,C})?

Question 4: Theta-tree -- Initialization

In an initialized theta tree, the activities (are not necessarily inserted yet and) are given a position in the leaf nodes such that they ...

... are sorted but according to a criterion that depends on the filtering algorithm.

... are placed in an arbitrary order.

... are always sorted according to their est for all the filtering algorithms.

Question 5: Theta-tree -- Global ect

Consider four activities {A, B, C, D} that must be inserted into a theta tree:

A(est: 0, duration: 5);
B(est: 1, duration: 7);
C(est: 3, duration: 5);
D(est: 5, duration: 8).

They will form a tree like this:

Enter the content of the theta tree in the following form: \(ect_A,ect_B,ect_C,ect_D,ect_E,ect_F,ect_G\) with \(ect_A\) being the earliest completion time of node A of the theta tree:

Question 6: Theta-tree -- Remove an activity

Consider the following theta tree:

What will \(ect_G\) be after removal of activity D?

Question 7: Filtering rule

Which of the following filtering rules corresponds to the "Not Last" reasoning?

Question 8: Overload checker

Consider the set of activities {A,B,C,D,E} where:

A has a duration of 4 and the domain of start(A) is [0..13],
B has a duration of 1 and the domain of start(B) is [0..13],
C has a duration of 3 and the domain of start(C) is [0..5],
D has a duration of 4 and the domain of start(D) is [2..6], and
E has a duration of 4 and the domain of start(E) is [4..5].

Does the overload-checker rule detect infeasibility?

yes

Question 9: Detectable-precedence filtering

Consider the set of activities {A,B,C,D} where:

A has a duration of 1 and the domain of start(A) is [0..13],
B has a duration of 3 and the domain of start(B) is [0..4],
C has a duration of 4 and the domain of start(C) is [2..6], and
D has a duration of 2 and the domain of start(D) is [3..5].

What is the new domain of start(C) after a detectable-precedence filtering (in the form of [min..max])?

Question 10: Not-last filtering