Skip to content
Question 30 of 32
Q.

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.

JobsIIIIIIIVVVIVII
Machine A3874987
Machine B4325143
Machine C675115612
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:
JobsIIIIIIIVVVIVII
------------------------
Machine G71199101210
Machine H101071661015
Using the optimal sequence algorithm, the following sequence can be obtained.
VIII
---------------------
Work table:
JobsMachine AMachine BMachine C
---------------------
InOutInOutInOut
I0337713
IV377121324
□\square71414172436
VI142222263642
II22303033□\square49
□\square303737394954
V374646475459
∴ Total elapsed time is = 59 hrs.
Idle time for machine A = □\square hrs
Idle time for machine B = □\square hrs
Idle time for machine C = 7 hrs.
Maharashtra MsbshseMaharashtra HSC (MSBSHSE) Board 2026Subjective· 4mImportance★★★★★
94% · 30/32 Questions
🔒 Locked · start free trial →

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 min⁡C=5≥max⁡B=5\min C=5\ge \max B=5, reduce to G=A+B, H=B+CG=A+B,\ H=B+C and apply Johnson's rule. Optimal sequence I,IV,VII,VI,II,III,VI,IV,VII,VI,II,III,V; total elapsed time =59=59 hrs; idle times A=13A=13, B=37B=37, C=7C=7 hrs.

Step 1 — Check the reduction condition. For the three-machine problem, min⁡A=3\min A=3, max⁡B=5\max B=5, min⁡C=5\min C=5. Since min⁡C=5≥max⁡B=5\min C=5\ge\max B=5, the problem can be converted into an equivalent two-machine problem with fictitious machines G=A+BG=A+B and H=B+CH=B+C:

JobsIIIIIIIVVVIVII
G=A+BG=A+B71199101210
H=B+CH=B+C101071661015

Step 2 — Johnson's rule on G,HG,H. Pick the smallest time; if it is under GG schedule that job as early as possible, if under HH schedule it as late as possible.

  • Smallest is 66 (VV, in HH) ⇒\Rightarrow VV last.
  • Next 77: G(I)=7⇒IG(I)=7\Rightarrow I first; H(III)=7⇒IIIH(III)=7\Rightarrow III next-to-last.
  • Next 99: G(IV)=9⇒IVG(IV)=9\Rightarrow IV second.
  • Next 1010: G(VII)=10⇒VIIG(VII)=10\Rightarrow VII third; then H(VI)=10⇒VIH(VI)=10\Rightarrow VI toward end; H(II)=10⇒IIH(II)=10\Rightarrow II toward end.

Optimal sequence:   I→IV→VII→VI→II→III→V\;I\to IV\to VII\to VI\to II\to III\to V.

Step 3 — Work table (In/Out on the real machines A, B, C).

JobA InA OutB InB OutC InC Out
I0337713
IV377121324
VII71414172436

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.