Determine the optimal sequence of jobs that minimizes the total elapsed time for the data given below (processing time on machines is given in hours). Also find the total elapsed time and the idle time for three machines.
| Jobs | I | II | III | IV | V | VI | VII |
|---|---|---|---|---|---|---|---|
| Machine A | 3 | 8 | 7 | 4 | 9 | 8 | 7 |
| Machine B | 4 | 3 | 2 | 5 | 1 | 4 | 3 |
| Machine C | 6 | 7 | 5 | 11 | 5 | 6 | 12 |
| Solution: | |||||||
| Here min A = 3, min C = 5, Max B = 5. Since Min C ≥ max B is satisfied, the problem can be converted into a two-machine problem. | |||||||
| Let G and H be two fictitious machines | |||||||
| ∴ G = A + B, H = B + C | |||||||
| The above problem can be written as: | |||||||
| Jobs | I | II | III | IV | V | VI | VII |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Machine G | 7 | 11 | 9 | 9 | 10 | 12 | 10 |
| Machine H | 10 | 10 | 7 | 16 | 6 | 10 | 15 |
| Using the optimal sequence algorithm, the following sequence can be obtained. | |||||||
| VI | II | ||||||
| --- | --- | --- | --- | --- | --- | --- | |
| Work table: | |||||||
| Jobs | Machine A | Machine B | Machine C | ||||
| --- | --- | --- | --- | --- | --- | --- | |
| In | Out | In | Out | In | Out | ||
| I | 0 | 3 | 3 | 7 | 7 | 13 | |
| IV | 3 | 7 | 7 | 12 | 13 | 24 | |
| 7 | 14 | 14 | 17 | 24 | 36 | ||
| VI | 14 | 22 | 22 | 26 | 36 | 42 | |
| II | 22 | 30 | 30 | 33 | 49 | ||
| 30 | 37 | 37 | 39 | 49 | 54 | ||
| V | 37 | 46 | 46 | 47 | 54 | 59 | |
| ∴ Total elapsed time is = 59 hrs. | |||||||
| Idle time for machine A = hrs | |||||||
| Idle time for machine B = hrs | |||||||
| Idle time for machine C = 7 hrs. |
You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.
Start your 14-day free trial to unlock the full solution →As , reduce to and apply Johnson's rule. Optimal sequence ; total elapsed time hrs; idle times , , hrs.
Step 1 — Check the reduction condition. For the three-machine problem, , , . Since , the problem can be converted into an equivalent two-machine problem with fictitious machines and :
| Jobs | I | II | III | IV | V | VI | VII |
|---|---|---|---|---|---|---|---|
| 7 | 11 | 9 | 9 | 10 | 12 | 10 | |
| 10 | 10 | 7 | 16 | 6 | 10 | 15 |
Step 2 — Johnson's rule on . Pick the smallest time; if it is under schedule that job as early as possible, if under schedule it as late as possible.
- Smallest is (, in ) last.
- Next : first; next-to-last.
- Next : second.
- Next : third; then toward end; toward end.
Optimal sequence: .
Step 3 — Work table (In/Out on the real machines A, B, C).
| Job | A In | A Out | B In | B Out | C In | C Out |
|---|---|---|---|---|---|---|
| I | 0 | 3 | 3 | 7 | 7 | 13 |
| IV | 3 | 7 | 7 | 12 | 13 | 24 |
| VII | 7 | 14 | 14 | 17 | 24 | 36 |
Unlock everything free for 14 days
- Full step-by-step solutions
- Concept-first explanations
- Methods, shortcuts & mistakes
- PYQ mapping + timed mock tests
Full access for 14 days. No credit card required.