A Genetic algorithm with shuffle to solve the job shop scheduling problem
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Job shop scheduling problems are computationally complex combinatorial optimization problems. Genetic algorithms have been used in various forms and in combination with other algorithms to solve job shop scheduling problems. A partially flexible job shop with precedence constraints increases this complex behaviour. There are two main parts to optimizing a job shop, the routing and the scheduling. The objective here is to get consistent optimal makespan using a genetic algorithm. This paper firstly, presents a representation of the considered partially flexible job shop scheduling problem, which helps take into account the precedence constraints and reduce situations of deadlock. It starts with the genetic crossovers for routing and then a random shuffle technique is used for scheduling the problem. The computational results have shown that the algorithm performs well in terms of finding a consistent optimal schedule for the given problem.
Place, publisher, year, edition, pages
2015. , 14 p.
Job shop scheduling, genetic algorithm, shuffle, string, makespan
IdentifiersURN: urn:nbn:se:hv:diva-9011Local ID: EXR900OAI: oai:DiVA.org:hv-9011DiVA: diva2:900850
Subject / course