1.서 론

셀 생산 방식(cellular manufacturing)은 다품종 소량생 산방식에서의 문제점을 보완하고 대량생산방식의 장점 을 살리기 위한 생산방식이다. 기업들은 셀 생산 방식을 적용함으로써 준비시간의 단축, 재공품재고 통제, 자재 취급비용 감소, 준비비용과 직/간접 노동비용의 감소, 품 질 개선, 자재흐름 유연화, 기계활용도 제고, 공간활용의 개선, 종업원의 사기 앙양 등 다양한 장점들을 누릴 수 있다[4]. 셀 생산방식 시스템의 개발과 시행을 위한 기본 단계로서 셀 형성 과정은 각각의 기계 셀에 할당된 부품 군을 처리하는 상호 독립적인 여러 개의 셀들을 구성하 는 것이다. 셀을 형성하기 위해서는 기계 그룹 및 부품 그룹의 형성 문제를 해결해야 한다[9].

기계-부품 그룹 형성(machine-part grouping)은 셀 생산 방식에서 발생하는 문제로 부품들의 물류비용을 최소화 하기 위해 한 기계 그룹에서 특정 부품들을 가공하도록 m대의 기계와 p개의 부품을 k개의 그룹으로 묶는 것이 다[3]. 특정부품을 가공하는데 하나의 공정만 사용하는 것 이 아니라 다수의 공정을 통해서도 부품을 만들 수 있는 데 이를 대체공정(alternative process)이 있는 기계-부품 그 룹 형성 문제라 한다.

공정별로 가공할 수 있는 부품과 그렇지 않은 부품을 나타내기 위하여 기계-부품 공정 행렬을 사용하고 행렬 의 요소는 a_ijr로 나타낸다. 기계 i가 부품 j를 가공할 때 공정 r을 사용하는 경우 행렬의 요소는 1의 값을 가지며 사용하지 않는 경우에는 0의 값을 가진다. <Figure 1>에 서 요소 값 0은 생략하였다. <Figure 1>은 <Figure 2>와 같이 대각선을 따라 표현할 수 있는데 이것을 블록대각 구조(diagonal blocks)라고 한다.

본 연구에서는 성능 평가 척도로서 Kumar et al.[9]이 정의한 그룹화 효율(GE : Grouping Efficacy)을 사용한다. GE는 블록대각행렬에서 다음과 같이 정의한다.(1)

그룹화 효율은 클러스터링의 질(quality)을 평가하기 위한 척도로서 널리 사용되며, 블록대각구조의 밀집도를 나타낸다. 이 값이 클수록 클러스터링이 잘된 것이다. 대 체공정이 있는 기계-부품 그룹 형성 문제는 NP-Complete 이므로[11] 그룹을 형성해야할 기계의 대수와 부품의 개 수가 많은 경우에는 많은 계산량이 소요된다.

기계-부품 그룹 형성 문제는 지금까지 많은 연구자들 이 매우 다양한 해법을 제시하였다. 최근에는 이전 연구 의 단점을 보완하기 위하여, 생산 현장의 복잡한 문제를 해결하는 데 있어서 효과적인 수단으로 알려진 인공지능 에 기초한 방법이 많이 연구되었다. 인공지능에 기초한 방법 중 신경망(neural networks)은 학습 능력을 통하여 실제 생산 현장의 문제에 대하여 유연하고 적응력 있는 해 를 제공해 왔다. 자기조직화 신경망(SOM : Self Organizing feature Map)은 입력데이터의 특징을 추출하여 지도를 형 성하는 패턴 분류에 효과적인 신경망이다. 본 연구에서는 SOM의 이러한 성질을 이용하여 대체공정이 있는 문제 에서 기계-부품 그룹을 형성하는 알고리듬을 제시한다.

2.기존 연구

대체공정이 있는 기계-부품 그룹 형성 문제를 해결하 기 위해서 다양한 해법이 제안되었다. Kusiak[12]은 최초 로 대체 공정하에서의 기계-부품 그룹 문제를 제안하였다. 그 이후 Nagi et al.[15], Sankaran et al.[16], Moon et al. [14], Won et al.[18]이 이 문제를 해결하기 위한 수리적 인 모델을 제시하였다.

유사계수를 이용하여 대체공정이 있는 기계-부품 그룹 형성 문제를 해결한 해법은 부품 간, 또는 기계 간 유사 도에 따라 유사계수를 구하고, 이 유사계수를 사용하여 그룹을 형성한다. Kusiak et al.[10]이 제안한 방법은 부품 간의 유사계수를 사용하는 방법이고 Won et al.[18]이 제 안한 방법은 기계간의 유사계수를 이용하는 방법이다.

