Skip to content

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.


    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.