1.서 론

본 논문은 제조공정에서 전용설비와 범용설비가 혼재 되어 있는 생산시스템에서 납기지연시간 총 합의 최소화 를 위한 일정계획 수립을 유전 알고리즘으로 접근하기 위한 연구이다.

제조기업의 경쟁우위 수단으로서 정해진 납기에 공급 할 수 있는 능력, 설계 규격에 대한 적합성(conformance with specification)이나 고객 요구조건에 대한 적합성(conformance to requirements), 공정의 표준화 등을 들 수 있다. 경쟁우위 수단을 가진 중․소 제조 기업이라 하더라도 설 비에 대한 투자나 추가적인 설비증설을 빈번히 할 수 없 기 때문에 기존 설비의 활용을 극대화하지 않을 수 없다.

특히 제조공정에서 전용설비와 범용설비를 혼용하여 운영하는 경우는 그 설비의 활용을 극대화 할 필요가 있 다. 이러한 경우 제조에 필요한 설비는 동일한 작업을 처 리할 수 있는 기계가 하나 이상 있고, 설비 능력이나 효 율, 용량 등이 상이한 기계로 구성된 경우를 이종 병렬설 비라 한다. 이종 병렬설비 제조방식은 제조 기업에서 흔 히 발견될 수 있는 설비유형이다. 이종 병렬설비는 한 단 위의 작업이 끝나면 동일하지 않은 다음 작업을 수행하 려면 준비과정이 필요하다. 준비 작업을 위한 작업 준비 시간(setup time)이 소요되는데 작업 준비시간이 적게 소요 되도록 이종 병렬설비의 효과적인 관리와 효율적인 일정 계획이 필요하다.

본 연구의 사례기업 T사의 면취기 공정(beveling process) 은 출하된 강관(steel pipes)을 연결시킬 때 연결부위 의 접합을 위해 이음새 부분을 나선형 곡선으로 양 끝을 그라인딩으로 갈아내는 작업이다. 강관류의 형상에 따라 각 제품은 전용설비에 할당되고, 철의 부피와 두께에 따 라 설비가 처리할 수 있는 능력을 벗어나는 제품은 범용 설비에서 작업을 처리하게 된다. 하지만 전․범용 설비 는 한 종류의 제품을 처리한 후 다른 형상의 작업을 위 해 금형을 교체하는 작업 준비시간이 필요하다. 각 설비 에 어떠한 순서로 작업이 할당하는가에 따라 완제품 납 기일에도 큰 영향을 미치므로 주문의 납기일을 만족시킬 수 있는 최적화된 일정 수립의 필요성을 확인하였다.

여기서 작업 준비시간은 한 제품을 생산한 후 다른 종 류의 제품을 생산하기 위해 발생되는 준비시간으로 라인 교체나 성형틀 교체 등의 setup을 말하는 것으로 준비작 업을 하는 시간에는 제품을 생산할 수 없기 때문에 최적 의 로트 크기를 정하거나 최적의 작업순서를 정하여 작 업교체횟수를 줄여야 한다.

이러한 병렬설비 일정계획의 기존 연구는 오랫동안 많은 연구의 대상이 되었고, 목적함수에 따라 설비에 작 업(제품)을 할당하여 총 작업완료시간(makespan) 최소화 문제, 작업(제품) 납기지연 수 최소화 문제, 납기 조기달 성과 납기지연(earliness/tardiness) 최소화 문제 등으로 분 류된다[1, 4].

Piersma and Van Dijk[22]의 연구에서는 병렬설비의 일 정계획 문제를 세 가지 유형으로 분류하고 있다. 단, 아 래에서 여기서 p_ij 는 작업 j 를 설비 에서 처리하는 시간이 고, p_j 는 작업 j 의 작업시간을 나타낸다.

작업을 처리할 수 있는 설비가 여러 대 있을 경우를 병렬설비를 지닌 공정이라고 한다. 병렬설비 공정에서 설 비의 능력이 동일하거나 그 차이의 정도에 따라 각각의 유형으로 분류하고 있다.

