1. 서 론

다품종 소량생산방식은 제품표준화에 의한 대량생산방 식에 비하여 비효율적이며 비경제적이다. 이와 같은 다품종 소량생산방식의 어려운 문제점을 해결하고 대량생산방식의 장점을 살리기 위하여 그룹 테크놀로지(Group Technology : GT)개념이 도입되었다. 셀 생산방식(cellular manufactur-ing)은 그룹 테크놀로지의 개념을 제조시스템에 적용한 것 이다. 기업들은 셀 생산 방식을 적용함으로써 준비시간의 단축, 재공품재고 통제, 자재취급비용 감소, 준비비용과 직/간접 노동비용의 감소, 품질 개선, 자재흐름 유연화, 기계활용도 제고, 공간활용의 개선, 종업원의 사기 앙양 등 다양한 장점들을 누릴 수 있다[3]. 셀 생산방식 시스템 의 개발과 시행을 위한 기본 단계로서 셀 형성 과정은 각 각의 기계 셀에 할당된 부품군을 처리하는 상호 독립적인 여러 개의 셀들을 구성하는 것이다. 셀을 형성하기 위해 서는 셀 형성 문제(cell formation problem, CFP)를 해결해 야 한다[9].

셀 형성 문제는 m대의 기계와 n개의 부품으로 구성된 생산체계에서, a_ij = 0, 1로 특정 부품이 특정 기계를 사용 하는지 여부를 명시하는 경우(이를 일반적으로 CFP라 한다), a_ij = 1, 2, ⋯, m으로 기계사용 순서를 명시한 경우, a_ij = t로 특정 기계로 작업을 수행하는 시간을 명시하는 경우 셀 능력을 만족시키도록 형성하는 CaCFP(Capacitated CFP) 로 분류된다. 기계사용 순서를 명시한 a_ij = 1, 2, ⋯, m문 제는 다시 부품 이동 비용(cost)을 최소화시키도록 셀(군)을 형성하는 CoCFP(Cost CFP)와 기계 배치순서 LCFP(layout CFP)를 결정하는 문제로 분류된다. LCFP와 CoCFP의 a_ij는 작업순서(sequence)로 값이 주어진다. 이 문제에 대해 셀 내부의 기계 배치순서는 고려하지 않고, 단지 셀 내부 의 불연속적인 기계간과 다른 셀들로의 부품 이동비용만을 최소화시키도록 셀을 형성하는 문제를 CoCFP라 하며, 단순 히 셀 내부의 기계 배치순서만을 고려하는 경우를 LCFP 라 한다[10]. 본 연구에서는 LCFP에 초점을 맞춘다.

셀 형성 문제를 풀기위해 많은 연구가 진행되었다. 대 표적인 방법으로는 군집분석(cluster analysis), 그래프분 할법(graph partitioning approaches)과 메타휴리스틱 방법 (metaheuristic approaches)이 있다[2]. 셀 형성 문제는 NP- 난제(NP-Hard)인 조합 최적화 문제로, 휴리스틱의 다항 시간 알고리듬이 존재하지 않고 있어 부득이 메타휴리스 틱 방법을 적용하고 있다[1, 16, 13]. 대표적인 메타 휴리 스틱 방법으로는 유전자 알고리듬(genetic algorithm, GA), 진화 알고리듬(evolutionary algorithm, EA), 군집최적화(particle swarm optimization, PSO), GRASP(greedy randomized adaptive search procedure) 등을 적용하고 있음에도 불구 하고 아직까지 다양한 모든 문제들에 대해 최적 해를 구하 는 알고리듬이 존재하지 않고 있다. CoCFP는 Teymourian et al.[18]이 있으며, LCFP에 대해서는 Nair와 Narendran [15]의 군집분석 기법의 CASE, Mutingi와 Onwubolu[14]의 군 유전자 알고리듬(group genetic algorithm, GGA), Mahadivi 와 Mahadevan[11]의 CLASS, Maddavi et al.[12]의 흐름 행렬 기반 휴리스틱 알고리듬, Lee[10]의 흐름행렬 기반 역-구성 알고리듬(RCA) 등이 있다.

