A comparison of two chromosome representation schemes used in solving a family-based scheduling problem

Abstract

Meta-heuristic algorithms have been widely used in solving scheduling problems; previous studies focused on enhancing existing algorithmic mechanisms. This study advocates a new perspective developing new chromosome (solution) representation schemes may improve the performance of existing meta-heuristic algorithms. In the context of a scheduling problem, known as permutation manufacturing-cell flow shop (PMFS), we compare the effectiveness of two chromosome representation schemes (S-old and S-new) while they are embedded in a meta-heuristic algorithm to solve the PMFS scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. Denote a tested meta-heuristic algorithm by X_Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that GA_S-new outperforms GA_S-old, and ACO_S-new also outperforms ACO_S-old. These findings reveal the importance of developing new chromosome representations in the application of meta-heuristic algorithms. (C) 2012 Elsevier Ltd. All rights reserved.