Chapter 7.5, Problem 1P

Explanation of Solution

Given:

Five employees are available for performing four jobs. The time taken to perform each job by each of the person is given in the following table:

		Time	(hours)
Person	Job 1	Job 2	Job 3	Job 4
1	22	18	30	18
2	18	M	27	22
3	26	20	28	28
4	16	22	M	14
5	21	M	25	28

To Determine:

Find an optimal assignment order of jobs to minimize the total time required for performing four jobs using Hungarian method.

Assignment of employees to jobs:

Step 1:

Add another column for Job 5 with zero costs, since the table is not balanced.

		Time	(hours)
Person	Job 1	Job 2	Job 3	Job 4	Job 5
1	22	18	30	18	0
2	18	M	27	22	0
3	26	20	28	28	0
4	16	22	M	14	0
5	21	M	25	28	0

Step 2:

Take minimum from each row and subtract from the corresponding row. The new resultant table will be as follows:

		Time	(hours)
Person	Job 1	Job 2	Job 3	Job 4	Job 5
1	22	18	30	18	0
2	18	M	27	22	0
3	26	20	28	28	0
4	16	22	M	14	0
5	21	M	25	28	0
Minimum	16	18	25	14	0

Step 3:

Take minimum from each column and subtract from the corresponding column. The new resultant table will be as follows:

		Time	(hours)
Person	Job 1	Job 2	Job 3	Job 4	Job 5
1	6	0	5	4	0
2	2	M	2	8	0
3	10	2	3	14	0
4	0	4	M	0	0
5	5	M	0	14	0

Step 4:

Draw minimum number of lines for covering all zeros in the resultant table...