[Module8 Theory] Disjunctive Scheduling

Disjunctive scheduling.

עליך להדביק את הפקודה הזאת במסוף שלך:

הסיסמה להתחברות אל

נא לענות על כל השאלות. שגיאה פנימית ל־{} אין סיומת תקפה. {} כבדה מדי.

שאלה 1: Decomposition

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

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).

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

שאלה 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})?

שאלה 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})?

שאלה 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 always sorted according to their est for all the filtering algorithms.

... are placed in an arbitrary order.

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

שאלה 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:

שאלה 6: Theta-tree -- Remove an activity

Consider the following theta tree:

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

שאלה 7: Filtering rule

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

שאלה 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

שאלה 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])?

שאלה 10: Not-last filtering