1. 서 론

최근 제조 시스템은 개인화된 고객 요구와 짧은 제품 수명 주기에 대응하기 위해 다품종 소량 생산 체제로의 변화가 활발히 일어나고 있다[1, 5, 12]. 이러한 환경에서는 동일한 작업을 반복하는 주기적(cyclic) 스케줄링보다는, 서로 다른 공정 시간을 가지는 이종 작업(heterogeneous jobs)의 비주기적 스케줄링(non-cyclic scheduling)이 필수적이며 이는 생산성과 직결된다[13, 19, 22].

본 연구에서는 구체적으로 로봇 셀에서의 비주기적 스케줄링 문제를 다룬다. 로봇 셀(robotic cell 또는 robotic flow shop)은 반도체, 디스플레이, 전기도금, 섬유, 화장품 등 다양한 제조 산업에서 널리 활용되고 있다[2, 3, 4, 11, 20, 21]. <Figure 1>은 전형적인 로봇 셀의 구성을 보여준다. <Figure 1>의 예에서는 네 개의 공정설비들(processing machine)이 직렬로 배치되어 있으며 시작과 끝에 각각 작업물의 투입과 회수가 일어나는 입력장치(input device)와 출력장치(output device)가 존재한다. <Figure 1>의 예와는 달리 공정설비들이 원형(circular)으로 배치되는 구성도 존재한다[9]. 공정설비 이외에 로봇 셀에서 중요한 역할을 하는 구성요소는 이송로봇이다. 이송로봇은 설비에 작업물을 이적재(unloading or loading)하거나 설비 간 작업물을 이동시키는 역할을 한다. 반면, 공정설비는 이송로봇이 작업물을 투입해주면 공정을 시작하고 이송로봇이 공정이 끝난 작업물을 회수해야 다음 공정을 진행할 수 있는 준비상태가 된다. 즉, 공정설비는 수동적인 구성요소라고 할 수 있으며, 로봇 셀 스케줄링의 핵심은 결국 이송로봇의 작업순서와 타이밍을 결정하는 것이라고 할 수 있다[1, 2].

이송로봇은 일반적으로 한팔(single-gripper) 혹은 양팔(dual-gripper)을 가진다[8]. 양팔 로봇의 경우 두 개의 작업을 동시에 파지할 수 있어 한팔 로봇보다 생산성이 높다는 장점이 있으나, 로봇 작업 스케줄링의 복잡도가 높다[8]. 본 연구에서는 양팔 이송로봇이 탑재된 양팔 로봇 셀(dual-gripper robotic cell) 스케줄링 문제를 다룬다.

로봇 셀 스케줄링에 관한 기존 연구는 주로 이송로봇의 주기적 스케줄링에 집중되었다[20]. Dawande et al.[2]는 2~3개의 설비로 구성된 로봇 셀에서 최적의 주기적 로봇 작업 순서를 도출하였고, 일부 연구자들은 유사한 조건 하에서 1-unit 또는 k-unit 주기적 스케줄링에 대한 수리적인 분석을 수행하였다[20]. 양팔 로봇 셀의 주기적 스케줄링에 대해서는 비교적 최근 pick-up 제약이나 근사 해법을 중심으로 연구가 진행되었으나, 복잡한 문제 특성으로 인해 여전히 연구가 제한적이다[8, 9].

로봇 셀과 유사한 논리적 구조를 가지는 반도체 제조용 클러스터 장비(cluster tool) 분야에서도 활발한 연구가 진행되어왔다[6, 14, 17, 18, 23, 24]. Jung and Lee[6]은 timed Petri net(TPN) 기반의 혼합 정수 계획법(MIP) 모델을 제안하였으며, 이후 분기한정법(B&B)과 도달가능트리(reachability tree) 기반의 최적 알고리즘이 개발되었다[7, 10]. 또한, 스케줄링 가능 여부(schedulability) 분석이나 최적 조건(optimality condition) 도출을 위한 이론적 연구들이 수행되었으나, 대부분 주기적 스케줄링의 범주에 머물러 있다.

비주기적 스케줄링 연구는 그 고유한 복잡성으로 인해 상대적으로 미진한 실정이다. Hurink and Knust[5]는 단위 공정 시간을 가지는 2-설비 로봇 셀의 복잡도(complexity)를 분석하였고, Shabtay and Arviv[19]은 3-설비 환경의 특수 케이스에 대해 최적 순서(optimal sequence)를 분석하였다. Carlier et al.[1]은 makespan(또는 최대완료시간) 최소화를 위한 최적화 기반 휴리스틱을 제안하였으며, Wikborg and Lee[22]은 자원 준비 시간을 고려한 다목적 최적화를 통해 한팔 클러스터 장비 스케줄링을 위한 알고리즘을 제시하였다. 최근 Lee and Kim[15]은 Wikborg and Lee[22]에서 제시된 아이디어를 확장/발전시켜 양팔 로봇 셀의 최적 스케줄링을 위한 효율적인 알고리즘을 제안하였다.

