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
