A SearchCol Algorithm for the unrelated parallel machine scheduling problem with job splitting

Abstract

In this dissertation, the unrelated parallel machine scheduling problem with job splitting and sequence independent setup times is addressed, implementing a method to solve it in a recently proposed framework, SearchCol, short for ‘Metaheuristic search by Column Generation’. The study of scheduling problems is of high relevance due to its real-world application in multiple fields, as documented in its vast literature, and also due to its high complexity derived from the diverse environments, variables, restrictions and the combinations of these in different systems. The problem consists in finding a scheduling plan for a set of independent jobs on a set of unrelated parallel machines, considering jobs and machines release dates, sequence independent setup times and the job splitting property, with due date related objectives. The introduction of setup times and job splitting properties in unrelated environments has not been extensively studied, even though its use can play an important role in scheduling. A mixed integer programming model is developed featuring the aforementioned properties, which is then decomposed by machine using the Dantzig-Wolfe decomposition. To solve the decomposed model a hybrid approach entitled SearchCol is applied, which results from the interaction between column generation and metaheuristics. Problem specific heuristics to use in the column generation component of the SearchCol are also developed and diverse alternatives within the global algorithm are tested. A problem specific algorithm for one of the main SearchCol components is also suggested. To evaluate the effectiveness of the model and the proposed algorithms, computational tests are performed and their solutions analysed for a set of test instances.

O trabalho que se apresenta nesta dissertação, aborda o problema de escalonamento em máquinas paralelas não relacionadas com dimensionamento de lotes e tempos de preparação independentes da sequência, recorrendo a uma ferramenta recentemente proposta, designada por SearchCol, abreviatura de ‘Metaheuristic Search by Column Generation’. O estudo de problemas de escalonamento revela-se de grande importância devido à sua aplicação em diferentes áreas, documentado na sua vasta literatura, e também devido à sua elevada complexidade decorrente das diversas configurações e tipos de máquinas, variáveis e restrições, bem como as combinações destas nos diversos sistemas. O problema consiste na determinação de um plano de produção para um conjunto de tarefas independentes em máquinas paralelas não relacionadas, considerando tempos de disponibilidade de tarefas e máquinas, tempos de preparação independentes da sequência e o dimensionamento de lotes. O estudo deste problema com incorporação de tempos de preparação e da propriedade de dimensionamento de lotes em máquinas paralelas não relacionadas não é comum na literatura, apesar de se revelar de extrema importância em problemas de escalonamento. Um modelo de programação inteira mista é desenvolvido para o problema e é também efectuada uma decomposição por máquina através da decomposição de Dantzig-Wolfe. Para resolver o problema, estuda-se uma abordagem híbrida que consiste na interação entre a técnica de geração de colunas e metaheurísticas, de seu nome SearchCol. São desenvolvidas heurísticas específicas para o problema, as quais são usadas na componente de geração de colunas do SearchCol, sendo testadas também diversas alternativas e ferramentas no contexto do algoritmo global. Além disso, um algoritmo específico para o problema é também sugerido, para incluir num dos principais componentes do SearchCol. Para avaliar o desempenho e qualidade dos modelos e algoritmos propostos, são realizados testes computacionais e analisadas as suas soluções para um conjunto de instâncias de teste.