| dc.creator | Corrêa, Ricardo Cordeiro | |
| dc.creator | Ferreira, Afonso | |
| dc.date | 2017-08-04T13:09:54Z | |
| dc.date | 2023-09-27T03:01:47Z | |
| dc.date | 1996-12-31 | |
| dc.date.accessioned | 2023-09-27T13:10:04Z | |
| dc.date.available | 2023-09-27T13:10:04Z | |
| dc.identifier | 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) | |
| dc.identifier | http://hdl.handle.net/11422/2594 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/8902350 | |
| dc.description | 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. | |
| dc.language | eng | |
| dc.publisher | Brasil | |
| dc.publisher | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais | |
| dc.relation | Relatório Técnico NCE | |
| dc.rights | Acesso Aberto | |
| dc.subject | Multiplus multiprocessor | |
| dc.subject | Escalonamento multidimensional | |
| dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO | |
| dc.title | A polynomial-time branching procedure for the multiprocessor scheduling problem | |
| dc.type | Relatório | |
