| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 4.65 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
O presente trabalho estuda o escalonamento em sistemas Job-Shop flexíveis com divisão de
lotes, motivado por um problema real da indústria têxtil. Inicialmente, foi apresentado um
modelo de programação linear inteira mista, com o objetivo de minimizar o tempo de conclusão
de todos os trabalhos, utilizando a técnica de job-splitting, que possibilita a divisão de um lote
em sublotes para operações com múltiplas máquinas disponíveis. Este modelo, implementado
em Python com a biblioteca Pulp e o solver CPLEX, mostrou-se viável para instâncias pequenas,
mas revelou-se incapaz de encontrar soluções em tempos aceitáveis para instâncias de média
dimensão.
Para superar esta limitação, é proposto um Algoritmo Genético Híbrido, que incorpora um
algoritmo de pesquisa local para otimizar tanto o número quanto o tamanho dos sublotes. A
meta-heurística, também desenvolvida em Python, foi testada em diversas instâncias,
apresentando resultados promissores em termos de tempo de CPU. Em avaliações de instâncias
reais da indústria têxtil, foi observado um tempo de CPU de aproximadamente 20 minutos para
uma instância com 57 trabalhos e 35 minutos para uma com 67 trabalhos.
Adicionalmente, foi explorada a técnica de lot streaming, que permite a divisão de trabalhos
em sublotes tratados de forma independente ao longo do processo produtivo. Um modelo de
programação linear inteira mista foi apresentado e implementado, e, embora os resultados
obtidos tenham superado os do job-splitting, este modelo mostrou-se inviável para algumas
instâncias devido aos tempos computacionais.
Este trabalho destaca a importância das técnicas desenvolvidas e evidencia que a aplicação de
meta-heurísticas pode facilitar a obtenção de soluções eficientes para problemas de
escalonamento na indústria, em particular, no setor têxtil.
The present work studies scheduling in flexible job shop systems with lot sizing, motivated by a real problem in the textile industry. First, a mixed-integer linear programming model with jobsplitting is presented to minimise the makespan. This technique enables the division of lots into sub-lots for operations with multiple machines available. This model, implemented in Python using the Pulp library with the CPLEX solver, performed well for small cases but failed to find solutions within acceptable time limits for medium cases. To overcome this limitation, a hybrid genetic algorithm that integrates a local search algorithm to optimise the number and size of the sub-lots is proposed. The metaheuristic, also developed in Python, was tested on several instances and showed promising results in terms of CPU time. In evaluations with real cases from the textile industry, the CPU time was about 20 minutes for a case with 57 jobs and 35 minutes for an instance test with 67 jobs. In addition, the lot streaming technique is explored, enabling the division of lots into sub-lots that are processed independently throughout the production flow. A mixed integer linear programming model was developed and implemented. Although the results surpassed the performance of job-splitting, the model became infeasible for certain instances due to excessive computational time. This work highlights the importance of the techniques developed, demonstrating that metaheuristics can significantly improve the effectiveness of scheduling solutions in industry, particularly in the textile sector.
The present work studies scheduling in flexible job shop systems with lot sizing, motivated by a real problem in the textile industry. First, a mixed-integer linear programming model with jobsplitting is presented to minimise the makespan. This technique enables the division of lots into sub-lots for operations with multiple machines available. This model, implemented in Python using the Pulp library with the CPLEX solver, performed well for small cases but failed to find solutions within acceptable time limits for medium cases. To overcome this limitation, a hybrid genetic algorithm that integrates a local search algorithm to optimise the number and size of the sub-lots is proposed. The metaheuristic, also developed in Python, was tested on several instances and showed promising results in terms of CPU time. In evaluations with real cases from the textile industry, the CPU time was about 20 minutes for a case with 57 jobs and 35 minutes for an instance test with 67 jobs. In addition, the lot streaming technique is explored, enabling the division of lots into sub-lots that are processed independently throughout the production flow. A mixed integer linear programming model was developed and implemented. Although the results surpassed the performance of job-splitting, the model became infeasible for certain instances due to excessive computational time. This work highlights the importance of the techniques developed, demonstrating that metaheuristics can significantly improve the effectiveness of scheduling solutions in industry, particularly in the textile sector.
Description
Keywords
Scheduling Flexible job-shop lot streaming Job-splitting MILP Hybrid genetic algorithm Escalonamento Algoritmo genético híbrido Job-shop flexível Programação linear inteira mista