Estágio realizado na empresa Swedwood Portugal e orientado pelo Engº. Luís Vasques / Tese de mestrado integrado. Engenharia industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2010

Este trabalho dedica-se ao problema de programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de execução das tarefas com o objetivo de minimizar a duração total da programação (Makespan). Por intermédio de investigações realizadas sobre as características estruturais do problema de programação e sua solução, uma propriedade deste problema é apresentada. Esta propriedade, denominada \"Propriedade LBY\", considerando quaisquer duas tarefas adjacentes Ju e Jv (Ju imediatamente precede Jv) independentemente de suas posições na seqüência de tarefas, fornece, um limitante inferior do tempo de espera para a tarefa Jv entre o fim do seu processamento na máquina Mk e o início do seu processamento na máquina seguinte. Dois novos métodos heurísticos são desenvolvidos, com base na propriedade apresentada e no procedimento de inserção de tarefas dos conhecidos métodos N&M e NEH: um construtivo, denominado BMc; e, um melhorativo, denominado BMm. Os métodos heurísticos propostos são comparados com os métodos heurísticos melhorativos de Cao; Bedworth (1992) e Rajendran; Ziegler (1997), através de um grande número de problemas gerados aleatoriamente. Os tempos de processamento são distribuídos no intervalo [1, 99] e os tempos de setup nos intervalos de [1, 49], [1, 99], [51, 149] e [101, 199]. Os métodos são avaliados quanto à porcentagem de sucesso em obter a melhor solução, ao desvio relativo médio e o tempo médio de computação. Os resultados da experimentação computacional mostram a qualidade do método construtivo BMc e a melhor performance do método melhorativo BMm. Estes resultados são apresentados e discutidos. / This work addresses the permutation flow shop scheduling problem with separated, non-batch, and sequence-independent setup times with the objective of minimizing the total time to complete the schedule (Makespan). Following an investigation of problem structural characteristics and your solution a property of this scheduling problem is presented. This property, denoted by \"Property LBY\", given any two adjacent jobs Ju e Jv (Ju immediately precedes Jv), regardless of their position in the sequence of jobs, provides an lower bound of the waiting time for job Jv between the end of its operations on the machine Mk and the beginning on machine M(k+1). Two news heuristics methods are development, on the basis of the presented property and in the job insertion procedure of the known methods named N&M and NEH: one constructive, denote by BMc; and, one improvement, denote by BMm. The proposed heuristics methods are compared with the improvement heuristics methods of Cao; Bedworth (1992) and Rajendran; Ziegler (1997), by a large number of randomly generated problems. The processing time are sampled from a distribution ranging from [1, 99] and, the setup times are sampled from distributions ranging from [1, 49], [1, 99], [51, 149] and [101, 199]. The methods are evaluated by the percentage of success in find the best solution, the average relative deviation and the average computation time. The results of the computational investigation show the quality of the constructive heuristic method BMc and that the improvement heuristic method BMc outperforms all others. These results are presented and discussed.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.

