Métodos heurísticos construtivos para o problema de programação de operações Flow Shop híbrido com estágio de produção dominante
Data
2017-11-15
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Biblioteca Digital de Teses e Dissertações da USP
Universidade de São Paulo
Escola de Engenharia de São Carlos
Universidade de São Paulo
Escola de Engenharia de São Carlos
Resumo
Descrição
Este trabalho trata o problema multi-estágios de programação da produção em ambientes Flow Shop com máquinas paralelas, apresentando um estágio de produção dominante (máquina única), no qual os tempos de preparação (setup) da máquina são assimétricos e dependentes da seqüência de execução das tarefas. Tal ambiente é constituído de k estágios de produção, com k = {4, 7}, divididos em três etapas assim definidas: na etapa um, o número de estágios de produção pode variar de um até cinco e cada estágio será constituído de m1 máquinas paralelas idênticas , com m1 ∈ {2, 3, 4}, o que determina m1 flow shops paralelos. A etapa dois constitui o estágio dominante d, cuja localização oscila dependendo do número de estágios das etapas um e três. Por ultimo, a etapa três, semelhante à etapa um, possui m2 máquinas paralelas idênticas, onde m2 ∈ {2, 3, 4} e m1 e m2 são gerados aleatoriamente. Todas as tarefas são processadas nas três etapas e o critério de desempenho é a otimização da duração total da programação (makespan) e também a análise do deslocamento do estágio dominante. A programação das tarefas é feita separadamente em cada uma das etapas. Na primeira etapa foi utilizado o método heurístico N&M para cada um dos m1 flow shops paralelos. Para segunda etapa foram desenvolvidos quatro regras e dois métodos heurísticos construtivos com base nos problemas do caixeiro viajante (TSP). Na última etapa, a alocação das tarefas é feita por ordem de chegada na máquina disponível ou com menor carga. Não foram encontrados na literatura trabalhos que retratassem ambientes dessa natureza, logo os métodos desenvolvidos foram comparados entre si. A experimentação computacional analisou os resultados obtidos por meio da porcentagem de sucesso de cada regra, desvio relativo entre os resultados de cada regra, deslocamento da posição do estágio dominante, influência das ordens de grandeza dos tempos de processamento e setup e tempo médio de computação.
This dissertation deals with problem multi-periods of production scheduling of the in Flow Shop environment with parallel machines, presenting a period of dominant production (single machine), in which the setup times for the processing of the jobs is asymmetric and sequence dependent on the execution of the jobs. Such environment is constituted by k periods of production, with k = {4, 7} divided in to three stages defined as: First stage: In stage one the number of production periods can vary from one to five, and each period will be constituted of m1 ∈ {2, 3, 4} identical parallel machines, determining m1 parallel flow shops. Stage two - It constitutes the dominant period d, whose localization oscillates between the periods of stages one and three. Finally stage three it is similar to stage one, and has m2 ∈ {2, 3, 4} identical parallel machines, where m1 and m2 Randomly generated. All the jobs are processed in the three stages and the objective is to optimize the total time to complete the scheduling (makespan) and also to analyze the displacement of the dominant period position. The scheduling of the jobs was performed separately in each of the stages. In the first stage the heuristic method N&M was used for each m1 parallel flow shops. In the second stage four constructive rules and two heuristic methods were developed based on traveling salesman problems (TSP). In the last stage the allocation of the jobs was performed according to the arrival time of the available machine or with lesser load. This type of work has not been found in literature; therefore the developed methods were compared among themselves. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation and average computational time. The displacement of the dominant period position as well as the influence of the relation of setup-times and processing-times, were also studied. The results of computational experience are discussed.
This dissertation deals with problem multi-periods of production scheduling of the in Flow Shop environment with parallel machines, presenting a period of dominant production (single machine), in which the setup times for the processing of the jobs is asymmetric and sequence dependent on the execution of the jobs. Such environment is constituted by k periods of production, with k = {4, 7} divided in to three stages defined as: First stage: In stage one the number of production periods can vary from one to five, and each period will be constituted of m1 ∈ {2, 3, 4} identical parallel machines, determining m1 parallel flow shops. Stage two - It constitutes the dominant period d, whose localization oscillates between the periods of stages one and three. Finally stage three it is similar to stage one, and has m2 ∈ {2, 3, 4} identical parallel machines, where m1 and m2 Randomly generated. All the jobs are processed in the three stages and the objective is to optimize the total time to complete the scheduling (makespan) and also to analyze the displacement of the dominant period position. The scheduling of the jobs was performed separately in each of the stages. In the first stage the heuristic method N&M was used for each m1 parallel flow shops. In the second stage four constructive rules and two heuristic methods were developed based on traveling salesman problems (TSP). In the last stage the allocation of the jobs was performed according to the arrival time of the available machine or with lesser load. This type of work has not been found in literature; therefore the developed methods were compared among themselves. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation and average computational time. The displacement of the dominant period position as well as the influence of the relation of setup-times and processing-times, were also studied. The results of computational experience are discussed.
Palavras-chave
Setup dependente, Programação da produção, Estágio dominante, Flow Shop híbrido, Métodos heurísticos, Production scheduling, Hybrid flow shop, Heuristic methods, Dominant period, Dependent setup