## Problem Set 2

Assigned: Feb. 15.
Due: Mar. 1.

### Problem 1

The MULTIPROCESSOR PRECEDENCE CONTRAINED SCHEDULING problem is defined as follows: You are given:
• 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).
The object is to give a schedule for T that observes all these constraints. A schedule is an assignment of a processor and a starting time to each task such that each processor is running at most one task at a time; each task runs for the specified length; and the precedence constraints are observed.

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

### Problem 2

Consider a first-order language L over a universe of people with the following primitives:
p(X,Y) --- Predicate. X is a parent of Y.
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.
Express the following statements in L.
• 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.