Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11422/1077| Tipo: | Relatório |
| Título: | Algorithms for two scheduling problems |
| Autor(es)/Inventor(es): | Szwarcfiter, Jayme Luiz Richa, Andréa Werneck |
| Resumo: | 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. |
| Resumo: | 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. |
| Palavras-chave: | Algoritmos Algorithms Escalonamento |
| Assunto CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade produtora: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| In: | Relatório Técnico NCE |
| Número: | 0692 |
| Data de publicação: | 30-Jul-1992 |
| País de publicação: | Brasil |
| Idioma da publicação: | eng |
| Tipo de acesso: | Acesso Aberto |
| Citação: | 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). |
| Aparece nas coleções: | Relatórios |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 06_92_000040791.pdf | 594.96 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.