Five jobs are performed first on machine $M_1$ and then on machine $M_2$. Time taken in hours by each job on each machine is given below: | Machines \\ Jobs | 1 | 2 | 3 | 4 | 5 | | --- | --- | --- | --- | --- | --- | | $M_1$ | 6 | 8 | 4 | 5 | 7 | | $M_2$ | 3 | 7 | 6 | 4 | 16 | Determine the optimal sequence of jobs and total elapsed time. Also find the idle time for machine $M_2$.

> > [!TLDR] > Johnson's rule gives the sequence $3, 5, 2, 4, 1$. Tabulating in/out times, $M_2$ finishes at hour $41$ (total elapsed time), and $M_2$ is idle for $4 + 1 = 5$ hours. > > **Apply Johnson's rule.** Repeatedly pick the smallest time in the table: if it is on $M_1$, schedule that job as early as possible; if on $M_2$, as late as possible. > > - Smallest is $3$ ($J_1$ on $M_2$) → place $J_1$ **last**. > - Next $4$: $J_3$ on $M_1$ → place **first**; $J_4$ on $M_2$ → place next-to-last. > - Next $7$: $J_5$ on $M_1$ → next front slot; $J_2$ on $M_2$ → next back slot. > > Sequence: $\;3 \to 5 \to 2 \to 4 \to 1$. > > **In–out timings:** > > | Job | $M_1$ in–out | $M_2$ in–out | > | --- | --- | --- | > | 3 | $0-4$ | $4-10$ | > | 5 | $4-11$ | $11-27$ | > | 2 | $11-19$ | $27-34$ | > | 4 | $19-24$ | $34-38$ | > | 1 | $24-30$ | $38-41$ | > > $M_2$ starts a job only after $M_1$ finishes it **and** $M_2$ is free (e.g. job 5 waits until $t = 11$). > …

Five jobs are performed first on machine M₁ and then on machine M₂. Time taken in hours by each job on each ma

Question 31 of 32

Five jobs are performed first on machine $M_1$ and then on machine $M_2$ . Time taken in hours by each job on each machine is given below:

Machines \ Jobs	1	2	3	4	5
$M_1$	6	8	4	5	7
$M_2$	3	7	6	4	16
Determine the optimal sequence of jobs and total elapsed time. Also find the idle time for machine $M_2$ .

Maharashtra MsbshseMaharashtra HSC (MSBSHSE) Board 2020Subjective· 4mImportance★★★★★

97% · 31/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 →

Johnson's rule gives the sequence $3, 5, 2, 4, 1$ . Tabulating in/out times, $M_2$ finishes at hour $41$ (total elapsed time), and $M_2$ is idle for $4 + 1 = 5$ hours.

Apply Johnson's rule. Repeatedly pick the smallest time in the table: if it is on $M_1$ , schedule that job as early as possible; if on $M_2$ , as late as possible.

Smallest is $3$ ( $J_1$ on $M_2$ ) → place $J_1$ last.
Next $4$ : $J_3$ on $M_1$ → place first; $J_4$ on $M_2$ → place next-to-last.
Next $7$ : $J_5$ on $M_1$ → next front slot; $J_2$ on $M_2$ → next back slot.

Sequence: $\;3 \to 5 \to 2 \to 4 \to 1$ .

In–out timings:

Job	$M_1$ in–out	$M_2$ in–out
3	$0-4$	$4-10$
5	$4-11$	$11-27$
2	$11-19$	$27-34$
4	$19-24$	$34-38$
1	$24-30$	$38-41$

$M_2$ starts a job only after $M_1$ finishes it and $M_2$ is free (e.g. job 5 waits until $t = 11$ ).

…

Start your 14-day free trial to unlock the full solution →

←Previous questionQ17 — Determine the optimal sequence of jobs that minimizes the total elapse…→Next questionQ19 — A computer centre has 4 expert programmers. The centre needs four appl…

🎓Unlock everything free for 14 days

Unlock everything free for 14 days