Information

Deadline Keine Frist
Abgabenlimit No limitation

Einloggen

[Module8 Theory] Disjunctive Scheduling

Disjunctive scheduling.


Question 1: Decomposition

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

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].
ect_q2

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].
ect_q2

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

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

They will form a tree like this:

insertion

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:

insertion

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?

insertion
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].
insertion

Does the overload-checker rule detect infeasibility?

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].
insertion

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

Question 10: Not-last 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 5 and the domain of start(B) is [0..6],
  • C has a duration of 4 and the domain of start(C) is [0..6], and
  • D has a duration of 2 and the domain of start(D) is [3..5].
insertion

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