UNIT 3 ASSIGNMENT PROBLEM OUTLINE OBJECTIVES

[Pages:132]OUTLINE Session 2.1: Session 2.2: Session 2.3:

UNIT 3 ASSIGNMENT PROBLEM

Introduction Solution of Minimization Assignment Problem Solution of Maximization Assignment Problem

OBJECTIVES By the end of this unit you should be able to: 1. Identify and explain an Assignment Problem. 2. Solve Minimization and Maximization Assignment Problems.

Note: In order to achieve these objectives, you need to spend a maximum of two (2) hours working through the sessions.

61

SESSION 3.1:

INTRODUCTION

In its most general form, the assignment problem is as follows:

There are a number of agents and a number of tasks. Any agent can be assigned to

perform any task, incurring some cost that may vary depending on the agent-task

assignment. It is required to perform all tasks by assigning exactly one agent to each task

in such a way that the total cost of the assignment is minimized.

In the classical assignment problem, the goal is to find an optimal assignment of agents to tasks without assigning an agent more than once and ensuring that all tasks are completed. The objective might be to minimize the total time to complete a set of tasks, or to maximize skill ratings, or to minimize the cost of the assignments. A feature of the assignment problem particular is that only one machine is assigned to one and only one job.

Illustration: A certain machine shop has n machines denoted by M1, M2, M3 ..., Mn. A group of n different jobs(J1, J2, J3, ..., Jn) is to be assigned to these machines. For each job the machining cost depends on the machine to which it is assigned. Each machine can work only on one job. The problem is to assign the jobs to the machines, which will minimize the total cost of machining.

SESSION 3.2: SOLUTION OF MINIMIZATION ASSIGNMENT PROBLEM

The basic principle is that the optimal assignment is not affected if a constant is added or

subtracted from any row or column of the cost matrix. For example if the cost of doing

any job in machine 3 in the table below is increased by $2 so that the third row of the cost

matrix becomes 4, 3, 3, 4, it can be easily verified that the optimal solution is not affected

by this change.

J1

J2

J3

J4

M1

10

9

8

7

M2

3

4

5

6

M3

2

1

1

2

M4

4

3

5

6

62

In essence, the solution procedure is to subtract a sufficiently large cost from the various rows or columns in such a way that an optimal assignment is found by inspection. We initiate the algorithm by examining each row (column) of the cost matrix to identify the smallest element. This quantity is then subtracted from all the elements in that row (column). This produces a cost matrix containing at least one zero element in each row(column). Now try to make a feasible assignment using the cells with zero costs. If it is possible then we have an optimal assignment.

Examining the rows first, a reduced cost matrix can be obtained by subtracting: i. Seven(7) from the first row. ii. Three(3) from the second row. iii. One(1) from the third row. iv. Three(3) from the fourth row.

This produces the following results:

J1

J2

J3

J4

M1

3

2

1

0

M2

0

1

2

3

M3

1

0

0

1

M4

1

0

2

3

From the above table a feasible assignment using only the cells with zero costs is M1 J4 M2 J1 M3 J3 M4 J2 Hence this is an optimal solution..

In general, it may not always be possible to find a feasible assignment using cells with zero costs.

63

To illustrate this consider the following assignment problem

J1

J2

J3

J4

M1

10

9

7

8

M2

5

8

7

7

M3

5

4

6

5

M4

2

3

4

5

The solution is as follows.

First, the minimum element in each row is subtracted from all the elements in that row.

This gives the following reduced-cost matrix.

J1

J2

J3

J4

M1

3

2

0

1

M2

0

3

2

2

M3

1

0

2

1

M4

0

1

2

3

Since both the machines M2 and M4 have a zero cost corresponding to job J1 only, a feasible assignment using only cells with zero costs is not possible. To get additional zeros subtract the minimum element in the fourth column from all the elements in that column. The result is shown in the table below.

J1

J2

J3

J4

M1

3

2

0

0

M2

0

3

2

1

M3

1

0

