ReasoningAbility.com

Job Shop Scheduling

Job Shop Scheduling problems involve processing jobs that have different routes through multiple machines (each job may visit machines in a different order). Finding the optimal schedule is NP-hard, but you can calculate lower bounds.

10Worksheets
200+Practice Questions
ExpertDifficulty
4-5 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 Job Shop Scheduling

Job Shop Scheduling problems involve processing jobs that have different routes through multiple machines (each job may visit machines in a different order). Finding the optimal schedule is NP-hard, but you can calculate lower bounds.

Prerequisites

Machine routing Makespan lower bounds Workload calculation Complexity concepts
Why This Matters: Job Shop problems appear in 0-1 questions in Olympiad-level exams and CAT. They test understanding of complexity and bounds.

How to Solve Job Shop Scheduling Problems

1

Step 1: List all jobs with their machine sequences and processing times

2

Step 2: Calculate machine workloads (sum of processing times on each machine)

3

Step 3: Calculate job workloads (sum of processing times for each job)

4

Step 4: Lower bound = max(max(machine workloads), max(job workloads))

5

Step 5: Answer with lower bound (optimal makespan ≥ this value)

Pro Strategy: Lower bound = max( total work on any machine, total work of any job ). Optimal makespan cannot be less than this.

Example Problem

Example: Job1: M1(3)→M2(4); Job2: M2(2)→M1(5). Lower bound on makespan? Solution: Step 1: Machine loads: M1: 3+5=8, M2:4+2=6 → max=8 Step 2: Job loads: J1:7, J2:7 → max=7 Step 3: Lower bound = max(8,7) = 8 Answer: At least 8 units

Pro Tips & Tricks

  • Machine workload = sum of processing times on that machine
  • Job workload = sum of processing times for that job
  • Makespan ≥ max(machine loads, job loads)
  • This is a simple lower bound (not necessarily achievable)
  • For 2-machine job shop, Johnson's Rule works if all jobs have same route

Shortcut Methods to Solve Faster

LB = max( Σ times per machine, Σ times per job )
If one machine is bottleneck, LB = that machine's load
If one job is long, LB = that job's total time

Common Mistakes to Avoid

Assuming lower bound is achievable (often not)
Forgetting that machines can process only one job at a time
Not considering machine order constraints
Using average instead of maximum

Exam Importance

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

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

Ready to Master Job 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