CS787 Advanced Algorithms Topic Scheduling with Precedence Constraints 17 5 1 Motivation 17 5 1 1 Objective Presenter s James Jolly Pratima Kolan Consider the problem of scheduling a collection of weighted tasks with precedence constraints where the objective is produce a schedule that minimizes the sum of their weighted completion times Generating an optimal single machine schedule for this task is NP Hard We discuss an algorithm that approximates the optimal schedule in polynomial time within a factor of 2 We then discuss a second approximation that converts a single machine schedule into a multi machine schedule in polynomial time 17 5 1 2 A Precedence Graph as Tasks Waiting for Input Many scheduling tasks in databases and operating systems involve reasoning about tasks that depend on the output of other tasks A collection of these related tasks can be thought of as a graph where each task is represented by a vertex and each depedency or precedence constraint is represented by an edge Figure 17 5 1 1 Example Precedence Graph Often in addition to precedence constraints there is some notion of task priority A system scheduling a collection of tasks might aim to run the most important ones first while still obeying the precedence constraints between them 1 This problem can be cast as finding a schedule that minimizes the sum of weighted completion times across tasks where each weight represents the priority of its respective task 17 5 2 Formalization We are given a collection of n tasks V t1 t2 tn each with its own processing time pi and weight wi Let ci be the time ti finished note that pi ci Our objective is to find a feasible schedule that minimizes V n X wi ci under precedence i 1 constraints A feasible schedule is a list of tasks V ht1 t2 tn i ordered from the first scheduled to the last scheduled that does not violate precedence constraints We represent precedence constraints using a graph G V E where E contains the dependencies between tasks in V We denote the dependency of task j on the output of task i as i j read i preceeds j Note that the addition of precedence constraints to the weighted completion time problem have potential to increase for a given V 17 5 3 Single Machine Scheduling With Precedence This problem is NP Hard when arbitrary precedence constraints are present Here we present a 2 approximation discovered by Chekuri that runs in polynomial time 1 17 5 3 1 Rank of a Sub DAG As in many other approximation algorithms here it is useful to order the inputs using a heuristic We define the rank of a job ri as ri pi wi We may also wish to reason about the rank the of collection of tasks T t1 t2 tk defined as R T k X R T pi i 1 k X wi i 1 Rank gives us some notion of which task or group of tasks we should schedule first We also need to consider precedence constraints in this problem and will need an additional construct to take them into account 2 17 5 3 2 Precedence Closed Sub DAG A sub DAG is precedence closed if all its tasks only depend on other tasks within itself For any vertex i V let Gi denote the sub DAG of G induced by the set of vertices preceding i More formally we define a sub DAG G0 of G to be precedence closed when ti G0 Gi G0 Precedence closed sub DAGs are important as we can schedule them by only considering the tasks inside them Scheduling a sub DAG with precedence constraints can be done in polynomial time using a topological sort linear time in terms of the sum of edges and nodes 17 5 3 3 G The Minimum Rank Precedence Closed Sub DAG To minimize V we need to schedule tasks or groups of tasks in order of their rank while still satisfying precedence constraints To do this we need a fast way to identify the precedence closed group with lowest rank in the DAG G You might be able to guess what comes next scheduling this group removing it from the graph and then finding the group with next lowest rank Chekuri tells us that there exists an optimal schedule for G in which an optimal schedul for G occurs as a segment that starts at time 0 For an arbitrary graph there are many possible groupings of nodes 2 V many of which are not precedence closed Thankfully Chekuri has also devised a clever min cut problem formulation that finds G in polynomial time 17 5 3 4 2 approximation Proof In this algorithm each precedence closed subgraph that does not contain a subgraph of lesser rank is subproblem We can schedule the nodes in this subgraph using any arbitrary method that obeys precedence constraints and still acheive a 2 approximation OPT X X wj C j j j wj X wi X 2 wj j i j W G 2 W G 2 2 X wi wj i j W G 2 P G W G 2 2 The last equality is true because r G r G 3 p G w G 17 5 3 5 Finding G Here we construct a graph G with vertex set V T s t We add an edge from source s to every job with cost on the edges equal to processing time of the job Also we add an edge from every job to the sink t with cost on it equal to wi Also if there is a precedence constraint between two vertices t1 t2 in G then we add an edge from t2 to t1 having infinite cost in G By adding this edge we will be sure that we are not going to violate any precedence constraints during construction of a mincut To construct a G we solve a more general problem that if there exists any cut A B in G whose value is bounded w G then subgraph A s is precedence closed and that the rank of A s is at most The main challenge here is to calculate the value of which satisfies above property Here ranges from M IN lowest rank of the vertex and M AX rank of the graph Using binary search with in this range we can find a minimal value of that satisfies the above property This process takes polynomial time Once we find an appropriate value of the we have a precedence closed subgraph G A s 17 5 3 6 Algorithm Overview At the highest level we are repeatedly taking a new G out of G and scheduling it We produce a schedule consisting of precedence closed graphs from lowest to highest rank Given a graph G calculate G which takes polynomial time If G is a proper subset of G then we recursively schedule both G and G G separately If G G we can schedule the jobs in G in any order only taking into consideration the precedence constraints getting a 2 approximation …