Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1641
Tipo: Relatório
Título: Algorithms for scheduling independent jobs with restricted processing times
Autor(es)/Inventor(es): Szwarcfiter, Jayme Luiz
Resumo: 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.
Resumo : 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.
Palavras-chave: Algoritmos
Escalonamento
Algorithms
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 0386
Data de publicação: 30-Abr-1986
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
03_86_000040325.pdf575,93 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.