A genetic algorithm for job shop scheduling - A case study

The problem of scheduling n jobs on m machines with each job having a specific route has been one of considerable research over the last several decades. Branch and Bound algorithms for determining the optimal makespan have been developed and tested on small sized problems and dispatching rule based heuristic algorithms to minimize specific performance measures such as makespan, flowtime, tardiness, etc, are available to solve large sized problems. This paper addresses the same problem faced by an organization and reports the solution of this problem using genetic algorithms (GA) and a combination of dispatching rules. The proposed algorithm yields an improvement of about 30% in makespan over the present system.