Unified Genetic Algorithm Approach for Solving Flexible Job-Shop Scheduling Problem

Abstract

This paper proposes a novel genetic algorithm (GA) approach that utilizes a multichromosome to solve the flexible job-shop scheduling problem (FJSP), which involves two kinds of decisions: machine selection and operation sequencing. Typically, the former is represented by a string of categorical values, whereas the latter forms a sequence of operations. Consequently, the chromosome of conventional GAs for solving FJSP consists of a categorical part and a sequential part. Since these two parts are different from each other, different kinds of genetic operators are required to solve the FJSP using conventional GAs. In contrast, this paper proposes a unified GA approach that enables the application of an identical crossover strategy in both the categorical and sequential parts. In order to implement the unified approach, the sequential part is evolved by applying a candidate order-based GA (COGA), which can use traditional crossover strategies such as one-point or two-point crossovers. Such crossover strategies can also be used to evolve the categorical part. Thus, we can handle the categorical and sequential parts in an identical manner if identical crossover points are used for both. In this study, the unified approach was used to extend the existing COGA to a unified COGA (u-COGA), which can be used to solve FJSPs. Numerical experiments reveal that the u-COGA is useful for solving FJSPs with complex structures.

Keywords

• flexible job-shop scheduling problem
• combinatorial optimization
• genetic algorithm
• candidate order-based genetic algorithm
• multichromosome