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/1641| Type: | Relatório |
| Title: | Algorithms for scheduling independent jobs with restricted processing times |
| Author(s)/Inventor(s): | Szwarcfiter, Jayme Luiz |
| Abstract: | Descrevemos algoritmos para R//Cmax, P//Cmax e RM//Cmax. Seja a menor cardinalidade de um subconjunto de tarefas, onde duas quaisquer dessas possuem tempos de processamento diferentes em alguma máquina. e Se k é fixo, os algoritmos terminam em tempo polinomial. Nesse caso, se adicionalmente o tempo de processamento máximo for expresso como um polinômio no número n de tarefas então Rm//Cmax pode ser resolvido em tempo 0 (n). Os algoritmos propostos permitem que os tempos de processamento sejam números reais, exceto no problema Rm//Cmax' qye os restringe a inteiros. |
| Abstract: | We describe exact algorithms for R//Cmax' P//Cmax and RM//Cmax. Let k be the maximum cardinality of a subset of jobs, any two of them with different processing times in some machine. If k is fixed the algorithms terminate within polynomial time. In this case, if additionally the maximum processing time can be expressed as a polynomial in the number n of jobs then Pm//Cmax can be solved in 0 (n) time. The proposed algorithms allow the processing times to be real numbers, except that for Pm//max which restricts them to integers. |
| Keywords: | Algoritmos Escalonamento Algorithms |
| 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: | 0386 |
| Issue Date: | 30-Apr-1986 |
| Publisher country: | Brasil |
| Language: | eng |
| Right access: | Acesso Aberto |
| Citation: | SZWARCFITER, J. L. Algorithms for scheduling independent jobs with restricted processing times. Rio de Janeiro: NCE, UFRJ, 1986. 8 p. (Relatório Técnico, 03/86) |
| Appears in Collections: | Relatórios |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 03_86_000040325.pdf | 575.93 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.