Flow Shop Scheduling: Explained

Flow shop scheduling problem:

  • 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.
  • We can find the optimal schduling using dynamic programming.

Algorithm for Flow Shop Scheduling

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 Jobj to the first empty slot of Q
  else
    Add Jobj to last empty slot of Q
  end
  Remove processed job from consideration
end
return 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.

 M1M2
A42
B56
C98
D71
E311

Solution:

  • The smallest job is D, which is on machine M1, so schedule this job last. And skip that job from further consideration.
xxxxD
  • 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.
xxxAD
  • 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.
ExxAD
  • 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.
EBxAD
  • The only job left is C.
EBCAD
  • So final schedule is {E, B, C, A, D}.

Additional Reading: Read More