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?

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 - Mathematics and Statistics

प्रश्न

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?

बेरीज

उत्तर

We can express the matrix form

`[(31,25,33,29), (25,24,23,21), (19,21,23,24), (38,36,34,40)]`

Subtracting the smallest element in each row from every element of it,

`[(6,0,8,4), (4,3,2,0), (0,2,4,5), (4,2,0,6)]`

Subtracting the smallest element In each column from very element of it.

`[(6,0,8,4), (4,3,2,0), (0,2,4,5), (4,2,0,6)]`

All the zeros of the above matrix are covered with minimum number of lines as below :

No. of lines = No. of rows/columns

Assignment of jobs :

A → Q, B → S, C → P, D → R

Minimum cost = 25 + 21 + 19 + 34

= Rs 99

shaalaa.com

Assignment Problem

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

Q 6.2.3 Q 6.2.2 Next

2014-2015 (March)

APPEARS IN

2014-2015 (March) (with solutions)

Q 6.2.3 | 4 marks

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

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

video tutorial00:20:25

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

Solve the following minimal assignment problem and hence find the minimum value :

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

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

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

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 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	3	2	4	4	5
4	18	9	12	17	15
5	11	6	14	19	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.

Fill in the blank :

An _______ is a special type of linear programming problem.

State whether the following is True or False :

In assignment problem, each facility is capable of performing each task.

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 plant manager has four subordinates, and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. This estimate of the time each man would take to perform each task is given in the effectiveness matrix below.

	I	II	III	IV
A	7	25	26	10
B	12	27	3	25
C	37	18	17	14
D	18	25	23	9

How should the tasks be allocated, one to a man, as to minimize the total man hours?

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 ______

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, if number of columns is greater than number of rows, then a dummy row is added

State whether the following statement is True or False:

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

Give mathematical form of Assignment problem

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)

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.

Find the optimal solution for the assignment problem with the following cost matrix.

		Area
		1	2	3	4
	P	11	17	8	16
Salesman	Q	9	7	12	6
	R	13	16	15	12
	S	14	10	12	11

Choose the correct alternative:

If number of sources is not equal to number of destinations, the assignment problem is called ______

Choose the correct alternative:

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

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?

A department store has four workers to pack goods. The times (in minutes) required for each worker to complete the packings per item sold is given below. How should the manager of the store assign the jobs to the workers, so as to minimize the total time of packing?

Workers	Packing of
	Books	Toys	Crockery	Cutlery
A	3	11	10	8
B	13	2	12	12
C	3	4	6	1
D	4	15	4	9

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 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 - Mathematics and Statistics

Advertisements

Advertisements

प्रश्न

उत्तर

APPEARS IN

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

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

Select a course

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 - Mathematics and Statistics

Advertisements

Advertisements

प्रश्न

उत्तरShow Solution

APPEARS IN

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

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

Select a course

उत्तर