Assignment Problems - Operations Research PDF

Preview

Summary

Download Assignment Problems - Operations Research PDF

Description

Assignment Problems - OPERATIONS RESEARCH

ASSIGNMENT PROBLEM Introduction: The Assignment Problem is a special case of Transportation Problem in which the objective is to assign the number of origins to the equal number of destinations at a minimum cost or minimum time. The units available at each origin and units demanded at each destination are equal to 1.

Mathematical Form of an Assignment Problem: Consider a problem of assignment of ‘n’ workers to ‘n’ jobs, so as to minimize the overall cost or time. In such a way that each worker can associate with one and only one job. The cost matrix Cij is given as follows: J1

J2

……….

JN

AVAILABLE

W1

C11

C12

……….

C1n

1

W2

C21

C22

……….

C2n

1

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Wn

Cn1

Cn2

……….

Cnn

1

Required

1

1

………..

1

The Mathematical Formulation of the Assignment Problem is: Min Z = ∑∑Cij * Xij i j Subject to Constraints: ∑Xij = 1 i ∑Xij =1 J Types of Assignment Problems:

For all, Xij ≥ 0

The assignment problem is classified into “Balanced assignment problem” and “Un-Balanced assignment problem”. If the number of rows (jobs) is equal to the number of columns (Workers), then the problem is termed as a “Balanced Assignment Problem”; otherwise, an “Un-Balanced Assignment Problem”. If the problem is unbalanced, like an unbalanced transportation problem, then necessary number of dummy row(s)/column(s) is added such that the cost matrix is a square matrix. The values for the entries in the dummy row(s)/column(s) are assumed to be zero. Under such a condition, while implementing the solution, the dummy row(s) or job(s) (column(s) or Worker(s)) will not have assignment(s).

HUNGARIAN METHOD: An assignment problem can be easily solved by applying Hungarian Method which consists of two phases. In the first phase, row reductions and column reductions are carried out. In the second phase, the solution is optimized on iterative basis. PHASE-1: Row and Column reductions Step 1: Consider the given cost matrix and Obtain the next matrix by subtracting the minimum value of the each row from the entries of that row. Step 2: Obtain the next matrix by subtracting the minimum value of each column from the entries of that column. Now, treat this matrix as the input for phase-2.

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Assignment Problems - OPERATIONS RESEARCH PHASE-2: Optimization of the Problem Step 3: Draw a minimum number of lines to cover all the zeros of the matrix. The Procedure for drawing minimum number of lines involves the following steps. Row Scanning:  Starting from the first row, ask the following question. Is there exactly one zero in that row? If yes, mark a square around that zero entry and draw a vertical line passing through that zero; otherwise skip that row.  After scanning the last row, check whether all the zeros are covered with lines. If yes, go to step (4); otherwise, do column scanning Column Scanning:  Starting from the first column, ask the following question: Is there exactly one zero in that column? If yes, mark a square around that zero entry and draw a horizontal line passing through that zero; otherwise, skip that column.  After scanning the last column, check whether all the zeros are covered with lines. If yes, go to step (4); otherwise, do row scanning. Step 4: Check whether the number of squares marked is equal to the number of rows of the matrix. If yes, go to step (7); otherwise go to step (5). Step 5: Identify the minimum value of the undeleted cell values. Obtain the next matrix by following the steps mentioned below:  Copy the entries on the lines but not on the intersection points of the present matrix as such without any modification to the corresponding positions of the next matrix.  Copy the entries at the intersection points of the present matrix after adding the minimum undeleted cell value to the corresponding positions of the next matrix.  Subtract the minimum undeleted cell value from all the undeleted cell values and then copy them to the corresponding positions of the next matrix. Step 6: Go to Step (3) Step 7: Treat the solution as marked by the squares as the optimal solution. Note: While performing step (3), sometimes it will repeat endlessly when the number of zeros in the applicable rows as well as columns is more than one. Under such a situation, one should mark squares on diagonally opposite cells having zeros. This means multiple optimal solutions exist.

PROBLEMS ON ASSIGNTMENT (HUNGARIAN METHOD) PROBLEMS: 1) Solve the following Assignment problem:

A B C D

I

II

III

IV

12 18 44 23

30 33 25 30

21 9 24 28

