1.204 Lecture 14 Dynamic programming: Job scheduling Job scheduling Dynamic programming formulation • To formulate a problem as a dynamic program: – Sort by a criterion that will allow infeasible combinations tto bbe elili mitinatedd effiffi citl iently – Choose granularity (integer scale or precision) that allows dominated subsequences to be pruned • Choose coarsest granularity that works for your problem – Use dynamic programming in fairly constrained problems with tight budgets and bounds • If problem is not highly constrained, you will need to applyheuristic constraints to limit the search space – Choose between multistage graph, set or custom implementation • Decide if a sentinel is helpful in set implementation – Experiment • Every problem is a special case, since DP is O(2n) • Can you find special structure that makes your DP fast? 1••DP examples • This lecture shows another example – Job scheduling, using multistage graph • Example of sorting feasibility pruning used effectively Example of sorting, feasibility, pruning used effectively • Example of good software implementation – No graph data structure built; solution tree built directly – Good but not ideal representation of tree/graph nodes; some nodes are created but not used – We don’t even consider 2-D arrays, linked lists, etc., which do not scale at all, but which are popular in many texts. Crazy☺ • Good DP codes are somewhat hard to write; there is much detail to handle and many lurking inefficiencies to combatdetail to handle and many lurking inefficiencies to combat – We will not dwell on the code details, but they are important – Knapsack problem in next lecture, using sets • Example of sorting, feasibility, pruning in different framework • Multistage graph doesn’t work: too many nodes per stage • Object oriented design is big improvement over past codes – Be careful: many texts have zillions of inefficient, tiny objects Job scheduling dynamic program • Each jjob to be scheduled is treated as a pprojject with a profit, time required, and deadline – We have a single machine over a given time (resource) – Use multistage graph formulation from last lecture • Algorithm pseudocode: – Sort jobs in deadline order (not profit order as in greedy) – Build source node for job 0 – Consider each job in deadline order: • Build set of nodes for Build set of nodes for nextnext stage (job) stage (job) for each state (time spent) for each state (time spent) • For current job: – Build arc with no time assigned to job – If time so far + current job time <= job deadline, build arc with job done – Build sink node for artificial last job – Trace back solution using predecessor nodes 23Job scheduling algorithm• We will label every node in the graph that we encounter ygpwith its profit and time used– If we find a better path to that node, we update its profit and time labels– This is exactly the same as the shortest path label correcting algorithm• We know this algorithm runs fast– The issue is then: how big is the graph?• A smart formulation keeps the graph size at some polynomial bdith bl ibound in the problem size• Otherwise, the graph becomes exponentially large and this is why dynamic programming worst case is exponential– If our model is good, we also need a good implementation• A bad implementation can make a good model run very slowly• (A good implementation can’t really speed up a bad model…)Job scheduling exampleJob Deadline Profit Time01391013911290122882322014337353252647014 time units of machine time available.Job scheduling graph: forward 0 0 0 1 V(1,0) V(2,0) V(3,0)0 6 1 2 6 7 V(1,1) V(2,1) E(2,0)=0 E(2,0)=0 11 12 V(3,1) E(3,0)=0 E(3,0)=0 0 0 39 0 90 1 90 7 0 3 8 V(0,0) V(1,2) V(2,2) 13 V(3,2)E(3,0)=0 129 2 129 8 4 9 V(1,3) V(2,3) 14 V(3,3) 5 10 V(1,4) V(2,4) Stage: 0 1 2 3 15 V(3,4)V pred | Job 0 decision | Job 1 decision | Job 2 decision | Profit: 39 Profit: 90 Profit: 88 Time: 1 Time: 1 Time: 2 Deadline: 1 Deadline: 2 Deadline: 2 Job scheduling graph: backward 0 0 0 1 V(1,0) V(2,0) V(3,0)0 6 1 2 6 7 V(1,1) V(2,1) E(2,0)=0 E(2,0)=0 11 12 V(3,1) E(3,0)=0 E(3,0)=0 0 0 39 0 90 1 90 7 0 3 8 V(0,0) V(1,2) V(2,2) 13 V(3,2)E(3,0)=0 129 2 129 8 V(1,3) V(2,3) V(3,3) 4 9 14 5 10 V(1,4) V(2,4) Stage: 0 1 2 3 15 V(3,4)V pred | Job 0 decision | Job 1 decision | Job 2 decision | Profit: 39 Profit: 90 Profit: 88 Time: 1 Time: 1 Time: 2 Deadline: 1 Deadline: 2 Deadline: 2 4t ttJob class public class Job implements Comparable { int jobNbr; // Package access int deadline; // Package access int profit; // Package access int time; // Package access public Job(int j, int d, int p, int t) {p ( j, , p, ) { jobNbr= j; deadline= d; profit= p; time= t; } public int compareTo(Object other) { Job o= (Job) other; if (deadline < o.deadline) return -11; else if (deadline > o.deadline) return 1; else return 0; } public String toString() { return("J: "+ jobNbr+" D: "+ deadline+" P: "+ profit+" T: "+ time); } } JobScheduler public class JobScheduler { private Job[] jobs; // Input set of jobs to schedule private int nbrJobs; //// Number of inpput jjobs p ; private int endTime; // Latest end time of job (=max resource) private int[] path; // List of nodes in the optimal solution private int jobsDone; // Output: total number of jobs private int totalProfit; // Output private int nodes; // Nodes generated in DP graph private int[] nodeProfit; // Profit of jobs prior to this node private int[] nodeTime; // Time spent on jobs prior to node i i t[] d // P // Predecessor nodde with best profitfitprivate int[] pred; d ith b private int stageNodes; // Difference in node numbers from // one stage to next 5JobScheduler constructor, jsd() public JobScheduler(Job[] j, int e) { jobs = j; endTime = e; nbrJobs= jobs.length; path= new int[nbrJobs+1]; nodes= (nbrJobs-1)*(endTime+1)+2; // nodes= stages*states + source, sink nodeProfit= new int[nodes]; nodeTime= new int[nodes]; pred= new int[nodes]; for (int i= 0; i < nodes; i++) pred[i]= -1; stageNodes= endTime+1; stageNodes= endTime+1; } public void jsd() { buildSource(); buildCenter(); buildSink(); backPath(); } buildSource() private void buildSource() { nodeProfit[0]= 0; // Source is node 0 nodeTime[0]= 0;;[] // Treat stage 0 as special case because it has only 1 node // If job not in solution set