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
Department : 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)
URI: http://hdl.handle.net/11422/1641
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
03_86_000040325.pdf575,93 kBAdobe PDFView/Open


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