Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-09-05T17:12:27Z
No. of bitstreams: 1
texto completo.pdf: 804859 bytes, checksum: ed4ee44a672aa18b9e35cf4a363ab38a (MD5) / Made available in DSpace on 2018-09-05T17:12:27Z (GMT). No. of bitstreams: 1
texto completo.pdf: 804859 bytes, checksum: ed4ee44a672aa18b9e35cf4a363ab38a (MD5)
Previous issue date: 2017-12-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda um problema de sequenciamento (scheduling) onde as tarefas são processadas em lotes em máquinas paralelas idênticas. Neste problema uma má- quina pode executar um conjunto (lote) de tarefas simultaneamente. Além disso, as tarefas são classificadas em famílias, onde uma família agrupa tarefas que possuam alguma característica em comum. Assim, os lotes devem conter somente tarefas de uma mesma família. O problema também considera tarefas com diferentes tempos de chegada (release times) e tempos de processamento. As tarefas possuem ainda uma data de entrega e uma prioridade. O problema consiste em determinar os lo- tes (grupos) de tarefas para serem sequenciados nas máquinas de tal maneira que o atraso total ponderado das tarefas seja minimizado. O problema envolvendo se- quenciamento de lotes, que é uma extensão do sequenciamento de tarefas clássico (onde uma máquina processa somente uma tarefa por vez), possui muitas aplicações reais, como em indústrias de fundição, de fabricação de móveis, de processamento de metais, de processamento de alimentos, farmacêuticas e de semicondutores. Para resolver o problema abordado, três algoritmos baseados em meta-heurísticas foram desenvolvidos: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) e Simulated Annealing (SA). Todos estes algoritmos utilizam técnicas de busca em vizinhança para melhorar a qualidade de uma solução. As meta-heurísticas ALNS, IG e SA possuem estruturas simples e elas têm sido aplicadas satisfatoriamente para resolver diferentes problemas de otimização combinatória, especialmente problemas de sequenciamento da produção, o que justifica a utilização para o problema em es- tudo. Experimentos computacionais, utilizando dados da literatura foram realizados a fim de avaliar o desempenho dos algoritmos. Os resultados são comparados com os resultados gerados por dois algoritmos da literatura (Memetic Algorithm e Variable Neighborhood Search) e com os resultados da resolução do modelo matemático do problema. Os experimentos e testes realizados demonstram que os algoritmos de- senvolvidos neste trabalho geram soluções válidas de excelente qualidade superando as melhores soluções apresentadas na literatura. / This work addresses a scheduling problem where the jobs are processed in batches on a identical parallel machines. In this problem a machine can process a set (batch) of jobs simultaneously. In addition, jobs are classified into families, where a family groups jobs that have some characteristic in common. Thus, the batches must con- tain only jobs of a same family. Also, the problem considers jobs with different release times and processing times. The jobs also have a due date and a priority. The objective of the problem is to group the job set into batches and assign the batches to the parallel machines in order to minimize the total weighted tardiness of the jobs. The parallel batch processing machines scheduling problem, that is an extension of classic job sequencing(where a machine processes only one task at a time) has many real application, such as in the foundry industry manufacturing, food processing industries, pharmaceutical industries and semiconductor industries. To solve this problem, three algorithms based on meta-heuristics were developed: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) and Simula- ted Annealing (SA). All of these algorithms use neighborhood search techniques to improve the quality of solutions. In addition, the meta-heuristics ALNS, IG and SA have been applied satisfactorily to solve different combinatorial optimization problems. Computational experiments using literature data were performed to eva- luate the performance of the algorithms. The obtained results are compared with the results generated by two algorithms from the literature (Memetic Algorithm and Variable Neighborhood Search) and with the mathematical model of the problem. The computational experiments demonstrate that the algorithms developed in this work generate valid solutions of excellent quality, outperforming the best solutions presented in the literature.
| Identifer | oai:union.ndltd.org:IBICT/oai:localhost:123456789/21644 |
| Date | 14 December 2017 |
| Creators | Fidelis, Michele Bernardino |
| Contributors | Arroyo, José Elias Claudio |
| Publisher | Universidade Federal de Viçosa |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFV, instname:Universidade Federal de Viçosa, instacron:UFV |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0026 seconds