Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2594
Type: Relatório
Title: A polynomial-time branching procedure for the multiprocessor scheduling problem
Author(s)/Inventor(s): Corrêa, Ricardo Cordeiro
Ferreira, Afonso
Abstract: 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.
Keywords: Multiplus multiprocessor
Escalonamento multidimensional
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0496
Issue Date: 31-Dec-1996
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: 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
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
04_96.pdf1,65 MBAdobe PDFView/Open


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