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. / 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.
| Identifer | oai:union.ndltd.org:usp.br/oai:teses.usp.br:tde-22042015-165306 |
| Date | 29 September 2014 |
| Creators | Lemos, Rafael de Freitas |
| Contributors | Ronconi, Debora Pretti |
| Publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| Source Sets | Universidade de São Paulo |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | Dissertação de Mestrado |
| Format | application/pdf |
| Rights | Liberar o conteúdo para acesso público. |
Page generated in 0.0028 seconds