A new metaheuristic proposal for unrelated parallel machine scheduling problem with sequence-dependent setup times

Scheduling, determines which job will be performed by which machine at the production stage, is extremely important for an effective production in businesses. As a business grow, scheduling will be more complex in the planning and production stages. In a business, optimal scheduling in small machine job environment can be done by an expert opinion or integer programming techniques. As the number of jobs and machines increase, it becomes impossible to find an exact solution. When the exact solution cannot be found, approximate solutions are obtained with metaheuristic algorithms. The problem studied in this study is the one that can be solved by metaheuristic algorithms that cannot be found exact solutions. This is an unrelated parallel machine scheduling problem with setup times. The study aims to minimize makespan. In this problem, machines are unrelated. Each job has different process time on different machines and different setup times on different machines. In this study, a benchmark dataset has been studied. Many researchers have tried to find the approximate best solution with different metaheuristic algorithms. In this thesis, a new Adapted Variable Neighborhood Search Algorithm is proposed to solve the benchmark dataset. The new proposed algorithm adds 2 different parameters to the neighborhood structures. The effect of added parameters on the result was discussed and it was seen that the findings were beneficial in using these new parameters. The local search module in the proposed variable neighborhood search algorithm has 4 different local search algorithms. A new local search selection phase was added according to the neighborhood makespan values. The local search selection phase saves the algorithm from unnecessary local searches. The benchmark dataset was tested more than 50 times and best results were stored. When the results obtained with the proposed algorithm were compared with the best known results, it was seen that the proposed algorithm is successful in some machine job configurations. Better results than the best known results were obtained in 141 of 540 sample in the data set. In 140 samples, the best known solutions were reached. The proposed algorithm works with an average error of 0.095% in all samples.