Assignment Problems:SOLUTION OF AN ASSIGNMENT PROBLEM

<< Assignment Problems:MATHEMATICAL FORMULATION OF THE PROBLEM

Queuing Theory:DEFINITION OF TERMS IN QUEUEING MODEL >>

Operations Research (MTH601)

203

Subject to restrictions,

Row restrictions

x11 + x12 + x13 + x14 = 1

for job 1

x21 + x22 + x23 + x24 = 1

for job 2

x31 + x32 + x33 + x34 = 1

for job 3

x41 + x42 + x43 + x44 = 1

for job 4

Column restrictions

x11 + x21 + x31 + x41 = 1

for person 1

x12 + x22 + x32 + x42 = 1

for person 2

x13 + x23 + x33 + x43 = 1

for person 3

x14 + x24 + x34 + x44 = 1

for person 4

xij = 0 or 1

and

In general,

xi1 + xi2 + ... + xin = 1, for i = 1, 2, ..., n

x1j + x2j + ... + xnj = 1, for j = 1, 2, ..., n

and

When compared with a transportation problem, we see that ai = 1 and bj = 1 for all rows and columns, xij = 0 or

We shall not attempt simplex algorithem or the transportation algorithm to get a

solution to an assignment problem. Certain systematic procedure has been devised so as to

obtain the solution to the problem with ease.

SOLUTION OF AN ASSIGNMENT PROBLEM

The solution to an assignment problem is based on the following theorem.

Theorem:

If in an assignment problem we add a constant to every element of a row or column in the

effectiveness matrix then an assignment that minimizes the total effectiveness in one matrix also minimizes the

total effectiveness in the other matrix.

Example:

A works manager has to allocate four different jobs to four workmen. Depending on the

efficiency and the capacity of the individual the times taken by each differ as shown in the table 2. How should

the tasks be assigned one jot to a worker so as to minimize the total man-hours?

Table 2

Worker

Job

203

Operations Research (MTH601)

204

The following steps are followed to find an optimal solution.

Solution:

STEP 1:Consider each row. Select the minimum element in each row. Subtract this smallest element form all

the elements in that row. This results in the table 3.

Table 3

Worker

Job

STEP 2: We subtract the minimum element in each column from all the elements in its column. Thus we obtain

table 4

Table 4

Worker

Job

STEP 3:In this way we make sure that in the matrix each row and each column has atleast one zero element.

Having obtained atleast one zero in each row and each column, we assign starting from first row.

In the first row, we have a zero in (1, A). Hence we assign job 1 to the worker A. This assignment is indicated

by a square . All other zeros in the column are crossed (X) to show that the other jobs cannot be assigned to

worker A as he has already been assigned. In the above problem we do not have other zeros in the first column

Proceed to the second row. We have a zero in (2, C). Hence we assign the job 2 to worker C, indicating by a

square . Any other zero in this column is crossed (X).

Proceed to the third row. Here we have two zeros corresponding to (3, B) and (3, D). Since there is a tie for the

job 3, go to the next row deferring the decision for the present. Proceeding to the fourth row, we have only one

zero in (4, D). Hence we assign job 4 to worker D. Now the column D has a zero in the third row. Hence cross

(3, D). All the assignments made in this way are as shown in table 5.

Table 5

Worker

Job

204

Operations Research (MTH601)

205

STEP 4: Now having assigned certain jobs to certain workers we proceed to the column 1. Since there is an

assignment in this column, we proceed to the second column. There is only one zero in the cell (3, B); we assign

the jobs 3 to worker B. Thus all the four jobs have been assigned to four workers. Thus we obtain the solution to

the problem as shown in the table 6.

Table 6

Worker

Job

The assignments are

Job to Worker

We summarise the above procedure as a set of following rules:

Subtract the minimum element in each row from all the elements in its row to make sure that at least

we get one zero in that row.

Subtract the minimum element in each column from all the elements in its

column

the

above

reduced matrix, to make sure that we get at least one zero in each column.

Having obtained at least one zero in each row and atleast one zero in each column, examine rows

