Scheduling of multi-level parts in a flexible manufacturing system

Abstract

In this research, we consider a scheduling problem for components and sub-assemblies of final products. The final products have a multi-level product structure and are composed of sub-assemblies and components. Considered is a scheduling problem for the production of components and/or sub-assemblies lest the set-back should not occur in making final products. The scheduling problem is divided into two sequential sub-problems: period allocation and loading. The former is formulated as a single machine scheduling problem to minimize the weighted sum of discrete earliness and tardiness, and the latter is viewed as a bin-packing problem. To solve the problems in a reasonable amount of time, we suggest two heuristics, called GAPA and GAL based on the methodology of genetic algorithm, which is a search technique for global optimization in a complex search space. It employs the concepts of natural selection and genetics. To investigate the performance of two algorithms, a series of computational experiments is carried out. In the period allocation problems, differences between best solutions of the GAPA and optimal solutions are less than 7\%. In the loading problem, the GAL performs better than existing LPT-type and MULTIFIT-type algorithms.