# Assignment Problem With Multiple Assignments For Students

1.

Balinski, M. L.,*Signature Methods for the Assignment Problem*, Operations Research, Vol. 33, pp. 527–536, 1985.Google Scholar

2.

Barr, R. S., Glover, F., andKlingman, D.,*The Alternating Basis for Assignment Problems*, Mathematical Programming, Vol. 13, pp. 1–13, 1977.Google Scholar

3.

Hung, M. S., andRom, W. O.,*Solving the Assignment Problem by Relaxation*, Operations Research, Vol. 28, pp. 969–982, 1980.Google Scholar

4.

McGinnis, F.,*Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem*, Operations Research, Vol. 31, pp. 277–291, 1983.Google Scholar

5.

Kuhn, H. W.,*The Hungarian Method for the Assignment Problem*, Naval Research Logistics Quarterly, Vol. 2, pp. 83–97, 1955.Google Scholar

6.

Lawler, E. L.,*Combinatorial Optimization: Networks and Matroids*, Holt, Rinehart, and Winston, New York, New York, 1976.Google Scholar

7.

Garfinkel, R. S.,*An Improved Algorithm for the Bottleneck Assignment Problem*, Operations Research, Vol. 18, pp. 1747–1751, 1971.Google Scholar

8.

Ravindran, A., andRamaswamy, V.,*On the Bottleneck Assignment Problem*, Journal of Optimization Theory and Applications, Vol. 21, pp. 451–458, 1979.Google Scholar

9.

Baksi, H. C., Bhatia, H. L., andPuri, M. C.,*Tradeoff Relations in Assignment Problems*, Cahiers du CERO, Vol. 21, pp. 367–374, 1979.Google Scholar

10.

Berman, O., Einav, D. andHandler, G.,*The Constrained Bottleneck Problem in Networks*, Operations Research, Vol. 38, pp. 178–181, 1990.Google Scholar

11.

Geetha, S., andNair, K. P. K.,*A Variation of the Assignment Problem*, European Journal of Operational Research, Vol. 68, pp. 422–426, 1993.Google Scholar

12.

Bazaraa, M. S., andJarvis, J. J.,*Linear Programming and Network Flows*, 2nd Edition, John Wiley and Sons, New York, New York, 1990.Google Scholar

In the following we are facing the problem of multiple assignments of the hungarian algorithm.

Scenario:

We have 100 students and 5 courses, which the students can vote with priority. So every student will get assigned for one specific course.

Priority from 1 to 5. 1 lowest, 5 highest

The raw data would look like this:

Obviously there are more rows than columns.

The problem we are facing is: we need more than one assignment per column.

Here is the PHP code which is responsible to do assignments with the Hungarian algorithm returning invalid results.

**EDIT**: Here is the Sktip returning VALID RESULTS.

Note: Please be patient, this is a low quality port from Java.

Hence the algorithm is making a square matrix of this one, the result presents corrupted data.

I thought about diverse solutions.

Cut the matrix according to the column size, to produce a lot of square matrizes. This may break the algorithms main function.

Another solution is to assign as much as possible, and handle the rest in a new routine until there are no more entries left.

Apparently the algorithm does not yet provide this ability.

Is there maybe a solution to do this in MySQL, hence the raw data is stored in an MySQL DBS.

phpalgorithmassignsubgraphpairing-heap