Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
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 |
| Production unit: | 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). |
| Appears in Collections: | Relatórios |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 06_92_000040791.pdf | 594.96 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.