Artificial Intelligence: Solution Set 1

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:

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:

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?

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

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

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

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].