Minimizing Average Flow-Time in Machine Job Scheduling

Minimizing Average Flow-Time Naveen Garg IIT Delhi Joint work with Amit Kumar, Jivi Chadha ,V Muralidhara, S. Anand

Problem Definition Given : A set of M machines A set of jobs A matrix of processing times of job ion machine j. Each job specifies a release date pij rj rj

Problem Definition Conditions : rj Pre-emption allowed rj Migration not allowed

Problem Definition rj Cj Fj=Cj rj Flow-time of j, Goal : Find a schedule which minimizes the average flow-time

Special Cases pij= pj Parallel : all machines identical pij= pj/si Related : machines have different speeds Subset Parallel : parallel except that a job can only go on a subset of machines pij pj Subset Related All of these are NP-hard.

Previous work The problem is well studied when the machines are identical. For a single machine the Shortest- remaining-processing-time (SRPT) rule is optimum. [Leonardi-Raz 97] argued that for parallel machines SRPT is (min (log n/m, log P)) competitive, where P is max/min processing time. They also show a lower bound of (log P) on competitive ratio

Preemptive, unweighted Flow time Online O(log P), (log P) [LR97] O(log P) [GK06] Offline (log1- P) [GK07] Parallel machines Related machines Subset parallel Unbounded [GK07] O(log P) (log P/loglogP) [GK07] O(k) [S09] Unrelated machines

a O(1= O(1)) b Fractional flow-time C j Recall, flow-time of j = 1 t r = j pj(t) = remaining processing of job j at time t remaining fraction at time t = pj (t) processing total time Fractional flow-time of j = t rjpj(t)/pj

O(1=O(1)) O(1= O(1)) Fractional flow-time 0 2 1 5 12 Fractional flow-time = 1*2 + 2/3*3 + 1/3*7 Fractional flow-time can be much smaller than (integral) flow-time

Integer Program Define 0-1 variables : x(i,j,t) : 1 iff job j processed on i during [t,t+1] Write constraints and objective in terms of these variables. Fractional flow-time of j = t rj (t-rj) x(i,j,t)/pij

LP Relaxation x(i, j, t) Min (t r ) j p i, j, t ij x(i, j, t) 1 for all j = p i, t ij x(i, j, t) 1 for all i, t j x(i, j, t) 0 One Caveat

Fractional flow-time A job can be done simultaneously on many machines : flow-time is almost 0

LP Relaxation x(i, j, t) Min (t r ) x(i, j, t) + j p i, j, t i, j, t ij x(i, j, t) 1 for all j = p i, t ij x(i, j, t) 1 for all i, t j x(i, j, t) 0 Add a term for processing time

Class of a job pj: The processing time of j rounded up to nearest power of 2 k 2 pj If , we say k is the class of job j Number of different classes = O(log P)

Modified Linear Program x(i, j, t) Min (t r ) x(i, j, t) + ij j p i, j, t i, j, t x(i, j, t) 1 for all j = p i, t ij x(i, j, t) 1 for all i, t j x(i, j, t) 0

Modified LP LP value changes by a constant factor only. But : rearranging jobs of the same class does not change objective value.

From fractional to integral The solution to the LP is not feasible for our (integral) problem since it schedules the same job on multiple m/c s. We now show how to get a feasible, non- migratory schedule.

Rounding the LP solution Find the optimum solution to the LP. Consider jobs of one class, say blue.

Rounding the LP solution (contd.) Additional space Rearrange blue jobs in the space occupied by the blue jobs so that each job is scheduled on only one m/c. If additional space is needed it is created at the end of the schedule

Preemptive, unweighted Flow time Online O(log P), (log P) Offline Parallel machines (log1- P) Related machines Subset parallel O(log P) Unbounded O(log P) (log P/loglogP) O(k) Unrelated machines

Assignment as flow Fix a class k : arrange the jobs in ascending order of release dates. 0 r1 r2 r3 r4 r5 r6 r7 z i, j tx i, j,t i v(i,k,j) pj s Flow = ?

Unsplittable Flow Problem s d3 d2 d1

Unsplittable Flow Problem s d3 d2 d1 Flow can be converted to an unsplittable flow such that excess flow on any edge is at most the max demand [Dinitz,Garg, Goemans]

Back to scheduling... Fix a class k : find unsplittable flow 0 1 2 3 4 5 6 7 i v(i,j,k) pj s Gives assignment of jobs to machines

Back to scheduling... J(i,k) : jobs assigned to machine i Can we complete J(i,k) on class k slots in I ? 0 1 2 3 4 5 6 7 i v(i,j,k) pj s

Building the Schedule Flow increases by at most max processing time = 2k So all but at most 2 jobs in J(i,k) can be packed into these slots Extra slots are created at the end to accommodate this spillover

Increase in Flow-time (t r ) p How well does i, j x(i, j, t) + 1 t ij capture the flow-time of j ? Charge to the processing time of other classes

Finally... Since there are only log P classes Can get OPT + O(log P).processing time flow-time for subset parallel case.

Preemptive, unweighted Flow time Online O(log P), (log P) Offline Parallel machines (log1- P) Related machines Subset parallel O(log P) Unbounded O(log P) (log P/loglogP) O(k) Unrelated machines

Integrality Gap for our LP(identical m/c) 1 Phase 0 k-1 k 0 mk-1 2mk-1 mk +mk-1 T m 1 mk-1 mk

