Due: Mar. 1.

- M identical processors.
- A set T of tasks.
- A partial ordering on the tasks in T, representing precedence constraints (that is T1 < T2 means that T2 cannot be begun until T1 is complete.)
- For each task t in T, a length l(t).
- An overall deadline D.

For example, suppose M=3, T1 ... T6 have respective lengths 3, 2, 3, 4, 2, and 1, and T2 < T3, T1 < T4, T2 < T4, T3 < T5, and D=8. Then one valid schedule would be the following:

M1: Task T1 from 0 to 3, idle from 3 to 5, task T5 from 5 to 7, idle from 7 to 8 M2: Task T2 from 0 to 2, idle from 2 to 3, task T4 from 3 to 7, idle from 7 to 8 M3: Idle from 0 to 2, Task T3 from 2 to 5, task T6 from 5 to 6.If l(T), M, and D are all small integers, then the problem can be compiled into propositional satisfiability using propositional atoms of the form T_P_K meaning that task T begins on processor P at time K, where K=0 ... D-1. The number of propositional atoms is thus |T| * M * D. Describe the constraints you need for the general case. Illustrate each category of constraint with a sample constraint from the above example. As a function of M, |T|, and D, how many constraints are there (order of magnitude)?

** Answer: **

First category of constraints: Every task is begun on
some processor no later than D-l(T). Thus, for each task T,

T_P1_0 V T_P1_2 V ... V T_P0_(D-l(T)) V T_P1_1 V ... V T_P1_(D-l(T)) V
... T_PM_1 V ... V T_PM_(D-l(T)).

In our example, with T=T4, this would be,

T4_P1_0 V T4_P1_1 V T4_P1_2 V T4_P1_3 V T4_P1_4 V

T4_P2_0 V T4_P2_1 V T4_P2_2 V T4_P2_3 V T4_P2_4 V

T4_P3_0 V T4_P3_1 V T4_P3_2 V T4_P3_3 V T4_P3_4.

In general, there are |T| such constraints, each with O(M*D) disjuncts

Second category of constraints:
A task begins on only one processor at only one time. For each
task T, for each pair of processors P1, P2, for each pair of times I,J,
if either P1 != P2 or I != J, then ~(T_P1_I ^ T_P2^J). In our example
an instance would be ~(T1_P1_0 ^ T1_P3_2). There are
|T|*|M|^{2}*D^{2} such constraints.

Third category of constraints:
A processor runs only one task at one time. Thus, if P is a processor,
T1 and T2 are tasks with T1 != T2 , and K1 and K2 are times with
K1 <= K2 < K1 + l(T1) then ~(T1_P_K1 ^ T2_P_K2). An instance
in our example would be ~(T1_P1_0 ^ T2_P1_0).
Number of constraints:
|T|^{2}*M*D^{2}. (More precisely,
|T|^{2}*M*D * max_{T} l(T). The difference may be significant
if all of the l(T) are much smaller than D.)

Fourth category of constraints: Precedence constraints. Thus,
if T1 and T2 are any pair of tasks where T1 < T2, P1 and P2 are two
processes (either equal or different), and K1 and K2 are times such
that K2 < K1 + l(T1), then ~(T1_P1_K1 ^ T2_P1^K2). An instance in
our example would be ~(T1_P1_1 ^ T4_P1_2). The number of such contraints
is O(|T|^{2} * M^{2} * D^{2}). (More exactly,
O(C * M^{2} * D^{2}), where C is the number of precedence
constraints, which is generally much smaller than T^{2}.)

In counting the total number of constraints, the dominating term is
either the second or the fourth category, depending whether C or T is
larger. O(max(C,T) *M^{2} * D^{2})

p(X,Y) --- Predicate. X is a parent of Y.Express the following statements in L.

fa(X,Y) --- Predicate. X is a father of Y.

mo(X,Y) --- Predicate. X is a mother of Y.

fe(X) --- Predicate. X is female

a(X) --- Predicate. X is alive.

o(X) --- Predicate. X is an orphan.

s,a,b --- Constant. Sarah, Andy, Bob.

- 1. A mother is a female parent.
- 2. A father is a parent who is not female.
- 3. An orphan is someone with no living parents.
- 4. Sarah is not an orphan.
- 5. Sarah either has a living father or a living mother.
- 6. Everyone has a father and a mother.

** Answer:**

- 1. forall(X,Y) mo(X,Y) <=> fe(X) ^ p(X,Y).
- 2. forall(X,Y) fa(X,Y) <=> ~fe(X) ^ p(X,Y).
- 3. forall(X) o(X) <=> ~(exists (Y) p(Y,X) ^ a(Y)).
- 4. ~o(s).
- 5. (exists(X) a(X) ^ fa(X,s)) V (exists(X) a(X) ^ mo(X,s)).
- 6. forall(X) exists(Y,Z) fa(Y,X) ^ mo(Z,X).