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

Question

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.

Answer in Brief

Solution

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

Is there an error in this question or solution?

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

Video TutorialsVIEW ALL [1]

view
Video Tutorials For All Subjects
Assignment Problem

video tutorial00:20:25

RELATED QUESTIONS

A job production unit has four jobs A, B, C, D which can be manufactured on each of the four machines P, Q, R and S. The processing cost of each job is given in the following table:

Jobs	Machines
	P	Q	R	S
	Processing Cost (Rs.)
A	31	25	33	29
B	25	24	23	21
C	19	21	23	24
D	38	36	34	40

How should the jobs be assigned to the four machines so that the total processing cost is minimum?

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

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

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

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

Jobs	Machines (Processing Cost in ₹)
Jobs	P	Q	R	S
A	31	25	33	29
B	25	24	23	21
C	19	21	23	24
D	38	36	34	40

Find the optimal assignment to minimize the total processing cost.

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.

The assignment problem is said to be unbalance if ______

Choose the correct alternative :

The assignment problem is said to be balanced if it is a ______.

Choose the correct alternative :

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

The objective of an assignment problem is to assign ______.

Fill in the blank :

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

Fill in the blank :

An _______ is a special type of linear programming problem.

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?

If the given matrix is ______ matrix, the assignment problem is called balanced problem

State whether the following statement is True or False:

The objective of an assignment problem is to assign number of jobs to equal number of persons at maximum cost

What is the Assignment problem?

Give mathematical form of Assignment problem

What is the difference between Assignment Problem and Transportation Problem?

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?

Choose the correct alternative:

Number of basic allocation in any row or column in an assignment problem can be

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?

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 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

Question

Advertisements

Solution

APPEARS IN

Video TutorialsVIEW ALL [1]

RELATED QUESTIONS

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

Question

Advertisements

SolutionShow Solution

APPEARS IN

Video TutorialsVIEW ALL [1]

RELATED QUESTIONS

Select a course

Solution

	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