• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2014.tde-22042015-165306
Documento
Autor
Nome completo
Rafael de Freitas Lemos
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2014
Orientador
Banca examinadora
Ronconi, Debora Pretti (Presidente)
Ho, Linda Lee
Nagano, Marcelo Seido
Título em português
Heurística para o problema estocástico de programação de máquina única com minimização de earliness e tardiness.
Palavras-chave em português
Determinação de datas
Earliness/Tardiness
Heurística
Máquina única
Programação estocástica de tarefas
Resumo em português
O presente trabalho aborda o problema de determinação de datas de entrega e o sequenciamento de tarefas com tempos de processamento estocásticos. O ambiente considerado constitui em uma máquina simples e tarefas com custos individuais e distintos de adiantamento e atraso de entrega (earliness e tardiness ou simplesmente E/T). O objetivo é determinar a sequência e as datas de entrega ótimas que simultaneamente minimizam o custo total esperado de E/T. Para a determinação de sequências candidatas, são apresentadas diversas heurísticas construtivas com tempo de execução polinomial baseadas em um método de inserção de tarefas. Considerando tarefas com distribuição normal, experimentos computacionais comprovam a eficácia dos algoritmos para problemas de menor porte, os quais fornecem soluções ótimas em 99,85% dos casos avaliados. Quando aplicadas a um conjunto com uma maior quantidade de tarefas, as heurísticas apresentaram resultados melhores do que o algoritmo disponível na literatura em mais de 80% dos casos. Consideradas tarefas com distribuição lognormal, obteve-se um percentual de otimalidade entre 93,87% e 96,45%, a depender da heurística aplicada. Demonstra-se ainda para o caso com distribuição normal que os métodos propostos são assintoticamente ótimos e, portanto, são indicados para a resolução de problemas de grande porte.
Título em inglês
Heuristics for the stochastic single-machine problem with E/T costs.
Palavras-chave em inglês
Due-date assignment
Earliness/Tardiness
Heuristic
Single machine
Stochastic scheduling
Resumo em inglês
This work addresses the problem of concurrent due-date assignment and sequencing of a set of jobs on a stochastic single-machine environment with distinct job earliness and tardiness penalty costs. It is assumed that the jobs processing times are statistically independent and follow a normal distribution whose mean and variance are provided and they are not necessarily integer values. The objective is to determine the job sequence and the integer due dates which minimize the expected total earliness and tardiness costs. Several efficient insertion-based construction heuristics are proposed in order to find candidates for the optimal sequence with polynomial time complexity. For the normal distribution problem, numerical experiments show that the proposed heuristic methods are able to find the optimal solution in 99,85% when applied to problems with a smaller size. When applied to problems with a bigger size, the solutions found by the proposed heuristics had better costs than the solutions described in the literature in more than 80% of cases. For the lognormal distribution problem, the proposed heuristic methods provided solutions with a percentage of optimality between 93,87% and 96,45%. Furthermore, for the normal distribuition case, it was proven that the heuristics are asymptotically optimal, i.e., it can be used for problems of any size.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2015-04-29
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • LEMOS, R. F., and Ronconi, Debora P. A HEURISTIC FOR THE STOCHASTIC SINGLE-MACHINE PROBLEM WITH E/T COSTS. In 22nd International Conference on Production Research, Foz de Iguaçu, 2013. 22nd International Conference on Production Research.Foz de Iguaçu : International Foundation for Production Research, 2013.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.