A multiobjective genetic algorithm for job shop scheduling

Abstract

In this paper, a Multi Objective Genetic Algorithm (MOGA) is proposed to derive the optimal machine-wise priority dispatching rules ( pdrs ) to resolve the conflict among the contending jobs in the Giffler and Thompson (GT) procedure applied for job shop problems. The performance criterion considered is the weighed sum of the multiple objectives minimization of makespan, minimization of total idle time of machines and minimization of total tardiness. The weights assigned for combining the objectives into a scalar fitness function are not constant. They are specified randomly for each evaluation. This in turn leads to the multidirectional search in the proposed MOGA, which in turn mitigates the solution being entrapped in local minima. The applicability and usefulness of the proposed methodology for the scheduling of job shops is illustrated with 28 benchmark problems available in the open literature. Keywords: Multiobjective Genetic Algorithm