Solving Job-Shop Scheduling Problem Using Genetic Algorithm Approach

Abstract

An effective job shop scheduling (JSS) in the manufacturing industry
is helpful to meet the production demand and reduce the production cost,
and to improve the ability to compete in the ever increasing volatile market
demanding multiple products.
In so many combinatorial optimization problems, job shop
scheduling problems have earned a reputation for being difficult to solve.
Job-shop scheduling is essentially an ordering problem. A new encoding
scheme for a classic job-shop scheduling problem is presented. The aim is
to find an allocation for each job and to define the sequence of jobs on
each machine so that the resulting schedule has a minimal completion time.
Genetic algorithm that has demonstrated considerable success in providing
efficient solutions to many non polynomial-hard optimization problems is
used to solve job-shop scheduling problem. The schedules given by genetic
algorithms are constructed using a priority rule and under several
constraints. After a schedule is obtained a checking operation is applied to
ensure that the solution is feasible. The approach is tested on a set of
instances. The results validate the effectiveness of the algorithm.