일반적인 단일설비의 일정계획 문제에서 작업의 수가 n개가 있다면 이를 처리하기 위한 작업일정(스케줄) 갯수 는 n!개이며, 작업을 처리할 수 있는 설비의 수가 m 개가 된다면 작업일정의 수는 (n!)m 개가 된다. 그러므로 병렬 설비의 일정계획 문제에서 동일한 성능을 가정한 경우라 하더라도 문제의 복잡도는 NP-hard로 알려져 있다[23, 15, 9].

납기지연시간 총 합의 최소화 문제는 Lenstra et al.[16] 에 의해 NP-hard로 알려져 있고, Du et al.[17]의 연구에 서와 같이 단일 설비의 문제라 하더라도 NP-hard 영역의 복잡도를 가지는 것으로 알려져 있고, 전통적인 최적화 기법은 문제의 복잡도가 높아질수록 최적의 대안을 찾는 것이 어렵다[19]. 이러한 문제를 해결하기 위하여 다양한 휴리스틱 기법이 제안되었고, 여기에는 시뮬레이티드 어 닐링(SA : simulated annealing), 타부서치(TS : tabu search), 분지한계(B&B : branch and bound), 신경망 네트워크(NN : neural network), 유전 알고리즘(GA : genetic algorithm) 등이 있다[2].

이러한 다양한 방법을 활용한 연구들을 살펴보자면 Lee and Pinedo[14]는 WSPT(Weighted Shortest Processing Time) 규칙과 LSR(Least Slack Remaining)규칙을 결합한 ATS (Apparent Tardiness Cost) 알고리즘에서 작업 준비시간을추가한 ATCS(Apparent Tardiness Cost with Setups)를 고안 하여 순서 의존적인 작업 준비시간이 요구되는 단일 및 이종 병렬설비의 총 가중 납기지연 시간을 최소화하는 휴리스틱 기법을 제안하였다. 이는 ATCS 규칙의 적용을 위해 각 작업들의 총 처리시간, 결정모수, 통계적인 특성 을 고려하였으며, 작업을 기계로 할당하여 시뮬레이티드 어닐링 방법을 사용하여 보다 개선된 해를 구하였다.

Kanet[12]은 모든 작업이 공통의 납기일자가 작업완료 시간보다 클 경우의 단일설비에서 MAD(Mean Absolute Deviation)를 최소화하는 일정계획 문제 대하여 연구하고, 최적 알고리즘을 제안하였다. Hall[10]은 Kanet의 연구를 확장하여 한 문제에 대한 여러 해가 존재함을 밝히고, 해를 구하는 알고리즘을 제시하였다. 또한 Lawler[13]은 pseudo- Polynomial 알고리즘을 이용하여 전체 작업의 납기지 연을 줄이는 방법을 제시하였고, Monma and Potts[20]은 Batch Setup 시간을 갖는 두 대의 동일 설비에 대한 문제에 서 총 작업시간, 최대 지연시간(maximum lateness), 지연작 업의 수(number of late jobs), 전체 가중 완료시간(total weighted time)의 pseudo-Polynomial 알고리즘을 개발하여 알고리즘을 m 개의 설비에 대한 문제로 확장하였다.

Wilkerson and Irwin[25]은 납기지연 시간을 최소화하기 위하여 단일설비에서 EDD(Earliest Due-Date)규칙을 확 장하는 알고리즘을 제안하였고, Dobson and Nabinadom[7] 은 각각의 작업들이 서로 다른 작업 완료시간의 가중치 합을 요구하는 작업군을 갖는 작업들을 처리하는 방법을 연구하였다. Schutten and Leussink[24]은 출하날짜(release dates)와 납기일, 작업군별 작업 준비시간을 고려하여 최대 지연시간을 최소화하는 분지한계 알고리즘을 제안하였다.

