Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 The teacher assignment problem: A special case of the fixed charge transportation problem
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
authors: Hultberg, T.H.
Cardoso, D.M.
keywords: 0-1 integer programming
Branch and bound
Fixed charge transportation problem
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.
URI: http://hdl.handle.net/10773/4317
ISSN: 0377-2217
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S0377221796000823
source: European Journal of Operational Research
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
EJOR-HultbergCardoso1997.pdfEletronicVersion619.72 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

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


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2