15 31 21 14

Sol) Select the smallest element in each row and subtract it from every element of that row. Step-1: Row-wise: Here, 12, 9, 21, 14 are the smallest elements of 1st, 2nd, 3rd, 4th rows respectively. By subtracting these respective elements from every element of the respective row, we get the matrix as below: I II III IV A 0 18 9 3 B 9 24 0 22 C 23 4 3 0

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Assignment Problems - OPERATIONS RESEARCH D 9 16 14 0 Step-2: Column-wise: Now, select the smallest element in column and subtract it from each element of that column in the reduced above matrix. Here, columns I, II, III, IV have 0, 4, 0, 0 as the smallest elements respectively. Subtracting these smallest elements from every element of the column, we get the matrix as follows: I II III IV A 0 14 9 3 B 9 20 0 22 C 23 0 3 0 D 9 12 14 0 Step-3: (a) Starting with row ‘1’ of the matrix, we examine the rows one by one until a row containing exactly single zero elements are found. We make an assignment indicated by o that cell. Then we cross all other zeros in the column in which the assignment was made. This eliminates the possibility of making further assignments in that column. (b) When the set of rows has been completely examined, an identical procedure is applied successfully to columns. Starting with column ‘1’, we examine all the columns until a column containing exactly one remaining zero is found. We make an assignment in that position and cross other zeros in the row in which the assignments was made. (c) We continue these successive operations on rows and columns until all zeros have been either assigned or crossed out. Since the number of assignments made is equal to the number of rows/columns. Then we have obtained the optimum solution. The complete set of assignments of subordinates to perform different tasks along with their respective man hours is as follows: I A B

9

C

23

II

III

IV

14

9

3

20 3 12

D

22 0

14

9 Hence, the departmental head should assign the task to his subordinates as given above and the total minimum time required is: A  I, B  III, C  II, D  IV = 12 + 9 + 21 14 = 56 Therefore, the minimum assignment cost is Rs.56/-

MACHINES

2) A certain equipment needs five repair jobs which have to be assigned to five machines. The estimated time (in hrs) that each mechanic requires to JOBS complete the repair job is given in the following J1 J2 J3 J4 J5 table: 7 5 9 8 11 M1 9 12 7 11 10 M2 8 5 4 6 9 M3 7 3 6 9 5 M4 4 6 7 5 11 M5

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Step-2: Column-wise: minimum element in subtract this element that column. The is shown below:

MACHINES

Step-1: Row-Wise: element in each row and from every element in reduced matrix is shown

MACHINES

Assuming that each assigned at only one minimum time Sol) Given that,

MACHINES

Assignment Problems - OPERATIONS RESEARCH

M1 M2 M3 M4 M5

J1 7 9 8 7 4

JOBS J2 J3 5 9 12 7 5 4 3 6 6 7

J4 8 11 6 9 5

J5 11 10 9 5 11

M1 M2 M3 M4 M5

J1 2 2 4 4 0

JOBS J2 J3 0 4 5 0 1 0 0 3 2 3

J4 3 4 2 6 1

J5 6 3 5 2 7

M1 M2 M3 M4 M5

J1 2 2 4 4 0

JOBS J2 J3 0 4 5 0 1 0 0 3 2 3

J4 2 3 1 5 0

J5 4 1 3 0 5

mechanic can be job. Determine the assignment.

Select the minimum subtract that element that row. The resultant below:

Next, we select the each column and from every element in resultant reduced matrix

Step-3: Now, check for the rows in which there is only one zero and make the assignment in those rows and strike out all other zeros in its column. Then, also check for the column in which there is only one zero and make the assignment in those columns and strike out all other zeros in its rows. After that draw the lines on unmarked rows and columns.

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Assignment Problems - OPERATIONS RESEARCH

J1

J2

JOBS J3

J4

J5

4

2

4

2

0

M1 MACHINES

2 4

M2 M3

1 3

0

0

M4

4

0

4

2 5

Since, there are 2 4 0 5 M5 only 4 lines which is less than the number of rows/columns, i.e., 4 < 5. The current solution is not an optimum solution. Now, choose the smallest cost element in the uncovered elements and add the remaining at point of intersection of line. The remaining element on the lines remains ASSIGN JOB TO COST (RS.) unchanged. MACHINES M1 J1 5 M2 J2 7 M3 J3 6 M4 J4 5 M5 J5 4 Minimum total cost Rs.27/-