하지만 이러한 선행 연구들의 대부분은 단순한 구조하에서 주기적 스케줄 도출에 초점을 맞추거나, 그렇지 않은 경우 스케줄 도출을 위해 매우 긴 연산 시간이 요구된다는 한계가 있다. 전술한 바와 같이 본 연구에서 다루는 양팔 로봇 셀의 비주기적 스케줄링을 위해 사용할 수 있는 최적 알고리즘이 Lee and Kim[15]에 의해 최근 제시되었으나, 문제 자체의 계산복잡도가 높아 문제의 크기가 커지면 최적해를 구하기까지 많은 시간이 소요된다. 실제 생산 현장에서 실용적으로 활용될 수 있는, 즉, ‘실용적인 크기의 문제’에 대해 합리적인 연산 시간 내에 우수한 스케줄을 도출할 수 있는 휴리스틱 알고리즘에 대한 연구는 부족한 실정이며, 본 연구를 통해 이러한 연구 공백을 채우고자 한다. 본 연구에서 목표로 하는 ‘실용적인 크기의 문제’는 실제 제조 현장의 운영 단위와 기존 연구의 수리적 한계를 종합적으로 고려하여 정의될 수 있다. 반도체나 디스플레이 제조와 같이 양팔 로봇 셀이 널리 쓰이는 산업에서는 통상적으로 25~30단위의 작업물이 담긴 다수의 카세트가 연속적으로 투입되며, 하나의 스케줄링 계획 기간(예: 1 Shift) 내에 처리해야 하는 이종 작업의 수는 일반적으로 수백 개 이상이다. 반면, 기존 문헌에 제시된 최적 알고리즘들은 작업의 수가 100~200개만 되어도 합리적인 시간 내에 해를 도출하지 못하는 경우가 빈번히 발생한다[15]. 따라서 본 연구는 실제 산업 현장의 대규모 연속 생산 물량을 지연 없이 스케줄링할 수 있는 수준인 최대 500개의 작업 규모를 실용적인 크기로 정의하며, 이를 합리적인 연산 시간 내에 해결할 수 있는 휴리스틱 알고리즘의 개발을 목표로 한다.

마지막으로 본 연구의 주요 기여점은 다음과 같이 요약할 수 있다. 첫째, 양팔 로봇 셀의 비주기적 스케줄링 문제를 해결하기 위한 실용적이고 효율적인 휴리스틱 알고리즘을 새롭게 제안한다. 둘째, 선행 연구에서 검증된 최적 알고리즘의 탐색 논리를 기반으로 하되, 조건을 전략적으로 완화하고 탐색 공간을 제한하는 방식을 도입함으로써 최적화 이론과 휴리스틱 기법 간의 연구 공백을 효과적으로 메운다. 셋째, 제안된 알고리즘이 최적해에 근접한 우수한 스케줄을 합리적인 계산 시간 내에 도출함을 수치적으로 입증한다.

2. 문제정의

본격적인 문제정의에 앞서 본 논문에서 사용되는 기호 및 변수에 관한 요약을 <Table 1>에 제시한다.

본 연구에서는 양팔 로봇 셀의 비주기적 스케줄링 문제를 다루며, 목적식(objective function)은 makespan 최소화이다. 구체적으로 <Figure 1>과 같이 m개의 공정설비가 직렬로 배치된 로봇 셀 환경을 가정하며, n개의 서로 다른 작업(job)이 해당 로봇 셀을 통해 생산된다. M = { 0 , 1 , 2 , … , m + 1 }와 J = { 1 , 2 , … , n }는 각각 설비와 작업 집합을 나타낸다(단, 설비 0과 m+1은 각각 입력장치와 출력장치를 의미). 각 작업 j ∈ J는 설비 i ∈ M에서 p i j의 공정시간을 가지며, 이는 작업-설비 조합에 따라 서로 다른 값을 갖는다. 초기에 로봇 셀은 비어있다고 가정하며, n개의 작업 중 마지막 작업이 출력장치에 투입되는 시점을 makespan으로 정의한다. 모든 작업은 첫 번째 설비부터 m번째 설비를 순서대로 거치며, 각 설비에 투입되는 작업의 순서는 사전에 결정되어있는, 즉, 순열흐름생산(permutation flowshop)을 가정한다. 각 작업의 설비 이동 경로와 순서는 비교적 단순하지만, 전술한 바와 같이 로봇 셀의 생산성을 결정하는 핵심점인 구성요소는 이송로봇이며 결국 이송로봇의 작업순서와 타이밍이 결정되면 전체 로봇 셀의 생산 스케줄이 정해진다. 따라서, 본 연구에서는 이송로봇의 작업순서와 타이밍을 결정하는 것을 목표로 한다. 순열흐름생산을 가정하더라도, 매 순간 이송로봇이 수행할 수 있는 작업의 종류가 많고 어떤 작업을 선택하는가에 따라 목적식의 값이 달라지므로 스케줄링 복잡도가 매우 높다. 순열흐름생산을 가정하는 로봇 셀 혹은 반도체 제조용 클러스터 장비에서 이송로봇의 스케줄링 복잡도가 NP-hard임이 알려져 있다[1, 12].

