[Module8 Theory] Disjunctive Scheduling

Disjunctive scheduling.

Lim denne kommandoen inn i din terminal:

Passord for å koble til er

Vennligst svar på alle spørsmål. Intern feil {} har ikke gyldig filetternavn. {} veier for mye.

Spørsmål 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.

Spørsmål 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})?

Spørsmål 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})?

Spørsmål 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 placed in an arbitrary order.

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

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

Spørsmål 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:

Spørsmål 6: Theta-tree -- Remove an activity

Consider the following theta tree:

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

Spørsmål 7: Filtering rule

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

Spørsmål 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

Spørsmål 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])?

Spørsmål 10: Not-last filtering