Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/4317
Título: | The teacher assignment problem: A special case of the fixed charge transportation problem |
Autor: | Hultberg, T.H. Cardoso, D.M. |
Palavras-chave: | 0-1 integer programming Branch and bound Fixed charge transportation problem Algorithms Computational complexity Integer programming Mathematical models |
Data: | 1997 |
Editora: | Elsevier |
Resumo: | 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 |
Versão do Editor: | http://www.sciencedirect.com/science/article/pii/S0377221796000823 |
Aparece nas coleções: | DMat - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
EJOR-HultbergCardoso1997.pdf | EletronicVersion | 619.72 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.