이송로봇의 작업은 크게 이재(unloading), 적재(loading), 이동(transporting or moving)으로 볼 수 있으며, 이재와 적재에 각각 u와 l의 시간이 소요된다고 가정한다. 이동의 경우 로봇 팔에 작업을 든 채로 이동하는 경우와 빈 채로 이동하는 경우로 나눌 수 있으나 이동 시간에 차이는 없다고 가정한다. 이동 시간에 영향을 미치는 요소는 실제 이동 거리이다. 즉, 설비 i와 k 사이를 이동할 때 δ × | i − k | 만큼의 시간이 소요된다고 가정한다(δ는 이동 단위 시간). 마지막으로 본 연구에서 고려하는 로봇 셀은 양팔을 가지고 있기 때문에 두 팔의 위치를 교환(swapping)하는 작업이 때때로 필요하며, 이때 소요되는 시간을 s라 가정한다. 전술한 바와 같이 본 논문에서는 makespan 최소화를 목적식으로 고려하며, 이를 달성할 수 있는 이송로봇 작업 스케줄을 빠른 시간 내에 도출할 수 있는 효율적인 휴리스틱 알고리즘의 개발을 목표로 한다.

3. 휴리스틱 알고리즘

전술한 바와 같이 본 연구의 목표는 양팔 로봇 셀의 비주기적 스케줄링을 위한 휴리스틱 알고리즘 개발이다. 휴리스틱 알고리즘 개발을 위한 다양한 접근법이 있지만, 본 연구에서는 기존에 개발된 최적 알고리즘을 기반으로 일부 조건을 완화하거나 탐색공간을 전략적으로 제한하는 방식으로 연산 시간을 줄이고 효과적으로 해를 탐색하는 휴리스틱 알고리즘을 개발한다. 양팔 로봇 셀의 비주기적 스케줄링을 위해 개발된 최적 알고리즘 중 우수하다고 알려진 Lee and Kim[15]의 알고리즘을 바탕으로 휴리스틱 알고리즘을 개발한다. 본 논문의 자체완결성을 높이기 위해 우선 Lee and Kim[15]의 최적 알고리즘을 간단히 소개한 후, 본 논문에서 제안하는 휴리스틱 알고리즘에 대한 설명을 제시한다.

Lee and Kim[15]이 제안한 지배속성(dominance property) 기반 최적 알고리즘은 TPN을 통해 문제를 모델링하고, 해당 TPN 모델의 도달가능트리를 탐색하여 makespan을 최소화하는 최적해를 찾는다. 알고리즘의 진행방식 자체는 전형적인 분기한정법과 유사하지만, 효율성을 높이기 위해 차별화된 요소들을 활용한다. 첫 번째는 자원마킹(resource marking)이며 시스템의 방대한 상태 공간을 효율적으로 표현하기 위해 설비의 점유 상태, 이송로봇의 점유 여부, 이송로봇 내 작업물의 목적지, 이송로봇의 현재 위치 등의 정보를 표현하는 ( m + 4 )-tuple의 상태 정의 방식이다. 현재 노드를 A라고 가정할 때, 처음 m개(a i, i=1, 2, …, m)는 각 설비별 점유 여부를 나타낸다. 예를 들어 a 2=0이면 두 번째 설비가 비어있다는 것을 의미하며, 작업물에 의해 점유되어 있을 경우 1로 표현한다. ( m + 4 )-tuple 중 마지막 4개는 각각 a 1 r, a 2 r, a 3 r, a D이다. a 1 r과 a 2 r은 양팔 이송로봇의 점유 상태 및 로봇에 들려 있는 작업의 목적지를 표현한다. 만약 a 1 r과 a 2 r이 모두 0이라면 로봇이 양팔에 어떠한 작업물도 들고 있지 않다는 것을 의미한다. 반면, 로봇이 작업물을 들고 있는 경우 해당 작업물의 목적지를 a 1 r과 a 2 r로 나타낸다. 예를 들어, 로봇이 양팔에 모두 작업물을 가지고 있고 각각의 목적지가 설비 1과 2라면, a 1 r=1, a 2 r=2가 된다. 또 다른 예로 로봇이 하나의 작업물만을 가지고 있고 해당 작업물의 목적지가 설비 4라면, a 1 r=4, a 2 r=0으로 표현된다. a 3 r은 로봇의 현재 위치를 나타낸다. 즉, 예를 들어 현재 로봇이 설비 2 앞에 있다면, a 3 r=2로 표현된다. 마지막으로 a D는 입력장치에 남아있는 작업물의 수를 나타낸다.

