ReasoningAbility.com

Flow Shop Scheduling

Flow Shop Scheduling problems involve processing jobs on multiple machines in the same order (each job goes through Machine 1, then Machine 2, etc.). For 2 machines, Johnson's Rule gives the optimal sequence to minimize makespan.

10Worksheets
200+Practice Questions
AdvancedDifficulty
3-4 hoursHours to Master

What You'll Learn

Introduction & Overview Why This Matters How to Solve Pro Tips & Tricks
Shortcut Methods Common Mistakes Practice Worksheets Exam Importance

Introduction to Flow Shop Scheduling

Flow Shop Scheduling problems involve processing jobs on multiple machines in the same order (each job goes through Machine 1, then Machine 2, etc.). For 2 machines, Johnson's Rule gives the optimal sequence to minimize makespan.

Prerequisites

Johnson's Rule Makespan calculation Processing times Sequencing algorithms
Why This Matters: Flow Shop problems appear in 1-2 questions in CAT and advanced Banking exams. They test sequencing optimization.

How to Solve Flow Shop Scheduling Problems

1

Step 1: List all jobs with processing times on Machine 1 (A) and Machine 2 (B)

2

Step 2: Apply Johnson's Rule: Find min processing time

3

Step 3: If min on Machine 1, schedule job early; if on Machine 2, schedule job late

4

Step 4: Remove scheduled job, repeat

5

Step 5: Calculate makespan for resulting sequence

Pro Strategy: Johnson's Rule: Find smallest processing time. If on first machine, schedule as early as possible; if on second, schedule as late as possible.

Example Problem

Example: Jobs: J1(3,5), J2(4,2), J3(6,3), J4(2,4). Optimal sequence? Solution: Step 1: Min times: J4(2 on M1) → schedule first, J2(2 on M2) → schedule last Step 2: Remaining: J1(3,5), J3(6,3). Min=3(J1 on M1) or 3(J3 on M2) Step 3: Johnson's rule: J1 early, J3 middle Step 4: Sequence: J4 → J1 → J3 → J2 Answer: J4 → J1 → J3 → J2

Pro Tips & Tricks

  • Johnson's Rule optimal for 2-machine flow shop
  • If tie, can schedule either
  • Calculate makespan by simulation after sequence determined
  • For 3+ machines, problem is NP-hard (use heuristics)

Shortcut Methods to Solve Faster

List all jobs, find min A or B
If min A, put at front; if min B, put at back
Remove and repeat
Resulting sequence minimizes makespan

Common Mistakes to Avoid

Using Johnson's Rule for more than 2 machines (not optimal)
Forgetting to recalculate makespan after sequencing
Misidentifying which machine is first vs second
Not handling ties correctly

Exam Importance

Flow Shop Scheduling is an important topic for various competitive exams. Here's how frequently it appears:

SSC CGL
0-1 questions
BANKING PO
1-2 questions
RAILWAYS RRB
0-1 questions
CAT
2-3 questions
INSURANCE
0-1 questions

Ready to Master Flow Shop Scheduling?

Start with Worksheet 1 and work your way up to expert level! Each worksheet includes:

20 practice questions
Detailed solutions
Step-by-step explanations
Start Practicing Now