[Part8 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 obtains the strongest filtering for 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 pair of activities i,j ("<<" is the precedence relation)

Question 2: Earliest completion time

Given a set of activities {A,B,C}:

a1 has a duration 2 and the domain of start(A)=[2..3],

a2 has a duration 3 and the domain of start(B)=[4..10], and

a3 has a duration 4 and the domain of start(C)=[2..5].

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

Question 3: Latest completion time

Given a set of activities {A,B,C}:

A has a duration 2 and the domain of start(A)=[2..3],

B has a duration 3 and the domain of start(B)=[4..10], and

C has a duration 4 and the domain of start(C)=[2..5].

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

Question 4: Theta-tree intialization

In a theta-tree, the activities initialize with n activities (that are not necessarily inserted yet) are given a position in the leaf nodes such that activities:

are sorted but according to 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), which must be inserted in a theta tree:

A(est: 0, duration: 5);

B(est: 1, duration: 7);

C(est: 3, duration 5);

D(est: 5, duration: 8).

It will form a tree like this:

You have to 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 ectA being the earliest completion time of the node A in the theta-tree.'

Question 6: Theta-tree - remove an activity

Consider the following theta tree:

What will be \(ect_G\) if one removes the activity D?

Question 7: Filtering rule

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

Question 8: Overload checker

Given the set of activities {A,B,C,D,E} such that: A has a duration 4 and the domain of start(A)=[0..13], B has a duration 1 and the domain of start(B)=[0..13], C has a duration 3 and the domain of start(C)=[0..5], D has a duration 4 and the domain of start(D)=[2..6], and E has a duration 4 and the domain of start(E)=[4..5].

Does the overload checker rule detect infeasibility?

yes

Question 9: Detectable precedence based filtering

Consider the set of activities {A,B,C,D} such that: A has a duration 1 and the domain of start(A)=[0..13], B has a duration 3 and the domain of start(B)=[0..4], C has a duration 4 and the domain of start(C)=[2..6], and D has a duration 2 and the domain of start(D)=[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 rule based filtering

Consider the set of activities {A,B,C,D} such that: a1 has a duration 1 and the domain of start(A)=[0..13], a2 has a duration 5 and the domain of start(B)=[0..6], a3 has a duration 4 and the domain of start(C)=[0..6], and a4 has a duration 2 and the domain of start(D)=[3..5].

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

Deadline	No deadline
Submission limit	2 submissions every 1 hour(s)

Information

Sign in