Lee and Kim[15]에서 제시된 최적 알고리즘의 두 번째 핵심요소는 자원준비시간(resource ready time)이다. 이는 각 자원(설비 및 이송로봇)이 다음 작업을 수행할 수 있는 가장 빠른 시점으로 정의되며, ( m + 1 )-tuple로 표현된다. 처음 m개는 공정설비별 자원준비시간을 의미하며, 마지막 한 개는 이송로봇의 자원준비시간을 의미한다. 이들 자원준비시간은 각 자원별 현재 작업이 끝나는 시간을 계산함으로써 도출할 수 있다.

전술한 바와 같이 Lee and Kim[15]에서 제안한 방법은 문제를 TPN으로 모델링하고 해당 TPN 모델에 대한 도달가능트리를 생성해나가면서 최적 스케줄을 도출한다. <Figure 2>는 설비가 4개이고 처리해야 할 작업이 2개인, 즉, m=4, n=2인 간단한 경우의 도달가능트리 예를 보여준다. 그림의 노드 A는 설비와 이송로봇이 모두 비어있고 작업 2개가 대기 중인 초기 상태를 나타낸다. 따라서 자원마킹은 [ 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 ]이며 모든 자원들이 바로 가용하기에 자원준비시간 R A = ( 0 , 0 , 0 , 0 , 0 )이 된다. 각 노드에서 이송로봇이 가능한 작업을 수행할 때마다 다음 노드로 상태가 전이되며 도달가능트리가 형성된다. 예를 들어, 노드 A에서 이송로봇이 첫 번째 작업을 입력장치에서 이재할 경우 노드 B로 상태가 전이되고, 노드 B에서 이송로봇이 현재 한 팔에 들고 있는 작업을 설비 1에 적재할 경우 상태 C로 전이된다. 이때 노드 C의 자원마킹은 [ 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 ]이며, 이는 전술한 바와 같이 첫 번째 설비만이 작업물을 가지고 있고 로봇은 작업물을 들고 있지 않은 채로 설비 1에 위치하고 있음을 나타낸다. 자원준비시간 또한 TPN을 통해 쉽게 파악 가능하며, 더욱 자세한 내용은 Lee and Kim[15]를 참고할 수 있다.

전술한 요소들을 바탕으로 도달가능트리를 형성해나가며 노드 간 비교를 통해 다른 노드에 의해 지배당한(dominated) 노드는 향후에 최적해를 도출할 가능성이 없으므로 더 이상 탐색하지 않고 제거하는 방식으로 최적해 탐색이 이루어진다. 구체적으로 동일한 자원마킹을 가지는 두 노드 X와 Y가 있을 때(즉, x i = y i , i = 1 , … , m ; x i r = y i r , i = 1 , … , 3 ; x D = y D), R X ( i ) ≤ R Y ( i ) , i = 1 , 2 , … , m + 1이면, 노드 X가 노드 Y보다 우수하다고 판단하고 노드 Y는 더 이상 탐색하지 않고 제거하는 방식으로 알고리즘이 작동하게 된다. 예를 들어, <Figure 2>에서 노드 H와 노드 I는 동일한 자원마킹을 갖고 R H ( i ) ≤ R I ( i ) , i = 1 , 2 , … , 5이므로 노드 I는 가지치기(pruning)되며 더 이상 탐색하지 않는다. 해당 논문에서 제시된 최종 알고리즘을 정리하면 아래와 같다.

Step 1 (초기화):

Step 2 (최적해 탐색):

Step 3 (결과반환):

Lee and Kim[15]이 제시한이 최적 알고리즘은 기존 방법 대비 탐색 공간을 획기적으로 줄여 큰 규모의 문제에 대해서도 최적해를 도출하는 성능을 보였다. 그러나 전술한 바와 같이 문제의 계산 복잡도가 NP-hard이므로 설비 수가 증가하거나 공정 조건이 복잡해질 경우 합리적인 연산 시간 내에 최적해를 도출하는 것은 여전히 불가능하다. 따라서, 본 연구에서는 이러한 최적 알고리즘의 지배속성을 전략적으로 완화하거나 탐색 폭 또는 범위를 인위적으로 제한하는 방식의 휴리스틱 알고리즘을 제안한다.

