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.

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.

Made available in DSpace on 2016-06-02T19:52:03Z (GMT). No. of bitstreams: 1 5761.pdf: 2593684 bytes, checksum: 000d3a163875f2beb7e15774305fbab2 (MD5) Previous issue date: 2014-02-18 / Financiadora de Estudos e Projetos / Many scheduling problems found in the literature are classified as NP-Hard, which means that the computational costs of the solutions within known exact mathematical methods can be very time consuming. In the case of partial outsourcing it is essential to consider the outsourcing decisions inside the scheduling problem to achieve optimal results from outsourcing. This project discusses the following issue: a single machine environment where the setup times are sequence-dependent and there is an outsourcing option. The goal is to determinate the set of jobs that will be outsourced and the production sequence of the jobs that will be performed inhouse, aiming to eliminate the total tardiness of all jobs, witch is a NP-Had problem. New approaches regarding meta-heuristics, like ACO (Ant Colony Optimization) show a new horizon for this kind of issues. The hybrid algorithm, including ACO and local search methods, reached the optimal values in 94,7% of the problems. / Diversos problemas de scheduling são classificados na literatura como NP-Difíceis, o que significa que os custos computacionais das soluções desenvolvidas usando métodos exatos conhecidos são muito altos para esses problemas. No caso da possibilidade de terceirização de parte das tarefas existentes se torna vital inserir essas decisões nos problemas de scheduling visando à obtenção de resultados ótimos para os objetivos de desempenho. O presente trabalho trata de um caso como esse: um ambiente de máquina única onde os tempos de setup são dependentes da sequência de execução das operações e com a possibilidade de terceirização. O objetivo é determinar a sequência de operações executadas no ambiente de máquina única e o conjunto de operações a serem terceirizadas de forma que nenhuma das ordens de serviço seja entregue com atraso e o custo de terceirização seja mínimo. A aplicação de meta-heurísticas, como o ACO (Ant Colony Optimization) abre um novo horizonte para o desenvolvimento de soluções para problemas este, classificado como NP-Difícil, sobretudo quando aplicadas em conjunto com métodos de busca local para o refinamento das soluções. Os resultados demontram que o algoritmo híbrido incluindo ACO e busca local, obteve resultados significativos, atingindo a resposta ótima em 94,7% dos problemas.