Loading...
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
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 8.58 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
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.
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.
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.
Description
Keywords
GRASP Máquinas paralelas dedicadas Múltiplas alternativas Setups Recursos adicionais Máquinas alternativas Dedicated parallel machines Multiple alternatives Additional resources Alternative machines