Mahadavi와 Mahadevan[11]의 CLASS 알고리듬과 Mahadavi et al.[12]의 휴리스틱 알고리듬은 모두 기계 i에서 j로의 연속적인 순방향 제품 이동 횟수를 계산한 흐름 행렬(flow matrix)에 기반을 두고 있으며, 각각 9단계와 15단계의 과 정을 수행한다. 이들 방법은 셀을 형성하는데 있어 체계적 인 방법 대신 휴리스틱 방법을 적용하여 기계 대수가 많아 질수록 셀을 형성하는데 어려움이 있다. Lee[10]의 흐름행 렬 기반 역-구성 알고리듬(RCA)은 체계적인 방법으로 셀 을 형성한다.

최근 생산 현장의 광범위한 문제에 인공지능 기법을 적용하고 있다. 인공지능 기법은 생산 현장의 복잡한 문 제를 해결하는 데 있어서 효과적인 수단으로 알려져 있다. 인공지능에 기초한 방법 중 신경망(neural networks)은 학 습 능력을 통하여 실제 생산 현장의 문제에 대하여 유연 하고 적응력 있는 해를 제공해 왔다. 셀 형성 문제에도 신경망의 이러한 성질을 이용하여 훌륭한 효과를 보았다 [6, 7]. 자기조직화 신경망(Self Organizing Map : SOM) 은 입력데이터의 특징을 추출하여 지도를 형성하는 패턴 분류에 효과적인 신경망이다. 본 연구에서는 SOM의 이 러한 성질을 이용하여 LCFP에 대해 셀 형성과 셀 내부 의 기계 배치순서를 결정하는 알고리듬을 제안한다.

2. LCFP의 효율성 평가 척도

특정 부품이 특정 기계로 작업하는 순서가 결정된 셀 형성 문제는 n × m ( i = 1 , 2 , ⋯ , n , j = 1 , 2 , ⋯ , m ) 의 부 품 P_i와 기계 M_j 행렬에 대해 s_ij는 부품 i가 기계 j로 작 업을 수행하는 순서로 주어진다. LCFP는 셀을 형성함과 더불어 셀 내부의 기계 배치순서도 결정하는 문제이다. 이 문제에 대해 다음과 같이 정의한다.

LCFP의 기계 배치 효율성은 Mahadavi와 Mahadevan[11] 이 제안한 식 (1)의 ACMI(average cell movement index)와 식 (2)의 OMI(overall movement index)로 평가한다.

ACMI와 OMI는 모두 연속적인 순방향 작업 순서 효율 성에만 초점을 맞추고 있다. 만약, Nm_k를 극대화하도록 1 개의 셀로 구성한다면 ACMI와 OMI를 증가시킬 수 있다. 그러나 척도만을 강조하면 셀 내부의 기계 활용도 측면은 저하된다. 이러한 단점을 보완하고자, Mahadavi et al.[12] 은 셀 내부의 기계 활용도에 대한 셀 형성 효율성 평가 척도로 식 (3)의 ACUI(average cell utilization index)를 제 안하였다.

3. 자기 조직화 신경망

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

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

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

여기서

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

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

4. 제안하는 알고리듬

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

각 기계 그룹에서 다음의 과정을 통하여 기계 배치순 서를 결정한다.

먼저 기계별 연속적인 순방향 이동 빈도수를 계산한 전체 기계의 흐름행렬(flow matrix)을 작성한다. 각 기계 그룹에서 기계 배치순서를 이 흐름행렬을 기반으로 하여 다음과 같이 결정한다.

각 기계 그룹 내에 있는 기계만의 흐름행렬을 전체 기 계의 흐름행렬에서 추출한다. 이 흐름행렬을 고려하여 각 기계 그룹의 기계 배치순서를 다음과 같이 결정한다.

기계 그룹의 기계가 2개일 경우는 다음과 같이 기계 배치순서를 결정한다. 기계 그룹 내의 기계 흐름행렬에 서 큰 값을 선택한다. 해당 기계순서의 셀을 형성한다. 기계 흐름행렬에서 값이 동일할 경우 임의로 선택한다.

