Question

Solve the following minimal assignment problem : 

Machines	A	B	C	D	E
M1	27	18	∞	20	21
M2	31	24	21	12	17
M3	20	17	20	∞	16
M4	21	28	20	16	27

Answer 1

Machines	A	B	C	D	E
M1	27	18	__	20	21
M2	31	24	21	12	17
M3	20	17	20	__	16
M4	21	28	20	16	27

Step 1 : We introduce a dummy machine M₂ with time zero for each job and replace '-' by ∞

	A	B	C	D	E
M1	27	18	∞	20	21
M2	31	24	21	12	17
M3	20	17	20	∞	16
M4	21	28	20	16	27
M5	0	0	0	0	0

Step 2: Subtracting minimum element of each row from all its elememts 

As minimum number of lines = 4 ≠ order of the matrix.
. . Optimal solution is not reached.
Step 3 : We subtract minimum element (from uncovered elements) from each uncovered element and add to intersection elements.

Minimum number of lines= 5
= order of matrix.
:. Optimum solution is reached.
Step 4 : Making assignment at single zero of the row and of the column.

. . The optimal assignment of jobs to machines is

M₁ → B       M₂ → D     M₃ → E      M₄ → C     M₅ → A