3.1 지배속성 완화 휴리스틱(DPHA)

첫 번째로 제시하는 휴리스틱 알고리즘 DPHA(Dominance Property-based Heuristic Algorithm)는 Lee and Kim[15]에서 제시한 지배속성을 전략적으로 완화하여 더 많은 노드를 빠른 시기에 가지치기함으로써 탐색속도를 높이는 방식을 취한다. 구체적으로 최적 알고리즘에서는 설비의 상태뿐 아니라 로봇에 들려 있는 작업의 목적지까지 정확히 일치해야만 두 노드를 비교하였다. 반면, 해당 최적 알고리즘을 구현하여 실험을 진행한 결과 이송로봇 내 작업물의 목적지가 조금 다르더라도 설비들의 작업 진행 상황과 남아있는 작업의 수가 비슷하면 최종 makespan에서 큰 차이가 없는 경우가 빈번히 발생하였다. 따라서, 본 연구에서는 두 노드 간 비교 조건을 완화하여, 즉, 현재 노드를 A라 가정했을 때 자원마킹 중 a i, i=1, 2, …, m,와 a D만 동일하면 두 노드의 자원준비시간을 비교하여 지배당한 노드를 가지치기한다. 이를 통해 가지치기의 빈도를 높일 수 있고 따라서 더 빠른 시간 내에 해를 도출할 수 있다. 반면, 최적 알고리즘의 지배속성을 완화하여 가지치기를 수행하므로 최적해를 보장하진 않는다.

결과적으로 본 장에서 소개한 DPHA는 앞서 3장에서 소개한 최적 알고리즘의 Step 2에서 이루어지는 지배여부 판단 기준을 완화한 것이며 구체적으로 다음과 같이 판단한다. 노드 A와 B가 아래 조건을 만족하는 경우 노드 B가 더 우수하다고 판단하며, 따라서 노드 A는 더 이상 탐색하지 않는다.

3.2 빔서치 기반 휴리스틱(HBS)

본 연구에서 두 번째로 제안하는 휴리스틱 알고리즘 HBS(Heuristic by Beam Search)는 이름에서 나타나듯이 빔서치(beam search) 개념을 활용한 알고리즘이다. 전술한 바와 같이 기존 연구들에서 효율적인 최적 알고리즘들이 제시되었지만, 본 연구에서 다루는 문제의 계산 복잡도가 높아 문제 크기가 커질수록 탐색공간이 기하급수적으로 팽창하여 합리적인 연산 시간 내에 최적해를 도출할 수 없다. 예를 들어 앞서 3장에서 소개한 최적 알고리즘의 경우 “현재 노드 s로부터 전이 가능한 모든 자식 노드 집합 CN을 생성”하는 부분이 있으며 이러한 과정이 몇 번만 반복되더라도 탐색해야하는 공간이 기하급수적으로 커지게 된다. 이러한 수치적 한계를 극복하기 위해 제안된 빔서치는 너비우선탐색(breadth-first search)의 변형으로, 트리의 각 레벨에서 모든 자식 노드를 확장하는 대신 미리 정의된 빔폭(beam width) w만큼의 유망한 노드만을 선택하여 탐색을 이어가는 기법이다[16]. 앞서 3장에서 소개한 최적 알고리즘에 이를 적용하면, Step 2의 “현재 노드 s로부터 전이 가능한 모든 자식 노드 집합 CN을 생성” 부분이 “현재 노드 s로부터 전이 가능한 자식 노드들 중 유망한 w개의 노드를 선별하여 집합 CN을 생성”으로 변경된다고 할 수 있다. 이를 통해 최적해 도출을 위한 탐색공간이 기하급수적으로 증가하는 것을 방지할 수 있다. 반면, ‘유망한 노드’를 선별하기 위한 적절한 방법이 필수적으로 요구되며, 제대로 설계되지 않을 경우 최적해와 거리가 먼 해가 도출될 가능성이 있다.

전술한 바와 같이 본 연구에서 제안하는 HBS의 성능은 각 단계에서 어떤 노드를 ‘유망한 노드’로 판단하느냐에 달려 있으며, 이를 결정하기 위해 본 논문에서는 모든 설비의 예상평균작업부하(estimated average workload) W L을 평가 지표로 사용하는 것을 제안한다. 도달가능트리의 한 특정 노드를 가정하면, 해당 노드가 최종노드가 아닌 이상 이송로봇의 전체 스케줄(작업순서 및 타이밍)은 아직 결정되지 않았기에 현 상황에서 최종 makespan을 정확히 도출하는 것은 사실상 불가능하다. 대신 이송로봇의 스케줄에 관계없이 각 설비 별로 남은 작업을 모두 처리하기까지 걸리는 필수적인 시간인 작업부하를 유망한 노드 선별을 위한 기준으로 활용하는 것이 핵심 아이디어라고 할 수 있다. 특정 노드 A의 유망한 정도를 나타내는 W L은 각 설비 i의 예상 완료시간(W L i)의 평균값으로 정의하며, 아래와 같다.

