Solving job shop scheduling problem with genetic algorithms: A case study in manufacturing plant for aluminium products

Abstract

Over the years, the scheduling of several jobs for several machines with each specific machine route has been investigated. Job shop scheduling problem (JSP) has been one of the general and difficult problems of combinatorial optimization that allows the operation to be carried out on the number of available machines. Over the decades, many researchers have been interested in this problem and many works of literature have been published. However, the NP-hard structure of a mathematical modeling approach makes JSP very difficult to reach an optimal solution for real-life problems. This has led to a recent interest in solving this problem with a Genetic Algorithm. When used in scheduling, genetic algorithms suppose sequences or schedules as individuals or population members. The children are generated by reproducing and mutating individuals who were part of the previous generation (the parents). The most suitable individual will reproduce while the least fit dies in each generation. In the proposed initial GA population, effective representation of the chromosome is produced randomly and the appropriate crossover and mutation operations are also developed. The result shows that the genetic algorithm was successfully used to calculate efficiency of Job Shop problems. The algorithm performance is applied in a real case study. Keywords: Genetic Algorithms, optimization, flexible Job-shop Scheduling, NP – hard, Heuristic Rules