Open AccessCrossover and Mutation Strategies applied in Job Shop Scheduling Problems
Author(s) -
J. Vilma Roseline,
D. Saravanan
Publication year - 2019
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1377/1/012031
Subject(s) - crossover , flow shop scheduling , computer science , mathematical optimization , job shop scheduling , subsequence , scheduling (production processes) , swap (finance) , mathematics , algorithm , artificial intelligence , mathematical analysis , schedule , finance , economics , bounded function , operating system
This paper reviews modern genetic algorithm based approaches for solving job shop scheduling problems. This paper elaborates the types of crossover methods such as Partially Mapped crossover (PMX), Order One Crossover (OX), etc involved in Genetic Algorithm (GA) that are used for Job Shop Scheduling problems. Job Shop Scheduling represents one of the hardest combinatorial optimization problems where number of possible schedules drastically increases with the number of operations and machines. Normal crossover operators will often lead to inadmissible solution . Many specialized combining order or adjacency information from the two parents. The crossover method operators builds an offspring by choosing a subsequence of elements from one parent and preserving the order and position of as many elements as possible from the other parent. A subsequence of elements is selected by choosing two random cut points, which serve as boundaries for the swapping operations. There are few distinct mutation operators widely used for JSS problems such as swap, inversion, insertion (shift) and displacement mutation. Here some modern genetic algorithm-based approaches from the literature are also discussed as well.