여기서 W L i는 현재 노드 A로부터 설비 i에서 남은 모든 작업이 완료되고 최종적으로 출력장치에 투입되기까지 필요한 최소시간을 추정한 값이다. W L i를 산출하는 방식은 해당 설비가 현재 작업에 의해 점유되어 있는지에 따라 두 가지 케이스로 구분된다. 첫 번째로 설비 i에서 이미 작업이 진행 중인 경우, W L i = T ( A ) + ∑ j = n − n i + 1 n p i j + ( u + s + l ) ( n i − 1 ) + ∑ j = i + 1 m p j n + ( u + δ + l ) ( m − i + 1 )와 같이 구할 수 있다. 이 때, ( T A )는 현재 노드인 A에 도달하기까지 필요한 시간을 의미하며, 이는 이전 노드들과 전이에 필요한 이송로봇 작업들을 역추적함으로써 쉽게 구할 수 있다. ∑ j = n − n i + 1 n p i j는 설비 i에서 처리해야 할 남은 모든 작업들의 공정시간 합이다. 이 때, n i는 설비 i에서 공정을 진행해야 하는 남은 작업들의 수를 나타낸다. ( u + s + l ) ( n i − 1 )은 이송로봇이 설비 i에서 공정을 진행해야 하는 남은 작업들을 이적재하는 데 소요되는 최소 작업시간을 의미한다. ∑ j = i + 1 m p j n + ( u + δ + l ) ( m − i + 1 )은 설비 i에서의 마지막 공정이 끝난 후, 나머지 설비들을 거쳐 출력장치에 최종 투입되기까지의 최소 소요 시간을 나타낸다. 두 번째로, 설비 i가 비어있는 경우(단, 설비 i에 투입될 작업이 현재 설비 h에 있다고 가정)에는 기본적으로 앞서 첫 번째 경우와 거의 유사하지만 추가적으로 ∑ j = h i − 1 p j , n − n i + 1 + ( u + δ + l ) ( i − h )이 더해져야하며, 이는 해당 작업이 설비 h에서 설비 i에 도달하기까지 필요한 최소 시간을 의미한다.

마지막으로 정리하면, HBS 알고리즘은 도달가능트리의 각 레벨에서 다음과 같은 절차를 거친다. 최적 알고리즘과 같이 모든 자식 노드들을 생성하는 것이 아니라 모든 자식 노드들에 대해 전술한 W L 값을 계산하고 W L 값이 작을수록 유망하다고 판단하여 가장 유망한 w개의 자식 노드들에 대해서만 탐색을 이어간다.

4. 계산실험

4.1 실험환경 및 디자인

제안한 휴리스틱 알고리즘(DPHA, HBS)의 성능을 평가하기 위해 계산실험을 수행하였다. 실험은 Intel Core i7-8700K(3.7GHz) CPU 및 32GB RAM이 장착된 PC에서 진행되었다. 실험의 기본 테스트베드로는 3대의 설비를 가진 양팔 로봇 셀을 가정하였으며, 알고리즘의 확장성을 평가하기 위해 설비 4대 및 5대인 경우의 실험도 진행하였다. 작업의 수(n)는 20개부터 최대 500개까지 다양하게 설정하여 알고리즘이 소규모부터 대규모 문제까지 적절히 대응할 수 있는지 확인하고자 하였다. 각 작업의 공정시간(p i j)은 1에서 100 사이의 범위에서 임의의 정수를 생성하였으며, 이송로봇의 물리적 제약을 반영하기 위해 이재(u), 적재(l), 이동(δ), 로봇 팔 위치 교환(s) 시간은 모두 2로 설정하였다[15]. 또한, HBS에서 최적의 빔폭 w를 결정하기 위한 예비실험을 진행하였으며, 연산 시간과 해의 품질 간의 상충관계 및 설비 수에 따른 문제 복잡도 증가를 종합적으로 고려하여 설비 수 m에 비례하는 3 m으로 설정하였다.

알고리즘의 성능 평가지표로는 최적해 대비 makespan의 오차율(Makespan Gap,%)과 연산 시간(Computation Time, 초)을 사용하였다. 구체적으로 오차율은 ‘(휴리스틱 알고리즘의 makespan - 최적 makespan) * 100 / 최적 makespan’으로 계산하였으며, 기준이 되는 최적 makespan은 Lee and Kim[15]에서 제안된 최적 알고리즘을 활용하여 도출하였다. 각 조합 별 30번의 반복실험을 수행하여 평균 오차율과 연산 시간을 도출하였고, 모든 알고리즘의 연산 제한 시간은 1시간(3600초)으로 설정하였다.

