다품종 분해라인균형 문제에 관한 발견적 기법

Abstract

다 품종 분해라인균형 문제는 제품 회수 시스템의 분해공정내에서 다 뤄지는 가장 기본적이면서도 중요한 문제들 중의 하나로써, 분해 공정 내 에선 수명이 다한 제품이나 더 이상 사용 할 수 없는 제품들의 분해활동이 이뤄진다. 일련의 이러한 활동들에는 다양한 의사결정 문제가 존재하며 이 들 중 본 연구에서는 공장내의 공간확보를 통한 원활한 작업활동을 위하여 공장 내에서 사용되는 작업장의 수를 최소한으로 줄이기 위한 문제에 주안 점을 두었다. 다 품종 분해라인균형 문제는 순서가 결정되지 않은 일련의 작업들에 대해선 일정한 규칙을 적용하여 순서를 결정하고, 순서가 결정된 작업들에 대해선 작업장내에 주어진 용량의 제약과 작업들 사이의 선행관 계를 고려하여, 작업장의 갯수가 최소화되는 것을 목적으로 한다. 본 연구 에서는 고려하고 있는 문제를 정수계획법을 이용 수리적 모델로 제시하였 으며, 문제의 복잡도가 높음으로 인해 여러 가지 발견적 기법들을 제안하 였다. 이들 알고리듬들에 대한 계산 실험을 위하여 다양한 크기의 문제들 을 500개의 작업들로 임의 생성하였으며 그 결과를 제시하였다. 특히, 본 연구에서 제안하고 있는 발견적 기법들은 작은 크기의 문제에서 최적해와 비교하여 대부분 1% 내 근사 최적해를 주었다. 추후, 본 연구에서 고려하 지 못했던 분해라인만의 독특한 조건들과 특징들을 고려할 수 있다면 현장 에서 실제로 사용되는 분해라인에 근접하는 문제를 다룰 수 있을 것이라 생각한다.; During the last decades, growing concerns on environmental issues have en-forced the industry to develop environmentally conscious products and their processes. Among others the disassembly process, one of the elements in product recovery system, was the most based on in the product process system. This dissertation considers the line balancing problem for designing disassembly systems called the disassembly line balancing problem (DLBP) in the literature. For a given disassembly process plan that specifies all parts and components together with necessary disassembly tasks, the DLBP is to assign individual disassembly tasks to workstations while satisfying the precedence relations among tasks. As an extension of the existing research, this dissertation considers a mixed-model version of the DLBP since multiple used or end-of-life products are usually disassembled in ordinary disassembly systems. The objective is to minimize the number of workstations. A 0-1 integer programming model is presented to describe the problem mathematically. Since the problem considered in this dissertation is NP-hard, this dissertation suggests several simple heuristic algorithms in which disassembly tasks are ordered using a certain priority rule and then they are assigned to workstations according to this order while considering a given cycle time and precedence relations among tasks. Com-putational experiments were done on a number of test problems up to 500 tasks, and the results are reported. In particular, some of the heuristics gave the near optimal solutions for most small-size test problems.