English

Find the optimal sequence that minimizes total time required to complete the following jobs in the order ABC. The processing times are given in hrs. - Mathematics and Statistics

Advertisements
Advertisements

Question

Find the optimal sequence that minimizes total time required to complete the following jobs in the order ABC. The processing times are given in hrs.

Job 1 2 3 4 5
Machine A 5 7 6 9 5
Machine B 2 1 4 5 3
Machine C 3 7 5 6 7
Sum

Solution

Job 1 2 3 4 5
Machine A 5 7 6 9 5
Machine B 2 1 4 5 3
Machine C 3 7 5 6 7

Here min A = 5, max B = 5, min C = 3
Since min A ≥ max B is satisfied, the problem can be converted into a two machine problem.
Let G and H be two fictitious machines such that G = A + B and H=B+C
Then the problem can be written as

Job 1 2 3 4 5
Machine G 7 8 10 14 8
Machine H 5 8 9 11 10

Observe that Min (G, H) = 5, corresponds to Job 1 on machine H.
∴ Job 1 is placed last in sequence.

        1

Then the problem reduces to

Job 2 3 4 5
Machine G 8 10 14 8
Machine H 8 9 11 10

Now, Min (G, H) = 8, corresponds to Job 2 on machine G as well as on machine H and Job 5 on machine G.
∴ Job 2 and 5 are placed either first or second in the sequence OR Job 5 is placed first and Job 2 is placed second last in the sequence.

2 5     1

                                                 OR

5 2     1

                                                OR

5     2 1

Then the problem reduces to

Job 3 4
Machine G 10 14
Machine H 9 11

Now, Min (G, H) = 9, corresponds to job 3 on machine H.
∴ Job 3 is placed either second last or third last and job 4 on remaining in the sequence.

2 5 4 3 1

                                            OR

5 2 4 3 1

                                           OR

5 4 3 2 1

∴ We consider the optimal sequence as 2 – 5 – 4 – 3 – 1
Total time elapsed

Job Machine
A
Machine
B
Machine
C
In Out In  Out In  Out
2 (7, 1, 7) 0 7 7 8 8 15
5 (5, 3, 7) 7 12 12 15 15 22
4 (9, 5, 6) 12 21 21 26 26 32
3 (6, 4, 5) 21 27 27 31 32 37
1 (5, 2, 3) 27 32 32 34 37 40

Total elapsed time = 40 hrs
Idle time for Machine A = 40  32 = 8 hrs
Idle time for Machine B = (40  34) + 7 + 4 + 6 + 1 + 1 = 25 hrs
Idle time for Machine C = 8 + 4 = 12 hrs.

shaalaa.com
Finding an Optimal Sequence
  Is there an error in this question or solution?
Chapter 7: Assignment Problem and Sequencing - Exercise 7.2 [Page 126]

APPEARS IN

Balbharati Mathematics and Statistics 2 (Commerce) [English] 12 Standard HSC Maharashtra State Board
Chapter 7 Assignment Problem and Sequencing
Exercise 7.2 | Q 6.2 | Page 126

RELATED QUESTIONS

A publisher produces 5 books on Mathematics. The books have to go through composing, printing and binding done by 3 machines P, Q, R. The time schedule for the entire task in proper unit is as follows.

Book A B C D E
Machine P 4 9 8 6 5
Machine Q 5 6 2 3 4
Machine R 8 10 6 7 11

Determine the optimum time required to finish the entire task.


In sequencing, an optimal path is one that minimizes _______.


If job A to D have processing times as 5, 6, 8, 4 on first machine and 4, 7, 9, 10 on second machine then the optimal sequence is : ______.


Solve the following problem :

Consider the problem of assigning five operators to five machines. The assignment costs are given in following table.

Operator Machine
1 2 3 4 5
A 6 6 3 7
B 8 5 3 4 5
C 10 4 6 4
D 8 3 7 8 3
E 7 6 8 10 2

Operator A cannot be assigned to machine 3 and operator C cannot be assigned to machine 4. Find the optimal assignment schedule.


Solve the following problem :

A chartered accountant’s firm has accepted five new cases. The estimated number of days required by each of their five employees for each case are given below, where - means that the particular employee cannot be assigned the particular case. Determine the optimal assignment of cases of the employees so that the total number of days required to complete these five cases will be minimum. Also find the minimum number of days.

Employee Cases
I II III IV V
E1 6 4 5 7 8
E2 7 8 6 9
E3 8 6 7 9 10
E4 5 7 4 6
E5 9 5 3 10

Choose the correct alternative:

In sequencing, an optimal path that minimizes ______


Book A B C D
Printing 5 8 10 7
Data Entry 7 4 3 6

The optimum sequence for the above data is ______


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

Machines↓\Jobs→ 1 2 3 4 5
M1 6 8 4 5 7
M2 3 7 6 4 16

Determine the optimal sequence of jobs and total elapsed time. Also, find the idle time for two machines.


Six jobs are performed on Machines M1 and M2 respectively. Time in hours taken by each job on each machine is given below:

Jobs `→` A B C D E F
Machines `↓`
M1 3 12 5 2 9 11
M2 8 10 9 6 3 1

Determine the optimal sequence of jobs and find total elapsed time. Also find the idle time for machines M1 and M2.

Solution:

Given jobs can be arranged in optimal sequence as,

D A C B E F

 

Jobs Machine M1 Machine M2
  In Out In Out
D 0 2 `square` 8
A 2 5 8 16
C 5 10 16 25
B 10 22 25 35
E 22 31 35 38
F 31 42 `square` 43

Total Elapsed time = `square` hrs.

Idle time for Machine M1 = 43 – 42 = 1 hour.

Idle time for Machine M2 = `square` hrs.


Share
Notifications

Englishहिंदीमराठी


      Forgot password?
Use app×