Leung and Young[17]은 동일하지 않은 작업 처리시간을 가지는 단일설비에서 작업의 총 납기지연 최소화를 위한 알고리즘을 제안하였고, Park[21]은 작업의 처리시간이 모 든 기계에서 동일하고, 납기 및 납기 가중치가 주어졌을 때 납기지연 가중 합을 최소화를 위해 유전 알고리즘을 제 안 및 MDD(Modified Due Date) 알고리즘과 비교 분석하 였고, Jeon and Park[11]는 단일기계 문제에서 총 납기지 연시간을 최소화하기 위해서 두 개 작업씩 쌍으로 비교 하는 JPC(Job Pair Comparison)할당규칙을 제시하고, 적 용에 있어 이행성을 증명하였고, Bilge[3]는 일정한 비율 로 성능의 차이를 보이는 병렬기계에서 순서의존적 작업 준비시간을 가지는 작업의 총 납기 지연시간 최소화를 위해 기존 연구의 해의 검색 절차를 개선하는 Tabu search 알고리즘을 제안하였고, Logendran[18]은 타부서치 알고 리즘을 활용하여 이종 병렬설비의 가중 납기지연시간의 최소화를 위한 알고리즘을 제안하였다.

본 연구에서는 현실적인 문제의 상황을 해결하기 위 하여 설비의 능력이 각각 다르며, 설비는 전용과 범용 설 비로 구분됨을 가정하였다. 또한 작업 종류에 따라 지정 된 전용설비에서 작업되고, 범용설비는 모든 제품을 작 업할 수 있다. 각 작업이 완료되면 작업교체나 예방정비 를 위한 준비시간을 고려한 납기지연시간 총 합 최소화 일정계획을 수립하고자 한다.

그러므로 본 연구에서는 각 작업(제품)은 각기 다른 납 기일을 가지고 있다. 이러한 작업을 전․범용설비로 구성 된 공정에서 처리할 경우 작업 완료시간과 납기 지연시간 을 어떻게 최소화할 것인가 하는 문제를 다룬다. 위의 상황 에서의 문제를 해결하기 위하여 유전 알고리즘을 제안하 고 EDD(Earliest Due-Date), LPT(Longest Processing Time), SPT(Shortest Processing Time) 기법과 비교하여 알고리즘 의 성능을 평가하고자 한다.

본 논문은 5장으로 구성되어 있으며 각 장의 구체적인 내용은 다음과 같다. 제 2장에서는 연구의 대상 문제를 정의하고, 제 3장에서는 문제의 분석을 통하여 유전 알 고리즘 적용시켜 보았다. 제 4장에서는 제안된 유전 알 고리즘의 성능을 평가하였으며, 제 5장에서는 추후 연구 및 결론에 대하여 논하였다.

2.문제의 정의

