Transcription
Load BalancingLoad Balancing: ExampleProblemExampleInput: m identical machines, n jobs with ith job having processingtime tiGoal: Schedule jobs to computers such thatConsider 6 jobs whose processing times is given as followsIJobs run contiguously on a machineIA machine processes only one job a timeIMakespan or maximum load on any machine is minimizedJobsti12233526262Load Balancing is NP-Complete46Consider the following schedule on 3 machinesDefinitionLet A(i)P be the set of jobs assigned to machine i. The load on i isTi j A(i) tj .The makespan of A is T maxi Ti34514The loads are: T1 8, T2 5, and T3 6. So makespan ofschedule is 8Greedy Algorithm1. Consider the jobs in some fixed order2. Assign job j to the machine with lowest load so farDecision version: given n, m and t1 , t2 , . . . , tn and a target T , isthere a schedule with makespan at most T ?ExampleJobstiProblem is NP-Complete: reduce from Subset Sum.122334321466545262
Putting it togetherfor each machine iTi 0 (* initially no load *)A(i) (* initially no jobs *)for each job jLet i be machine with smallest loadA(i) A(i) {j} (* schedule j on i *)Ti Ti tj (* compute new load *)Running TimeIFirst loop takes O(m) timeISecond loop has O(n) iterationsIBody of loop takes O(log m) time using a priority heapITotal time is O(n log m m)Quality of SolutionOptimalityProblemIs the greedy algorithm optimal? No! For example, onJobsti122334465262the greedy algorithm gives schedule with makespan 8, but optimalis 7In fact, the load balancing problem is NP-complete.Bounding the Optimal ValueLemmaTheorem (Graham 1966)T maxj tj , where T is the optimal makespanThe makespan of the schedule output by the greedy algorithm is atmost 2 times the optimal make span. In other words, the greedyalgorithm is a 2-approximation.Proof.ChallengeT How do we compare the output of the greedy algorithm with theoptimal? How do we get the value of the optimal solution?IWe will obtain bounds on the optimal valueSome machine will run the job with maximum processing timeLemma P1mj tj ,where T is the optimal makespanProof.PITotal processing time isISome machine must do at leastworkj tj1m(or average) of the total
Analysis of Greedy AlgorithmTheoremTightness of AnalysisPropositionProof.The analysis of the greedy algorithm is tight, i.e., there is anexample on which the greedy schedule has twice the optimalmakespanLet machine i have the maximum load Ti , and let j be the last jobscheduled on machine iProof.The greedy algorithm is a 2-approximationIIIIAt the time j was scheduled, machine i must have had theleast load; load on i before assigning job j is Ti tjSince i has the least Pload, we know Ti tj Tk , for all k.Thus, m(Ti tj ) k TkPPPPBut k Tk t . So Ti tj m1 k Tk m1 t T Finally, Ti (Ti tj ) tj T T 2T Improved Greedy AlgorithmModified GreedySort the jobs in descending order of processing time, and processjobs using greedy algorithmConsider problem of m(m 1) jobs with processing time 1 and thelast job with processing time m.Greedy schedule: distribute first the m(m 1) jobs equally amongthe m machines, and then schedule the last job on machine 1,giving a makespan of (m 1) m 2m 1The optimal schedule: run last job on machine 1, and thendistribute remaining jobs equally among m 1 machines, giving amakespan of mTechnical LemmaLemmaIf there are more than m jobs then T 2tm 1Proof.for each machine iTi 0 (* initially no load *)A(i) (* initially no jobs *)for each job j in descending order of processing timeLet i be machine with smallest loadA(i) A(i) {j} (* schedule j on i *)Ti Ti tj (* compute new load *)Consider the first m 1 jobsITwo of them must be scheduled on same machine, bypigeon-hole principleIBoth jobs have processing time at least tm 1 , since weconsider jobs according to processing time, and this proves thelemma
Analysis of Modified GreedyTightness of AnalysisTheoremThe modified greedy algorithm is a 3/2-approximationProof.Once again let i be the machine with highest load, and let j be thelast job scheduledIIf machine i has only one job then schedule is optimalIIf i has at least 2 jobs, then it must be the case thatj m 1. This means tj tm 1 12 T ITheorem (Graham)Modified greedy is a 4/3-approximationThe 4/3-analysis is tight.Thus, Ti (Ti tj ) tj T 12 T (Weighted) Set Cover ProblemGreedy RuleInput Given a set U of n elements, a collectionS1 , S2 , . . . Sm of subsets of U, with weights wiGoal Find a collection C of thesePsets Si whose union isequal to U and such that i C wi is minimized.IIExampleLet U {1, 2, 3, 4, 5, 6, 7, 8}, withS1 {1}w1 1S2 {2}w2 1S3 {3, 4}w3 1S4 {5, 6, 7, 8} w4 1S5 {1, 3, 5, 7} w5 1 S6 {2, 4, 6, 8} w6 1 {S5 , S6 } is a set cover of weight 2 2 Pick the next set in the cover to be the one that makes “mostprogress” towards the goalIICovers many (uncovered) elementsHas a small weightIf R is the set of elements that aren’t covered as yet, add setiSi to the cover, if it minimizes the quantity Siw R
Greedy AlgorithmInitially R U and C while R 6 let Si be the set that minimizes wi / Si R C C {i}R R \ Sireturn CRunning TimeIIIExample: Greedy Algorithm1 11 1Example11Main loop iterates for O(n) time, where U nLet U {1, 2, 3, 4, 5, 6, 7, 8}, withS1 {1}S2 {2}S3 {3, 4}S4 {5, 6, 7, 8}S5 {1, 3, 5, 7} S6 {2, 4, 6, 8}w1 w2 w3 w4 1 and w5 w6 1 Greedy Algorithm first picks S4 , then S3 , andfinally S1 and S2Minimum Si can be found in O(log m) time, using a priorityheap, where there are m sets in set cover instanceTotal time is O(n log m)Cost for covering an elementCost of element: ExampleExampleDefinitionISuppose the greedy algorithm selects sets S 1 , S 2 , . . . S k (inthat order) to form the set cover.IConsider an element s that is first covered when S i is pickedILet R be the set of elements that are uncovered when S i ispickedIThe cost of covering s is cs w (S i )/ S i R , where w (S i ) isweight of the set S iLet U {1, 2, 3, 4, 5, 6, 7, 8}, withS1 {1}S2 {2}S3 {3, 4}S4 {5, 6, 7, 8}S5 {1, 3, 5, 7} S6 {2, 4, 6, 8}w1 w2 w3 w4 1 and w5 w6 1 . The greedyalgorithm picks S4 , S3 , S2 , S1 in that order. The costs of elementsare given as followsc1 1c2 1c3 1/2 c4 1/2c5 1/4 c6 1/4 c7 1/4 c8 1/4
Costs of Covers and ElementsBounding costs of setsLemmaPropositionIfPC is the setP cover computed by the greedy algorithm theni C wi s U csProof left as exerciseMain IdeaPs ScskUpper bound the ratio, i.e., to say “to cover a lot of cost,wkyou need to use a lot of weight”PFor every set Sk , s Sk cs H( Sk ) · wk , wherePH(n) ni 1 1i Θ(ln n)Proof.Let Sk {s1 , . . . sd }, where si is covered before sj if i jIIIIAnalysis of the Greedy AlgorithmConsider the iteration when sj is covered; at this timeR {sj , sj 1 , . . . sd }Average progress cost of Sk is wk / Sk R wk /(d j 1)Suppose sj gets covered because Si is selected by greedywkikalgorithm. Then, csj Siw R Skw R d j 1PPPwi H(d)wkHence, s Sk cs dj 1 csj dj 1 d j 1Tightness of AnalysisTheoremThe greedy algorithm for set cover is a H(d )-approximation,where d maxi Si Proof.Let C be the optimal set cover, and C the set cover computed bygreedy algorithmP1I By previous lemma we know wi s Si csi and so weH(d )PPP1 have w i C wi i C H(d ) s Si csiPPPI Further,i C s Si cs s U csPPP1I Thus, w i C wi i C H(d )s Si csi PP11s U cs H(d )i C wiH(d )Analysis Tight?Does the Greedy Algorithm give better approximation guarantees?No!Consider a generalization of the set cover example. Each columnhas 2k 1 elements, and there are two sets consisting of a columneach with weight 1 . Additionally there are log n sets ofincreasing size of weight 1. The greedy algorithm will pick theselog n sets given weight log n, while the best cover has weight 2 2
Best Algorithm for Set CoverTheoremIf P 6 NP then no polynomial time algorithm can achieve a betterthan H(n) approximation.Proof beyond the scope of this course.
Load Balancing Problem Input: m identical machines, n jobs with ith job having processing time ti Goal:Schedule jobs to computers such that I Jobs run contiguously on a machine I A machine processes only one job a time I Makespanor maximum load on any machine is minimized De nition Let A (i) be the set of jobs assigned to machine i. Theloadon i .
