Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/4317
Title: | The teacher assignment problem: A special case of the fixed charge transportation problem |
Author: | Hultberg, T.H. Cardoso, D.M. |
Keywords: | 0-1 integer programming Branch and bound Fixed charge transportation problem Algorithms Computational complexity Integer programming Mathematical models |
Issue Date: | 1997 |
Publisher: | Elsevier |
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, concludes the paper. © 1997 Elsevier Science B.V. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/4317 |
ISSN: | 0377-2217 |
Publisher Version: | http://www.sciencedirect.com/science/article/pii/S0377221796000823 |
Appears in Collections: | DMat - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
EJOR-HultbergCardoso1997.pdf | EletronicVersion | 619.72 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.