Flow Shop Scheduling

PRESENTATION ON FLOW-SHOP SCHEDULING SUBMITTED TO: Dr. V.K. Pathak SUBMITTED BY: Akanksha Shukla III C.S.E. 552/07

FLOWSHOP SCHEDULING • In a general flowshop we may have, n jobs each having m tasks T1i ,T2i ,…Tmi , where 1≤i≤n • Task Tji is to be performed on processor Pj, where 1≤j≤m. • The time required to complete task Tji is tji .

FLOWSHOP SCHEDULING A schedule for the n jobs is an assignment of tasks to time intervals on the processors. • No processor may have more than one task assigned to it in any time interval. • For any job i the processing of tasks Tji, j >1, will not be started until task Tj-1,i has been completed.

FLOW SHOP SCHEDULING Given: A set of jobs each having some tasks to be performed. Processors for each of the tasks.

Main Objective- To determine the order of assigning the tasks to processors such that the sum finishing time is minimal.

EXAMPLE Two jobs have to be scheduled on three processors. The task times are given in the matrix below

[j]=

2 3 5

0 3 2

=

T11

T12

T21

T22

T31

T32

Time 0

2

P1

T11

P2

T22

5

T21

6

10

12

T22 T31

P3

T32

Figure (a)

This is a preemptive schedule. A preemptive schedule is the one which allows the processing of a task to be terminated before its completion.

Time 0 P1 P2 P3

2

3

5

6

10 11

T11 T22

T21 T32

T31

Figure (b)

This is a non-preemptive schedule. A non-preemptive schedule is a schedule in which the processing of a task on any processor is not terminated until the task is complete.

FINISH TIME OF JOBS The finish time fi(S) of job i is the time at which all tasks of job i have been completed in schedule S. In figure (a), f1(S)=10 and f2(S)=12 In figure (b), f1(S)=11 and f2(S)=5

OBJECTIVE FUNCTIONS The Finish Time F(S) of a schedule S is given by ; F(S)=max{fi(S)} where 1 ≤ i ≤ n. The Mean Flow Time, MFT(S) is defined to be: MFT(S)=(Σfi(s))/n where 1 ≤ i ≤ n

RELATED TERMS • OFT: Optimal Finish Time schedule for a given set of jobs is a non-preemptive schedule S for which F(S) is minimum over all non-preemptive schedules. • POFT: Preemptive Optimal Finish Time schedule for a given set of jobs is a preemptive schedule S for which F(S) is minimum over all preemptive schedules.

MORE RELATED TERMS • OMFT: Optimal Mean Flow Time for a given set of jobs is a non-preemptive schedule S for which MFT(S) is minimum over all non-preemptive schedules. • POMFT: Preemptive Optimal Mean Flow Time schedule for a given set of jobs is a preemptive schedule S for which MFT(S) is minimum over all preemptive schedules.

CONSTRAINT The general problem of obtaining schedules for m > 2 is computationally difficult, dynamic programming leads to an efficient algorithm to obtain OFT (optimal finish time) schedules for the case m=2(tasks=2).

ASSUMPTIONS • t1i  ai, where t1i is time of task1 of job i • t2i bi, where t2i is time of task2 of job i • Case being considered, ai≠0, 1 ≤ i ≤ n • Special case, If ai=0 , then All jobs with ai≠0 are optimally scheduled and then all jobs with ai=0 are simply added to it.

DERIVATION Let σ1, σ2, σ3,…..σk be a permutation prefix defining a schedule for jobs T1, T2, T3,…Tk. f1time taken by T1, T2,…Tk on processor p1 f2time taken by T1, T2,…Tk on processor p2 Let t=f2-f1

DERIVATION g(S,t)= length of an optimal schedule for the subset of jobs S under the assumption that p2 is not available until time t. Thus, for S={1, 2,..n}, g(S,t)=g({1,2,..n},0)

g({1,2,…n},0)=min{ai+g({1,2,…n}-{i},bi)}, where 1≤i≤n

DERIVATION • The task,T2i cannot be started until max{ai,t}. Hence, f2-f1= bi+max{ai,t}-ai= bi+max{t-ai,0}

g(S,t)= min{ai+g(S-{i},bi+max{t-ai,0})} (1) where i belongs to S Now, let R be any schedule for a job subset S. Let i and j be the first two jobs.

DERIVATION • g(S,t)=ai+g(S-{i},bi+max{t-ai,0}) g(S,t)=ai+aj+g(S-{i,j},bj+max{bi+max{tai,0}-aj,0} (2) Above equation can be simplified as, tij=bj+max{bi+max{t-ai,0}-aj,0} =bj+bi-aj+max{max{t-ai,0},ajbi} =bj+bi-aj+max{t-ai,aj-bi,0} tij=bj+bi-aj-ai+max{t,ai+aj-bi,ai}

DERIVATION • If jobs i and j are interchanged in R, then g’(S,t)=ai+aj+g(S-{i,j},tji) (3) where tji=bj+bi-aj-ai+max{t,ai+aj-bj,aj}

max{t,ai+aj-bi,ai} ≤ max{t,ai+aj-bj,aj} (4) comparing, eqns. (1)and(3) , if eqn. (4) holds, then g(S,t) ≤ g’(S,t)

DERIVATION For eqn. (4) to hold, max{ai+aj-bi,ai} ≤ max{ai+aj-bj,aj} or max{-bi,-aj} ≤ max{-bj,-ai} or min{bi,aj} ≥ min{bj,ai}

(5)

CONCLUSION • There exists an optimal schedule in which for every pair(i,j) of adjacent jobs, min{bi,aj} ≥ min{bj,ai}, holds true. • For making an optimal scedule, If min{a1,a2, …an,b1,b2,…bn} is ai, then job i should be the first job. If min{a1,a2, …an,b1,b2, …bn} is bj, then job j should be the last job. • The above procedure helps positioning one of the n jobs and we need to reapply the eqn.(5) to position the remaining n-1 jobs.

SCHEDULING RULE • Sort all the ai’s and bj’s into nondecreasing order. • If the next number in the sequence is aj and job j hasn’t yet been scheduled, schedule job j at the leftmost available spot. If the next number is bj and job j hasn’t yet been scheduled, schedule job j at the rightmost available spot. If j has already been scheduled go to the next number in the sequence.

EXAMPLE Let n=4 (a1,a2,a3,a4)=(3,4,8,10) and (b1,b2,b3,b4)=(6,2,9,15) Now sort all these tasks into nondecreasing order: (b2,a1,a2,b1,a3,b3,a4,b4)=(2,3,4,6,8,9,10,15) Let σ1,σ2,σ3,σ4 be the optimal schedule. Since the smallest number is b2, we set σ4=2.

The next number is a1 and we set σ1=1. The next number is a2 but job2 has already been scheduled. The next number is b1 but job1 has already been scheduled. The next is a3 and we set it to σ2. This leaves σ3 free and job 4 unscheduled. Thus σ3=4. Time 0 P1 P2

a1

3

9 11 a3 b1

20 21 a4 b3

25

36 38

a2 b4

b2

TIME COMPLEXITY • Solving eqn.(1), g(S,t)= min{ai+g(S{i},bi+max{t-ai,0})} directly for g({1,2,… n},0) for the optimal schedule will take Ώ(2n). • The scheduling rule above can be implemented to run in time 0(n log n).

THANK YOU