A job production unit has four jobs P, Q, R, and 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 ₹) I II III IV P 31 25 33 29 Q 25 24 23 21 R 19 21 23 24 S 38 36 34 40 Find the optimal assignment to minimize the total processing cost.

Step 1: Subtract smallest element of each row from every element of that row. Jobs 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: Since each column contains element 0, column minimization will give us the some matrix. Step 3: Drawing minimum number of horizontal and vertical lines to cover all zeros. Jobs I II III IV ← P 6 0 8 4 → ← Q 4 3 2 0 → ← R 0 2 4 5 → ← S 4 2 0 6 → ∵ No. of lines drawn (4) = order of the matrix (4), optimal solution has reached. Step 4: Assignment Jobs I II III IV P 6 0 8 4 Q 4 3 2 0 R 0 2 4 5 S 4 2 0 6 Job Assignment: Job Machine Min.cost P II 25 Q IV 21 R I 19 S III 34 Total Cost ₹ 99 Minimum Processing Cost = ₹ 99.

A job production unit has four jobs P, Q, R, and 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

प्रश्न

A job production unit has four jobs P, Q, R, and 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

Find the optimal assignment to minimize the total processing cost.

थोडक्यात उत्तर

उत्तर

Step 1: Subtract smallest element of each row from every element of that row.

Jobs	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: Since each column contains element 0, column minimization will give us the some matrix.

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

	Jobs	I	II	III	IV
←	P	6	0	8	4	→
←	Q	4	3	2	0	→
←	R	0	2	4	5	→
←	S	4	2	0	6	→

∵ No. of lines drawn (4) = order of the matrix (4), optimal solution has reached.

Step 4: Assignment

Jobs	I	II	III	IV
P	6	0	8	4
Q	4	3	2	0
R	0	2	4	5
S	4	2	0	6

Job Assignment:

Job	Machine	Min.cost
P	II	25
Q	IV	21
R	I	19
S	III	34
	Total Cost	₹ 99

Minimum Processing Cost = ₹ 99.

shaalaa.com

Assignment Problem

या प्रश्नात किंवा उत्तरात काही त्रुटी आहे का?

Q 5.A.ii Q 5.A.i Q 5.A.iii

2021-2022 (March) Set 1

APPEARS IN

2021-2022 (March) Set 1 (with solutions)

Q 5.A.ii | 3 marks

व्हिडिओ ट्यूटोरियलVIEW ALL [1]

view
व्हिडिओ ट्यूटोरियल For All Subjects
Assignment Problem

video tutorial00:20:25

संबंधित प्रश्‍न

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 minimal assignment problem and hence find minimum time where '- ' indicates that job cannot be assigned to the machine :

Machines	Processing time in hours
Machines	A	B	C	D	E
M₁	9	11	15	10	11
M₂	12	9	-	10	9
M₃	-	11	14	11	7
M₄	14	8	12	7	8

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

In a factory there are six jobs to be performed each of which should go through two machines A and B in the order A - B. The processing timing (in hours) for the jobs arc given here. You are required to determine the sequence for performing the jobs that would minimize the total elapsed time T. What is the value of T? Also find the idle time for machines · A and B.

Jobs	J₁	J₂	J₃	J₄	J₅	J₆
Machine A	1	3	8	5	6	3
MAchine B	5	6	3	2	2	10

Five different machines can do any of the five required jobs, with different profits resulting from each assignment as shown below:

Job	Machines (Profit in ₹)
Job	A	B	C	D	E
1	30	37	40	28	40
2	40	24	27	21	36
3	40	32	33	30	35
4	25	38	40	36	36
5	29	62	41	34	39

Find the optimal assignment schedule.

Choose the correct alternative :

In an assignment problem if number of rows is greater than number of columns then

Fill in the blank :

When an assignment problem has more than one solution, then it is _______ optimal solution.

In an assignment problem, if number of column is greater than number of rows, then a dummy column is added.

State whether the following is True or False :

It is not necessary to express an assignment problem into n x n matrix.

