Chapter 7 Assignment Problem and Sequencing Miscellaneous Exercise 7 Solutions

(c) Both (a) and (b)

(b) DBCA

(c) to find the sequence in which jobs on hand are to be processed to minimize the total time required for processing the jobs

(d) (n!)m

(b) Hungarian method

(d) The time of passing depends on the order of machining

(a) Converting all profits to opportunity losses

(a) 1 – C, 2 – B, 3 – D, 4 – A

(d) Both (a) and (b)

(c) Number of rows is equal to number of columns

(a) Square matrix

(a) Dummy column is added

(b) A – B – C

(b) Number of jobs to equal number of persons at minimum cost

the number of rows is not equal to the number of columns

balanced

square matrix

square

zero

Total elapsed time

Idle time

maximum

Answer: multiple

A – D – B – C

False

True

False

True

False

True

True

False

True

False

The hr matrix is given by Subtracting row minimum from all values in that row we get Subtracting column minimum from all values in that column we get The minimum no. of lines covering ail the zeros (4) is equal to the order of the matrix (4) ∴ The assignment is possible. The assignment is A → I, B → III, C → II, D → IV For the minimum hrs. take the corresponding value from the hr matrix. Minimum hrs = 7 + 3 + 18 + 9 = 37 hrs

The distance matrix is given by Subtracting row minimum from all values in that row we get Subtracting column minimum from each value in that column we get The number of lines covering all the zeros (3) is less than the order of the matrix (5) so the assignment is not possible. The modification is required. The minimum uncovered value (15) is subtracted from uncovered values and added to the values at the intersection. The numbers on the lines remain the same. We get The minimum lines covering all the zeros (4) are less than the order of the matrix (5) so the assignment is not possible. The modification is required the minimum uncovered value (5) is subtracted from uncovered values and added to the values at the intersection. The numbers on the lines remain the same we get The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) So assignment is possible. The assignment is A → II, B → III, C → V, D → I, E → IV Total minimum distance is = 120 + 120 + 175 + 40 + 70 = 525 kms.

As it is a maximization problem so we need to convert it into a minimization problem. Subtracting all the values from the maximum value (19) we get Also, it is an unbalanced problem so we need to add a dummy row (E) with all values zero, we get Subtracting row minimum from all values in that row we get Subtracting column minimum from all values in that column we get the same matrix The minimum number of lines covering all the zero (4) is less than the order of the matrix (5) So assignment is not possible. The modification is required. The minimum uncovered value (2) is subtracted from the uncovered values and added to the values at the intersection. The values on the lines remain the same. We get The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so the assignment is not possible. The modification is required. The minimum uncovered value (1) is subtracted from the uncovered value and added to the values at the intersection. The values on the lines remain the same. We get The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible. The assignment is A → V, B → II, C → IV, D → III, E → I No salesman goes to I as E is a dummy row. For the maximum value take the corresponding values from the original matrix. We get Maximum value = 15 + 19 + 14 + 17 + 0 = 65 units

This is a maximizing problem. To convert it into minimizing problem subtract all the values of the matrix from the maximum (largest) value (39) we get Also as it is an unbalanced problem so we have to add a dummy column (T) with all the values as zero. We get Subtracting row minimum from all values in that row we get the same matrix Subtracting column minimum from all values in that column we get The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so assignments are not possible. The modification is required. The minimum uncovered value (1) is subtracted from the uncovered values and added to the values at the intersection. The values on the lines remain the same. We get The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible. So I → S, II → T, III → Q, IV → P, V → R. As T is dummy manager II is not given any city. To find the maximum sales we take the corresponding value from the original matrix Total maximum sales = 35 + 39 + 36 + 35 = 145 tons