본 연구의 핵심 기여가 휴리스틱 알고리즘 개발인만큼 기존의 다른 휴리스틱 알고리즘과의 비교 실험을 통한 성능 검증을 고려하였으나, 양팔 로봇 셀 스케줄링을 위한 휴리스틱 연구가 매우 제한적이어서 적절한 비교 대상 알고리즘을 찾을 수 없었다[20]. 또한, 휴리스틱 이외에도 우선순위 기반 규칙이나 디스패칭 룰과의 비교를 고려해 볼 수 있으나, 기존 연구에서 FIFO(First-In, First-Out)와 같은 간단한 규칙 기반 스케줄의 성능이 매우 좋지 않음이 규명된 바 있어 본 논문에서는 비교실험을 생략하였음을 밝힌다[11].

4.2 실험결과

설비 3대를 가정한 로봇 셀 환경에서의 실험 결과, 제안된 두 가지 휴리스틱 알고리즘은 모든 경우에 대해 평균 3% 미만의 매우 우수한 makespan 오차율을 보였다. 구체적으로 DPHA와 HBS의 평균 오차율은 각각 1.39%와 2.07%로 나타났으며, 평균 연산 시간은 각각 142.4초와 48.1초로 확인되었다. 지배속성을 전략적으로 완화한 DPHA가 더 낮은 오차율을 기록하며 해의 품질 측면에서 더 나은 성능을 보였으나, 상대적으로 긴 연산 시간을 필요로 하였다. 반면 빔서치 기반의 HBS는 오차율 측면에서 DPHA에 비해 약간 성능이 떨어졌으나, 연산 시간은 1/3 수준으로 단축되어 해의 품질과 탐색 속도 사이의 우수한 균형을 보였다고 판단된다. 이는 HBS에서 제안한 설비의 예상평균작업부하 기반의 유망 노드 선별 로직이 빔서치 환경에서 매우 유효하게 작동함을 시사한다.

자세한 실험결과는 <Table 2>와 같다. 표에서 Gap과 CT는 각각 makespan 오차율과 연산 시간을 의미한다. <Table 2>에서 확인할 수 있는 바와 같이, 작업 수 증가에 따른 확장성(scalability) 측면에서도 긍정적인 결과를 관측할 수 있다. 작업 수가 증가할수록 최적 알고리즘의 연산 시간은 기하급수적으로 증가하는 반면, 본 연구에서 제안한 휴리스틱 알고리즘은 훨씬 완만한 증가폭을 보임을 확인할 수 있다. 특히, 작업물의 수가 500개인 대규모 작업 환경에서 HBS 알고리즘은 최적해와 비교해 2.11%의 근소한 오차만을 보이면서도 연산 시간은 획기적으로 단축하였다.

<Figure 3>은 <Table 2>에 제시된 실험결과에 대해 makespan 오차율 분포를 상자수염그림(box plot)으로 시각화한 결과이다. 구체적으로 작업의 수가 20, 60, 100, 200, 300인 경우에 대하여 각 알고리즘의 실험결과를 상세히 보여준다. 각 작업 수(n) 별로 배치된 두 그래프 중 왼쪽(흰색)은 DPHA의 결과를, 오른쪽(회색)은 HBS의 실험결과를 나타내며, y축은 makespan 오차율(%)이다. <Figure 3>에서 확인할 수 있듯이 평균 오차율이 낮을뿐 아니라, 오차율의 편차 또한 충분히 작게 형성됨을 알 수 있다. 이는 제안된 알고리즘들이 다양한 공정 환경에서도 일관되게 우수한 스케줄을 생성하며, 안정성과 강건성이 충분히 확보되었음을 입증한다고 할 수 있다.

설비의 수를 4대 및 5대로 확장한 추가 실험에서도 유사한 결과를 확인할 수 있다. 평균 오차율은 설비가 3대인 경우 대비 소폭 상승하였으나, 여전히 안정적인 성능을 유지하여 제안된 휴리스틱 알고리즘들의 강건성을 확인할 수 있었다. 설비의 수가 4대 및 5대인 경우의 구체적인 실험결과는 각각 <Table 3>과 <Table 4>에서 확인할 수 있다. 설비의 수가 4대 및 5대인 경우 작업의 수(n)가 커지면 최적 알고리즘으로 연산 시간 제한(3600초) 내에 해를 구하지 못하는 경우가 발생하였다. 예를 들어 설비가 4대인 경우 n이 300보다 커지자 최적 알고리즘으로 연산 시간 제한 내에 해를 구할 수 없었고, 따라서 실험결과에 포함시키지 않았다. n이 300인 경우도 30번의 반복실험 중 일부에서는 연산 시간 제한 내에 최적해가 도출되지 않았고, 그러한 경우 연산 시간을 3600초로 기록하고 해당 시간까지 도출된 최소의 makespan을 오차율 계산에 활용하였다.

