Job Shop Scheduling Problem Using Evolutionary Algroithm
Abstract
Genetic algorithms (GAs) are search algorithms that are used to solve optimization problems in
theoretical computer science. Job shop scheduling problem (JSSP) is a combinatorial optimization
problem finding minimum make span for processing of jobs on a set of machines in form of a
schedule. In this report, I have suggested a genetic algorithm (GA) to solve the JSSP which uses a
particular genetic programming method for scheduling of jobs and machine distribution. Followed
by genetic representation, an initial population is randomly generated. The relevant crossover and
mutation operation is also designed and applied on the population for the creation of new off
springs until some stopping criterion is reached. Temporary list is to save good solutions during
the iterative process, and when the objective value of the optimal solutions is gained, the
scheduling Gantt charts need to be considered. To evaluate the performance of our proposed
algorithm, set of standard benchmark instances from the OR library in different sizes are
optimized. Consequently, the computational results and comparisons have validated the
effectiveness of the proposed algorithm.