Multiple parts process planning in serial–parallel flexible flow lines: part II—solution method based on genetic algorithms with fixed- and variable-length chromosomes

Abstract

Multiple parts process planning (MPPP) is a hard optimization problem that requires the rigor and intensity of metaheuristic-based algorithms such as simulated annealing and genetic algorithms. In this paper, a solution method for this problem is developed based on genetic algorithms. Genetic algorithms solve problems by exploring a given search space. To do this, a landscape over which the search traverses is constructed based on a number of algorithm choices. Key algorithm choices include (a) type of chromosome representation, which affects the efficiency of an algorithm, and (b) type and form of genetic operators, which affect the effectiveness of an algorithm. More specifically, the suitability of a variable-length chromosome (VLC) representation for encoding a solution to a MPPP problem is investigated. The effectiveness and efficiency of implementing the VLC algorithm is analyzed and compared with: (a) the commonly used fixed-length chromosome representation, (b) a variant of the simulated annealing algorithm, and (c) a knowledge-informed simulated annealing algorithm. The scalability of the algorithms is analyzed and their effectiveness demonstrated by experimental results based on four problem sizes. Obtained results show that, although there are variances in performances, all algorithms investigated are capable of obtaining good solutions. In addition, variances were observed for different aspects of the MPPP problem. The results indicate that the VLC algorithm is effective in solving MPPP problems that consider multiple aspects in the search for optimal process planning solutions.