Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1077
Type: Relatório
Title: Algorithms for two scheduling problems
Author(s)/Inventor(s): Szwarcfiter, Jayme Luiz
Richa, Andréa Werneck
Abstract: Descrevemos algoritmos para resolver os dois problemas de escalonamento envolvendo processadores paralelos idênticos, que se seguem. Cada tarefa necessita de uma unidade de tempo de processamento, tem uma data de chegada e um peso associados. O primeiro problema também envolve a existência de prazos e consiste em minimizar o somatório ponderado das tarefas tardias. Já o segundo problema consiste em se minimizar o somatório ponderado dos tempos de término das tarefas. Os algoritmos propostos rodam em tempos O((1+log m)n² /m) e O((log n+n/m)n), respectivamente.
Abstract: We describe algorithms for solving the following two scheduling problems on identical pa.rallel processors. Each job requires unit processing time, has a release date and a weight. The first problem also involves the existence of dea.dlines and consists of minimizing the weighted sum of tardy jobs. The second consists of minimizing the weighted sum of completion times. The proposed algorithms run in time 0((1 + log m)n² /m) and O((log n + n/m)n), respectively.
Keywords: Algoritmos
Algorithms
Escalonamento
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0692
Issue Date: 30-Jul-1992
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: SZWARCFITER, J. L.; RICHA, A. W. Algorithms for two scheduling problems. Rio de Janeiro: NCE, UFRJ, 1992. 7 p. (Relatório Técnico, 06/92).
URI: http://hdl.handle.net/11422/1077
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
06_92_000040791.pdf594,96 kBAdobe PDFView/Open


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