We have seven jobs each of which has to go through two machines ${{M}_{1}}$ and ${{M}_{2}}$ in the order ${{M}_{1}}$ to ${{M}_{2}}$. Processing times in hours are given as:
Jobs A B C D E F G Machine ${{M}_{1}}$ 3 12 15 6 10 11 19 Machine ${{M}_{2}}$ 8 10 10 6 12 1 3
Determine a sequence of these jobs that will minimize the total elapsed time ‘T’, and idle time for each machine?
(a) 20 hrs
(b) 21 hrs
(c) 25 hrs
(d) 27 hrs
| Jobs | A | B | C | D | E | F | G |
| Machine ${{M}_{1}}$ | 3 | 12 | 15 | 6 | 10 | 11 | 19 |
| Machine ${{M}_{2}}$ | 8 | 10 | 10 | 6 | 12 | 1 | 3 |
Answer
Verified573.6k+ views
Hint: We start solving the problem by recalling the definition and steps of Johnson’s algorithm for solving these problems. We then find the sequence of jobs done by each machine based on Johnson's algorithm. We then find the starting and ending time of each job by both machines using the steps given in the algorithm. We then find the total elapsed time which is the completion time of all jobs by both machines together. We then find the idle time of both machines by checking the total time that the machines wait for the job to start.
Complete step-by-step solution:
According to the problem, we are given that there are seven jobs each of which has to go through two machines ${{M}_{1}}$ and ${{M}_{2}}$ in the order ${{M}_{1}}$ to ${{M}_{2}}$ and processing times in hours are as given below:
We need to determine the sequence of these jobs so that it will minimize the total elapsed time ‘T’ and we also need to find the idle time for each machine.
We solve this problem by using Johnson's algorithm. Let us recall the steps of Johnson’s algorithm which are as shown below.
Step1: Select the minimum processing times out of all ${{M}_{1}}'s$ and ${{M}_{2}}'s$. If it is of ${{M}_{1}}$, then do that job first. If it is ${{M}_{2}}$, then do that job at last.
Step2: If there is a tie in selecting the minimum of all the processing times, then such a situation is dealt with the following three ways:
(i) If the minimum of all the processing times is one of ${{M}_{1}}'s$ processing times and is equal to one of ${{M}_{2}}'s$ processing times i.e., \[\min \left( {{M}_{{{1}_{i}}}},{{M}_{{{2}_{j}}}} \right)={{M}_{{{1}_{r}}}}={{M}_{{{2}_{s}}}}\] then we do the ${{M}_{{{1}_{r}}}}$ job first and \[{{M}_{{{2}_{s}}}}\] job last.
(ii) If \[\min \left( {{M}_{{{1}_{i}}}},{{M}_{{{2}_{j}}}} \right)={{M}_{{{1}_{r}}}}={{M}_{{{1}_{s}}}}\], then there is a tie for minimum among ${{M}_{1}}'s$ we can select any one of them.
(ii) If \[\min \left( {{M}_{{{1}_{i}}}},{{M}_{{{2}_{j}}}} \right)={{M}_{{{2}_{r}}}}={{M}_{{{2}_{s}}}}\], then there is a tie for minimum among ${{M}_{2}}'s$ we can select any one of them.
Step3: Now, we eliminate the job which has already been assigned from further consideration, and repeat steps 1 and 2 until an optimal sequence is found.
Let us follow these steps and solve our problem.
We can see that the minimum processing time is 1 hour that is related to job F of machine ${{M}_{2}}$. So, we need to perform that job F last of all.
Now, let us check the minimum processing time in the remaining jobs.
We can then see that the minimum processing time is 3 hours which is related to job A of ${{M}_{1}}$ and job G of ${{M}_{2}}$. So, we need to perform job A first of all and job G just before F.
Now, let us check the minimum processing time in the remaining jobs.
We can then see that the minimum processing time is 6 hours which is related to job D of ${{M}_{1}}$ and job D of ${{M}_{2}}$. So, we need to perform job D just after A.
Now, let us check the minimum processing time in the remaining jobs.
We can then see that the minimum processing time is 10 hours which is related to job E of ${{M}_{1}}$ and job B of ${{M}_{2}}$. So, we need to perform job E just after D and job B just before G.
We can see that the only remaining job is C, which is performed between jobs E and B.
We need to know that the job is to be passed to machine \[{{M}_{2}}\] only if the job is completed in machine \[{{M}_{1}}\]. But jobs in machine \[{{M}_{1}}\] can be started with/without completion in machine \[{{M}_{2}}\].
Now, let us find the time at which job A starts and ends in machines \[{{M}_{1}}\] and \[{{M}_{2}}\].
Now, we need to perform D after job A. We can see that job D can be performed immediately after the end of the job A by machine \[{{M}_{1}}\]. So, the starting time of job D by machine \[{{M}_{1}}\] will be 3 hours.
Now, we can see that job D is completed in 9 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is not available for 9 hours. So, the job D starts at 11 hours by machine \[{{M}_{2}}\].
Now, we need to perform E after job D. We can see that job E can be performed immediately after the end of job D by machine \[{{M}_{1}}\]. So, the starting time of job E by machine \[{{M}_{1}}\] will be 9 hours.
Now, we can see that job E is completed in 19 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 19 hours. So, the job E starts at 19 hours by machine \[{{M}_{2}}\].
Now, we need to perform C after job E. We can see that job E can be performed immediately after the end of job E by machine \[{{M}_{1}}\]. So, the starting time of job C by machine \[{{M}_{1}}\] will be 19 hours.
Now, we can see that job C is completed in 34 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 34 hours. So, the job C starts at 34 hours by machine \[{{M}_{2}}\].
Now, we need to perform B after job C. We can see that job B can be performed immediately after the end of job C by machine \[{{M}_{1}}\]. So, the starting time of job D by machine \[{{M}_{1}}\] will be 34 hours.
Now, we can see that job B is completed in 46 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 46 hours. So, job B starts at 46 hours by machine \[{{M}_{2}}\].
Now, we need to perform G after job B. We can see that job G can be performed immediately after the end of job B by machine \[{{M}_{1}}\]. So, the starting time of job G by machine \[{{M}_{1}}\] will be 46 hours.
Now, we can see that job G is completed in 65 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 65 hours. So, job G starts at 65 hours by machine \[{{M}_{2}}\].
Now, we need to perform F after job G. We can see that job F can be performed immediately after the end of job F by machine \[{{M}_{1}}\]. So, the starting time of job F by machine \[{{M}_{1}}\] will be 65 hours.
Now, we can see that job F is completed in 76 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 76 hours. So, job F starts at 76 hours by machine \[{{M}_{2}}\].
We can see that all jobs can be completed in 77 hours which is the required elapsed time ‘T’.
So, the elapsed time T = 77 hours.
Now, we can see that the machine \[{{M}_{1}}\] is not idle except after completing job F. So, the idle time of machine \[{{M}_{1}}\] = $77-76=1hr$.
We can see that the machine \[{{M}_{2}}\] needs to wait for starting jobs E, C, B, G, and F.
So, the idle time for the machine \[{{M}_{2}}\] at each job can be found by subtracting the ending times of the previous job from the starting time of a new job.
We get the idle time of machine \[{{M}_{2}}\] = $\left( 19-17 \right)+\left( 34-31 \right)+\left( 46-44 \right)+\left( 65-56 \right)+\left( 76-68 \right)$.
Idle time of machine \[{{M}_{2}}\] = $2+3+2+9+8=24hrs$.
So, the idle time for both machines together is $24+1=25hrs$.
$\therefore$ The idle time for both machines together is 25hrs. The correct option for the given problem is (c).
Note: We should know that all jobs are independent of each other i.e., job D is not dependent on job A, job E is not independent of job D, and so on. We need to remember that machine \[{{M}_{1}}\] need not wait for machine \[{{M}_{2}}\] to complete the jobs in order to proceed next. We should not make calculation mistakes and confuse while finding the sequence of the proceeding of jobs. Similarly, we can expect problems to find the utilization of machines in the total elapsed time ‘T’.
Complete step-by-step solution:
According to the problem, we are given that there are seven jobs each of which has to go through two machines ${{M}_{1}}$ and ${{M}_{2}}$ in the order ${{M}_{1}}$ to ${{M}_{2}}$ and processing times in hours are as given below:
| Jobs | A | B | C | D | E | F | G |
| Machine ${{M}_{1}}$ | 3 | 12 | 15 | 6 | 10 | 11 | 19 |
| Machine ${{M}_{2}}$ | 8 | 10 | 10 | 6 | 12 | 1 | 3 |
We need to determine the sequence of these jobs so that it will minimize the total elapsed time ‘T’ and we also need to find the idle time for each machine.
We solve this problem by using Johnson's algorithm. Let us recall the steps of Johnson’s algorithm which are as shown below.
Step1: Select the minimum processing times out of all ${{M}_{1}}'s$ and ${{M}_{2}}'s$. If it is of ${{M}_{1}}$, then do that job first. If it is ${{M}_{2}}$, then do that job at last.
Step2: If there is a tie in selecting the minimum of all the processing times, then such a situation is dealt with the following three ways:
(i) If the minimum of all the processing times is one of ${{M}_{1}}'s$ processing times and is equal to one of ${{M}_{2}}'s$ processing times i.e., \[\min \left( {{M}_{{{1}_{i}}}},{{M}_{{{2}_{j}}}} \right)={{M}_{{{1}_{r}}}}={{M}_{{{2}_{s}}}}\] then we do the ${{M}_{{{1}_{r}}}}$ job first and \[{{M}_{{{2}_{s}}}}\] job last.
(ii) If \[\min \left( {{M}_{{{1}_{i}}}},{{M}_{{{2}_{j}}}} \right)={{M}_{{{1}_{r}}}}={{M}_{{{1}_{s}}}}\], then there is a tie for minimum among ${{M}_{1}}'s$ we can select any one of them.
(ii) If \[\min \left( {{M}_{{{1}_{i}}}},{{M}_{{{2}_{j}}}} \right)={{M}_{{{2}_{r}}}}={{M}_{{{2}_{s}}}}\], then there is a tie for minimum among ${{M}_{2}}'s$ we can select any one of them.
Step3: Now, we eliminate the job which has already been assigned from further consideration, and repeat steps 1 and 2 until an optimal sequence is found.
Let us follow these steps and solve our problem.
We can see that the minimum processing time is 1 hour that is related to job F of machine ${{M}_{2}}$. So, we need to perform that job F last of all.
| F |
Now, let us check the minimum processing time in the remaining jobs.
We can then see that the minimum processing time is 3 hours which is related to job A of ${{M}_{1}}$ and job G of ${{M}_{2}}$. So, we need to perform job A first of all and job G just before F.
| A | G | F |
Now, let us check the minimum processing time in the remaining jobs.
We can then see that the minimum processing time is 6 hours which is related to job D of ${{M}_{1}}$ and job D of ${{M}_{2}}$. So, we need to perform job D just after A.
| A | D | G | F |
Now, let us check the minimum processing time in the remaining jobs.
We can then see that the minimum processing time is 10 hours which is related to job E of ${{M}_{1}}$ and job B of ${{M}_{2}}$. So, we need to perform job E just after D and job B just before G.
| A | D | E | B | G | F |
We can see that the only remaining job is C, which is performed between jobs E and B.
| A | D | E | C | B | G | F |
We need to know that the job is to be passed to machine \[{{M}_{2}}\] only if the job is completed in machine \[{{M}_{1}}\]. But jobs in machine \[{{M}_{1}}\] can be started with/without completion in machine \[{{M}_{2}}\].
Now, let us find the time at which job A starts and ends in machines \[{{M}_{1}}\] and \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
Now, we need to perform D after job A. We can see that job D can be performed immediately after the end of the job A by machine \[{{M}_{1}}\]. So, the starting time of job D by machine \[{{M}_{1}}\] will be 3 hours.
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 |
Now, we can see that job D is completed in 9 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is not available for 9 hours. So, the job D starts at 11 hours by machine \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
Now, we need to perform E after job D. We can see that job E can be performed immediately after the end of job D by machine \[{{M}_{1}}\]. So, the starting time of job E by machine \[{{M}_{1}}\] will be 9 hours.
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 |
Now, we can see that job E is completed in 19 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 19 hours. So, the job E starts at 19 hours by machine \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
Now, we need to perform C after job E. We can see that job E can be performed immediately after the end of job E by machine \[{{M}_{1}}\]. So, the starting time of job C by machine \[{{M}_{1}}\] will be 19 hours.
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 |
Now, we can see that job C is completed in 34 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 34 hours. So, the job C starts at 34 hours by machine \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
Now, we need to perform B after job C. We can see that job B can be performed immediately after the end of job C by machine \[{{M}_{1}}\]. So, the starting time of job D by machine \[{{M}_{1}}\] will be 34 hours.
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
| B | 34 | 34+12=46 |
Now, we can see that job B is completed in 46 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 46 hours. So, job B starts at 46 hours by machine \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
| B | 34 | 34+12=46 | 46 | 46+10=56 |
Now, we need to perform G after job B. We can see that job G can be performed immediately after the end of job B by machine \[{{M}_{1}}\]. So, the starting time of job G by machine \[{{M}_{1}}\] will be 46 hours.
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
| B | 34 | 34+12=46 | 46 | 46+10=56 |
| G | 46 | 46+19=65 |
Now, we can see that job G is completed in 65 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 65 hours. So, job G starts at 65 hours by machine \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
| B | 34 | 34+12=46 | 46 | 46+10=56 |
| G | 46 | 46+19=65 | 65 | 65+3=68 |
Now, we need to perform F after job G. We can see that job F can be performed immediately after the end of job F by machine \[{{M}_{1}}\]. So, the starting time of job F by machine \[{{M}_{1}}\] will be 65 hours.
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
| B | 34 | 34+12=46 | 46 | 46+10=56 |
| G | 46 | 46+19=65 | 65 | 65+3=68 |
| F | 65 | 65+11=76 |
Now, we can see that job F is completed in 76 hours by the machine \[{{M}_{1}}\] and machine \[{{M}_{2}}\] is available at 76 hours. So, job F starts at 76 hours by machine \[{{M}_{2}}\].
| Jobs | Machine \[{{M}_{1}}\] | Machine \[{{M}_{2}}\] | ||
| Job starting time | Job ending time | Job starting time | Job ending time | |
| A | 0 | 0+3=3 | 3 | 3+8=11 |
| D | 3 | 3+6=9 | 11 | 11+6=17 |
| E | 9 | 9+10=19 | 19 | 19+12=31 |
| C | 19 | 19+15=34 | 34 | 34+10=44 |
| B | 34 | 34+12=46 | 46 | 46+10=56 |
| G | 46 | 46+19=65 | 65 | 65+3=68 |
| F | 65 | 65+11=76 | 76 | 76+1=77 |
We can see that all jobs can be completed in 77 hours which is the required elapsed time ‘T’.
So, the elapsed time T = 77 hours.
Now, we can see that the machine \[{{M}_{1}}\] is not idle except after completing job F. So, the idle time of machine \[{{M}_{1}}\] = $77-76=1hr$.
We can see that the machine \[{{M}_{2}}\] needs to wait for starting jobs E, C, B, G, and F.
So, the idle time for the machine \[{{M}_{2}}\] at each job can be found by subtracting the ending times of the previous job from the starting time of a new job.
We get the idle time of machine \[{{M}_{2}}\] = $\left( 19-17 \right)+\left( 34-31 \right)+\left( 46-44 \right)+\left( 65-56 \right)+\left( 76-68 \right)$.
Idle time of machine \[{{M}_{2}}\] = $2+3+2+9+8=24hrs$.
So, the idle time for both machines together is $24+1=25hrs$.
$\therefore$ The idle time for both machines together is 25hrs. The correct option for the given problem is (c).
Note: We should know that all jobs are independent of each other i.e., job D is not dependent on job A, job E is not independent of job D, and so on. We need to remember that machine \[{{M}_{1}}\] need not wait for machine \[{{M}_{2}}\] to complete the jobs in order to proceed next. We should not make calculation mistakes and confuse while finding the sequence of the proceeding of jobs. Similarly, we can expect problems to find the utilization of machines in the total elapsed time ‘T’.
Recently Updated Pages
Master Class 10 Computer Science: Engaging Questions & Answers for Success
Master Class 10 General Knowledge: Engaging Questions & Answers for Success
Master Class 10 English: Engaging Questions & Answers for Success
Master Class 10 Social Science: Engaging Questions & Answers for Success
Master Class 10 Maths: Engaging Questions & Answers for Success
Master Class 10 Science: Engaging Questions & Answers for Success
Trending doubts
What is the median of the first 10 natural numbers class 10 maths CBSE
Which women's tennis player has 24 Grand Slam singles titles?
Who is the Brand Ambassador of Incredible India?
Why is there a time difference of about 5 hours between class 10 social science CBSE
Write a letter to the principal requesting him to grant class 10 english CBSE
A moving boat is observed from the top of a 150 m high class 10 maths CBSE