Assignment Problems

Assignment Problem: Least Cost Allocation

A publication employs typists on an hourly basis. There are five typists for service and their charges are different. According to earlier understanding, only one job is given to one typist. Find the least cost allocation for the following data.

$$\begin{array}{|c|ccccc|}\hline \text{Typists/Jobs} & P & Q & R & S & T \ \hline A & 85 & 75 & 65 & 125 & 75 \ \hline B & 90 & 78 & 66 & 132 & 78 \ \hline C & 75 & 66 & 57 & 114 & 69 \ \hline D & 80 & 72 & 60 & 120 & 72 \ \hline E & 76 & 64 & 56 & 112 & 68 \ \hline \end{array}$$

[5]

Assignment Problem - Hungarian Method

A software company wants to assign its technical support agents to different regions to maximize customer satisfaction. The company has four agents, each with varying effectiveness in different regions. The table below shows the expected satisfaction score if each agent is assigned to a specific region. Use the Hungarian method to assign each technical support agent to a region in a way that maximizes overall customer satisfaction.

$$\begin{array}{|c|cccc|}\hline \text{Regions/Agents} & \text{Sandip} & \text{Sanjay} & \text{Shankar} & \text{Subhash} \ \hline \text{Kathmandu} & 140 & 146 & 148 & 136 \ \hline \text{Biratnagar} & 148 & 132 & 136 & 129 \ \hline \text{Janakpur} & 149 & 135 & 141 & 138 \ \hline \text{Butwal} & 130 & 146 & 149 & 144 \ \hline \end{array}$$

[5]

The ABC Company Job Assignment Problem

The ABC company has three jobs to be done on three machines. Each job must be done on one and only one machine. The cost of each job on each machine is given in the following table. By using Hungarian method, find the job assignments which will minimize the machine cost.

$$\begin{array}{|c|c|c|c|}\hline \text{Jobs\backslash Machine} & X & Y & Z \ \hline A & 4 & 6 & 8 \ B & 2 & 3 & 4 \ C & 4 & 8 & 5 \ \hline \end{array}$$

[5]

Assignment Problem - Hungarian Method

Kathmandu Metropolitan is putting up bids for four used motorbikes company. The Metropolitan allows individuals to make bids on all four motorbikes company but will accept only one bid per individual. Four individuals have made the following bids (in thousands Rs.). Make the use of Hungarian method to assign the individuals to different motorbike company in order to maximize the revenue.

$$\begin{array}{|c|c|c|c|c|}\hline \text{Individuals} & \text{Honda} & \text{Hero} & \text{Bajaj} & \text{Yamaha} \ \hline A & 100 & 90 & 110 & 90 \ B & 110 & 100 & 95 & 95 \ C & 105 & 95 & 90 & 105 \ D & 115 & 100 & 95 & 100 \ \hline \end{array}$$

[10]

Describe Hungarian Assignment Method (HAM) used for finding the optimal solution of assignment problem. [5]

Assignment Problem - Hungarian Method

A marketing manager has four salesmen and four sales districts. Considering the capabilities of the salesmen and nature of districts, the marketing manager estimates that sales per month in hundreds of rupees for each salesman in each district would be as follows:

$$\begin{array}{|c|c|c|c|c|}\hline \text{Sales} & A & B & C & D \ \hline P & 32 & 38 & 40 & 28 \ Q & 40 & 24 & 28 & 21 \ R & 41 & 27 & 33 & 30 \ S & 22 & 38 & 41 & 36 \ \hline \end{array}$$

Make the use of Hungarian method to assign the salesmen in different districts in such a way that total sales would be maximized. [5]

There are three jobs P, Q and R to be completed on four machines A, B, C and D. The costs of performing the different jobs on machines are given below. Assign the jobs to different machines to minimize the total cost of performing the jobs on machines.

$$\begin{array}{|c|c|c|c|c|}\hline \text{Jobs/Machines} & A & B & C & D \ \hline P & 90 & 120 & 140 & 160 \ Q & 40 & 65 & 85 & 95 \ R & 50 & 75 & 95 & 110 \ \hline \end{array}$$

[5]