Five jobs must each be processed first on Machine $M_1$ and then on Machine $M_2$. The processing times (in hours) are:

| Job | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| $M_1$ | 3 | 8 | 5 | 7 | 4 |
| $M_2$ | 6 | 3 | 2 | 8 | 5 |

Find the optimal sequence, the total elapsed

Question

Five jobs must each be processed first on Machine $M_1$ and then on Machine $M_2$. The processing times (in hours) are:

| Job | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| $M_1$ | 3 | 8 | 5 | 7 | 4 |
| $M_2$ | 6 | 3 | 2 | 8 | 5 |

Find the optimal sequence, the total elapsed time and the idle time of each machine.

Accepted Answer

**Step 1 — Apply Johnson's rule.**
- Smallest time overall $= 2$ (job $3$, on $M_2$) $	o$ place job $3$ **last**: $(\;-,-,-,-,3\;)$.
- Next smallest $= 3$: job $1$ on $M_1$ $	o$ **first**; job $2$ on $M_2$ $	o$ **last available** (just before $3$): $(\;1,-,-,2,3\;)$.
- Remaining jobs $4,5$: smallest $= 4$ (job $5$, $M_1$) $	o$ earliest free slot; then job $4$ ($M_1 = 7$) $	o$ next free slot: $(\;1,5,4,2,3\;)$.

**Optimal sequence: $1 	o 5 	o 4 	o 2 	o 3$.**

**Step 2 — In/out-time table.** On $M_2$, in-time $= \max(M_1$ out-time, previous $M_2$ out-time$)$.

| Job | $M_1$ in | $M_1$ out | $M_2$ in | $M_2$ out |
|---|---|---|---|---|
| 1 | 0 | 3 | 3 | 9 |
| 5 | 3 | 7 | 9 | 14 |
| 4 | 7 | 14 | 14 | 22 |
| 2 | 14 | 22 | 22 | 25 |
| 3 | 22 | 27 | 27 | 29 |

**Step 3 — Read the results.**
- **Total elapsed time** $=$ last $M_2$ out-time $= \mathbf{29}$ **hours**.
- $M_1$ processing total $= 3+4+7+8+5 = 27$, so **$M_1$ idle** $= 29 - 27 = 2$ h. …

🎓Unlock everything free for 14 days

Unlock everything free for 14 days