H301 Assignment Problem

Subroutine subprogram ASSNDX solves the so-called Assignment problem: Given an $n\; xm$ matrix A of real numbers $a(i,j)$ , find either

1. a set $k(1),k(2),...,k(n)\in 1,2,...,m,0,...,0$ , where $0,...,0$ indicates $max(n-m,0)$ zeros, and where for non-zero elements $k(p)\; \ne k(q)$ for $p\; \ne q$ , which minimizes

   $S\; =\; \sum$_i=1ⁿa(i,k(i))

   assuming that $a(i,0)=0$ , or

2. a set $k(1),k(2),...,k(m)\in 1,2,...,n,0,...,0$ , where $0,...,0$ indicates $max(m-n,0)$ zeros, and where for non-zero elements $k(p)\; \ne k(q)$ for $p\; \ne q$ , which minimizes

   $S\; =\; \sum$_j=1^ma(k(j),j)

   assuming that $a(0,j)=0$ .

Structure:

SUBROUTINE subprogram
User Entry Names: ASSNDX
Files Referenced: Unit 6

Usage:

    CALL ASSNDX(MODE,A,N,M,IDA,K,SMIN,IW,IDW)

MODE

( INTEGER) Must be set either 1 (for case (1)), or 2 (for case (2)).

A

( REAL) Two-dimensional array of dimension ($IDA,\ge M$ ). Must contain, on entry, the matrix A. Destroyed during execution.

N

( INTEGER) Number n of rows of A.

M

( INTEGER) Number m of columns of A.

IDA

( INTEGER) Declared first dimension of A in the calling program ($IDA\; \ge N)$ .

K

( INTEGER) One-dimensional array of length $\ge max(N,M)$ . Contains, on exit, the assigned set of integers $k(1),...,k(n)$ or $k(1),...,k(m)$ , respectively.

SMIN

( REAL) The calculated minimum value of S.

IW

( INTEGER) Two-dimensional array of dimension ($IDW,\ge 6$ ). Used as working space.

IDW

( INTEGER) Declared first dimension of IW in the calling program ($IDW\; \ge max(N,M)$ ).

Method:

The subprogram is based on the Algol procedure given in Ref. 3.

Error handling:

Error H301.1: or .
A message is written on Unit 6, unless subroutine MTLSET (N002) has been called.

Examples:

The following example illustrates a possible use of the subprogram. A workshop has to carry out N jobs, each of which can be performed on any of $M\; (>N)$ available machines. The cost of performing job I on machine J is $A(I,J)$ . It is required to assign jobs to machines in such a way as to minimize the total cost. The solution is obtained by calling the subprogram with $MODE=1$ and then assigning job I to machine $K(I),\hspace{0.17em}(I=1,2,...,N)$ .

References:

1. J. Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957) 32--38.
2. R. Silver, An algorithm for the assignment problem, Comm. ACM 3 (1960) 605--606.
3. R. Silver, Algorithm 27 ASSIGNMENT, Collected Algorithms from CACM (1960).

Input/Output

I101