This is a restricted assignment problem, so we assign a very high cost (oo) to the prohibited cells we get Subtracting row minimum from all values in that row we get. Subtracting column minimum from all values in that column we get As the minimum number of lines covering all the zeros (4) is equal to the order of the matrix (5) so the assignment is not possible. The modification is required. The minimum uncovered value (2) is subtracted from all the uncovered values and added to the values at the intersection. The values on the lines remain the same. We get As the minimum number of lines covering all the zeros (5) is equal to the order of the matrix, assignment is the possible So A → 4, B → 3, C → 2, D → 1, E → 5 For the minimum cost take the corresponding values from the cost matrix we get Total minimum cost = 3 + 3 + 4 + 3 + 7 = 20 units

This is a restricted assignment problem so we assign a very high cost (∞) to all the prohibited cells. The day matrix becomes Subtracting row minimum from all values in that row we get Subtracting column minimum from all values in that column we get The minimum number of lines covering all the zeros (4) is less than the order of the matrix (5) so the assignment is not possible, The modification is required. The minimum uncovered value (1) is subtracted from all the uncovered values and added to the values at the intersection. The values on the lines remain the same, we get The minimum number of lines covering all the zeros (5) is equal to the order of the matrix (5) so the assignment is possible. So E1 → I, E2 → IV, E3 → II, E4 → V, E5 → III To find the minimum number of days we take the corresponding values from the day matrix. Total minimum number of days = 6 + 6 + 6 + 6 + 3 = 27 days

Let A = cutting and B = sewing. So we have Observe min {A, B} = 2 for item 1 for B. The problem reduces to Now min {A, B} = 3 for item 3 for A The problem reduces to New min {A, B} = 4 for item 4 for A. The problem reduces to Now min(A, B} = 5 for item 6 for B The problem reduces to Now min {A, B} = 6 for item 5 for A and item 2 for B Now only 7 is left ∴ The optimal sequence is Worktable Total elapsed time = 46 hrs Idle time for A (cutting) = 46 – 44 = 2 hrs Idle time for B (Sewing) = 4 hrs

Let A = lathe and B = surface grinder. We have Observe min {A, B} = 1 for job II for A The problem reduces to Now min {A, B} = 2 for job IV for A The problem reduces to Now min {A, B} = 3 for job I for B The problem reduces to Now min {A, B} = 5 for jobs III and V for A ∴ We have two options or We take the first one. Worktable Total elapsed time = 21 hrs Idle time for A (lathe) = 21 – 17 = 4 hrs Idle time for B (surface grinder) = 3 hrs

Observe min {A, B} = 3 for job VII on B. The problem reduces to Now min {A, B} = 4 for job IV on B. The problem reduces to Now min {A, B} = 5 for job III & V on A. we have two options or We take the first one The problem reduces to Now min {A, B} = 5 for job II on A The problem reduces to Now min {A, B} = 7 for a job I on B and for job VI on A ∴ The optional sequence is Worktable Total elapsed time = 55 units Idle time for A = 55 – 52 = 3 units Idle time for B = 9 units.

Min A = 12, Max B = 12 As min A ≥ max B. The problem can be converted into two machine problems. Let G and H be two fictitious machines such that G = A + B and H = B + C, We get Now min {G, H} = 16 for type 3 on G The problem reduces to Min (G, H} = 18 for type 1, 4 & 5 on H We have more than one option, we take Now only type 2 is left. ∴ The optional sequence is Worktable Total elapsed time = 102 hours Idle time for A = 102 – 84 = 18 hours Idle time for B = 54 + (102 – 94) = 62 hours Idle time for C = 38 hours

The time matrix is Min A = 8, Max B = 8, as min A ≥ max B. 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 we get Observe min (G, H} = 12 for job 2 on H The problem reduces to Now min {G, H} = 14 for job 3 on G and job 4 on H Now only job 1 is left. ∴ The optimal sequence is Worktable Total elapsed time = 74 min Idle time for A (shapping) = 74 – 62 = 12 min Idle time for B (Drilling) = 47 + (74 – 70) = 51 min Idle time for C (trapping) = 31 min