In flow shop, m different machines should process n jobs. Each job contains exactly n operations. The ith operation of the job must be executed on the ith machine. Operations within one job must be performed in the specified order.
The first operation gets executed on the first machine, then the second operation on the second machine, and so on. Jobs can be executed in any order. The problem is to determine the optimal such arrangement, i.e. the one with the shortest possible total job execution makespan.
With two machines, problem can be solved in O(nlogn) time using Johnson’s algorithm. For more than 2 machines, the problem is NP hard. The goal is to minimize the sum of completion time of all jobs.
The flow shop contains n jobs simultaneously available at time zero and to be processed by two machines arranged in series with unlimited storage in between them. The processing time of all jobs are known with certainty.
It is required to schedule n jobs on machines so as to minimize makespan. The Johnson’s rule for scheduling jobs in two machine flow shop is given below: In an optimal schedule, job i precedes job j if min{pi1,pj2} < min{pj1,pi2}. Where as, pi1 is the processing time of job i on machine 1 and pi2 is the processing time of job i on machine 2. Similarly, pj1 and pj2 are processing times of job j on machine 1 and machine 2 respectively.
Johnson’s algorithm for flow shop scheduling is described below :
Algorithm JOHNSON_FLOWSHOP(T, Q)
// T is array of time of jobs, each column indicating time on machine Mi
// Q is queue of jobs
Q = Φ
for j = 1 to n do
t = minimum machine time scanning in booth columns
if t occurs in column 1 then
Add Job j to the first empty slot of Q
else
Add Job j to last empty slot of Q
end
Remove processed job from consideration
endreturn Q
Example
Example: Each of five jobs needs to go through machines M1 and M2. Find the optimum sequence of jobs using Johnson’s rule.
M1
M2
A
4
2
B
5
6
C
9
8
D
7
1
E
3
11
Solution:
The smallest job is D, which is on machine M1, so schedule this job last. And skip that job from further consideration.
x
x
x
x
D
Next smallest job is A, which is on machine M2, so schedule the job in last possible empty slot. And skip that job from further consideration.
x
x
x
A
D
Next smallest job is E, which is on machine M1, so schedule the job in earliest possible empty slot. And skip that job from further consideration.
E
x
x
A
D
Next smallest job is B, which is on machine M1, so schedule the job in earliest possible empty slot. And skip that job from further consideration.
E
B
x
A
D
The only job left is C.
E
B
C
A
D
So final schedule is {E, B, C, A, D}.
Some Popular Problems Solved using Dynamic Programming
Additional Reading: Read More