Solving single and parallel machine scheduling problems with sequence dependent setup times using differential evolution based algorithms

In this thesis, we present an application of the Differential Evolution (DE) algorithm for the single and parallel machine scheduling problems with sequence dependent setup times for the objective of minimizing makespan. To the best of our knowledge, this is the first attempt to use the DE heuristic for the parallel machine scheduling problem.To improve the solution quality of the DE algorithm in single machine scheduling problem, two simple local search methods which are insert-based neighborhood search and variable neighborhood search, are respectively embedded in the algorithm for a hybrid solution. Pure DE algorithm is compared with the hybrid DE algorithms by solving problems taken from TSPLIB. It is seen that hybridizing the DE algorithm improves the solution quality.The DE algorithm is an evolutionary optimization method. For solving the parallel machine problem, vector group encoding technique is adopted from genetic algorithm. Secondly, to make the DE algorithm suitable for solving scheduling problems, the largest order value and sub-range encoding rules are used to convert the continuous values of individuals in the DE algorithm to job and machine permutations. Local search procedure is applied to emphasize exploitation after the DE algorithm based exploration. The performance of the DE algorithm is enhanced by employing a population initialization scheme based on a constructive heuristic. Finally, a computational study is conducted to demonstrate that the proposed technique is capable of producing encouraging solutions.