Initial allocation
Cost matrix reduction (contd..)
Cost matrix reduction
Assignment Model Table
Make an allocation for each row in
ADMISSIBLE CELLS, if possible
and then strike-off the other
ADMISSIBLE CELLS in its column.
J5 J5 J4 J3 J2
J4
J3
J2
J1
J5
J4
J3
J2
J1
J1
J5
J4
J3
J2
J1
M1
M1
M1
M1
0 0 1 5 7 3 0 1 5 7 3 2 5
M2 M2
0 0 2 6 2 4 0 2 6 2 4 2 6
M3 M3
x 0 3 7 3 5 2 5 9 5 7 4
M4 M4
M2
M2
0 1 4 0 4 6 1 4 0 4 6
(Make new table now) (Make new table now)
1
M5 M5
R5 = R5 2 R4 = R4 4 R3 = R3 2 R2 = R2 1 R1 = R1 1 Apply row operations such that all rows have at least one cell having the value of ZERO (such cells are known as ADMISSIBLE CELLS). Then, search for the smallest values in each column that does not have an ADMISSIBLE CELL.
M3
M3
11
C4 = C4 2
M4
M4
M5
M5
Apply column operations such that
Search for the smallest values in each row.
all columns have at least one cell
having the value of ZERO (that is,
ADMISSIBLE CELLS).
ASSIGNMENT MODEL PROBLEM 1
Page 1
Labelling routine (contd..)
Labelling routine (contd..)
Labelling routine
Initial allocation (contd..)
J4 J5 J3 J5 J3
J2
J1
J4
J2
J1
J4
J2
J1
J5
J4
J3
J2
J1
J5
J3
0 x 0 1 5 7 3 0 1 5 7 3 0 1
M2 M2
M1
M1
M1
M1
R2
R2
M2
M2
Then go to the row having an
allocation in the current column,
and give this column the label 'Cj'
(where j is the column number of the
cell having the allocation.
0 0 2 6 2 4 0 2 6 2 4
M3 M3
1 0 3 7 3 5 0 3 7 3 5
M4 M4
M3
M3
0 1 4 0 4 6 1 4 0 4 6
M5
S S S S Label 'S' to each row not having any allocation so far.
0 x
M4
M4
0 x
M5
M5
M5
C1
Starting from 'S', label the column
Make an allocation for each column in ADMISSIBLE CELLS, if possible and then strike-off the other ADMISSIBLE CELLS in its row.
having an unallocated ZERO as 'Ri'
(where i is the row number of the
cell having unallocated ZERO).
Page 2
Labelling routine
(making lines as per procedure)
Further reduction routine
Further reduction routine
Labelling routine (contd..)
(making changes in values of cells)
J4 J5 J3
R2 R2
J2
J1
J5
J4
J3
J2
J1
J5
J4
J3
J2
J1
J4
J2
J1
Label 'S' to each row not having
any allocation so far.
J5
J3
M1
M1
M1
M1
1 + + 0 0 5 6 2 0 1 5 7 3 0 1
M2 M2
0 0 1 6 1 3 0 2 6 2 4 0 2
M3 M3
M2
M2
0 0 2 7 2 4 0 3 7 3 5
M4 M4
0 1 3 0 3 5 1 4 0 4 6
(Make new table now)
M3
M3
0
M5
1
C1 S S All unallocated columns are still case. Perform further reduction routine. Make lines over unlabelled rows and labelled columns.
M4
M4
M5
M5
M5
C1
Subtract the smallest value from
Repeat the labelling routine unlabelled NON-BREAKTHROUGH until possible.
the unhidden cells, from all
unhidden cells. And, add this value
to the cells having double lines
crossing over them.
Page 3
Labelling routine (contd..)
Labelling routine (contd..)
Labelling routine (contd..)
Labelling routine (contd..)
J4 J5 J3 J5 J3 J5 J3
J2
J1
J4
J2
J1
J4
J2
J1
J4
J2
J1
J5
J3
1 0 0 5 6 2 0 0 5 6 2 0 0
M2 M2
M1
M1
M1
M1
R2
R2
R2
R2
0 0 1 6 1 3 0 1 6 1 3
M3 M3
M2
M2
R4
R4
M3
M3
Repeat the labelling routine
until possible.
0 0 2 7 2 4 0 2 7 2 4
M4
1 1 3 0 3 5 1 3 0 3 5
M5
S S S S C1 C1 Then go to the row having an allocation in the current column, and give this column the label 'Cj' cell having the allocation.
M4
M4
M4
M5
M5
M5
C2
C1
Repeat the labelling routine
Starting from 'S', label the column having an unallocated ZERO as 'Ri' (where i is the row number of the (where j is the column number of the cell having unallocated ZERO).
until possible.
Page 4
Allocation change routine
Allocation change routine
Labelling routine (contd..)
Labelling routine (contd..)
(contd..)
J4 J2 J1 J4 J2 J1 J4 J2 J1 J5 J3 J5 J3 J5 J3
J5
J4
J2
J1
J3
1 0 0 5 6 2 0 0 5 6 2 0 0
R4 R4
M1
M1
M1
M1
R2
R2
R2
R2
0 0 1 6 1 3 0 1 6 1 3
R5 R5
M2
M2
M2
M2
R4
R4
x 0 1 6 1 3
M3 M3 M3
0 0 2 7 2 4 0 2 7 2 4
R5
M3
R5
R5
0 1 3 0 3 5 1 3 0 3
M5
S S S S C2 C1 C2 until possible.
M4
M4
M4
M4
R5 Repeat the labelling routine
R5
M5
M5
M5
Repeat the allocation change routine
until possible.
C2
C1
C1
C2
C1
Some unallocated columns now are
Repeat the labelling routine until possible.
labelled BREAKTHROUGH case.
Perform allocation change routine.
Make new allocations as per 'Ri'.
and remove allocation from that row
as per 'Cj'.
Page 5
Labelling routine (contd..) (contd..)
J5 J4 J2 J1 J5 J4 J2 J1 J5 J4 J2 J3 J3 J3
Labelling routine (contd..)
Allocation change routine
Allocation change routine
J5
J4
J2
J1
J1
J3
1
R4 R4
M1
M1
M1
M1
R2
R2
R2
M2
M2
M2
M2
Starting from 'S', label the column
having an unallocated ZERO as 'Ri'
(where i is the row number of the
cell having unallocated ZERO).
0
R5 R5
0 0 1 6 1 3 0 1 6 1 3
M3 M3
R5
0 x
M3
M3
0 0 2 7 2 4 0 2 7 2 4
M4
1 x 1 3 0 3 5 1 3 0 3 5
R5 (Make new table now)
M4
M4
M4
0
M5
C2 S S S until possible.
M5
M5
M5
C1
C2
C1
Label 'S' to each row not having
Repeat the allocation change routine
Repeat the allocation change routine until possible.
any allocation so far.
Page 6
Labelling routine
(making lines as per procedure)
Further reduction routine
Further reduction routine
Labelling routine (contd..)
(making changes in values of cells)
Label 'S' to each row not having
any allocation so far.
J5 J3
R2 R2
J4
J2
J1
J5
J4
J3
J2
J1
J5
J4
J3
J2
J1
J5
J4
J2
J1
J3
M1
M1
M1
M1
2 + + + 0 0 5 5 1 0 0 5 6 2 0 0
M2 M2
1 0 1 6 0 2 0 1 6 1 3 0 1
M3 M3
M2
M2
0 0 2 7 1 3 0 2 7 2 4
M4 M4
0 1 3 0 2 4 1 3 0 3 5
(Make new table now)
M3
M3
0
M5
1
C1 S All unallocated columns are still case. Perform further reduction routine. Make lines over unlabelled rows and labelled columns.
M4
M4
M5
M5
M5
C1
Subtract the smallest value from
Then go to the row having an unlabelled NON-BREAKTHROUGH allocation in the current column, and give this column the label 'Cj' (where j is the column number of the cell having the allocation.
the unhidden cells, from all
unhidden cells. And, add this value
to the cells having double lines
crossing over them.
Page 7
Labelling routine (contd..)
Labelling routine (contd..)
Labelling routine (contd..)
Labelling routine (contd..)
J5 J3 J3 J3
J4
J2
J1
J5
J4
J2
J1
J5
J4
J2
J1
J5
J4
J2
J1
J3
2 0 0 5 5 1 0 0 5 5 1 0 0
M2 M2
M1
M1
M1
M1
R2
R2
R2
R2
M2
M2
0 0 1 6 0 2 0 1 6 0 2
M3 M3
0 0 2 7 1 3 0 2 7 1 3
M4
M3
M3
R2
R2
M4
M4
M4
Repeat the labelling routine
until possible.
0 1 3 0 2 4 1 3 0 2
M5
S S C1 cell having the allocation.
M5
M5
M5
C3
C1
C1
Repeat the labelling routine
Then go to the row having an allocation in the current column, and give this column the label 'Cj' (where j is the column number of the
Starting from 'S', label the column having an unallocated ZERO as 'Ri' (where i is the row number of the cell having unallocated ZERO).
until possible.
Page 8
Allocation change routine
Labelling routine (contd..)
Labelling routine (contd..)
Labelling routine (contd..)
J5 J3 J3 J3
J4
J2
J1
J5
J4
J2
J1
J5
J4
J2
J1
J5
J4
J2
J1
J3
2 0 0 5 5 1 0 0 5 5 1 0 0
R5 R5
M1
M1
M1
M1
R2
R2
R2
R2
0 0 1 6 0 2 0 1 6 0 2
R2 R2
M2
M2
M2
M2
R5
R5
0 0 2 7 1 3 0 2 7 1 3
M4
M3
M3
M3
M3
R2
R2
0 1 3 0 2 4 1 3 0 2
M5
S S C3 C2 C1 C3 C2 until possible.
M4
M4
M4
R5 Repeat the labelling routine
R5
M5
M5
M5
Some unallocated columns now are
labelled BREAKTHROUGH case.
Perform allocation change routine.
Make new allocations as per 'Ri'.
and remove allocation from that row
as per 'Cj'.
C3
C2
C1
C1
C3
C1
Repeat the labelling routine
Repeat the labelling routine until possible.
until possible.
Page 9
OPTIMAL SOLUTION (contd..)
J5 J4 J2 J1 J5 J4 J2 J3 J3
All rows and columns are (contd..)
Allocation change routine
Allocation change routine
having allocations STOP.
J5 J4 J3 J2 J1
J5
R2 R2
J4
J3
J2
J1
J1
M1
M1
M1
M1
2
R5 R5
4 0 0 5 5 1 0 0 5 5 1 0 0
M2 M2
R2 R2
M2
M2
2 0 1 6 0 2 0 1 6 0 2
M3 M3
5 x
R5 R5
M3
M3
2 0 2 7 1 3 0 2 7 1 3
M4
6 1 3 0 2 4 1 3 0 2 4
M5
S C3 C2 C1
0 x
M4
M4
M4
11
4
until possible.
M5
M5
M5
1
C3
3
C2
2
S
4
C1
(Make the allocations shown above in the original assignment model table now)
SOLUTION ENDS
OPTIMAL COST =
Since all rows and columns are
Repeat the allocation change routine
Repeat the allocation change routine until possible.
1 + 3 + 2 + 5 + 4 = 15
having allocations now, write the
original values of costs from the
ASSIGN J1 TO M1; J2 TO M3;
original assignment table of the
J3 TO M5; J4 TO M2;
problem and find the OPTIMAL
AND J5 TO M4.
SOLUTION.
Page 10