successively until a row with exactly one unmarked zero is found and mark ( ) this zero, indicating

that assignment in made there. Mark (X) all other zeros in the same column, to show that they cannot

be used to make other assignments. Proceed in this way until all rows have been examined. If there is a

tie among zeros defer the decision.

Next consider columns, for single unmarked zero, mark them ( ) and

mark (X) any other unmarked

zero in their rows.

Repeat (c) and (d) successively until one of the two occurs.

205

Operations Research (MTH601)

206

1) There are no zeros left unmarked.

2) The remaining unmarked zeros lie atleast two in each row and column. i.e., they occupy

corners of a square.

If the outcome is (1), we have a maximal assignment. In the outcome (2) we use arbitrary assignments. This

process may yield multiple solutions.

206

Operations Research (MTH601)

207

MULTIPLE SOLUTIONS

Example 1 Given the following matrix, find the optimal assignment.

Solution: Note that all the rows and columns have at least one zero.

Row 1 has a single zero in column 2. So make an assignment, delete (mark X) the second zero in

0 denotes assignment

column 2. This is shown in table 7.

Table 7

Row 2 has a single zero in the first column. So make an assignment and delete the remaining zeros in column 1

as shown in table 8.

Table 8

207

Operations Research (MTH601)

208

Row 3, 4 and 5 have more than a single zero. So we skip these rows and examine the columns. Columns 3 has

three zeros and so omit it. Column 4 has a single zero in row 5. So we make an assignment, deleting the

remaining zeros in row 5. The result is as shown in table 9.

Table 9

Now we have two zeros in rows 3 and 4 in columns 3 and they occupy the corners of a square. An arbitrary

assignment has to be made. If we make an assignment in (3, 3) and delete the remaining zero in row 3 and in

column 3, this leaves one zero in the position (4, 5) and an assignment is made there. Thus we have a solution to

the problem as in table 10.

Table 10

One more assignment (as a solution) is possible in this problem. (i.e.) we could have made an assignment at (3,

5) deleting other zero in the row 3 and zero in column 5 and making the last assignment at (4, 3). This is shown

below in table 11.

208

Operations Research (MTH601)

209

Table 11

All the above markings can be done in a single matrix itself. We need not write the matrix

Remark:

repeatedly. This is done only to clarify the presentation.

HUNGARIAN ALGORITHM

In the two examples above, the first one gave a solution leaving no zeros. It was a case of no ambiguity

and in the second, we had more zeros and the tie was broken arbitrarily. Sometimes if we proceed in the steps

explained above, we get a maximal assignment, which does not contain an assignment in every row or column.

We are faced with a question of how to solve the problem. In such a case, the effectiveness matrix has to be

modified, so that after a finite number of iterations an optimal assignment will be in sight. The following is the

algorithm to solve a problem of this kind and this is known as Hungarian algorithm. The systematic procedure is

explained in different steps and a problem is solved as an illustration.

STEP 1: Starting with a maximal assignment mark (√ ) all rows for which assignments have not been made.

STEP 2:Mark (√ ) columns not already marked which have zeros in the marked-rows.

STEP 3:Mark (√ ) rows not already marked which have assignments in the marked columns.

STEP 4:Repeat steps 2 and 3 until the chain of markings ends.

STEP5: Draw lines through all unmarked rows and though all marked columns. (Check: If the above steps have

been carried out correctly, there should be as many lines as there were assignments in the maximal assignment

and we have atleast one line passing through every zero.) This is a method of drawing minimum number of lines

that will pass through all zeros. Thus all the zeros are covered.

STEP 6:Now examine the elements that do not have a line through them. Choose the smallest element and

subtract it form all the elements the intersection or junction of two lines. Leave the remaining elements of the

matrix unchanged.

STEP 7:Now proceed to make an assignment. If a solution is obtained with an assignment for every row, then

this will be the optimal solution. Otherwise proceed to draw minimum number of lines to cover all zeros as

explained in steps 1 to 5 and repeat iterations if needed.

Consider the following example.

209

Operations Research (MTH601)

210

Example 1

