Uma abordagem matheurística para o problema de sequenciamento de tarefas e balanceamento de linhas de montagem de modelo único com Tempos de Setup dependentes da sequência

Abstract

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas.

The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.