메타휴리스틱을 사용한 방법은 최근에 연구가 이루어 지고 있다. Sofianopoulou[17]는 부품에 대한 공정을 선택 한 후 기계 셀을 구성하는 시뮬레이티드 어닐링(SA : Simulated Annealing) 알고리듬을 제안하였으며, Adenso-Diaz et al.[1]은 부품군과 기계 셀을 동시에 형성하도록 공정 을 선택하는 Tabu 탐색 알고리듬을 제안하였다. Jeon et al. [5, 6]은 부품을 가공하는데 하나의 공정으로 이루어진 기계-부품 그룹형성 문제에 SOM을 적용하였다.

Wu et al.[19]은 시뮬레이티드 어닐링 기법이 유전자 알 고리듬(GA : Genetic Algorithm)과 비교하여 국소해(local optima)를 쉽게 찾지만 더 좋은 해를 찾는 방법으로 GA의 돌연변이(mutation)가 있는 SA 기법을 적용하여 부품 공정 을 선택하는 기계-부품 그룹 형성 알고리듬을 제안하였다.

3.자기 조직화 신경망

SOM은 비지도 학습(unsupervised learning)을 사용하는 신경망 알고리듬의 일종으로 Kohonen[8]에 의하여 제시 된 경쟁학습(competitive learning) 모형이다. 경쟁학습은 입 력 패턴에 대해서 경쟁층의 노드 중에서 승자 노드를 결 정하여 승자 노드의 연결강도만을 입력 패턴에 대응하여 조절하는 학습방법이다. SOM은 일반 경쟁학습 모델과는 달리 학습과정에서 이웃(neighborhood)의 개념을 사용한 다. SOM에서는 승자 노드뿐만 아니라 승자 노드의 이웃 노드들의 연결강도도 함께 조절된다. 그 결과로 출력층에 입력 패턴의 유사성을 반영하는 지도를 스스로 형성한다. 즉, SOM은 입력 패턴들을 출력 노드들에 의한 위상학적 인 공간으로 매핑(mapping)할 수 있는 능력을 가진다.

SOM의 일반적인 구조는 <Figure 3>과 같다. SOM은 입력층(input layer)과 출력층(output layer)으로 두 개의 층 으로 구성되어 있다. 입력층은 유클리디안 공간상의 m차원 벡터를 입력벡터로 가질 수 있으며 일차원 또는 이차원의 격자(lattice) 출력층과 연결되어 있다. 입력벡터는 모든 출 력노드와 연결되어 있고 연결선은 연결강도(weight)를 가 진다. 승자노드의 결정은 입력벡터와 연결강도벡터의 거 리를 계산하여 거리가 가장 작은 노드를 선택한다. 여기서 말하는 거리는 유클리디안 공간상의 벡터 거리(euclidean distance)를 의미한다.

승자 노드를 결정하고 난 후에는 코호넨의 학습규칙 에 따라 노드의 연결강도를 조정해야 하는데 이 규칙은 식 (2)로 표현된다.

여기서

SOM에서 신경망을 학습시키는 과정은 다음과 같다.

학습률은 신경망 학습 결과의 성능저하가 그리 크지 않는 범위 내에서 적당한 값을 정한다. 이웃의 범위는 처 음에는 출력층의 모든 노드를 포함하도록 하였다가, 점 차 이웃의 범위를 줄여나가 마지막에는 승자노드만 포함 하도록 한다.

4.제안하는 알고리듬

본 연구에서는 출력층을 <Figure 4>와 같이 1차원 구조 로 하고, 공정 및 기계에 대하여 2단계로 SOM을 적용하 는 알고리듬을 제안한다. 학습률은 사전 실험을 통하여 정한다. 출력층이 1차원 구조일 경우 출력노드의 수를 충 분히 크게 만들면(예를 들어 입력벡터의 2배) 입력데이터 (공정)를 입력벡터(가공 기계)가 유사한 순서로 1차원 출 력노드에 펼쳐놓을 수 있다[5]. 이 상태에서 기계를 입력 벡터로 하여 같은 방법을 적용하면 공정과 기계가 모여 군집을 형성하게 된다. 형성된 군집중 GE가 가장 높게 형 성되는 것부터 기계-공정 그룹으로 묶어 나가며, 이 과정 을 모든 기계가 기계-공정 그룹에 포함될 때까지 진행한 다. 이렇게 하여 형성된 것이 초기 기계-공정 그룹이다. 이 단계에서 기계 그룹이 형성된다.

초기 기계-공정 그룹을 다음의 단계를 통하여 최종 기 계-공정 그룹으로 수정해 나간다.

