# Flow Shop Scheduling using Dynamic Programming

## 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 i
^{th}operation of the job must be executed on the i^{th}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{p
_{i1},p_{j2}} < min{p_{j1},p_{i2}}. Where as, p_{i1}is the processing time of job i on machine 1 and p_{i2}is the processing time of job i on machine 2. Similarly, p_{j1}and p_{j2}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 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
**end**
**return **Q

## Example

**Example: Each of five jobs needs to go through machines M _{1} and M_{2}. Find the optimum sequence of jobs using Johnson’s rule.**

M_{1} | M_{2} | |

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 M
_{1}, 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 M
_{2}, 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 M
_{1}, 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 M
_{1}, 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

- Binomial Coefficient
- Making a Change
- Knapsack Problem
- Multistate Graph Problem
- Optimal Binary Search Tree
- Matrix Chain Multiplication
- Longest Common Subsequence
- Bellman-Ford (Single Source Shortest Path) Algorithm
- Floyd-Warshall (All Pair Shortest Path) Problem
- Assembly Line Scheduling
- Travelling Salseman Problem
- Flow Shop Scheduling

Additional Reading: Read More