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

Abstract

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.