Please note: This problem set ended up considerably harder than I had planned.

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.

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.

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?

** Answer ** There's more than one possible answer. One
solution is as follows.

Let C be the collection of tasks.

A * state * consists of a subset A of C and a function
s(T) mapping the tasks T in A into times such that

- The precedence constraints are observed.
- The deadline is observed.
- There are no more than
*m*different tasks assigned to any time*s*. - The schedule has no pointless gaps. That is, if s(T)=u,
then one of the following holds:
- u=0.
- There are
*m*different tasks assigned to time u-1. - There is a task T0 such that there is a constraint T0 < T and such that s(T0)=u-1.

An * operator * on state S extends the set A and the
assignment s(T) as follows:
Let Q be the maximal value of s(T) for T in U, or 0 if U is empty.

Let U := C-A, the set of unassigned tasks. Let V be the subset of U of
all unassigned tasks whose predecessors are all in A.
Let V1 be the subset of V of tasks T such that for every predecessor T0 of T,
s(T0) < Q.

If V1 is non-empty and there are fewer than * m * tasks T in U
such that s(T) = Q, then choose a task T in V1 and set s(T) to be Q.

Otherwise, choose a task T in V and set s(T) to be Q+1.

In either case, add T to A.

In the start state, U is the empty set, and s(T) is the empty assignment.

In the goal state, U is the entire set and s(T) < Z.

Note that the above is not a tree-structured state space. Our solution in Our solution in B will add further constraints to make the state space tree structured, but those would make the description as a state space even more complicated.

B. Write down a non-deterministic algorithm that describes search through the
space in (A).
,p>
** Answer **

PCMS1 (in U : collection of tasks; G : set of precedence constraints; M, Z : integer; out S : assignment of tasks to starting times) begin A := empty set; S := empty set; Q := 0; COUNT := 0; /* number of tasks assigned to TIME */ pick an order O over U; for I := 1 to | U | V := set of all tasks T in U-A such that every predecessor of T under G is in A; V1 := subset of V such that every predecessor T0 of T has S(T) < Q; if V1 is non-empty and COUNT < M then { VQ := set of tasks in A such that S(T)=Q; choose T in V1 such that T is later in O than any TQ in VQ; /* This last condition ensures that the tasks assigned to time Q are added in the order O, and hence that the search is systematic */ COUNT := COUNT+1; } else { choose T in V; Q := Q+1 if Q > Z then fail } endif add the assignment T -> Q to S; add T to A; endfor end

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.

** Answer:**
Maximum branching factor: |C|. Depth: |C|. Size of the state space:
|C|! (Given an assignment, you can enumerate the tasks from beginning to end;
each different assignment gives a different enumeration. Since
there are at most |C| different enumerations, there are at most |C| different
states.)

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

** Answer:** Prune if the ending times exceed Z.

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?

** Answer:**
If the branches are searched in alphabetical order, then the first
solution found in a DFS will be

Time 0: A C G Time 1: D E H Time 2: B F

Proc 1: A [0.0-3.0] Proc 2: B [0.0-2.0]; E [2.0-3.0]. Proc 3: C [0.0-1.0]; idle [1.0-2.0]; D [2.0-4.0].

NOTE: The original problem set was inconsistent here, and gave a time for E from 2.0 to 4.0

Answer the same questions as in problem 1.

A. A * state * consists of a subset A of C, a function
s(T) mapping the tasks T in A into times, and a function p(T) mapping
the tasks T in A into processors such that

- The precedence constraints are observed. T1 < T2 then s(T1) + l(T1) < = s(T2).
- The deadline is observed.
- No processor has more than one task at a time.
- The schedule has no completely pointless gaps. That is, if s(T)=u,
then one of the following holds:
- u=0.
- There is a task T0 such that p(T0)=p(T) and s(T0)+l(T0)=u.
- There is a task T0 such that there is a constraint T0 < T and such that s(T0)+l(T0)=u.

An * operator * on state S extends the set A and the
assignments s(T) and p(T) as follows. Let T be any task not in A
such that all the predecessors of T are in A. Let P be any processor.
Let Q be the maximum of (a) the ending time of any predecessor of T;
(b) the ending time of any task assigned to P. Then add T to A;
set s(T) to be Q; and set p(T) to be P. (Again, this is a non tree-structured
space which we will fix in the pseudo-code.)

The start state has the empty set for A and the empty assignments for s(T) and p(T).

The goal state is one where A=C and where all tasks complete before Z.

** B. Answer: **

This assigns tasks in increasing order of starting time. Among tasks
of equal starting time, it assigns them in increasing index order, to
avoid repeating states.

PCMS2 (in U : collection of tasks; G : set of precedence constraints; L(T) : assignment of lengths to tasks in U; M, Z : integer; out S : assignment of tasks to starting times; P : assignment of tasks to processors) begin A := empty set; S := empty set; P := empty set; for I := 1 to M do E[I] := 0; /* ending time on processor I */ for J := 1 to | U | do { for each task T in A, START[T] := maximum of S(T0) + L(T0) over predecessors T0 of T; EXEC_TIME := minimum over T in A of START[T]; /* first time some task become executable */ FREE_TIME := minimum over P1 of E[P1]; /* first time a processor is free */ E2 := max(EXEC_TIME, FREE_TIME) /* both processor and task are free */ pick a processor P1 for which E[P1] < = E2; choose a task T for which START[T] < = E2; if E2 + L(T) > Z then fail; if there is a T2 such that S(T2) = E2 and T2 > T then fail; /* Enforce order of assigning tasks with equal starting times */ P(T) := P1; S(T) := E2; E[P1] := E2 + L(T) } endfor end

** Answer:**
Maximum branching factor: |C|. Depth: |C|. Size of the state space:
|C|! (given an assignment, you can enumerate the tasks from beginning to end;
each different assignment gives a different enumeration. Since
there are at most |C| different enumerations, there are at most |C| different
states.

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

** Answer:** Prune if the ending times exceed Z.

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?
** Answer: **

Proc 1: A [0.0-3.0] Proc 2: B [0.0-2.0]; idle [1.0-2.0]; D [2.0-4.0]. Proc 3: C [0.0-1.0]; E [2.0-3.0].