Integrality Gap for our LP(identical m/c) 1 Phase 0 k-1 k 0 mk-1 2mk-1 mk +mk-1 T Blue jobs can be scheduled only in this area of volume (mk+mk-1)m/2 At least m/2 blue jobs left At least mk/2 jobs left For sufficiently large T, flow time mT(1+k/2)

Integrality Gap for our LP(identical m/c) 1 Phase 0 k-1 k 0 mk-1 2mk-1 mk +mk-1 T m 1 Optimum fractional solution is roughly mT mk-1 mk

Integrality gap Optimum flow time is at least mT(1+k/2) Optimum LP solution has value roughly mT So integrality gap is (k). Largest job has size P = mk. For k = mc, c>1, we get an integrality gap of (log P/loglogP)

Hardness results We use the reduction from 3-dimensional matching to makespan minimization on unrelated machines [lenstra,shmoys,tardos] to create a hard instance for subset-parallel. Each phase of the integrality gap example would have an instance created by the above reduction. To create a hard instance for parallel machines we do a reduction from 3- partition.

Preemptive, unweighted Flow time Online O(log P), (log P) Offline Parallel machines (log1- P) Related machines Subset parallel O(log P) Unbounded O(log P) (log P/loglogP) O(k) Unrelated machines

A bad example B x A x A+B=T A> T/2 A x T 0 T+L Flow time is at least AxL > T L/2 OPT flow time is O(T2+L) (T) lower bound on any online algorithm

Other Models What if we allow the algorithm extra resources ? In particular, suppose the algorithm can process (1+ ) units in 1 time-unit. [first proposed by Kalyanasundaram,Pruhs95] Resource Augmentation Model

O(1=O(1)) Resource Augmentation For a single machine, many natural scheduling algorithms are O(1/ O(1))- competitive with respect to any Lp norm [Bansal Pruhs 03] Parallel machines : randomly assign each job to a machine O(1/ O(1)) competitive [Chekuri, Goel, Khanna, Kumar 04] Unrelated Machines : O(1/ 2)-competitive, even for weighted case. [Chadha, Garg, Kumar, Muralidhara 09]

Our Algorithm When a job arrives, we dispatch it to one of the machines. Each machine just follows the optimal policy : Shortest Remaining Processing Time (SRPT) What is the dispatch policy ? GREEDY

The dispatch policy When a job j arrives, compute for each machine i the increase in flow-time if we dispatch j to i. j arrives at time t : pij1(t) pij2(t) pijr(t) < pij < pijr+1(t) j1 pj1(t) j2 Increase in flow-time = pj1(t) + + pjr(t) + pij+ pij(s-r) jr jr+1 j js

Our Algorithm When a job j arrives, compute for each machine i the increase in flow-time if we dispatch j to i. Dispatch j to the machine for which increase in fractional flow-time is minimum.

Analyzing our algorithm Dual LP Primal LP Algorithm s value Construct a dual solution LP opt. value Show that the dual solution value and algorithm s flow-time are close to each other.

Dual LP x(i, j, t) Min (t r ) x(i, j, t) + j p i, j, t i, j, t ij x(i, j, t) 1 for all j = j p i, t ij x(i, j, t) 1 for all i, t it j x(i, j, t) 0

Dual LP Max j it j i, t t r j j 1 for all i, j, t, t r + it j p p ij ij , 0 j it

Setting the Dual Values When a job j arrives, set j to the increase in flow- time when j is dispatched greedily. j arrives at time t : pij1(t) pij2(t) pijr(t) < pij < pijr+1(t) j1 pj1(t) j2 j = pj1(t) + + pjr(t) + pij + pij(s-r) Thus j j is equal to the total flow- time. jr jr+1 js

Setting the Dual Values Set it to be the number of jobs waiting at time t for machine i. j1 it = s pj1(t) j2 Thus i,t it is equal to the total flow- time. jr jr+1 js

Dual Feasibility Fix a machine i , a job j and time t . Suppose pi jl(t) < pi j < pi jl+1(t) pj1(t) j1 j2 p (t) ... p (t) p p + + + + s ( ) l j j j i' j i' j 1 l jl t' t j 1 + + Need to verify jl+1 i' t' p p i' j i' j js

Dual Feasibility What happens when t = t ? pj1(t) j1 ( ) l p (t) ... p (t) p p + + + + s j j j i' j i' j 1 l j2 p (t) ... p (t) + + ( ) j j j jl 1 1 + + + = + 1 s l s 1 l p i' i' t p j i' j jl+1 js

Dual Feasibility What happens when t = t + ? Suppose at time t job jk is being processed Case 1: k l j1 j2 p (t) ... p (t) p (t) ... p (t) + + + + + ( ) j j j j j 1 + + s l 1 1 - k k l p p i' j i' + j jl (t' t) p (t) ... p (t) + + ( ) j j 1 + + s l k l jl+1 p i' j js (t' t) (t' t) 1 (s - k 1) 1 + + + = + + i' t' p p i' j i' j

Dual Feasibility Case 2: k > l j2 jr ( ) p (t) ... p (t) p p + + + + s l jr+1 j j j i' j i' j 1 l p p js i' j i' j p (t) ... p (t) p (t) ... p (t) + + + + + ( ) j j j j 1 + + + 1 s k 1 r 1 - k l 1 + p i' j (t' t) (t' t) 1 (s - k 1) 1 + + + = + + i' t' p p i' j i' j