Artificial Intelligence: Problem Set 1

Assigned: Jan. 16
Due: Jan. 30

The following scheduling problem is known as PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING. You are given a collection of tasks T, each of which has a length l(T); a set of precedence constraints "X < Y" on the tasks; a set of m identical processors; and a deadline Z . The problem is to assign to each task X in T, a processor p(X) and a time slice from start time s(X) and end time e(X) = s(X) + l(X) such that:

• (a.) No processor is ever assigned to run two tasks at once. That is, if p(X) = p(Y) and X != Y then either e(X) < = s(Y) or e(Y) < = s(X).
• (b.) The precedence constraints are observed. That is, if "X < Y" is a precedence constraint, then e(X) < = s(Y).
• (c.) The deadline is met. That is, for all X, e(X) < = Z.

Problem 1

Consider the case where all the tasks have unit length l(T)=1. For example, suppose that T contains eight tasks labelled A-H; that m=3; that Z=3; and that the precedence constraints are A < B; A < F; C < D; D < F; E < F; G < H; H < F.

Then one possible schedule is

```Proc 1:  A E B
Proc 2:  C D F
Proc 3:  G H
```

For this problem, it suffices to specify the start times s(T) for all the tasks. Which particular processor gets which task at any given time doesn't matter, as long as no particular start time is assigned to more than m different tasks.

```Proc 1: A D
Proc 2: C H B
Proc 3: G E F
```

Therefore, in this problem, we can take a "solution" to be just an assignment of start times s(T), and reword condition (a) above as follows:

• (a'.) For any time q, there are at most m different tasks T for which s(T) = q.
Conditions (b) and (c) remain as above.

Thus, both of the above solutions reduce to the same assignment of start times: s(A)=s(C)=s(G)=1; s(D)=s(H)=s(E)=2; s(B)=s(F)=3.

A. Show how this problem can be formulated as in terms of state space search. What are the states? What are the operators? What is the start state? What is a goal state?

B. Write down a non-deterministic algorithm that describes search through the space in (A).

C. What is the maximum branching factor of the state space in (A)? What is the depth of the state space? Give an upper bound on the size of the state space.

D. Describe one pruning criterion for search in this space.

E. Impose an order on the branches in (A). Given that order, what is the first solution that a depth-first search will find to the given problem?

Problem 2

Same as problem 1, except that now the length of task T, l(T), and the deadline Z may be any floating point numbers. In this new problem, the processor assignment that are made at earlier times affect those that can be made a later time. For instance suppose we have five tasks A-E with lengths l(A) = 3.0; l(B) = 2.0; l(C) = 1.0; l(D) = 2.0; l(E) = 1.0; precedence constraints B < D, B < E; and deadline Z=4.0. Then the following is a solution
```Proc 1: A [0.0-3.0]
Proc 2: B [0.0-2.0]; E [2.0-4.0].
Proc 3: C [0.0-1.0]; idle [1.0-2.0]; D [2.0-4.0].
```

Answer the same questions as in problem 1.