A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the

Question

A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the time each man would take to perform each task is given below:

		Tasks
		1	2	3	4
Subordinates	P	8	26	17	11
	Q	13	28	4	26
	R	38	19	18	15
	S	9	26	24	10

How should the tasks be allocated to subordinates so as to minimize the total manhours?

Chart

Sum

Solution

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced.

Step 1: Select the smallest element in each row and subtract this from all the elements in its row.

		Tasks
		1	2	3	4
Subordinates	P	0	18	9	3
	Q	9	24	0	22
	R	23	4	3	0
	S	0	17	15	1

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
	S	0	13	15	1

Step 3: (Assignment)
Examine the rows with exactly one zero Mark the zero by □. Mark other zeros in its row by X.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
	S	0	13	15	1

Step 4: Now examine the columns with exactly one zero. Mark the zero by □. Mark other zeros in its row by X.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
	S	0	13	15	1

Step 5: Cover all the zeros of table 4 with three lines, since three assignments were made check (✓) row S since it has no assignment.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	9	20	0	22
	R	23	0	3	0
✓	S	0	13	15	1

Step 6: Develop the new revised tableau. Examine those elements that are not covered by a line in table 5.

Take the smallest element.

This is 1 (one) our case.

By subtracting 1 from the uncovered cells.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	10	20	0	22
	R	24	0	3	0
	S	0	12	14	0

[Adding 1 to elements (Q, S, R) that line at the intersection of two lines]

Step 7: Go to step 3 and repeat the procedure until you arrive at an optimal assignment.

Step 8: Determine an assignment.

		Tasks
		1	2	3	4
Subordinates	P	0	14	9	3
	Q	10	20	0	22
	R	24	0	3	0
	S	0	12	14	0

Thus all the four assignment have been made.

The optimal assignment schedule and total time is

Subordinates	Tasks	Time
P	1	8
Q	3	4
R	2	19
S	4	10
Total		41

The optimum time (minimum) = 41 Hrs.

shaalaa.com

Assignment Problem

Is there an error in this question or solution?

Q 6 Q 5 Q 7

Chapter 10: Operations Research - Exercise 10.2 [Page 256]

APPEARS IN

Samacheer Kalvi Business Mathematics and Statistics [English] Class 12 TN Board

Chapter 10 Operations Research
Exercise 10.2 | Q 6 | Page 256

RELATED QUESTIONS

Suggest optimum solution to the following assignment. Problem, also find the total minimum service time.
Service Time ( in hrs.)

Counters	Salesmen
Counters	A	B	C	D
W	41	72	39	52
X	22	29	49	65
Y	27	39	60	51
Z	45	50	48	52

Solve the following minimal assignment problem :

Machines	A	B	C	D	E
M₁	27	18	∞	20	21
M₂	31	24	21	12	17
M₃	20	17	20	∞	16
M₄	21	28	20	16	27

Determine `l_92 and l_93, "given that" l_91 = 97, d_91 = 38 and q_92 = 27/59`

Solve the following maximal assignment problem :

Branch Manager	Monthly Business ( Rs. lakh)
Branch Manager	A	B	C	D
P	11	11	9	9
Q	13	16	11	10
R	12	17	13	8
S	16	14	16	12

A departmental head has three jobs and four subordinates. The subordinates differ in their capabilities and the jobs differ in their work
contents. With the help of the performance matrix given below, find out which of the four subordinates should be assigned which jobs ?

Subordinates	Jobs
Subordinates	I	II	III
A	7	3	5
B	2	7	4
C	6	5	3
D	3	4	7

Choose the correct alternative:

The assignment problem is said to be balanced if ______

State whether the following statement is True or False:

In assignment problem each worker or machine is assigned only one job

A computer centre has got three expert programmers. The centre needs three application programmes to be developed. The head of the computer centre, after studying carefully the programmes to be developed, estimates the computer time in minitues required by the experts to the application programme as follows.

	Programmers
		P	Q	R
Programmers	1	120	100	80
	2	80	90	110
	3	110	140	120

Assign the programmers to the programme in such a way that the total computer time is least.

Five wagons are available at stations 1, 2, 3, 4 and 5. These are required at 5 stations I, II, III, IV and V. The mileage between various stations are given in the table below. How should the wagons be transported so as to minimize the mileage covered?

	I	II	III	IV	V
1	10	5	9	18	11
2	13	9	6	12	14
3	7	2	4	4	5
4	18	9	12	17	15
5	11	6	14	19	10

A job production unit has four jobs P, Q, R, S which can be manufactured on each of the four machines I, II, III and IV. The processing cost of each job for each machine is given in the following table :

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	31	25	33	29
Q	25	24	23	21
R	19	21	23	24
S	38	36	34	40

Complete the following activity to find the optimal assignment to minimize the total processing cost.

Solution:

Step 1: Subtract the smallest element in each row from every element of it. New assignment matrix is obtained as follows :

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Step 2: Subtract the smallest element in each column from every element of it. New assignment matrix is obtained as above, because each column in it contains one zero.

Step 3: Draw minimum number of vertical and horizontal lines to cover all zeros:

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Step 4: From step 3, as the minimum number of straight lines required to cover all zeros in the assignment matrix equals the number of rows/columns. Optimal solution has reached.

Examine the rows one by one starting with the first row with exactly one zero is found. Mark the zero by enclosing it in (`square`), indicating assignment of the job. Cross all the zeros in the same column. This step is shown in the following table :

Job	Machines (Processing cost in ₹)
Job	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Step 5: It is observed that all the zeros are assigned and each row and each column contains exactly one assignment. Hence, the optimal (minimum) assignment schedule is :

Job	Machine	Min.cost
P	II	`square`
Q	`square`	21
R	I	`square`
S	III	34

Hence, total (minimum) processing cost = 25 + 21 + 19 + 34 = ₹`square`

A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the

Advertisements

Advertisements

Question

Advertisements

Solution

APPEARS IN

RELATED QUESTIONS

Select a course

A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the

Advertisements

Advertisements

Question

Advertisements

SolutionShow Solution

APPEARS IN

RELATED QUESTIONS

Select a course

Solution