Scheduling with OutliersIntroductionA possible issueOvercoming this..Outliers vs “Prize-Collecting”Problems StudiedSlide 7Slide 8Our ResultsAn LP FormulationRounding: Some ObstaclesHow can the LP cheat?Slide 13Rounding 1: Local SwapLocal Swap ContinuedHandling General SizesA Not-so-local SwapIngredient 2: A Local ShiftWrapping UpThank You!Scheduling with OutliersRavishankar Krishnaswamy(Carnegie Mellon University)Joint work with Anupam Gupta, Amit Kumar and Danny SegevIntroduction•Classical Scheduling Problems–Given jobs and machines– Find best schedule according to some objective•Simple Example–N jobs, M machines.–Job j has a processing time of pj–Find schedule of minimum makespan•Minimize maximal load on any machine.A possible issue•What if there are some rogue jobs?–They dominate objective value–Algorithms focus on handling these–Ignore effects of others•For example,–Straggler job might slow down response time of all jobs–If we discard that job, other jobs finish much faster–Commonly seen in computersOvercoming this..•Ignore these rogue jobs•Scheduling with outliers–Or possibly, scheduling without liars? •More Formally–Each job comes with a penalty if we discard it–Discard a total penalty of R–Schedule the others to optimize given objectiveOutliers vs “Prize-Collecting”•Prize-Collecting Model–Penalty of jobs left out figures in objective function–Minimize objective of scheduled jobs + penalty of outliers•Outlier Model–Hard bound on penalty–leave out some jobs, while scheduling the others–Both model similar concept–Prize-Collecting combines two different measures–Can solve PC if we solve outlier problem.Problems Studied•Makespan/Generalized Assignment–n jobs and m unrelated machines–Job j has processing time pij and cost cij on machine i–Job j also has penalty rj–Goal is to minimize makespan •while leaving out jobs of total penalty RNon-Outlier Setting: (C,2T)-approximation algorithmNon-Outlier Setting: (C,2T)-approximation algorithmProblems Studied•Weighted Sum of Completion Times–n jobs and m unrelated machines–Job j has processing time pij on machine i–Job j also has penalty rj –Goal is to minimize average completion time of the jobs•while leaving out jobs of total penalty RNon-Outlier Setting: 2-approximation algorithmNon-Outlier Setting: 2-approximation algorithmProblems Studied•Average Flow Time–n jobs and m identical machines–Job j has processing time pj and arrival time aj–Goal is to minimize average flow time of the jobs•Fj = Cj – aj or the time for which j is present in the system•while leaving out jobs of total penalty RNon-Outlier Setting: O(log P)-approximation algorithmNon-Outlier Setting: O(log P)-approximation algorithmOur ResultsGeneralized Assignment / MakespanA deterministic [C(1+є), 3T] approximation algorithmGeneralized Assignment / MakespanA deterministic [C(1+є), 3T] approximation algorithmWeighted Sum of Completion TimesA randomized constant factor approximation algorithm for the general caseAn FPTAS in the case of single machine sum of completion timesWeighted Sum of Completion TimesA randomized constant factor approximation algorithm for the general caseAn FPTAS in the case of single machine sum of completion timesAverage Flow Time (Preemptive)A deterministic O(log P) approximation algorithm when all penalties are unitAverage Flow Time (Preemptive)A deterministic O(log P) approximation algorithm when all penalties are unitAn LP FormulationAdapted from Garg and Kumar [ICALP 06]xjt:: extent of job j is scheduled in time slot [t,t+1]yj:: fraction of j scheduledfj:: fractional flow time of jRounding: Some Obstacles•For sum of completion times and makespan–We can use ½ point of any job effectively•Does not quite work for flow time(α Cj – aj ) >> α (Cj – aj )•Such techniques need “speed-up” of α •Without speed-up, we really need to work inside LP scheduleHow can the LP cheat?2k2k-12k-2211 1… …2k+12k2k-1221 1 1 1…MLP Schedule:• fraction ½ of each large job in the corresponding gray intervals• fraction 1 of each small job in the blue intervalsLP Cost is roughly 2k + MRequirement: k/2 + M jobsHow can the LP cheat?2k2k-12k-2211 1… …2k+12k2k-1221 1 1 1…MIntegral Schedule:• once jobs M + k/2 jobs are chosen, SRPT is optimal• all small jobs will be chosen• k/2 large jobs all wait for period of MIntegral Cost is (M.k)Requirement: k/2 + M jobsGive up globally; Work locallyRounding 1: Local Swap•Consider two jobs of processing times 2k•Let y1 and y2 denote their fractional extents in LP•To make the schedule integral, suppose we swapΔ fraction of J2 with equal fraction of J1J1J2a1a2Observation: LP cost increase is roughly Δ (a2 – a1) Observation: LP cost increase is roughly Δ (a2 – a1) ΔLocal Swap Continued•Can perform such swaps and ensure that–Each time instant t is charged at most 1 in total•Good if job sizes are powers of two–Any point charged is not empty time–Total charge is upper bounded by LPOPT–Can get desired O(log P)-approximation algorithm•How do we handle fact that all jobs are not 2k ?Handling General Sizes•Group jobs into buckets. Look at one such bucket•If j2 has larger processing time–There is sufficient space to replace it by equal fraction of j1–Same argument as in previous slide•If j2 has smaller processing time–Not enough space–Schedule j2 over j1 ! –Might violate the release date of j2•Still no good.. J1J2a1a2A Not-so-local Swap•What’s the Problem?–Grow j for long time charging intervals till fraction 2/3–Then j sees smaller job j’ scheduled to 2/3–j’ eats j, but we’re still left with 1/3 of j–Cycle repeats…•A Fix–Don’t be local -- Look Ahead–Avoid such issues–More complex charging argumentIngredient 2: A Local Shift •To fix the release date issue–Look at any job class–Consider all the time intervals where we schedule that class jobs–Shift the schedule by 2k entirely within this intervalUnfinished jobs increase by 2 per classTotal extra cost: O(log P) LPOPTWrapping Up•O(log P) approximation algorithm–flow-time on single machine with unit penalties–can be extended to identical machines•Other results–O(1) for weighted completion times and makespan•What about flow time with non-uniform penalties?•Outlier versions of other problems?Thank