Development of hybrid multilevel genetic algorithm for medium and large jop shop scheduling problems

Abstract

The scheduling problem has been extensively studied due to its practical importance and computational complexity. Generally, the metaheuristic methods have been widely used for solving this kind of problem. However, despite there are sophisticated methods that can find good solutions for deterministic and relatively small problems, they maybe are not suitable to be applied in real medium and large problems, which are subject to randomness. Against this backdrop, this project proposes the development of Hybrid Multilevel version of the Genetic Algorithm method based on the creation of subspaces of the search space. The objective is to study techniques to project the problem in a suitable approximation subspace in order to reduce the size of the problem to be solved and the corresponding computational cost. Statistical and artificial intelligence techniques and discrete wavelet transform will be investigated. Specifically, the following two types of problems are addressed: 1) scheduling in a classic job shop, with n jobs and m machines, in which each job is processed on the machines according to a pre defined routes and deterministic processing times; 2) scheduling in a dynamic stochastic job shop environment, in which the production times and the time between arrivals of the jobs in the system are described by probability distributions. In both cases, the goal is to determine the production sequence in order to minimize the time to completion of all jobs in the production system (makespan). (AU)