Article ID: | iaor19991804 |
Country: | Netherlands |
Volume: | 101 |
Issue: | 3 |
Start Page Number: | 463 |
End Page Number: | 473 |
Publication Date: | Sep 1997 |
Journal: | European Journal of Operational Research |
Authors: | Cardoso Domingos M., Hultberg Tim H. |
Keywords: | education, programming: branch and bound, programming: transportation, programming: assignment |
A basic model of the task of assigning classes to professors, in such a way that the average number of distinct subjects assigned to each professor is minimized, is formulated as a mixed integer program. It turns out that the problem is a special case of the fixed charge transportation problem which in some cases corresponds to finding a basic solution of a transportation problem which is as degenerate as possible. We present an equivalent alternative formulation of the problem which makes it easy to prove that it is NP-hard in the strong sense and an exact branch and bound algorithm for its solution based on this alternative formulation is outlined. Computational experiments with data from a concrete problem conclude the paper.