Theory
1. Give the mathematical formulation of an assignment problem.
2. Describe the Hungarian Method of solving the assignment problem.
3. Explain the difference between a transportation and an assignment
problem.
4. Explain Unbalanced Assignment Problem with the help of an example.
5. Explain Maximization In An Assignment Problem with the help of an
example.
Practical
1. In a textile sales emporium, four salesmen A, B, C and D are available
to four counters W, X, Y and Z. Each salesman can handle any counter.
The service in (hour) of each counter when manned by each salesman is
given below:
Use Horizontal Scrollbar to View Full Table
Salesman 
Counter 
A 
B 
C 
D 
W 
41 
32 
39 
52 
X 
22 
29 
49 
65 
Y 
27 
39 
60 
51 
Z 
45 
50 
48 
52 
How should the salesman be allocated appropriate counters so as to
minimize the service time?
2. Five wagons are available at five stations 1, 2, 3, 4 and
5. These are required at five stations I, II, III, IV and V. The mileages
between various stations are given by:
Station 
Wagon 
I 
II 
III 
IV 
V 
1 
10 
5 
9 
18 
11 
2 
13 
19 
6 
12 
14 
3 
3 
2 
4 
4 
5 
4 
18 
9 
12 
17 
15 
5 
11 
6 
14 
19 
10 
3. A department head has four subordinates and four tasks. The subordinates
differ in efficiency and the tasks differ in their intrinsic difficulty.
His estimate of the time each man would take to perform each task is
given below. How should the tasks be allocated, one to a man, so as
to minimize the total man hours?
Man 
Job 
A 
B 
C 
D 
W 
8 
26 
17 
11 
X 
13 
28 
4 
26 
Y 
38 
19 
18 
15 
Z 
19 
26 
24 
10 
4. Four different buildings W, X, Y and Z are to be constructed
in a Maternity Hospital by four different contractors A, B, C and D.
It is also assumed that one contractor is required to build one building.
Each contractor has submitted bids for the four buildings. The bids
have been shown below. The problem is to determine which building is
to be awarded to each contractor to keep the cost of construction of
the four buildings at a minimum.
Contractor 
Building 
A 
B 
C 
D 
W 
48 
48 
50 
44 
X 
56 
60 
60 
68 
Y 
96 
94 
90 
85 
Z 
42 
44 
54 
46 
5. Solve the following assignment problems:
(a)
Man 
Job 
I 
II 
III 
IV 
1 
8 
26 
17 
11 
2 
13 
28 
4 
26 
3 
38 
19 
18 
15 
4 
19 
26 
24 
10 
(b)
Man 
Job 
I 
II 
III 
IV 
V 
1 
11 
17 
8 
16 
20 
2 
9 
7 
12 
6 
15 
3 
13 
16 
15 
12 
16 
4 
21 
24 
17 
28 
26 
5 
14 
10 
12 
11 
15 
(c)
Man 
Job 
I 
II 
III 
IV 
V 
1 
1 
3 
2 
3 
6 
2 
2 
4 
3 
1 
5 
3 
5 
6 
3 
4 
6 
4 
3 
1 
4 
2 
2 
5 
1 
5 
6 
5 
4 
(d)
Man 
Job 
I 
II 
III 
IV 
1 
12 
30 
21 
15 
2 
18 
33 
9 
31 
3 
44 
25 
24 
21 
4 
23 
30 
28 
14 
(e)
Man 
Job 
I 
II 
III 
IV 
1 
2 
3 
4 
5 
2 
4 
5 
6 
7 
3 
7 
8 
9 
8 
4 
3 
5 
8 
4 
(f)
Man 
Job 
I 
II 
III 
IV 
V 
1 
12 
8 
7 
15 
4 
2 
7 
9 
1 
14 
10 
3 
9 
6 
12 
6 
7 
4 
7 
6 
14 
6 
10 
5 
9 
6 
10 
10 
6 
6. One car is available at each of the station 1, 2, 3, 4, 5, 6 and
one car is required at each of the stations 7, 8, 9, 10, 11, 12. The
distances between the various stations are given in the matrix below.
How should the cars be dispatched so as to minimize the total mileage
covered ?

7 
8 
9 
10 
11 
12 
1 
41 
72 
39 
52 
25 
51 
2 
22 
29 
49 
65 
81 
50 
3 
27 
39 
60 
51 
32 
32 
4 
45 
50 
48 
52 
65 
43 
5 
29 
40 
39 
26 
30 
33 
7 
82 
40 
40 
60 
51 
30 
7. The Manager of a company wants to assign X, Y and Z to regional
offices Delhi, Mumbai, Kolkata and Chennai. The cost of reallocation
(in Rupees) of the three officers at the four regional offices are given
below:
Office 
Officer 
Delhi 
Mumbai 
Kolkata 
Chennai 
X 
16000 
22000 
24000 
20000 
Y 
10000 
32000 
26000 
16000 
Z 
10000 
20000 
46000 
30000 
How should the officers be allocated appropriate regional offices so
as to minimize the cost?
8. A company has four sales territories and four salesmen available
for assignment. The sales territories are not equally rich in their
sales potential and the salesmen also differ in their selling ability.
The following matrix gives the sales (in thousand rupees) for each salesman
to be assigned to each territory. How should the territories be assigned
to salesmen so as to maximize the total sales?
Territory 
Salesman 
A 
B 
C 
D 
W 
42 
35 
28 
21 
X 
30 
25 
20 
15 
Y 
30 
25 
20 
15 
Z 
24 
20 
16 
12 
9. OneRide Airlines that operates seven days a week has the timetable
given below. Crews must have a minimum layover of 6 hours between flights.
Obtain the pairing of flights that minimizes layover time away from
home. For any given pairing, the crew will be based at the city that
results in smaller layover.
Delhi  Jaipur 
Flight No. 
Departure 
Arrival 
101 
7.00 AM 
8.15 AM 
102 
8.30 AM 
9.45 AM 
103 
1.00 PM 
2.15 PM 
104 
6.00 PM 
7.15 PM 

Jaipur  Delhi 
Flight No. 
Departure 
Arrival 
201 
8.00 AM 
9.15 AM 
202 
9.00 AM 
10.15 AM 
203 
12.00 Noon 
1.15 PM 
204 
5.45 PM 
7.00 PM 

For each pair also mention the city where crew should be based.
10. Railways that operates seven days a week has the timetable given
below. Crews must have a minimum layover of 2 hours between trains.
Obtain the pairing of trains that minimizes layover time away from home.
For any given pairing, the crew will be based at the city that results
in smaller layover.
Delhi  Karnal 
Train No. 
Departure 
Arrival 
1010 
7.00 AM 
9.00 AM 
1020 
8.30 AM 
10.30 AM 
1030 
1.00 PM 
2.00 PM 
1040 
6.50 PM 
8.50 PM 

Karnal  Delhi 
Train No. 
Departure 
Arrival 
2010 
8.00 AM 
10.00 AM 
2020 
9.00 AM 
11.00 AM 
2030 
12.20 PM 
2.20 PM 
2040 
5.45 PM 
7.45 PM 

For each pair also mention the city where crew should be based.
11. One ride airline operating 7 days a week has given the following
timetable. Crews must have a minimum layover of 5 hours between flights.
Obtain the pairing flights that minimizes layover time away from home.
For any pairing the crew will be based at the city that results in the
smaller layover.