Given Data
| Job | Machine 1 (M1) | Machine 2 (M2) |
|---|---|---|
| Job 1 | 4 | 7 |
| Job 2 | 6 | 3 |
| Job 3 | 2 | 3 |
| Job 4 | 7 | 7 |
| Job 5 | 8 | 6 |
Step 1: Apply Johnson’s Rule
Step 1: Find the smallest processing time
Smallest time = 2 (Job 3 on M1)
👉 Since it is on Machine 1, place Job 3 at the beginning.
Sequence:
[ Job 3 _ _ _ _ ]
Remove Job 3.
Step 2: Remaining jobs
| Job | M1 | M2 |
|---|---|---|
| Job 1 | 4 | 7 |
| Job 2 | 6 | 3 |
| Job 4 | 7 | 7 |
| Job 5 | 8 | 6 |
Smallest time = 3 (Job 2 on M2)
👉 Since it is on Machine 2, place Job 2 at the end.
Sequence:
[ Job 3 _ _ _ Job 2 ]
Remove Job 2.
Step 3: Remaining jobs
| Job | M1 | M2 |
|---|---|---|
| Job 1 | 4 | 7 |
| Job 4 | 7 | 7 |
| Job 5 | 8 | 6 |
Smallest time = 4 (Job 1 on M1)
👉 On Machine 1 → place next from the start.
Sequence:
[ Job 3 Job 1 _ _ Job 2 ]
Remove Job 1.
Step 4: Remaining jobs
| Job | M1 | M2 |
|---|---|---|
| Job 4 | 7 | 7 |
| Job 5 | 8 | 6 |
Smallest time = 6 (Job 5 on M2)
👉 On Machine 2 → place from the end.
Sequence:
[ Job 3 Job 1 _ Job 5 Job 2 ]
Remove Job 5.
Step 5: Only Job 4 left
Place in remaining position.
✅ Optimal Sequence
Job 3→Job 1→Job 4→Job 5→Job 2
Step 2: Compute Total Elapsed Time (Makespan)
Now we calculate completion times.
| Job | M1 Start–Finish | M2 Start–Finish |
|---|---|---|
| J3 | 0 – 2 | 2 – 5 |
| J1 | 2 – 6 | 6 – 13 |
| J4 | 6 – 13 | 13 – 20 |
| J5 | 13 – 21 | 21 – 27 |
| J2 | 21 – 27 | 27 – 30 |
✅ Total Elapsed Time (Makespan)
Final Answer
Optimal Job Sequence:
J3 → J1 → J4 → J5 → J2
Minimum Total Elapsed Time:
30 units