Solve the following assignment problem to minimize the total cost represented as elements in the

matrix (cost in thousand rupees).

Contractor

Building

Solution:

STEP 1:Choose the least element in each row of the matrix and subtract the same from all the elements in each

row so that each row contains atleast one zero. Thus we have table 12.

Table 12

Contractor

Building

STEP 2:Choose the least element in each column and subtract the same from all the elements in that column to

ensure that there is atleast one zero in each column. Thus we have table 13.

Table 13

Contractor

Building

STEP 3:We make the assignment in each row and column as explained previously. This results in table 1

Table 14

Contractor

Building

210

Operations Research (MTH601)

211

Here we have only three assignments. But we must have four assignments. With this maximal assignment

we have to draw the minimum number of lines to cover all the zeros. This is carried out as explained in steps 4

to 9. Refer table 15.

Table 15

Contractor

Building

STEP 4:Mark (√ ) the unassigned row (row C).

STEP 5:Against the marked row C, look for any 0 element and mark that column (column 4).

STEP 6:Against the marked column 4, look for any assignment and mark that row (row A).

STEP 7:Repeat steps 6 and 7 until the chain of markings ends.

STEP 8:Draw lines through all unmarked rows (row B and row D) and through all marked columns (column 4).

(Check: There should be only three lines to cover all the zeros.)

STEP 9:Select the minimum from the elements that do not have a line through them. In this example we have 1

as the minimum element, subtract the same from all the elements that do not have a line through them and add

this smallest element at the intersection of two lines. Thus we have the matrix shown in table 16.

Table 16

Contractor

Building

STEP 10: Go ahead with the assignment with the usual procedure. This is carried out in the table 16. Thus we

have four assignments.

Building A is alloted to contractor 4

Building B is alloted to contractor 1

Building C is alloted to contractor 3

Building D is alloted to contractor 2

Total cost is 44 + 56 + 90 + 44 = Rs. 234 thousands.

An airline that operates seven days a week has a timetable given below. Crews must have a

Example:

minimum layover time of 6 hours between flights. Obtain the pairing of flights that minimizes layover time

211

Operations Research (MTH601)

212

away from home. For any given pairing the crew will be based at the city that results in the smaller layover.

For each pair also mention the city where the crew should be placed.

212

Operations Research (MTH601)

213

Flight No.

Karachi to

Islamabad

7.00 a.m.

9.00 a.m.

11.00 a.m.

1.30 p.m.

3.30 p.m.

7.30 p.m.

9.30 p.m.

Flight No.

Islamabad to Karachi

101

9.00 a.m.

11.00 a.m.

102

10.00 a.m.

12.00 Noon

103

3.30 p.m.

5.30 p.m.

104

8.00 p.m.

10.00 p.m.

Solution:

STEP 1: We prepare a matrix in which all the flights reaching Islamabad are paired with flights with No's 101,

102, 103 and 104. The elements in the matrix represent the time taken (hrs) by Karachi based crew in

Islamabad. Refer table 17.

Flight No.

101

102

103

104

6.5

28.5

17.5

18.5

28.5

11.5

12.5

22.5

Explanation: The crew in the first flight No. 1 leaving Karachi arrives at Islamabad at 9.00 a.m. If the crew is

to return by flight No. 101, it is not possible on the same day and it has to stay for 24 hours (layover time).

Similarly to return by flight No. 102, 103 and 104, the same crew takes 25 hours, 6.5 hours, 11 hours

respectively. In the same way we calculate the time spent by the crew in flights 2, 3 and 4 to pair with flights

with No. 101, 102, 103 and 104. This is shown in Table 17.

STEP 2:We prepare a matrix in which all the flights reaching Karachi are paired with flights with numbers

1,2,3 and 4. The elements in the matrix indicate the time spent by Islamabad based crew in Karachi. This is

shown in table 18.

Table 18

Flight No.

101

102

103

104

13.5

15.5

26.5

25.5

15.5

8.5

7.5

21.5

STEP 3:Comparing the corresponding elements of the two matrices (tables 17 and 18), we choose the minimum