본 연구에서의 납기지연 총 합의 최소화 문제는 설비 별로 작업 준비시간과 작업시간이 상이하고 각기 다른 납 기일 d_j 가 존재하는 n 개의 작업을 전용설비, 범용설비에 따라 다른 성능을 가지는 m 대의 설비에 납기지연시간의 총 합을 어떻게 최소화할 것인가 하는 문제이다. 즉, 작업은 전용설비의 처리시간과 작업 준비시간이 있고, 범용설비 에서도 처리시간과 작업 준비시간이 있다. 또한 작업 j 는 상이한 납기일 d_j 가 존재하며 작업 완료시간을 C_j 라 하면 이 문제에서의 목적함수는 납기지연시간 총 합(Total Tardiness: ∑ j = 1 n max 0, C j − d j 을 최소화 하고자 하는 것 이다. 문제에서 고려하는 가정은 다음과 같다.

j : 작업 index

i : 기계 index

a : 주문량 index

d : 납기일 index

C_j : 작업 j 의 작업완료시간

a_j : 작업 j 의 주문량

d_j : 작업 j 의 납기일

p_ij : 작업 j 가 i 번째 설비에서 작업할 때 처리시간

s_ij : 작업 j 가 i 번째 설비에서 작업할 때 준비시간

본 연구의 문제 상황에 관한 이해를 돕기 위해 다음의 예제 문제를 활용하여 설명하고자 한다. <Table 1 <에서 와 같이 사례기업 T사의 면취기 공정의 작업정보가 있고, 각 작업은 납기일이 정해져 있으며, 설비의 처리시간이 각각 다른 전용․범용설비가 2대, 2대 있다고 가정한다.

<Figure 1>을 통하여 전용(Identical)설비 2대, 범용(Non- Identical)설비 2대인 이종 병렬설비의 납기지연시간 총 합 최소화 목적을 위한 일정계획 문제의 예제를 참조할 수 있다. 그림에서 붉은색 점선으로 표시된 것은 각 작업 별 납기일을 표시한 것이며, 이를 초과하면 납기지연이 발생되는 것이다. “작업 j(T_j) ”는 작업 j 가 전용설비에 처리되는 납기지연시간으로 T_j = max {0, C_j - d_j} 이다. C_j는 설비에 작업이 투입되어 처리된 후 종료되는 시점을 의미하고, 첫 번째 작업 j 의 작업 종료시점인 p_ij 의 처리 시간과 주문량 a_j 의 곱으로 계산할 수 있다. 예를 들어 전용설비 1의 경우 “작업 3(0분)”의 의미는 작업 3의 납 기지연시간이 0분을 의미한다. d₃ 는 작업 3의 납기일로 T₃ 은 max {0, (p₁₃ × a₃)- d₃} 이며 작업 완료시점인 20분 에서 납기일 20분을 뺀 0분이 작업 3의 납기 지연시간이 된다. 작업 3과 작업 7의 사이에 표시된 노란색은 작업 7의 작업 준비시간 s₃₇ = 3 의 작업 준비시간 를 의미하며, T₇ = {0, C₇ - d₇ 은 작업 j₇ 의 작업 종료시점 C₇ 은 (p₃₃ × a₃) + s₃₇ + (p₃₇ × a₇) 이 된다. 그러므로 전용설비 1의 납기지연시간의 합은 26 분이 되며, 총 납기지연시간 ∑ j = 1 n T j 은 전용․범용설비의 납기지연시간의 모두 더한 합으로 ∑ j = 1 n max 0, C j − d j 가 된다.

3.유전알고리즘의 적용

본 연구에서 제안하는 유전 알고리즘 절차는 Choi et al.[5, 6]의 알고리즘을 문제의 상황에 따라 수정 및 적용 하였으며, 염색체의 해석과 전용․범용 설비의 작업할당 을 위하여 설비할당절차를 제안하였다.

3.1개체의 표현

유전 알고리즘의 첫 단계는 문제의 잠재해를 어떻게 표현하는지 결정하는 것으로 이때, 염색체의 표현방법에 따라 알고리즘의 성능이 달라진다. 본 연구에서는 <Figure 2>와 같이 각 염색체 비트에 작업을 표현하도록 하였다.

<Figure 3>은 염색체 구조의 예제로 작업이 7개 있으며, 작업 2가 면취기 공정에 처음으로 할당되고 작업 4는 두 번째로, 마지막으로 작업 5의 순서로 할당됨을 의미한다.

3.2초기 모집단 및 적합도 평가

염색체 개체들로 구성된 모집단을 운영하기 위항 본 연구에서는 100개의 염색체를 임의로 생성하여 구성하 였다. 또한 적합도(fitness)는 개체의 생존능력을 의미하 고, 모집단에서 다음 세대로 생존할 개체를 선별하기 위 하여 목적함수 ∑ j = 1 n T j 를 사용하였다.

3.3선별기법 및 교차연산

선별기법은 개체의 적합도에 기초하여 모집단에서 다 음 세대로 생존 또는 유전에 필요한 개체를 선별하는 과 정으로 모집단의 다양성과 좋은 해를 효율적으로 사용하 기 위하여 큰 적합도를 가지는 개체의 생존 가능성을 높 이는 확률적 과정인 roulette wheel selection 기법을 사용 하였다. 이는 모든 개체의 적합도를 계산하여 우수한 개 체를 그렇지 못한 개체에 비하여 비율적으로 넓은 룰렛 의 범위가 결정되도록 하여 개체의 생존가능성을 높였다.

교차연산에는 선별기법을 통하여 선택된 두 개의 개체 에서 공통적으로 두 개의 절단점을 임의로 선택하여 교 차하는 것 이점교차를 사용하였다. 이는 두 절단점을 기 준으로 앞, 중간, 뒤의 세 부분으로 구분하였다. 앞과 뒤 부분의 인자는 다른 자손에게 교차되어 상속되고, 중간의 유전인자는 자손 개체에 보존되어 상속되도록 하였다.

<Figure 4>는 교차연산의 예제로 두 개의 절단점을 선 정하고 부모의 유전인자를 자손에게 상속받도록 하였다. 교차연산을 수행하다 자손의 염색체에 동일한 인자가 중 복적으로 출현하는 경우가 발생할 수 있다. 이 경우 3.4 의 교정연산을 통하여 실행 불가능한 염색체를 유효하게 만들도록 하였다. 자손 염색체의 적합도 계산을 통하여 모집단의 가장 열등한 염색체와 비교하여 우월한 자손은 다음 세대의 진화에 참여시키고, 그렇지 못한 개체는 제 외시키도록 하였다.

3.4돌연변이 연산 및 교정연산

돌연변이 연산은 하나의 염색체를 부분적으로 조작해 서 새로운 염색체를 만드는 연산으로 교차연산을 통해 생성할 수 없는 염색체를 인위적으로 만들어 내는 연산 이다. 선택된 개체의 스트링 수 이내로 난수를 발생시켜, 난수에 해당되는 염색체 값을 인위적으로 변화를 주어 새로운 개체를 만들어 내도록 하였다.

초기 모집단 구성을 위한 임의생성, 교차, 돌연변이 연 산에서 작업이 염색체에 중복 표현되는 경우가 발생될 수 있다. 이러한 경우는 염색체의 일부가 연구의 기본적 인 가정을 만족하지 못하는 것으로 모든 작업이 염색체 에 출현할 수 있도록 염색체로 변형하였다.

[교정연산 절차]

step 1 : 모든 작업이 할당되었으면 종료.

step 2 : 염색체에 표현되지 않은 작업 j 를 선택.

step 3 : 중복 표현된 작업j′를 선택.

step 4 : 작업 j′ 를 삭제하고 그 자리에 작업 j 를 할당.

step 5 : 모든 작업의 할당이 완료되면 종료, 그렇지 않으면 step 1로 이동.

위의 ‘교정연산 절차’는 염색체에 모든 작업이 출현할 수 있도록 작업을 강제로 할당하는 방법이다.

3.5설비할당 절차

염색체는 작업들이 투입되는 순서 정보에 해당되는 것으로 염색체 해석을 통하여 전용․범용 설비에 적절 히 작업 할당을 결정해야 한다. 본 연구에서는 다음과 같 은 작업할당 절차를 활용하여 각 설비에 작업을 할당하 였다.

염색체의 작업순서 정보를 활용하여 전용설비에 투입 이 불가한 작업을 우선적으로 범용설비에 할당하는 규칙 으로 범용설비를 효율적으로 사용하도록 하였다. 이는 다음과 같은 세부절차를 따른다.

[설비할당 절차]

step 1 : 전용설비에서 작업시간이 0인 작업을 선택한다.

step 2 : 염색체에 표현된 순서대로 나열하고 선택한다.

step 3 : 범용설비 작업완료시간이 가장 짧은 설비에 작 업을 할당한다.

step 4 : 모든 작업이 할당되었으면 step 5로 이동, 그렇 지 않으면 step 2로 이동한다.

step 5 : 전용설비의 작업 처리시간이 0인 염색체를 삭 제한다.

step 6 : 전용설비의 처리시간이 범용설비의 처리시간 보다 작은 경우 염색체의 순서에 따라 작업을 전용설비에 할당한다. 그렇지 않다면 step 7로 이동한다.

step 7 : 범용설비 작업완료시간이 가장 짧은 설비에 작 업을 할당한다.

step 8 : 모든 작업의 할당이 완료되면 종료한다, 그렇 지 않으면 step 6으로 이동한다.

4.성능 평가

본 장에서는 납기지연시간 총 합의 최소화 문제에 대 하여 제 3장에서 제안된 유전 알고리즘의 성능을 평가하 고 분석한다. 본 연구에서는 복잡한 납기지연문제에서 단 시간에 효과적인 해를 도출하는 휴리스틱 방법인 EDD, SPT, LPT 규칙과 비교분석 하고자 한다.

유전 알고리즘은 1000세대까지 유전시켰으며, 각 문제 당 20가지의 문제를 임의 생성하였고, 10회에 걸쳐 유전 알고리즘으로 문제를 실험하였다. <Table 2 <는 작업과 설비의 유형, 각 설비 수의 변화에 따라 유전 알고리즘이 얼마나 좋은 성능을 보이는지에 대한 성능평가이다. 이 실험에서는 작업의 수가 30, 40, 50, 60, 70, 80개이고, 설 비의 수는 전용설비 3～6대, 범용설비 3～6대이며, 작업 j 의 설비별 작업 처리시간을 20～50, 작업 준비시간을 20～50, 주문량을 20～50사이에서 임의 생성하였다. 또 한 작업들의 납기일 d_j 는 U (T_l × R_L, T_u × R_L로부터 발 생시켰다. 여기서 R_L 은 작업완료시간 (C_max) 의 이론적 하 한값을 의미하며, (T_l, T_u) 값의 범위는 (0.4, 0.8)로 설정 하였다.

여기서 Gap1(%)은 유전 알고리즘의 연산을 통해 제시 된 가능해와 EDD와 오차를 의미하며, Gap 2(%)는 유전 알고리즘의 가능해와 LPT와 오차를 의미하며, Gap 3(%) 는 유전 알고리즘의 가능해와 SPT와 오차를 의미한다. Average Gap(%)은 Gap(%)의 오차 평균값을 의미한다.

Gap 1～3(%)은 다음과 같은 식에 의해 구할 수 있다.

Gap 1(%) = {(EDD-GA)/EDD} × 100

Gap 2(%) = {(LPT-GA)/LPT} × 100

Gap 3(%) = {(SPT-GA)/SPT} × 100

<Table 2 <는 작업과 설비의 유형, 각 설비 수의 변화에 따라 유전 알고리즘이 얼마나 좋은 성능을 보이는지에 대한 실험이다. 작업의 수는 30~70개, 전용․범용설비를 각 3~5대에 대하여 실험하였다. Average Gap 1(%)에서 작업의 수와 설비의 수가 증가할수록 즉, 문제의 복잡도 가 증가됨에 따라서 EDD와의 차이가 최소 23%까지 줄 어들었다. 작업의 수에 비해 설비의 수가 작은 경우는 EDD보다 최대 53% 개선된 해를 제공해 주었다.

Average Gap 2(%)는 유전 알고리즘과 LPT 해와의 차 이로 설비의 수가 작은 경우 최대 74% 유전 알고리즘이 우수한 해를 제공해 주었으며, 문제의 복잡도가 증가될 수록 최소 34% 유전 알고리즘의 가능 해와의 차이가 줄 어드는 것을 확인할 수 있었다.

Average Gap 3(%)는 유전 알고리즘과 SPT 해와의 차 이로 설비의 수가 작은 경우 최대 72% 유전 알고리즘이 우수한 해를 제공해 주었으며, 문제의 복잡도가 증가될 수록 최소 27% 유전 알고리즘의 가능 해와의 차이가 줄 어드는 것을 확인할 수 있었다.

Average Gap 1(%)은 납기일을 기준으로 한 휴리스틱 방법으로 LPT, SPT 방법보다 비교적 개선된 해를 제공 하였고, 공통적으로 Average Gap2(%)과 Average Gap 3(%) 은 납기일 최소화 관점의 휴리스틱 방법이 아니기 때문 에 유전 알고리즘의 해와 많은 차이를 보였으며, EDD, LPT, SPT와 비교하여 유전 알고리즘은 우수한 가능해를 제공함을 확인할 수 있었다.

<Table 3>, <Table 4>, <Table 5>은 작업의 수를 30, 40, 50, 60, 70, 80개, 설비의 대수는 전용설비 4대, 범용설비 5대인 경우를 대상으로 납기일 d_j 는 U (T_l × R_L, T_u × R_L로 부터 발생시켰다. (T_l, T_u) 는 (0.4, 0.8) 사이에서 임의 생성 하였으며, 전용설비에 투입될 수 없는 작업의 생성을 위한 비율은 전체 작업의 20%로 가정하고 임의생성 하였다. 작 업 준비시간, 주문량, 작업 처리시간 범위의 변동에 관한 실험으로 Gap(%)은 <Table 2>에서 실험한 휴리스틱 방법 중 비교적 좋은 가능해를 제공하는 EDD와의 비교하였다.

<Table 3>에서는 최소 작업 준비시간을 20으로 고정한 실험에서는 작업 준비시간의 범위가 증가되더라도 알고리 즘의 성능은 최소 25%에서 최대 48%, 작업 준비시간의 범위를 30으로 고정시킨 실험에서는 최소 22%에서 최대 53%로 EDD와 비교하여 유전 알고리즘의 해가 우수한 가 능해를 제공해 주었다. <Table 4 <, <Table 5>도 공통적으로 작업의 수가 증가하여 문제가 복잡할수록 EDD와의 차이 가 줄어드는 것을 확인할 수 있다. 이는 EDD 방법이 복잡 한 문제에서도 수렴가능한 해를 찾아주지만 최적해나 최적 해와 근사해를 제공하는 메타휴리스틱 기법의 유전 알고리 즘 보다 좋은 해를 제공해 주지는 못함을 확인할 수 있었다.

<Table 6>는 작업 j 의 납기일 범위의 변동에 따른 실험으 로 납기일 범위가 (0.4, 08)인 경우 (0.6, 1.0)인 경우보다 더 개선된 가능해를 제공해주고 있다. 이는 각 작업의 납기일의 초과한 기간이 더 긴 (0.6, 1.0)보다 초과 기간이 짧은 경우 더욱 안정적인 가능해를 제공해주는 것으로 해석할 수 있다.

<Table 7>은 유전 알고리즘의 전용설비에서 작업 불가 능한 작업의 비율에 대한 실험으로 작업의 수가 증가할 수록 EDD와의 차이가 줄어들며, 전용설비 불가 작업의 비율이 0.5에서 가장 좋은 가능해를 제공해 주었다. 이는 전용설비에서 처리 불가능한 작업이 전체 작업 50%인 경우로써 80%인 경우보다 전․범용 설비에 작업을 균등 하게 할당하는 것으로 판단된다. 즉, 작업을 비대칭적으 로 할당하는 80%인 경우보다 전용설비와 범용설비를 효 율적으로 배분하여 작업을 할당하기 때문에 처리시간의 차이가 줄어드는 것으로 판단된다.

<Table 8>는 작업 j 의 규모를 비현실적으로 크게 한 경 우의 실험으로 작업의 수가 증가함에 따라 알고리즘의 성 능은 EDD와 최대 33%에서 최소 26% 차이를 보인다. 본 연구에서 제안하는 유전 알고리즘이 규모가 큰 문제에 대 해서도 안정적인 가능해를 제공해 주는 것으로 판단되며, Average Gap 2(%) 최소 57%에서 최대 75%, Average Gap 3(%) 최소 23%에서 최대 50%로 LPT, SPT보다 개선된 가능해 를 제공하는 것으로 확인되었다. 하지만 작업의 수를 증 가시킬수록 실험시간도 증가됨을 확인할 수 있는데, 유전 알고리즘의 염색체 비트가 작업의 수를 의미하고, 이는 유전과정에서 염색체 해석과 유전연산에 소요되는 시간 이 길어지는 것으로 해석할 수 있다.

5.결 론

본 논문에서는 사례기업의 실제 생산시스템을 반영한 연구로써 전용설비와 범용설비가 혼재되어 제품을 제조 하는 면취기 공정상황으로 이종병렬설비의 납기지연시간 총 합의 최소화 문제를 유전 알고리즘을 활용하여 계획하 였다. 유전 알고리즘의 성능을 향상시키고자 염색체의 작 업순서를 각각의 설비에 할당하는 ‘설비할당 절차’와 해 의 가정을 만족시키는 ‘교정절차’를 제시하였다. 알고리 즘에서 제안하는 가능해의 검증을 위해 EDD, SPT, LPT 휴리스틱 알고리즘과 비교하였고, 가능해의 우수성을 분 석하였다.

추후 유전 알고리즘의 성능에 대한 다양한 접근과 평 가를 위해 이론적 하한값, 메타 휴리스틱 알고리즘의 개 발이 필요하며, 다단계 공정상황의 이종병렬설비 대상으 로의 연구 확장, 실제 기업에서 발생 가능한 복합적인 상 황들을 고려하는 연구가 필요하다.