Scheduling problem with unrelated parallel machines: mathematical formulation, decomposition methods and hybridization

Esta tese aborda dois problemas de sequenciamento de máquinas paralelas não-relacionadas com os tempos de preparação dependentes da máquina e da sequência. Ambos os problemas são NP-hard. As diferenças entre esses problemas são a função objetivo adotada e os métodos de solução utilizados. No primeiro problema, o makespan é função objetiva e a decomposição Benders combinatória é o método. Este método pode ser lento para convergir. Portanto, três procedimentos são introduzidos para acelerar sua convergência. O primeiro procedimento consiste em encerrar a execução do problema mestre quando uma solução ótima repetida é encontrada. O segundo procedimento é baseado na técnica multicut. Por fim, o terceiro procedimento é baseado no procedimento warm-start. O esquema de decomposição Benders combinatório melhorado é comparado com uma formulação matemática e uma implementação convencional da decomposição de Benders. Nos experimentos são utilizados dois conjuntos de testes da literatura. Para o primeiro conjunto, o método proposto executa 21,85% em média mais rápido do que a implementação convencional. Para o segundo conjunto, o método proposto não conseguiu encontrar uma solução ótima em apenas 31 em 600 instâncias, obteve uma diferença entre os limites inferiores e superiores de 0,07% e teve um tempo computacional médio de 377,86 s, enquanto os melhores resultados dos outros métodos foram 57, 0,17 % e 573,89 s, respectivamente. No segundo problema o atraso total é a função objetivo. Os modelos matemáticos para este problema em geral usam uma constante conhecida como big-M devido às restrições disjuntivas. Isso produz limites inferiores muito fracos que dificultam a obtenção da solução ótima, mesmo para instâncias de pequeno porte. Para resolver este problema é proposta uma formulação matemática que não use a constante big-M. Para este fim, apresenta-se uma abordagem que usa tarefas fictícias em vez da constante big-M. Além disso, é proposta uma condição de otimização que reduz o espaço de busca da solução do problema. Os experimentos realizados em cinco tipos de instâncias produziram prova computacional da superioridade do modelo proposto em comparação com modelos baseados nas formulações de Wagner (1959) e Manne (1960). O modelo proposto produziu 291 soluções ótimas em comparação com 98 e 148 dos modelos de Wagner (1959) e Manne (1960), respectivamente, e foi até três ordens de magnitude mais rápido nas 300 instâncias de pequeno porte que foram testadas. Um algoritmo de geração de coluna também é proposto para encontrar soluções quase ótimas para instâncias de tamanho médio com até 50 tarefas e dez máquinas. Ao contrário das abordagens padrão, o modelo proposto é usado em vez de um algoritmo de programação dinâmica para resolver o problema de pricing. Para acelerar a convergência do algoritmo de geração de colunas, várias heurísticas são propostas para gerar as colunas iniciais e resolver o problema de pricing. A geração de colunas híbrida obteve uma diferença média entre os limites inferiores e superiores e tempo de execução de 2,71% e 930,48 s, respectivamente, em comparação com 34,78% e 2.490,37 s, respectivamente, em relação ao modelo proposto. Os resultados indicam que as abordagens propostas são mais eficazes em tempo de execução e qualidade da solução.This thesis addresses two unrelated parallel machines scheduling problem with sequence and machine dependent setup times. Both problems are NP-hard. The differences between these problems are the objective function adopted and the solution methods used. In the first problem the makespan is objective function and combinatorial Benders decomposition is solution method. This method can be slow to converge. Therefore, three procedures are introduced to accelerate its convergence. The first procedure consists of terminating the execution of the master problem when a repeated optimal solution is found. The second procedure is based on the multicut technique. The third procedure is based on the warm-start technique. The improved combinatorial Benders decomposition scheme is compared to a mathematical formulation and a standard implementation of Benders decomposition algorithm. In the experiments, two test sets from the literature are used. For the first set the proposed method performs 21.85% on average faster than the standard implementation of the Benders algorithm. For the second set the proposed method failed to find an optimal solution in only 31 in 600 instances, obtained an average gap of 0.07%, and took an average computational time of 377.86s, while the best results of the other methods were 57, 0.17%, and 573.89s, respectively. In the second problem the total tardiness is objective function. Mathematical models for this problem often use a constant known as big-M because the disjunctive constraints. This yields very weak lower bounds that make it difficult to obtain the optimal solution, even for small-size instances. To address this problem is proposed a mathematical formulation that does not use the big-M constant. To this end is presented an approach that uses dummy jobs instead of the big-M constant. Additionally, an optimality condition method that reduces the solution space of the problem is proposed. Experiments conducted on five instance types produced computational proof of the superiority of the proposed model compared to models based on Wagners (1959) and Mannes (1960) formulations. The proposed model produced 291 optimal solutions compared to 98 and 148 of Wagners (1959) and Mannes (1960) models, respectively, and it was up to three orders of magnitude faster in the 300 small-size instances that were tested. A column-generation algorithm is also proposed to find near-optimal solutions for medium-size instances with up to 50 jobs and 10 machines. Unlike standard approaches, the proposed model is used instead of a dynamic programming algorithm to solve the pricing problem. For accelerating the convergence of the column-generation algorithm, various heuristics are proposed to generate the initial columns and solve the pricing problem. The hybrid column generation obtained an average gap and runtime of 2.71% and 930.48 s, respectively, compared to 34.78% and 2,490.37 s, respectively, of the proposed model. Results indicate that the proposed approaches are more effective in terms of both running time and solution quality