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:MAT - Artigos

Files in This Item:
File Description SizeFormat 
EJOR-HultbergCardoso1997.pdfEletronicVersion619.72 kBAdobe PDFView/Open    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.