Solve the following problem :

A dairy plant has five milk tankers, I, II, III, IV and V. These milk tankers are to be used on five delivery routes A, B, C, D and E. The distances (in kms) between the dairy plant and the delivery routes are given in the following distance matrix.

	I	II	III	IV	V
A	150	120	175	180	200
B	125	110	120	150	165
C	130	100	145	160	175
D	40	40	70	70	100
E	45	25	60	70	95

How should the milk tankers be assigned to the chilling center so as to minimize the distance travelled?

Choose the correct alternative:

The assignment problem is generally defined as a problem of ______

Choose the correct alternative:

Assignment Problem is special case of ______

Choose the correct alternative:

When an assignment problem has more than one solution, then it is ______

In an assignment problem if number of rows is greater than number of columns, then dummy ______ is added

State whether the following statement is True or False:

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

Three jobs A, B and C one to be assigned to three machines U, V and W. The processing cost for each job machine combination is shown in the matrix given below. Determine the allocation that minimizes the overall processing cost.

		Machine
		U	V	W
Jobs	A	17	25	31
	B	10	25	16
	C	12	14	11

(cost is in ₹ per unit)

Choose the correct alternative:

The purpose of a dummy row or column in an assignment problem is to

Choose the correct alternative:

In an assignment problem involving four workers and three jobs, total number of assignments possible are

A car hire company has one car at each of five depots a, b, c, d and e. A customer in each of the fine towers A, B, C, D and E requires a car. The distance (in miles) between the depots (origins) and the towers(destinations) where the customers are given in the following distance matrix.

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

How should the cars be assigned to the customers so as to minimize the distance travelled?

A natural truck-rental service has a surplus of one truck in each of the cities 1, 2, 3, 4, 5 and 6 and a deficit of one truck in each of the cities 7, 8, 9, 10, 11 and 12. The distance(in kilometers) between the cities with a surplus and the cities with a deficit are displayed below:

		To
		7	8	9	10	11	12
From	1	31	62	29	42	15	41
	2	12	19	39	55	71	40
	3	17	29	50	41	22	22
	4	35	40	38	42	27	33
	5	19	30	29	16	20	33
	6	72	30	30	50	41	20

How should the truck be dispersed so as to minimize the total distance travelled?

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 plant manager has four subordinates and four tasks to perform. The subordinates differ in efficiency and task differ in their intrinsic difficulty. Estimates of the time subordinate would take to perform tasks are given in the following table:

	I	II	III	IV
A	3	11	10	8
B	13	2	12	2
C	3	4	6	1
D	4	15	4	9

Complete the following activity to allocate tasks to subordinates to minimize total time.

Solution:

Step I: Subtract the smallest element of each row from every element of that row:

	I	II	III	IV
A	0	8	7	5
B	11	0	10	0
C	2	3	5	0
D	0	11	0	5

Step II: Since all column minimums are zero, no need to subtract anything from columns.

Step III: Draw the minimum number of lines to cover all zeros.

	I	II	III	IV
A	0	8	7	5
B	11	0	10	0
C	2	3	5	0
D	0	11	0	5

Since minimum number of lines = order of matrix, optimal solution has been reached

Optimal assignment is A →`square` B →`square`

C →IV D →`square`

Total minimum time = `square` hours.

A job production unit has four jobs P, Q, R, and 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

Advertisements

Advertisements

प्रश्न

Advertisements

उत्तर

APPEARS IN

व्हिडिओ ट्यूटोरियलVIEW ALL [1]

संबंधित प्रश्‍न

Select a course

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105

A job production unit has four jobs P, Q, R, and 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

Advertisements

Advertisements

प्रश्न

Advertisements

उत्तरShow Solution

APPEARS IN

व्हिडिओ ट्यूटोरियलVIEW ALL [1]

संबंधित प्रश्‍न

Select a course

उत्तर

	a	b	c	d	e
A	160	130	175	190	200
B	135	120	130	160	175
C	140	110	155	170	185
D	50	50	80	80	110
E	55	35	70	80	105