The teacher assignment problem: A special case of the fixed charge transportation problem

The teacher assignment problem: A special case of the fixed charge transportation problem

0.00 Avg rating0 Votes
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: ,
Keywords: education, programming: branch and bound, programming: transportation, programming: assignment
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.