A genetic algorithm for FMS part type selection and machine loading

Part type selection (PTS) and machine loading are two major problems in the production planning of flexible manufacturing systems. In this paper, we solve these problems by the use of genetic algorithms (GAs). We exploit the problem's MIP (mixed integer programming) model to make our GA more meaningful and less computation-intensive. The GA strategy is developed in three parts: solution coding, solution generation and solution recombination. In solution coding, we replace the original binary routing variables with integer variables and thus reduce the chromosome length significantly. Tn solution generation, the level of Feasibility is the main concern. We divide the constraints into two categories: direct and indirect. The direct constraints involve only two variables each and are easily satisfied by context-dependent genes. Since the direct constraints form the major chunk of constraints, their satisfaction controls infeasibility to a large extent. The remaining indirect constraints are handled by the penalty function approach. The solution recombination involves crossover and mutation. The crossover is performed in two steps, the PTS swap, followed by the routing swap, so that the feasibility level is not disturbed. With a similar intent, the mutation is allowed to operate only on selective genes. All the steps are illustrated with examples. Our GA is able to achieve optimum or near-optimum performance on a variety of objectives. A parametric study of GA factors is also carried out, indicating population size and mutation probability as influential parameters.