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.
본 연구에서는 최종 제품(final product)을 구성하는 구성품 (component)과 하위조립품(sub-assembly)의 일정계획문제 (scheduling problem)를 다루고 있다. 최종 제품은 여러 단계의 계층적 구조를 이루는 하위조립품과 구성품들로 이루어져 있다. 최종 제품을 생산하는 데 차질이 없도록 구성품과 하위조립품의 생산일정계획을 세우는 것이 문제의 목적이다. 본 일정계획문제는 순차적인 두 개의 하위문제(sub-problem)로 나누어 해결하였다. 첫번째 문제는 구성품과 하위조립품의 생산 기간을 결정하는 것으로 이산 납기선행과 납기지연의 가중합(weighted sum of discrete earliness and tardiness)을 최소화하는 단일기계 일정 계획문제로 구성하였다. 두번째 문제는 같은 기간 안에서 생산하도록 결정된 구성품 들을 시스템 내의 기계에 할당하는 것으로 빈 할당(bin-packing) 문제로 간주하였다.
위에서 제시된 문제들을 적절한 시간 안에 해결하기 위하여 제네틱 알고리즘(Genetic Algorithm)의 방법론을 이용한 두 개의 발견적 기법(heuristics)을 제시하였다. 제네틱 알고리듬은 자연 선택과 유전의 개념을 이용한 탐색 기법(search technique)의 하나이다. 컴퓨터를 이용한 실험 결과, 제시된 발견적 기법이 주어진 문제에 좋은 해를 주는 것으로 나타났다.
