Hybrid Evolutionary Approach for Multi-Objective Job-Shop Scheduling Problem

Abstract

Over the years, various evolutionary approaches have been proposed in efforts to solve the Job-Shop Scheduling Problem (JSSP), a particularly hard combinatorial optimization problem. Unfortunately, most of these approaches are limited to a single objective only, and often fail to meet the requirements for real-world applications. Previously, we proposed several evolutionary approaches for multi-objective JSSP using the Jumping Genes Genetic Algorithm (JGGA) [1], [2]. Simulation results indicated that these approaches are capable of maintaining consistency and convergence of the trade-off, non-dominated solutions. In some rare cases, however, the solutions may be too diverse due to the additional diversity that occurs naturally from the jumping operations introduced in JGGA. This paper extends the idea by describing a hybrid approach that alleviates the difficulty outlined above. Experimental results reveal that our proposed hybrid approach can search for the nearly-optimal and non-dominated solutions with better convergence by optimizing multiple criteria simultaneously. Concurrently, it is capable of producing a set of controlled, diverse solutions that provide a wide range of alternative scheduling choices.