기계 그룹의 기계가 3개 이상일 경우는 다음과 같이 기 계 배치순서를 결정한다. 기계 그룹 내의 기계 흐름행렬에 서 가장 큰 값을 선택한다. 해당 기계순서의 묶음을 형성 한다. 가장 큰 값이 복수일 경우 각각 기계순서의 묶음을 형성한다. 각각의 묶음이 좌우로 연결될 경우 연결하여 한 묶음으로 합친다. 기계그룹 내의 기계 흐름행렬에서 그 다 음으로 큰 값을 선택한다. 해당 기계순서의 묶음을 형성한 다. 형성된 묶음이 기존 묶음(앞 단계에서 구한 묶음)에 좌 우로 연결될 경우 연결하여 한 묶음으로 합친다. 선택한 값이 복수일 경우는 각각 기계순서의 묶음을 형성한다. 형 성된 묶음이 기존 묶음에 좌우로 연결될 경우 연결하여 한 묶음으로 합친다. 각각의 묶음이 좌우로 연결될 경우 연결하여 한 묶음으로 합친다. 지금까지의 묶음 형성 결과에 맞지 않는 묶음은 삭제한다. 이와 같은 과정을 기계 그룹 내의 모든 기계의 배치순서가 결정될 때까지 반복한다. 최 종적으로 형성된 묶음의 기계순서로 셀을 형성한다.

마지막 단계로 전체 기계와 부품에 대해 보다 기계 배 치 효율성을 증대시키는 최적화를 수행한다.

이렇게 하여 최종 셀이 형성되고 기계 배치순서가 결 정된다.

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

5. 수치예제

<Table 1>의 수치예제는 Nair와 Narendran[15]이 제시 한 작업순서가 주어진 8대의 기계와 20개의 부품이 있는 셀 형성 문제이다. <Table 1>의 수치예제에 대하여 본 연 구에서 제안하는 알고리듬을 적용하면 다음과 같다.

SOM에 적용시키기 위해서 <Table 2>와 같이 기계 작 업순서를 제외한 문제로 변환한다.

6. 실험 결과와 분석

본 연구에서 제안하는 알고리듬의 성능을 평가하기 위 해 Tam[17]의 12×19, Nair와 Narendran[15]의 8×20과 25× 40, Harhalakis et al.[4]의 20×20 문제에 대해 적용하여 본 다. Nair와 Narendran[15]의 8×20 문제는 수치예제에서 해 보았다. 나머지 문제들은 <Table 11>에 제시되어 있다. 이 데이터들이 실험 데이터로 선정된 이유는 기존 알고리듬 으로 얻은 해가 알려져 있기 때문에 기존 알고리듬과 본 연구에서 제안하는 알고리듬의 결과를 비교하여 제안하는 알고리듬의 성능을 평가할 수 있는 벤치마킹 데이터로 적 합하기 때문이다. 25×40 및 12×19, 20×20 문제에 대해서 는 결과만을 <Table 12>에 제시하였다.

8×20 문제와 25×40 문제에 대한 제안하는 알고리듬의 결과를 CASE, CLASS, CCA, RCA와 비교한 결과는 각 각 <Table 13>과 <Table 14>에 제시되어 있다. 제안하는 알고리듬은 기존의 여러 알고리듬과 비교하여 성능이 우 수함을 알 수 있다.

4개의 실험 데이터에 제안하는 알고리듬과 다른 알고 리듬 결과를 비교한 결과는 <Table 15>에 제시되어 있다. <Table 15>에서 ACMI, OMI와 ACUI의 3가지 성능평가 척도를 살펴보면 제안하는 알고리듬은 4개 데이터 모두 에서 ACMI, OMI와 ACUI의 3개 성능척도 거의 모두에 대해 기존의 알고리듬보다 더 좋은 해를 얻어 성능이 우 수한 알고리듬이라 할 수 있다.

7. 결 론

본 연구에서는 셀의 기계 배치순서를 결정하는 문제에 대해 인공지능 기법을 적용한 알고리듬을 제안하였다. 인공지능에 기초한 방법 중 신경망은 학습 능력을 통하여 실제 생산 현장의 문제에 대하여 유연하고 적응력 있는 해를 제공한다. 자기조직화 신경망은 입력데이터의 특징을 추출하여 지도를 형성하는 패턴 분류에 효과적인 신경망 이다. 본 연구에서는 SOM의 이러한 성질을 이용하여 LCFP 에 대해 셀 형성과 셀 내부의 기계 배치순서를 결정하는 알고리듬을 제안하였다.

본 연구에서 제안하는 알고리듬은 4개 데이터 모두에 대해 ACMI, OMI와 ACUI의 3개 성능척도 거의 모두에 대해 기존의 알고리듬보다 더 좋은 해를 얻어 성능이 우 수한 알고리듬이라 할 수 있다.