A note on assignment problems

It is shown that the Bottleneck Assignment problem can be transformed into a special case of the classical Assignment problem. A minor modification of the Hungarian method of the solution for the latter produces an algorithm for the former. Assignment problems deal with the allocation of items to locations, one to each, in such a way that some optimum return is obtained. Four examples are the following: 1 A. The expected value of orders that will be obtained by salesman i (i = 1, 2,..., n) in sales area j (J = 1, 2 n) is known to be F;y. Assign the salesmen one to each area so that the total expected value is greatest. IB. The comfort and convenience of class j in roomy is assessed by an index Fl7. It is wished to assign the classes, one to each room, so that the least index assigned is maximized. 2A. In 1A suppose that F/y is the distance salesman i has to travel to reach area / Assign the salesmen, one to each area, so that the total distance travelled is a minimum. 2B. Mechanics have to repair pieces of equipment; the time, F/y, for mechanic i to repair equipmentj is known. Assign the mechanics one to each equipment to minimize the time by which all equipments are repaired. Thus, given the n x n matrix (F/y) the four examples require the selection of n elements of the matrix, one from each row and each column Fi y i, F2y2,... TnJtl