MACHINES

Hence, the solution is:

J2

M1

J1 2

M2

2

5

M3

4

1

M4

4

M5

JOBS J3 4

optimum J4 2

J5 4

3

1

0

1

3

0

3

5

2

3

0

5

UNBALANCED ASSIGNMENT PROBLEM: 1) For the following problem, find the best way of assigning the repair work to contractors.

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

CONTRACTOR S

Assignment Problems - OPERATIONS RESEARCH COST OF REPAIR R1 R2 R3 9 14 19 7 17 20 9 18 21 10 12 18 10 15 21

C1 C2 C3 C4 C5

R4 15 29 18 19 16

Sol) Given that, CONTRACTORS

COST OF REPAIR R1 R2 R3 R4 9 14 19 15 C1 7 17 20 29 C2 9 18 21 18 C3 10 12 18 19 C4 10 15 21 16 C5 Since, the given assignment problem is with 5 rows and 4 columns we can say that the given assignment problem is an Unbalanced Assignment Problem.

CONTRACTORS

Hence, we have to add a dummy column with the zero cost of repairing for each contractor to make the problem balanced. Therefore, the newly balanced assignment problem is shown below:

C1 C2 C3 C4 C5

R1 9 7 9 10 10

COST OF PAPER R2 R3 R4 14 19 15 17 20 29 18 21 18 12 18 19 15 21 16

R5 0 0 0 0 0

Step-1:Row-Wise: Now, select the smallest element in each row and subtract that element from all elements of that row. Then the reduced table is as follows:

CONTRACTORS

CONTRACTORS

COST OF PAPER R1 R2 R3 R4 R5 9 14 19 15 0 C1 7 17 20 29 0 C2 9 18 21 18 0 C3 10 12 18 19 0 C4 10 15 21 16 0 C5 Step-2: Column-Wise: Now, select the smallest element in each column and subtract that element from all elements of that column. Then the reduced table is shown below:

C1 C2 C3 C4 C5

COST OF PAPER R1 R2 R3 R4 2 2 1 0 0 5 2 14 2 6 3 4 3 0 0 5 3 3 3 1

R5 0 0 0 0 0

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Assignment Problems - OPERATIONS RESEARCH Step-3: Now, check for the rows in which there is only one zero and make the assignment in those rows and strike out all other zeros in its column. Then, also check for the column in which there is only one zero and make the assignment in those columns and strike out all other zeros in its rows.

R1

R2 2

C1

CONTRACTORS

C2 C3

2

C4

3

C5

3

COST OF PAPER R3 R4 2 1

R5 0

5

2

14

6

3

4

0

5

0

3

1

0

3

0

Step-4: Since number of lines ≠ number of rows/columns, take the smallest cost from occupied cell and subtract it from all unoccupied cells and add that cost to the cells which are intersected with the two lines (both horizontal line and vertical line). Then we get: R1

R2 2

C1

CONTRACTORS

C2 C3

1

C4

3

C5

2

COST OF PAPER R3 R4 2 1

R5 1

5

2

14

5

2

2

0

4

1

2

0

0

2

1

Since, the number of lines ≠ number of rows/columns. Repeat the step-(4) again and again until we the lines and rows/columns get equal.

CONTRACTORS

R1 C1

1

C2 C3

0

C4

3

C5

1

COST OF PAPER R2 R3 R4 1 0 5

2

15

4

1

2

0

5

1

R5

1

1 2

2 0

In the above table, we have seen that the number of lines (5) = number of rows/columns (5). Hence, we obtain the optimum solution Therefore, the minimum assignment cost is = 19 + 7 + 0 12 + 16 = Rs.54/-

PRACTISE PROBLEMS ON HUNGARIAN METHOD: S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Assignment Problems - OPERATIONS RESEARCH

METHODS

1) A methods engineer wants to assign four new methods to three work centers. The assignments of the new methods will increase production and they are given below. If only one method can be assigned to a work center. Determine the optimum assignment. WORK CENTERS A B C 10 7 8 I 8 9 7 II 7 12 6 III IV 10 10 3

JOBS