Este trabalho dedica-se ao problema de programação em flow shop permutacional com tempos de setup separados dos tempos de processamento e independentes da seqüência de execução das tarefas com o objetivo de minimizar a duração total da programação (Makespan). Por intermédio de investigações realizadas sobre as características estruturais do problema de programação e sua solução, uma propriedade deste problema é apresentada. Esta propriedade, denominada \"Propriedade LBY\", considerando quaisquer duas tarefas adjacentes Ju e Jv (Ju imediatamente precede Jv) independentemente de suas posições na seqüência de tarefas, fornece, um limitante inferior do tempo de espera para a tarefa Jv entre o fim do seu processamento na máquina Mk e o início do seu processamento na máquina seguinte. Dois novos métodos heurísticos são desenvolvidos, com base na propriedade apresentada e no procedimento de inserção de tarefas dos conhecidos métodos N&M e NEH: um construtivo, denominado BMc; e, um melhorativo, denominado BMm. Os métodos heurísticos propostos são comparados com os métodos heurísticos melhorativos de Cao; Bedworth (1992) e Rajendran; Ziegler (1997), através de um grande número de problemas gerados aleatoriamente. Os tempos de processamento são distribuídos no intervalo [1, 99] e os tempos de setup nos intervalos de [1, 49], [1, 99], [51, 149] e [101, 199]. Os métodos são avaliados quanto à porcentagem de sucesso em obter a melhor solução, ao desvio relativo médio e o tempo médio de computação. Os resultados da experimentação computacional mostram a qualidade do método construtivo BMc e a melhor performance do método melhorativo BMm. Estes resultados são apresentados e discutidos. / This work addresses the permutation flow shop scheduling problem with separated, non-batch, and sequence-independent setup times with the objective of minimizing the total time to complete the schedule (Makespan). Following an investigation of problem structural characteristics and your solution a property of this scheduling problem is presented. This property, denoted by \"Property LBY\", given any two adjacent jobs Ju e Jv (Ju immediately precedes Jv), regardless of their position in the sequence of jobs, provides an lower bound of the waiting time for job Jv between the end of its operations on the machine Mk and the beginning on machine M(k+1). Two news heuristics methods are development, on the basis of the presented property and in the job insertion procedure of the known methods named N&M and NEH: one constructive, denote by BMc; and, one improvement, denote by BMm. The proposed heuristics methods are compared with the improvement heuristics methods of Cao; Bedworth (1992) and Rajendran; Ziegler (1997), by a large number of randomly generated problems. The processing time are sampled from a distribution ranging from [1, 99] and, the setup times are sampled from distributions ranging from [1, 49], [1, 99], [51, 149] and [101, 199]. The methods are evaluated by the percentage of success in find the best solution, the average relative deviation and the average computation time. The results of the computational investigation show the quality of the constructive heuristic method BMc and that the improvement heuristic method BMc outperforms all others. These results are presented and discussed.

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2016-10-20T17:39:38Z No. of bitstreams: 2 Dissertação - Fernanda Neiva Mesquita - 2015.pdf: 2481424 bytes, checksum: 2263ae4d21d732d49ebd0e6d2e2763c6 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-10-21T19:23:42Z (GMT) No. of bitstreams: 2 Dissertação - Fernanda Neiva Mesquita - 2015.pdf: 2481424 bytes, checksum: 2263ae4d21d732d49ebd0e6d2e2763c6 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-10-21T19:23:42Z (GMT). No. of bitstreams: 2 Dissertação - Fernanda Neiva Mesquita - 2015.pdf: 2481424 bytes, checksum: 2263ae4d21d732d49ebd0e6d2e2763c6 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2015-12-15 / This study deals with problems of parallel machines with independent setup times, different dates of release and minimizing the makespan. The production environment is common in the auto industry that there may be jobs through the production line, they are added new machines or equal equipment to expand productive capacity. Any production process requires effective management by the Production Planning and Control (PCP). This activity includes the planning of production, so the allocation of resources for task execution on a time basis. The programming activity is one of the most complex tasks in the management of production because the need to deal with several different types of resources and concurrent activities. Furthermore, the number of solutions grows exponentially in several dimensions, according to the number of tasks, operations or machines, thereby generating a combinatorial nature of the problem. The environment treated in this work each task has the same processing time on any machine. Considering only the restriction independently of the task setup time waiting for processing and the presence of release dates different from zero very practical characteristics in industries. As were found in the literature work that deals of this work environment, even less that used the meta-heuristic Simulated Anneling, so we developed the method to the problem, along with the initial solution their disturbance schemes and the setting of lower bounds for the makespan. / Este estudo trata de problemas de máquinas paralelas com tempos de setup independentes, diferentes datas de liberação e minimização do makespan. Este ambiente de produção é comum na indústria automobilística que pode haver postos de trabalho em meio à linha de produção, em que são adicionadas novas máquinas ou equipamentos iguais para ampliar a capacidade produtiva. Qualquer processo produtivo requer um gerenciamento eficaz por meio do Planejamento e Controle da Produção (PCP). Esta atividade inclui a programação da produção, ou seja, a alocação de recursos para execução de tarefas em uma base de tempo. A atividade de programação é uma das tarefas mais complexas no gerenciamento da produção, pois a necessidade de lidar com diversos tipos diferentes de recursos e atividades simultâneas. Além disso, o número de soluções cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações ou máquinas, gerando assim uma natureza combinatória ao problema. O ambiente tratado neste trabalho cada tarefa tem o mesmo tempo de processamento em qualquer máquina. Considerando a restrição de tempos de setup independente apenas da tarefa que espera por processamento e a presença de datas de liberação diferentes de zero características muito práticas nas indústrias. Como não foram encontrados na literatura trabalho que tratasse desse ambiente de trabalho, ainda menos que utilizasse a meta-heurística Simulated Anneling, então foi desenvolvido o método para o problema, juntamente com a solução inicial os respectivos esquemas de perturbação e a definição de limitantes inferiores para o makespan.