Publication
Desenvolvimento de um algoritmo greedy randomized adaptive search procedure para a programação de máquinas paralelas dedicadas com setups e recursos adicionais e datas de entrega
| datacite.subject.fos | Engenharia e Tecnologia | |
| datacite.subject.sdg | 09:Indústria, Inovação e Infraestruturas | |
| dc.contributor.advisor | Lopes, Manuel Joaquim Pereira | |
| dc.contributor.author | Gonçalves, Nuno Diogo | |
| dc.date.accessioned | 2025-02-18T15:01:17Z | |
| dc.date.available | 2025-02-18T15:01:17Z | |
| dc.date.issued | 2024-11-20 | |
| dc.description.abstract | A INPLAS, empresa pertencente à divisão de Plásticos do Grupo Simoldes e especializada na injeção de componentes termoplásticos, identificou a necessidade de aprimorar o Sistema Inteligente de Apoio à Decisão (SIAD) utilizado pelo seu Departamento de Planeamento de Produção para dar resposta ao problema de programação de máquinas paralelas dedicadas com múltiplas alternativas, setups e recursos adicionais e datas de entrega. Com esse objetivo, desenvolveu-se um novo SIAD que incorpora a consideração de máquinas alternativas e a aplicação de uma metaheurística Greedy Randomized Adaptive Search Procedure (GRASP), visando aumentar a flexibilidade e a eficiência do planeamento e responder melhor às necessidades de produção. O processo de planeamento foi inicialmente estudado em profundidade, abrangendo tanto as etapas a montante quanto as etapas a jusante, com o objetivo de identificar as variáveis-chave, os inputs e os outputs essenciais para a resolução deste problema. Neste contexto, foram analisadas minuciosamente as características e restrições do processo, especialmente aquelas associadas às limitações do sistema de produção. Com uma compreensão detalhada do problema em mãos, identificaram-se potenciais oportunidades de melhoria que poderiam aumentar tanto a adaptabilidade do sistema ao ambiente de produção da INPLAS quanto a eficácia dos resultados obtidos pelo SIAD. Assim, decidiu-se que a melhoria a implementar, com o intuito de potencializar o desempenho do SIAD, seria a inclusão de máquinas alternativas no sistema, enquanto a resolução do problema de escalonamento seria abordada com a aplicação de uma metaheurística GRASP. Considerando a complexidade do problema de escalonamento em máquinas paralelas dedicadas com múltiplas alternativas, setups e recursos adicionais, classificado como NP-Hard, este trabalho desenvolve uma metaheurística GRASP adaptada, fundamentada nas melhores práticas recomendadas na literatura. A abordagem proposta oferece cinco contribuições específicas. Em primeiro lugar, adapta os modelos de referência ao introduzir uma separação inovadora entre os processos de alocação e sequenciação, permitindo que estas etapas sejam tratadas de forma independente, o que é raro em abordagens tradicionais. Em segundo lugar, integra datas de entrega comuns, o que exige a introdução de uma variável de atraso para cada trabalho e de uma função multiobjetivo, com foco na minimização do número de trabalhos em atraso, assegurando o cumprimento dos prazos estabelecidos. Adicionalmente, a metaheurística GRASP foi adaptada para um sistema de produção contínua, em que os trabalhos inacabados do dia anterior são sequenciados na primeira posição do dia seguinte, refletindo de forma mais realista o ambiente produtivo. Por fim, ajustou-se uma heurística construtiva original, que utiliza um coeficiente exclusivo para classificar as posições de inserção dos trabalhos nas soluções parciais, visando não apenas a minimização dos atrasos, mas também a redução do número de setups e do makespan total. Os resultados obtidos demonstram a eficácia da metaheurística GRASP no apoio ao Sistema Inteligente de Apoio à Decisão (SIAD), com uma taxa média de cumprimento de prazos de 96,9% ao escalonar 396 dos 409 trabalhos planeados dentro do prazo. Nas cinco melhores instâncias, a taxa de cumprimento atinge 98%, evidenciando a robustez do GRASP em minimizar atrasos. A alocação inicial assegura a inclusão de 98,6% dos trabalhos solicitados, o que reflete uma elevada capacidade de resposta às necessidades dos clientes. Em termos computacionais, o tempo médio de processamento é de 22 minutos por instância, confirmando a viabilidade do SIAD para aplicações em ambientes de produção real. À data de conclusão do projeto, o SIAD está pronto para ser integrado na interface do sistema atual. Inicialmente, será implementado no sistema de produção da INPLAS, com a possibilidade de, após adaptações mínimas, ser expandido para outras fábricas do Grupo Simoldes. | por |
| dc.description.abstract | INPLAS, a company in the Plastics division of the Simoldes Group and specialized in the injection of thermoplastic components, identified the need to enhance the Decision Support Intelligent System (SIAD) used by its Production Planning Department to address the scheduling problem for dedicated parallel machines with multiple alternatives, setups, and additional resources. To this end, a new SIAD was developed, incorporating the consideration of alternative machines and the application of a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, aiming to increase the flexibility and efficiency of planning and better meet production needs. The planning process was initially studied in depth, covering both upstream and downstream stages, to identify key variables, the inputs, and the essential outputs for solving this problem. In this context, the characteristics and constraints of the process were thoroughly analysed, especially those associated with the limitations of the production system. With a detailed understanding of the problem, potential improvement opportunities were identified to increase both the adaptability of the system to the INPLAS production environment and the effectiveness of the results obtained by the SIAD. Thus, it was decided that the improvement to implement, aiming to enhance the SIAD's performance, would be the inclusion of alternative machines in the system, while the resolution of the scheduling problem would be tackled with a GRASP metaheuristic application. Given the complexity of the scheduling problem for dedicated parallel machines with multiple alternatives, setups, and additional resources, classified as NP-Hard, this work develops an adapted GRASP metaheuristic, grounded in best practices recommended in the literature. The proposed approach offers five specific contributions. First, it adapts the reference models by introducing an innovative separation between allocation and sequencing processes, allowing these steps to be handled independently, which is rare in traditional approaches. Secondly, it incorporates common due dates, requiring the introduction of a delay variable for each job and a multi-objective function focused on minimizing the number of delayed jobs, ensuring compliance with established deadlines. Additionally, the GRASP metaheuristic was adapted to a continuous production system, where unfinished jobs from the previous day are sequenced in the first position of the next day, realistically reflecting the production environment. Finally, an original constructive heuristic was adjusted, using a unique coefficient to rank insertion positions for jobs in partial solutions, aiming not only to minimize delays but also to reduce the number of setups and the total makespan. The results demonstrate the effectiveness of the GRASP metaheuristic in supporting the Decision Support System (SIAD), with an average deadline compliance rate of 96.2%, scheduling 393 out of 409 planned jobs on time. In the top five instances, the compliance rate reaches 97.2%, highlighting GRASP's robustness in minimizing delays. The initial allocation ensures the inclusion of 98.6% of requested jobs, reflecting a high response capacity to customers’ needs. In terms of computational time, the average processing time is 22 minutes per instance, confirming the SIAD's feasibility for real production environments. As of the project’s completion, the SIAD is ready for integration with the current system interface. Initially, it will be implemented in INPLAS’s production system, with the possibility of expansion to other Simoldes Group factories after minor adaptations. | eng |
| dc.identifier.tid | 203804554 | |
| dc.identifier.uri | http://hdl.handle.net/10400.22/29562 | |
| dc.language.iso | por | |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | GRASP | |
| dc.subject | Máquinas paralelas dedicadas | |
| dc.subject | Múltiplas alternativas | |
| dc.subject | Setups | |
| dc.subject | Recursos adicionais | |
| dc.subject | Máquinas alternativas | |
| dc.subject | Dedicated parallel machines | |
| dc.subject | Multiple alternatives | |
| dc.subject | Additional resources | |
| dc.subject | Alternative machines | |
| dc.title | Desenvolvimento de um algoritmo greedy randomized adaptive search procedure para a programação de máquinas paralelas dedicadas com setups e recursos adicionais e datas de entrega | por |
| dc.title.alternative | A greedy randomized adaptive search procedure algorithm for scheduling dedicated parallel machines with setups and resources | eng |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| thesis.degree.name | Mestrado em Engenharia e Gestãp da Cadeia de Abastecimento |