첫 번째 단계로 초기 기계-공정 그룹 중 GE를 가장 높 게 해주는 기계-공정 그룹을 선택한다. 그런 다음 선택된 기계-공정 그룹 내에서 GE를 가장 높게 해주는 공정을 선택한다. 그리고 그 공정이 속하는 부품의 다른 공정과 비교하여 GE를 가장 높게 해주는 공정을 선택하고 나머 지 공정은 삭제한다. 선택된 기계-공정 그룹 내에서 그 다음으로 GE를 높게 해주는 공정을 선택하여 같은 과정 을 반복하면서 마지막 공정까지 수행한다. 다음 단계로 초기 기계-공정 그룹 중 그 다음으로 GE를 높게 해주는 기계-공정 그룹을 선택하여 같은 과정을 반복하면서 마 지막 기계-공정 그룹까지 동일한 절차를 수행한다.

두 번째 단계로 초기 기계-공정 그룹에 포함되지 않고 남은 공정을 처리한다. GE를 가장 높게 해주는 기계-공 정 그룹에 인접한 공정 중에서, GE를 가장 높게 해주는 공정을 선택한다. 그리고 그 공정이 속하는 부품의 다른 공정과 비교하여 GE를 가장 높게 해주는 공정을 선택하 여, GE를 가장 높게 해주는 기계-공정 그룹에 추가하고 나머지 공정은 삭제한다. 그 다음으로 GE를 높게 해주는 공정을 선택하여 같은 과정을 반복하면서 마지막 공정까 지 수행한다. 다음 단계로 초기 기계-공정 그룹 중 그 다 음으로 GE를 높게 해주는 기계-공정 그룹에 인접한 공 정 중에서, GE를 가장 높게 해주는 공정을 선택하여 같 은 과정을 반복하면서 마지막 기계-공정 그룹까지 동일 한 절차를 수행한다.

이렇게 하여 최종 기계-공정 그룹이 형성된다. 최종 기 계-공정 그룹에서 각 공정의 부품을 나타내면 최종으로 구하는 기계-부품 그룹이 된다.

본 연구에서 제안하는 알고리듬의 절차를 요약하면 다 음과 같다.

5.수치예제

<Figure 1>의 수치예제는 Won et al.[18]이 제시한 7대 의 기계와 10개의 부품이 있는 기계-부품 그룹 형성 문 제이며, 부품별 공정의 개수는 각각 2, 2, 2, 2, 4, 2, 2, 3, 2, 2개로 총 23개의 공정이 있다. <Figure 1>의 수치예제 에 대하여 본 연구가 제안하는 알고리듬을 적용하면 다 음과 같다.

6.실험 결과와 분석

본 연구에서 제안하는 알고리듬의 성능을 평가하기 위 해 기존 연구에서 가장 좋은 해를 제공하는 Wu et al.[19] 이 제안한 돌연변이가 있는 시뮬레이티드 어닐링(HSAM : Hybrid Simulated Annealing Algorithm with Mutation) 해 법과 비교하였다.

제안하는 알고리듬의 GE를 HSAM 알고리듬의 GE와 비교하면 <Table 1>과 같다. 제안하는 알고리듬의 GE는 문제 4~10, 12, 14에서 HSAM 알고리듬의 GE보다 우수 하다. 총 14문제 중에서 9문제에서 GE가 높았고, 나머지 5문제에서는 동일하였다. 따라서 제안하는 알고리듬은 HSAM 알고리듬보다 성능이 우수함을 알 수 있었다.

7.결 론

본 연구에서 제안하는 알고리듬은 SOM의 출력층의 구 조를 1차원 구조로 하고 출력노드의 수를충분히 크게 만 들어, 1차원 출력노드에 입력벡터가 유사한 순서로 펼쳐 질 수 있도록 설계하였다. 그리고 이러한 과정을 2단계로 적용하여 기계-공정 군집을 형성하였다. 형성된 군집을 GE를 고려하여 수정하면서 최종적으로 기계-부품 그룹을 형성하였다. 제안하는 알고리듬을 기존의 논문에서 많이 인용되는 대체공정이 있는 기계-부품 그룹 형성 문제들에 적용해 본 결과, 가장 좋은 해를 제공하는 것으로 알려진 HSAM 알고리듬과 비슷하거나 우수한 성능을 나타내었다.

본 연구에서 제안하는 알고리듬의 특징은 단순 한 과 정을 반복하여 해를 구하는 것으로 기존의 수리계획법에 의한 방법보다 복잡한 연산을 사용하지 않는다. 따라서 문제 크기의 증가에 따라 계산량이 크게 증가하지 않기 때문에 규모가 큰 문제에 대해서도 쉽게 적용할 수 있을 것이다. 또한 유전자 알고리즘, Tabu 탐색, 시뮬레이티드 어닐링 등의 메타 휴리스틱 방법에 비해 목적함수나 평 가함수의 설정 없이 실제 문제에 적용할 수 있기 때문에 쉽게 응용할 수 있는 장점이 있다.