This subject is related to Operations Management and require some formulations,which is the most important part of the assignment

.

it require using some software like Excel, and appendix.

Also, some graphs and table

1. The assignment problem

formulation

2. The assignment problem

solution using the Hungarian

method

2

Assignment Problem

➢An IP problem;

➢A special form of transportation

problem in which all supply and

demand values equal one;

➢One to one allocation must be made;

➢ The signs of the constraints are =

rather than < or >;

➢ Solution will be 0-1 integer.

3

Min ΣΣcijxij

i j

s.t.

Σxij ≤ 1 for each agent i

j

Σxij = 1 for each task j

i

xij = 0 or 1 for all i and j

Assignment Problem: LP Formulation

4

A plant has three operators to be

assigned to three machines. The operation

time (seconds) for a product unit produced

by each operator over each machine is

given below. How should the plant assign

machines to operators in order to minimise

the total operating time?

Machines

Operators A B C

OP1 50 36 16

OP2 28 30 18

OP3 35 32 20

Example (1) : Machine-Operator Assignment

5

Example (1): Machine-Operator Assignment

Network Representation

50

36

16

28

30

18

35 32

20

OP1

M3

M2

M1

OP3

OP2

Subcontractors

6

Min

50×11+36×12+16×13+28×21+30×22+18×23+35×31+32×32+2

0x33

s.t. x11+x12+x13 < 1

x21+x22+x23 < 1

x31+x32+x33 < 1

x11+x21+x31 = 1

x12+x22+x32 = 1

x13+x23+x33 = 1

xij = 0 or 1 for all i and j

Operators

Machines

Example (1) : Machine-Operator Assignment

LP Formulation

7

Hungarian Solution Method

1) Perform row reduction by subtracting the

minimum value from all entries in the same row;

2) Perform column reduction by subtracting the

minimum value from all entries in the same

column;

3) Cross out all zeros with a minimum number of

horizontal/vertical lines;

4) If the number of lines is equal to the number

of rows/columns this is the optimal solution ,

otherwise subtract the minimum value from

uncrossed values from all uncrossed values and

add this value to the intersection values;

5) Go to step 3

8

Example (1): Machine-Operator Assignment

Matrix Representation for Hungarian Solution

Machine

Operator M1 M2 M3

OP1 50 36 16 1

OP2 28 30 18 1

OP3 35 32 20 1

1 1 1

9

Example (1): Machine-Operator Assignment

Hungarian Solution

34 20 0

10 12 0

15 12 0

24 8 0

0 0 0

5 0 0

Optimal Solution

X13=1

X21=1

X32=1

Other ‘Xij’ s =0

Z= 76

10

• There are 4 machines and 3 jobs to be allocated.

The

• operating time for each job by each machine is given

• in the table below. Allocate jobs to machines while

• minimising the total time.

Example (2): Machine-Operator Assignment

Job 4

Machine

Job M1 M2 M3 M4

Job 1 1 4 6 3

Job 2 9 7 10 9

Job 3 4 5 11 7

Job 4 8 7 8 5

11

Example (2): Hungarian Solution Steps

12

Example (2): Hungarian Solution

13

Example (3): Project-Team Assignment

• A computer installation company has

three projects to complete and three work

teams available and capable of completing the

projects. Although each team includes two

technicians, they are not equally efficient at

completing a particular project.

• The next slide shows the estimated

labor-hours required for each team to

complete each project. How should the work

teams be assigned in order to minimize total

labor-hours?

14

Project

Work Team A B C

1. Tony, David 28 30 18 1

2. Mary, Sam 35 32 20 1

3. Simon,Tina 25 25 14 1

1 1 1

Example (3): Project-Team Labor Hours

15

Project

Work Team A B C

1. Tony, David 28 30 18 1

2. Mary, Sam 35 32 20 1

3. Simon,Tina 25 25 14 1

1 1 1

Example (3): Project-Team Labor Hours

16

Example (3): Project-Team Labor Hours

10 12 0

15 12 0

11 11 0

0 1 0

5 1 0

1 0 0

17

Example (3): Project-Team Solution

The Optimal solution can be

obtained as follows:

Team 1 to Project A,

Team 2 to Project C,

Team 3 to Project B,

Total labour hours: 73 hrs

18

References

• Textbook : Chapter 6, The

Assignment Model

• CD ROM: Module