Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/2594
Tipo: Relatório
Título: A polynomial-time branching procedure for the multiprocessor scheduling problem
Autor(es)/Inventor(es): Corrêa, Ricardo Cordeiro
Ferreira, Afonso
Resumo : In this paper, we present and analyze a branching procedure suitable for branchand-bound algorithms for solving multiprocessor scheduling problems. The originality of this branching procedure resides mainly in its ability to enumerate all feasible solutions without generating duplicated subproblems. This procedure is shown to be polynomial in time and space complexities. The main applications of such branching procedure are instances of the MSP where the costs are large because the height of the search tree is linear on the number of tasks to be scheduled. This in opposition to another branching procedure in the literature that generates a search tree whose height is porportional to the costs of the tasks.
Palavras-chave: Multiplus multiprocessor
Escalonamento multidimensional
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 0496
Data de publicação: 31-Dez-1996
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: CORRÊA, R. C.; FERREIRA, A. A polynomial-time branching procedure for the multiprocessor scheduling problem. Rio de Janeiro: NCE, UFRJ, 1996. 31 p. (Relatório Técnico, 04/96)
URI: http://hdl.handle.net/11422/2594
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
04_96.pdf1,65 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.