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:
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:
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?
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.