<Table 3>과 <Table 4>의 결과와 같이 설비의 수를 증가시키면서 추가 실험을 수행한 결과, 연산 시간 측면에서 흥미로운 결과를 관측할 수 있었다. 두 휴리스틱 알고리즘 모두 설비의 수가 커질수록, 즉, 문제가 더욱 복잡해질수록 최적 알고리즘의 연산 시간 대비 비율적으로 더 빠른 시간 내에 해를 도출함을 확인할 수 있었다. 특히, HBS의 연산 시간은 설비의 수가 3대인 경우 최적 알고리즘의 연산 시간 대비 평균 17.1% 소요되었으나, 설비의 수가 4대와 5대로 증가하면서 연산 시간 비율이 각각 평균 5.8%와 1.8%로 급격히 감소함을 확인할 수 있었다.

<Figure 4>와 <Figure 5>는 각각 <Table 3>과 <Table 4>의 실험결과에 대한 상자수염그림을 보여준다. 앞서 설비의 수가 3대인 경우와 유사하게 makespan 오차율의 편차가 크지 않음을 확인할 수 있다. 또한, 작업의 수가 커질수록 오차율의 편차가 더욱 작아지는 경향 또한 확인할 수 있다.

결론적으로 본 연구에서 제안한 두 휴리스틱 알고리즘(DPHA, HBS) 모두 합리적인 연산 시간 내에 우수한 스케줄을 도출함을 실험적으로 입증하였다. 특히, HBS는 연산 시간을 획기적으로 단축하면서도 최적해와 근사한 해를 도출하여 실무적 효용성이 매우 높음을 확인하였다. 이러한 실험결과를 바탕으로, 실무적 관점에서 다음과 같은 상황별 알고리즘 적용을 권장한다. 첫째, 스케줄 도출을 위한 시간적 여유가 충분한 환경(예: 긴 주기의 rolling horizon을 적용하는 시스템)에서는 해의 품질이 상대적으로 더 우수한 DPHA의 적용이 적합하다. 반면, 짧은 주기의 rolling horizon 하에서 스케줄을 빈번하게 갱신해야 하거나, 단일 서버에서 다수의 로봇 셀 스케줄을 동시다발적으로 처리해야 하는 등 신속한 연산이 요구되는 환경에서는 HBS의 사용을 권장한다.

5. 결 론

최근 제조 산업이 다품종 소량 생산 체제로 전환됨에 따라, 이종 작업들이 투입되는 자동화 제조 시스템의 비주기적 스케줄링의 중요성이 대두되고 있다. 본 연구에서는 고가의 정밀 제조 공정에서 널리 사용되는 양팔 로봇 셀을 대상으로 makespan을 최소화하기 위한 효율적인 휴리스틱 스케줄링 알고리즘을 제안하였다.

탐색 공간이 기하급수적으로 팽창하여 대규모 문제에서 합리적인 시간 내에 최적해 도출이 어려운 기존 방법론의 한계를 극복하기 위해, 지배속성을 전략적으로 완화한 DPHA와 탐색 트리의 폭을 유망한 노드 위주로 제한하는 빔서치 기반의 HBS 알고리즘을 제안하였다. 계산 실험 결과, 제안된 휴리스틱 알고리즘들은 다양한 시나리오 하에서 평균 4% 이내의 오차율을 보이며, 합리적인 연산 시간 내에 우수한 해를 도출할 수 있음을 입증하였다. 반면, 이러한 우수한 성능에도 불구하고 본 연구의 접근법은 몇 가지 한계를 가진다. 제안된 휴리스틱 기법들이 양팔 로봇 셀 스케줄링에 특화된 최적 알고리즘의 탐색 논리를 기반으로 설계되었기에, 이를 일반화하여 다양한 구조의 유연한 생산시스템에 적용하기 위해서는 추가적인 연구와 노력이 요구된다.

향후 연구로는 재진입 공정(reentrant flows), 병렬 설비(parallel machines), 다중 로봇(multiple robots) 등보다 복잡한 스케줄링 요구사항을 갖는 시스템으로의 확장을 고려해 볼 수 있다. 또한, 본 연구에서는 기존에 제안된 최적 알고리즘에 기반하여 휴리스틱 알고리즘을 설계하였지만, 메타휴리스틱(metaheuristic) 또는 강화학습(reinforcement learning) 등의 보다 범용적인 기법을 활용하는 접근도 유의미한 후속 연구가 될 것이다.