element and indicate the base at the top of the element (Karachi base-D, Islamabad base-C,). Thus we prepare

the table 19. If the crew is placed in either city it is denoted by *.

213

Operations Research (MTH601)

214

Table 19

Flight No.

101

102

103

104

6.5

21C 15.5C

22*

17.5D 18.5D 20C 15.5C

8.5C 7.5C

18D 21.5C

STEP 4:We proceed with the usual steps of assignment problem. Thus we have the following tables 20 and 21.

Table 20

Flight No.

101

102

103

104

13.5

12.5

2.5

6.5

10.5

Table 21

Flight No.

101

102

103

104

12.5

6.5

10.5

We have the following assignments shown in table 22. The minimum number of lines (3), are drawn to cover all

zero following Hungarian algorithm.

Table 22

Flight No.

101

102

103

104

12.5

√

5.5

√

3.5

10.5

√

STEP 5

Select the smallest element from those, which have no lines through them. In this case this is 1. Hence subtract

the same from all the elements that do not have a line through them and add the same at the intersection of two

lines. Thus we have the table 23.

Table 23

Flight No.

101

102

103

104

12.5

5.5

3.5

214

Operations Research (MTH601)

215

10.5

We assign rowwise and then columnwise. We have the table 24

Table 24

Flight No.

101

102

103

104

12.5

5.5

3.5

10.5

The result can be given as,

Flight no. 1 is paired with 103 with base at Karachi.

Flight no. 2 is paired with 104 with base at Karachi.

Flight no. 3 is paired with 101 with base at Karachi.

Flight no. 4 is paired with 102 with base at Islamabad.

MAXIMIZATION IN ASSIGNMENT MODEL

The problem of maximization is carried out similar to the case of minization making a slight modification. The

required modification is to multiply all elements in the matrix by -1, based on the concept that minizing the

negative of a function is equivalent to maximize the original function. This case is illustrated in the following

example.

Example:

Six salesmen are to be allocated to six sales regions. The earning of each salesman at each

region is given below. How can you find an allocation, so that the earnings will be maximum?

Region

Salesman

(Figure are in Rs. 1000)

In this problem the objective is to maximize the earnings of six salesmen sent to different

Solution:

regions. The first step is to multiply all the elements by (-1) and apply the method for minimization. So we have

the starting table as shown in table 25.

Table 25

Region

Salesman

-15

-35

-25

-10

-45

215

Operations Research (MTH601)

216

-40

-5

-45

-20

-15

-20

-25

-60

-10

-65

-25

-10

-25

-20

-35

-10

-25

-60

-30

-70

-40

-5

-40

-50

-10

-25

-30

-40

-50

-15

The second step is to follow the procedure of subtracting the least element from each row and then in each

column to ensure that there is atleast one zero in each row and in each column. This is presented in tables 26 and

27.

Table 26

Region

Salesman

Table 27

Region

Salesman

The third step is to assign salesmen to regions and test for optimality with the usual method as in table 28.

Table 28

Region

Salesman

Since we have six assignments, we have an optimal solution as given below in tables 29 to 31.

216

Operations Research (MTH601)

217

Salesman A is assigned to region 1,

B to region 3,

C to region 4,

D to region 6,

E to region 2 and

F to region 5

Total earnings are 15 + 45 + 65 + 60 + 70 + 50 = Rs. 3.5 (in thousands)

217

Operations Research (MTH601)

218

First iteration

Table 29

Salesman

Region

Table 30

Second iteration

Salesman

Region

Table 31

Third iteration

Salesman

Region

IMPOSSIBLE ASSIGNMENT

Sometimes in an assignment model we are not able to assign some jobs to some persons. For example

if machines are to be allocated to locations and if a machine cannot be accommodated in a particular location,

then it i an impossible assignment. To solve the problem in such situations we attach a very highly prohibited

(say ∞) cost to the cell in the matrix so that there is absolutely no chance to get the assignment with infinite cost

in the optimal solution.

218

Operations Research (MTH601)

219

Example

The processing times in hours for the jobs when allocated to the different machines are indicated