2

0

M4

0

1

2

2

Only three jobs can be assigned using the zero cells, so a feasible assignment is still not possible. In such cases, the procedure draws a minimum number of lines through some selected rows and columns in such a way that all the cells with zero costs are covered by these lines. The minimum number of lines needed is equal to the maximum number of jobs that can be assigned using the zero cells.

64

In the current example, this can be done with three lines as follows.

J1

J2

J3

J4

M1

3

2

0

0

M2

0

3

2

1

M3

1

0

2

0

M4

0

1

2

2

Now select the smallest element, which is not covered by the lines. In the current

example, it is 1. Subtract this number from all the elements, which are not covered. Then

add this number to all those covered elements that are at the intersection of two lines.

This gives the following reduced cost matrix.

J1

J2

J3

J4

M1

4

2

0

0

M2

0

2

1

0

M3

2

0

2

0

M4

0

0

1

1

A feasible assignment is now possible and an optimal solution is assigned M1 J3 M2 J1 M3 J4 M4 J2 The total cost is given by: 7 +5+ 5+ 3 = 20 An alternate optimal solution is: M1 J3 M2 J4 M3 J2 M4 J1 In case a feasible set could not be obtained at this step, one has to repeat the step of drawing lines to cover the zeros and continue until a feasible assignment is obtained.

65

SESSION 3.3: SOLUTION OF MAXIMIZATION ASSIGNMENT PROBLEM

The following example will be used to illustrate the maximization algorithm. The figures

relate to contribution and it is required to maximize contribution

W

X

Y

Z

M1

25

18

23

14

M2

38

15

53

23

M3

15

17

41

30

M4

26

28

36

29

Step 1: Reduce each column by the largest figure in that column and ignore the resulting

minus sign. The result is shown in the table below.

W

X

Y

Z

M1

13

10

30

16

M2

0

13

0

7

M3

23

11

12

0

M4

12

0

17

1

Step 2: Reduce each row by the smallest figure in that row. The result is shown in the table below.

W

X

Y

Z

M1

3

0

20

6

M2

0

13

0

7

M3

23

11

12

0

M4

12

0

17

1

66

Step 3: Cover zeros by the minimum possible number of lines

W

X

Y

Z

M1

3

0

20

6

M2

0

13

0

7

M3

23

11

12

0

M4

12

0

17

1

Step 4: If the number of lines equals the number of assignments to be made go to step 6.

If less as in the current example , select the smallest element which is not covered by the

lines. In the current example, it is 3. Subtract this number from all the elements which are

not covered. Then add this number to all those covered elements that are at the

intersection of two lines. This gives the following reduced cost matrix

W

X

Y

Z

M1

0

0

17

6

M2

0

16

0

10

M3

20

11

9

0

M4

9

0

14

1

Step 5: A feasible assignment is now possible and an optimal solution is assigned.

M1 Z

M2X

M3 W

M4 Y

Step 6: Calculate the contribution to be gained from the assignments.

M1 Z $30

M2X$28

M3 W$25

M4 Y$53

Total= $136

67

SELF ASSESSMENT QUESTIONS QUESTION 1 A company employs service engineers based at various locations throughout the country to service and repair their equipment installed in customers' premises. Four requests for service have been received and the company finds that four engineers are available. The distances each of the engineers is from the various customers is given in the table below.

J1

J2

J3

J4

M1

25

18

23

14

M2

38

15

53

23

M3

15

17

41

30

M4

26

28

36

29

The company wishes to assign engineers to customers to minimize the total distance to be

traveled. Show how this could be done.

QUESTION 2

A foreman has four fitters and has been asked to deal with five jobs. The times for each

job are estimated as follows.

FITTERS

JOB

F1

F2

F3

F4

1

6

12

20

12

2

22

18

15

20

3

12

16

18

15

4

16

8

12

20

5

18

14

10

17

Allocate the men to the jobs so as to minimize the total time taken. Identify the job, which will not be dealt with.

68

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download