2) Determine the Optimum solution using Hungarian Method for the given data:

A B C D E

I 10 7 13 12 8

OPERATORS II III IV 12 15 12 16 14 14 14 7 9 10 11 13 13 15 11

V 8 11 9 10 15

PROBLEMS ON “TRAVELLING SALESMAN’S PROBLEM”: 1) A manager of a certain company, based in city 12, is in city 1 to attend a series of business seminars. On his return he wants to reach city 12 by adopting the least-cost route between city 1 and city 12. The cost from moving between cities is given below. (Only certain cities can be reached directly from a given city. For instance only cities 2, 3, 4 can be reached from city 1, cities 5, 6, 7, 8 can be reached directly from city 2 and so on). FROM CITY

TO CITY (FIGURES ARE IN HUNDRED RS.)

2 3 4 5 6 7 8 9 10 11 12 1 5 3 6 2 4 3 7 7 3 5 5 3 4 4 7 4 6 3 5 7 6 9 6 6 7 6 8 9 6 7 8 10 8 8 9 9 12 10 8 11 What route should be taken by the manager from city 1 to city 12, so that the cost is the least possible?

Sol)

5

2

9 6

1

3

10

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

7

Assignment Problems - OPERATIONS RESEARCH

12

The given problem is represented in the form of a network for better understanding as shown above. (Figures in squares represent the names of cities 1 to 12 and arrows indicate the route from one city to another city. The cost of the route between the two cities is given below the corresponding arrow). The problem is to determine the least cost route from city 1 to city 12. The problem can be split into five stages (although decision making stages are 1 to 4) as shown in the above network. We now solve it by applying the dynamic programming approach working it backward from the natural end of the problem. Stage 4: Suppose the manager has arrived at stage 4 and further suppose for a moment that he is in city 9. Since there is only one route possible, the minimum cost route is from city 9 to city 12 at a cost of Rs.9 hundred. But suppose the manager finds himself in city 10 in stage 4, and then the minimum cost route is from city 10 to city 12 at a cost of Rs.12 hundred. In case the manager is in city 11 in stage 4 then the minimum cost route is from city 11 to city 12 at a cost of Rs.8 hundred. So if the manager arrives at city 9 or city 10 or city 11 in stage 4 the best policy is to go to city 11 from it since it is only route for him to reach city 12. As such he is in fact not to make any decision when he is stage 4. SOLUTION AT STAGE 4 (OR DECISION AT STAGE 1 I.E., FIRST DECISION) Leaving from Going to Total Accumulated Cost City 9 City 12 9 Hundred Rupees City 10 City 12 12 Hundred Rupees City 11 City 12 8 Hundred Rupees Stage 3: Suppose at stage 3, the manager is in city 5. He can reach city 12 via any of the three cities stated above viz., 9 or 10 or 11. If he decides to visit city 9, 10 or 11 his total cost will be Rs.16, 18, and 17 hundred rupees respectively. Accordingly his choice would be to go to city 9 and then to city 12. Similarly, if he is in city 6 in stage 3 he should next stop in city 11 and then to city 12 for a minimum total cost of Rs.14 hundred. If he is in city 7 then he should stop in city 11 and then should go to city 12 for a minimum total cost of Rs.14 hundred. But if he happens to be in city 8 then he should next go to city 11 and then to city 12 for a minimum total cost of Rs.16 hundred. SOLUTION AT STAGE 3 (OR DECISION AT STAGE 2 I.E., SECOND DECISION) Leaving from Going to Total Accumulated Cost City 6 City 9 16 Hundred Rupees City 6 City 11 14 Hundred Rupees

S. Venkata Siva Kumar, Assistant Professor & COE (PG), St. Joseph’s Degree & PG College

Assignment Problems - OPERATIONS RESEARCH City 7 City 8

City 11 City 11

14 Hundred Rupees 16 Hundred Rupees

Stage 2: Now support at stage 2, the manager is in city 2 from where he can go to city 5 or 6 or 7 or 8 and then to city 12. If he goes to city 12 via city 5 his total costs would be 20 hundred rupees (utilizing the solution reached at stage three as shown in the table above) but if he goes via city 6 his costs would be 17 hundred rupees and these will be respectively 21 hundred and 23 hundred rupees if he decides to go vi...