below. When a job is not possible to be made in a particular manner, it is indicated as '-'

Machine

Jobs

III

Allocate the machines for the jobs so that the total processing time is minimum.

Solution:

We have the impossible assignments marked as -. We introduce deliberately a high prohibitive time

(say ∞) in those places and proceed with the usual steps of solution procedure for assignment problem. Thus we

have the

table 32.

Table 32

Machine

Jobs

III

∞

Reducing the matrix in rows and columns so as to have atleast one zero in each row and in each

column, we have the following tables 33 and 34

Table 33

Machine

Jobs

III

∞

Table 34

Machine

Jobs

III

∞

219

Operations Research (MTH601)

220

∞

Next we proceed to assign jobs to machines as in table 35.

Table 35

Machine

Jobs

III

∞

From 35 we see that there are only four assignments but we should have five assignments.

We now proceed with drawing minimum number of lines to cover all zeros as in table 36.

Table 36

Machine

Jobs

III

∞

Now subtract the least element from the elements that do not have a line through them. In this case this element

is 1. We subtract it from all elements, which do not have a line through them and add the same at the

intersection of two lines. Proceeding in this way we have the table 37.

Table 37

Machine

Jobs

III

∞

220

Operations Research (MTH601)

221

(Note: Since we have number of zeros occupying corner of a square, we have multiple solutions).

Job A is assigned to machine III, B to machine I, C to machine V, D to machine II, E to machine IV.

221

Operations Research (MTH601)

222

REVIEW QUESTIONS

Three jobs A, B, C are to be assigned to three machines X, Y, Z. The processing costs (in Rs.) are as

given in the matrix shown below. Find the allocation, which will minimize the overall processing cost.

Machine

jobs

A college department chairman has the problem of providing teachers for all courses offered by his

department at the highest possible level of educational 'quality'. He has one professor, two associate

professors, and one teaching assistant (TA) available. Four courses must be offered and, after

appropriate introspection and evaluation he has arrived at the following relative ratings (100 = basic

rating) regarding the ability of each instructor to teach the four courses, respectively.

Courses

Prof. 1

Prof. 2

Prof. 3

T.A.

How should he assign his staff to the courses to maximize educational quality in his department?

(a) Explain the Hungarian method of solving an assignment problem for minimization.

(b) Solve the following assignment problem for minimization with cost (in rupees) matrix as:

Machine

Jobs

State the linear programming formulation of an assignment problem.

Four Jobs can be processed on four different machines, one job on one

machine. Resulting profits vary with assignments. They are given

below.

Machine

Jobs

42 35 28

222

Operations Research (MTH601)

223

30 25 20

III

24 20 16

Find the optimum assignment of jobs to machines and the corresponding profit.

Five men are available to do five different jobs. From past records the time in hours that each man

takes for each job is known and is given below.

Jobs

Men

III

Find the assignment of men to jobs that will minimize the total time taken.

Pearl Corporation has four plants each of which can manufacture any one of four products. Production

costs differ from one plant to another as do sales revenue. Given the revenue and cost data below,

obtain which product each plant should produce to minimize the profit.

Sales Revenue

Production Cost

Plant

Product

Five different machines can process any of the five required jobs with different profits resulting from

each assignment.

Machine

Job

130

137

140

128

140

124

127

121

136

140

132

133

135

138

140

136

129

141

134

139

Find the maximum profit possible through optimum assignments.

A construction company has five bulldozers at different locations and one bulldozer is required at three

different constructions sites. If the transportation cost are as shown, determine the optimum shipping

schedule.

Shipping cost ('000 Rs)

Location

Construction site

223

Operations Research (MTH601)

224

A manager has the problem of assigning four new machines to three production facilities. The

respective profits derived are as shown. If only one machine is assigned to a production facility

determine the optimal assignment.

Profits ('000 Rs)

Machine

Production facility

10.

Solve the following unbalanced assignment problem of minimizing total time for doing all the jobs.

Jobs

Operator

224

Operations Research (MTH601)

225

Segment VII: Queuing Theory

Lectures 38 - 39

225

Table of Contents: