1. 서 론

최근 규모의 경제 효과를 지향하는 소품종 대량생산 설비 또는 유연성, 고객대응과 같은 성과목표가 중요시되는 다품종 소량생산 설비를 포함한 제조 공정에서 생산 효율성 증대에 대한 기술적 요구가 발생하고 있다. 특히 흐름 생산 공정은 일련의 m개의 기계에서 n개의 작업이 처리되는 NP-hard 문제로써 전자, 종이 및 섬유 산업, 콘크리트 생산, 사진 필름 제조 산업 등의 일반적인 제조환경뿐만 아니라 인터넷 서비스, 컨테이너 처리 시스템 및 토목 같은 비제조 분야에서도 활용되고 있다⁽¹⁾. 이렇게 다양한 제조환경에서 요구사항 또한 다양하므로 흐름 생산 공정이나 개별 작업 생산 공정의 작업 일정을 최적화하는 생산 일정 연구가 분야별로 활발히 진행되고 있다[2-5, 10-22].

최초의 흐름 생산 공정 문제⁽²⁾에서는 단일 기계 및 두 대의 기계에 대한 최적의 일정 계획을 도출하는 제한적인 분기한정법 기반의 해결방법을 이용하였다. 이후 제한된 개수의 기계와 작업에서 최종 공정시간을 목적함수로 하여 최적의 작업 일정을 도출하는 분기한정법 기반 해결방법이 지속적으로 연구되었다. 하지만 분기한정법 기반의 해결방법은 제한적인 상황에서 동작하여 복잡한 흐름 생산 공정문제를 해결할 수 없고, 단일 목적함수를 기반으로 동작한다는 한계가 존재한다⁽³⁾.

분기한정법 알고리즘의 한계를 극복하기 위해 합리적인 시간 내에 근사해를 도출하는 다양한 휴리스틱과 메타 휴리스틱 기반 해결방법이 연구되었다^(4-5). Framinan⁽¹⁰⁾은 흐름 생산 공정문제에 대해 NEH 휴리스틱⁽¹¹⁾을 기반으로 하는 휴리스틱 알고리즘을 제안하여 공정시간을 최소화했다. Ancau⁽¹²⁾는 α-탐욕 선택을 기반으로 하는 휴리스틱 기법과 확률 분포를 통한 선택기법을 제안하였다. 특히 Simulated Annealing(SA), Tabu Search(TS), Genetic Algorithm(GA)과 같은 메타 휴리스틱 접근 방식이 조합 최적화 문제를 해결하는 데 우수한 성능을 보여주었으며, 위와 같은 방식을 기반으로 한 방법이 생산 공정 문제에도 적용되었다. Yamada⁽¹³⁾은 GA, SA 및 TS를 흐름 생산 문제 및 개별생산 문제에 적용했으며, 메타 휴리스틱 기법의 가능성을 보였다. Ling Wang⁽¹⁴⁾은 제한된 버퍼를 사용하는 흐름 상점 스케줄링을 위한 하이브리드 유전 알고리즘(HGA)을 제안하였으며, SA 및 TS의 결과와 비교하여 유전 알고리즘의 유효성을 입증하였다. ⁽¹⁵⁾의 연구에서 전체 공정시간을 최소화하기 위한 SA 알고리즘을 설계하였으며, 서로 다른 매개 변수 설정을 사용하여 다중 목적함수 알고리즘을 제안하였다. 이처럼 흐름 생산 공정에 메타 휴리스틱을 적용한 많은 연구가 진행됐다^(15-22).

지금까지 연구되어 온 휴리스틱 및 메타 휴리스틱 기법들은 일반적으로 초기의 작업 일정 결과를 토대로 개선된 작업 일정을 직접 탐색한다. 기존의 기법들은 비교적 간단한 작업에서는 우수한 결과를 보이긴 하지만, 복잡한 다품종 생산 작업에서는 최적의 작업 순열을 찾는 방향으로 알고리즘을 수렴시키기 어려운 한계가 존재한다.

반면, 강화학습 기반의 흐름 생산 공정 최적화 방법은 일정 계획 정책을 탐색할 뿐만 아니라 $Q$ 함수의 정책을 조정하여 대규모 생산 작업상에서의 문제를 효율적으로 해결할 수 있다. 학습 과정에서 에이전트는 초기 탐색과정을 거친 후 $Q$ 함수를 이용해 예측되는 미래 보상을 기반으로 한 작업 순열을 도출하며 보상을 받는 과정을 반복한다. 학습이 진행되면서 에이전트는 현재 작업 상태에서 미래에 예상되는 누적 공정시간을 최소화하는 최적의 정책을 학습한다. Stefan⁽²³⁾의 연구에서 흐름 생산 공정문제를 강화학습으로 해결하는 알고리즘이 처음으로 제안되었으며, 5개의 기계와 6개의 작업에서 최적해를 찾는 방식이 설명되었다. 이후 Reyna⁽²⁴⁾는 강화학습 알고리즘에 사용되는 파라미터에 따른 알고리즘의 성능을 분석했다. 또한, Zhang⁽²⁵⁾은 32개의 인스턴스와 다양한 규모의 흐름 생산 공정 문제를 포함하는 Taillard⁽²⁶⁾ 벤치마크 데이터셋을 기준으로 강화학습 기반 알고리즘을 적용하여 최적해 도출에 우수한 성능을 보였다. Lee⁽²⁷⁾는 두 가지 부품이 처리되는 로봇 흐름 생산 공정에 Q-learning 기반 공정 최적화 기법을 적용하여 일반적으로 공정 최적화에 사용되는 RS(Reverse Sequence)기법보다 우수한 성능을 보였다. 현재까지 제시된 강화학습 및 Q-learning 기반 흐름 생산 공정 알고리즘은 최종 공정시간을 최소화하기 위해 강화학습 기법의 적용을 시도해왔으나 기존의 휴리스틱 기반 알고리즘들보다 우수한 최종 공정시간 최소화 성능을 보장하지 못하였다.

이 논문은 다양한 흐름 생산 공정 상황에 대해 최종 공정시간을 최소화할 수 있는 DDQL(Dueling Double Q-learning) 기반 흐름 생산 스케줄링 기법을 제안한다. DDQL 방식은 기존의 Q-learning과 달리 다음 상태의 최대 $Q$ 값을 가진 최상의 동작을 선택하기 위한 $Q$ 함수와 앞서 선택한 행동에 따른 기댓값 $Q$ 값을 계산하기 위한 $Q$ 함수를 둘 다 사용하여 편향이 없는 학습 환경을 제공하고, 이득 함수 $A$를 도입하여 가치함수의 분산을 감소시킴으로써 일반화 성능을 높일 수 있는 장점이 있다. 그러므로 DDQL 방식을 흐름 생산 공정문제에 적용하면 기존 강화학습의 과추정 및 불필요한 정책학습 문제를 해결하여 궁극적으로 최종 공정시간의 최소화를 보장할 수 있다. 본 연구에서 활용하는 두 개의 $Q$ 함수와 $A$ 함수는 일반적인 Q-learning 기반 알고리즘에서 에이전트가 획득한 보상에 따른 가치함수의 갱신 과정에서 적용된다. 상태-행동 함수를 학습하기 위한 목적함수는 에이전트가 도출한 작업 순열의 최종 공정시간으로 정의되었다. 제안된 기법의 성능을 Carlier ⁽²⁸⁾와 Reeves⁽²⁹⁾ 벤치마크 데이터에 대해 검증한 결과 기존 강화학습 기반 알고리즘 대비 최고 상대 오차 성능은 17%, 평균 상대 오차 성능은 22%의 성능 개선을 보였다. 또한, Taillard ⁽²⁶⁾벤치마크 데이터에 대해 최종공정시간 성능을 비교한 결과 다양한 규모의 공정상황에서 최적의 공정시간 결과를 나타내었으며, 특히, 큰 규모의 공정상황에서는 기존의 휴리스틱 알고리즘들의 결과 중 최소 공정시간 대비 18%의 성능 개선을 보였다.

2. 문제 정의

흐름 생산 공정 환경은 그림 1과 같이 $m$개의 기계와 $n$개의 작업으로 구성되며, 각 작업은 서로 다른 기계에서 실행되는 $m$개의 작업 세트 $pt_{jk,\:ih}=(pt_{j_{1,\:}i_{1}},\:...pt_{j_{n,\:}i_{m}})\in M$으로 구성된다. 여기서 서로 다른 작업 간에 우선순위 제약은 존재하지 않는다고 가정한다. 작업 $j_{k},\: k=1,\:...,\:n$은 시스템에서 한 번만 실행할 수 있고, 기계 $i_{h},\: h=1,\:...,\:m$은 한 번에 하나의 작업만을 수행할 수 있다. 작업 $j$가 각 기계 $i$에서 처리되며 걸리는 시간을 $pt_{j_{k},\:i_{h}}$로 표현한다. 각 작업은 기계 $i_{1}$부터 $i_{m}$까지 순서대로 실행되고 기계에 따라 각 작업의 처리 시간이 다르다. 각 작업의 처리 시간에는 기계의 설정과 실행 시간이 포함되고, 시작 시각은 0이라고 가정한다. $c(j_{k},\:i_{h})$는 기계 $i_{h}$에서 수행한 작업 $j_{k}$의 처리 완료 시간을 나타낸다. 흐름 생산 공정 문제의 작업 처리 완료 시간을 구하는 일련의 과정을 수식으로 표현하면 다음과 같다.

수식(1)은 첫 번째 기계의 첫 번째 작업이 종료되는 시간 $c(j_{1},\: i_{1})$을 나타낸다. 수식(2)는 첫 번째 작업이 다음 기계들 에서 처리되어 완료되는 시간을 나타낸다. 수식(3)은 첫 번째 기계에서 각각의 작업이 처리되어 완료되는 시간을 나타낸다. 수식(4)는 각각의 기계에서 수행되는 작업의 처리 완료 시간을 구하는 수식을 나타낸다. 수식(4)에서 수행되는 최댓값 (max) 연산은 기계 $i_{h}$가 현재 수행하고 있는 작업의 처리 시간과 이전 기계 $i_{h-1}$가 수행하고 있는 작업의 처리 시간 중 오래 걸리는 작업이 먼저 종료된 후 다음 작업이 처리된다는 것을 의미한다. 이때 기계 $i_{h}$에서 작업이 지연되는 유휴시간이 발생하므로 이를 최소화하기 위한 적절한 공정 순서를 선택해야 한다.

흐름 생산 공정 문제의 목적은 마지막 기계에서 마지막 작업의 완료 시간으로 정의되는 $c(j_{m},\: i_{n})$을 최소화하는 순열을 찾는 것이다. 본 연구에서 제안하는 기법의 공정한 성능평가를 위해 위에서 언급한 문제 정의는 [22, 30-34, 40-42]에서 제안한 문제와 같게 설정되었다.

3. 강화학습 기반 흐름 생산 공정 최적화 기법

흐름 생산 공정 문제를 Markov decision process로 표현하면 주어진 작업 상태의 집합 $S$, 상태에서 수행할 수 있는 행동의 집합 $A$, 특정 상태 $s_{t}$, 특정 상태 $s_{t}$에서 에이전트가 취한 행동 $a_{t}$, 에이전트의 상태에 따른 행동이 명시된 정책 $\pi(s_{t})$에 따라 얻게 되는 즉각적인 보상을 $r(s_{t},\:a_{t})$로 표현할 수 있다. 상태 $s_{t}$는 에이전트에 의해 선택된 흐름 생산 공정 작업을 뜻하고 이는 섹션 2에서 설명한 바와 같이 기계들이 수행해야 하는 하나의 작업을 의미한다. 여기서 $t$는 상태와 행동에 따른 시간 단위를 나타낸다. 행동 $a_{t}$란 에이전트가 지금까지 수행된 작업을 제외하고 나머지 작업 중에서 다음 작업을 선택하는 것으로 정의한다. 즉각적인 보상은 주어진 상태 $s_{t}$에서 에이전트는 정책 $\pi$에 따라 작업을 선택하는 행동 $a_{t}$를 수행한 다음, 새로운 상태 $s_{t+1}$과 즉각적 보상 $r(s_{t},\: a_{t})$를 받는다.

흐름 생산 공정 문제 에이전트의 목표는 예측되는 미래 보상 $R_{t}=\sum_{i=0}^{t}\gamma^{t}r(s_{i},\:a_{i})$를 최소화하는 것이다. 여기서 $\gamma$는 미래 보상에 대한 할인율을 나타낸다. 일련의 Markov decision process에서 벨만 방정식을 만족시키는 상태-행동 가치함수 $Q$는 다음과 같이 정의할 수 있다.

수식(5)에서 함숫값은 주어진 상태 $s$에서 행동 $a$를 한 후 얻을 수 있는 누적보상의 기댓값이 된다. 예측되는 누적보상을 최소화하는 $\pi *$에 대한 상태-행동 가치함수를 다음과 같이 정의할 수 있다.

일반적인 강화학습과는 달리 최종 공정시간을 최소화해야 하므로 $Q$ 함수의 누적보상 기댓값 역시 최소가 되도록 정책을 학습한다. 예측되는 누적보상을 최소화하는 정책 $\pi *$를 만족하면 상태 가치함수 $V$ 또한, 모든 상태 $S$에 대해 가장 작아지게 되므로 다음과 같이 수식으로 표현할 수 있다.

즉, 에이전트의 학습 목표는 예측되는 누적보상을 최소화하는 정책 $\pi *$을 찾는 것이다. 에이전트의 보상체계는 현재 작업 $s_{t}$에서 다음 작업을 수행할 때 발생하는 기계의 유휴시간 $r(s_{t},\:a_{t})= Id\le time(s_{t,\:}s_{t+1})$를 즉각적인 보상으로 받는다. 여기서 $Id\le time$은 현재 작업 $s_{t}$와 다음 작업 $s_{t+1 }$간에 발생하는 기계의 유휴시간을 연산한다.

그림 2는 Q-Learning 기반 흐름 생산 공정의 일반적인 절차를 나타내는 블록도를 나타낸다. 상태-행동 가치함수 $Q$ 및 상태 가치함수 $V$ 는 각각의 기계에서 수행되는 작업에 대한 미래에 예측되는 보상 정보를 담고 있다. 가치함수 $Q$ 와 $V$ 는 학습 초기 탐색과정에서 발생하는 에이전트 행동의 편향을 방지하기 위해 정규분포 난수 값으로 초기화된다. 입력 데이터는 각 기계에서 수행되는 작업 종류 및 각 작업의 수행 시간이 포함되어 있다. 이 정보들을 활용해 사용자가 사전에 설정한 epoch 횟수만큼 서로 다른 강화학습 에이전트를 통해 학습하게 된다. 단일 에이전트 기반의 강화학습은 학습 초기 탐색과정에서 편향된 학습이 수행되어 지역 최저점에 머무를 가능성이 있으므로, 여러 개의 에이전트를 학습함으로써 가장 낮은 목적함수를 도출하는 에이전트의 가치함수를 기반으로 최종 작업 순열을 결정할 수 있도록 설계하였다. 선택된 가치함수 $Q$와 $V$를 이용하여 Permutation algorithm을 통해 최적의 작업 순열이 결정된다.

알고리즘 1은 에이전트의 학습 과정에서 permutation algorithm 과정을 나타낸다. 알고리즘은 가치함수 $Q,\: V$ 및 $\epsilon$파라미터를 입력으로 완성된 최종 작업 순열 $p$를 반환한다. 가치함수가 수렴하지 못한 학습 초기에는 $\epsilon$값과 0과 1 사이의 무작위 난수를 비교하여 $\epsilon$값이 크면 무작위로 다음 작업을 결정한다. $\epsilon$값이 작으면 $Q$ 함수에서 가장 낮은 예측 보상 값을 갖는 작업을 다음 작업으로 결정한다. 만약 가치함수에 의해 첫 작업이 결정될 경우 최적의 작업 순열 완성을 보장하기 위해 $V$ 함수에서 가장 낮은 상태 가치를 갖는 작업을 첫 번째 작업으로 선택한다. 최종 작업 순열에 포함된 작업은 중복 선택을 피하고자 $Q$ 함수에서 선택된 작업에 해당하는 예측 보상 값을 매우 큰 값 ($l\arg e N UM$)으로 변경한다. 일련의 작업 순열을 결정하는 과정을 반복하며 $Q$ 함수와 $V$ 함수를 갱신하는 과정을 거친다.

그림 3은 섹션 2의 문제 정의에서 설명한 작업 순열에 따른 최종 공정시간 연산방법을 그림으로 나타낸 것이다. 위의 그림에서의 예는 3개의 작업을 4개의 기계에서 수행하는 흐름 생산 공정의 예시이다. 예를 들어 $pt_{22}$에서 수행되는 작업의 예상 종료 시각 $c_{22}$는 $2^{nd}ma\chi ne$이 수행한 이전 작업 $pt_{12}$가 종료되는 시점 $c_{12}$과 $1_{st}ma\chi ne$이 수행한 작업 $pt_{21}$이 종료되는 시점 $c_{21}$을 비교했을 때 큰 값과 수행할 작업 $pt_{22}$의 합으로 결정된다.

그림 3에서 표현된 공정시간 연산방법을 기반으로 현재 작업에서 다음 작업을 수행할 때 발생하는 기계의 유휴시간을 구하는 방법을 수식으로 표현하면 다음과 같다.

수식(8)에서 $i$는 작업을 수행해야 하는 기계의 총 개수이다. 수식(8)으로 즉각적인 보상으로 주어지는 기계의 유휴시간을 연산하여 상태-행동 가치함수 $Q$ 와 상태 가치함수 $V$ 를 갱신한다. 반환된 작업 순열의 유휴시간 보상에 따른 $Q$ 함수의 학습은 다음과 같은 수식으로 표현할 수 있다.

수식(9)에서 $j_{k}$는 시간차 오차 학습을 사용한 $Q$ 함수의 갱신방법에 따라 다음 상태 $j_{i}$에서 예상되는 누적보상을 최소화하는 다음 작업을 나타낸다. $Q$ 함수는 현재 상태의 작업에서 취할 수 있는 행동 $a$에 대한 누적보상의 합을 포함한 이차원 테이블 형태이다. $Q_{n+1}(j_{i},\:j_{j})$는 $j_{i}$작업에 대해 갱신된 예측 보상의 합을 의미한다. $Q_{n}(j_{i},\:j_{j})$는 $j_{i}$작업에 대한 갱신되기 이전의 누적된 예측 보상의 합이다. 여기서 $j_{j}$는 $j_{i}$ 작업에서 에이전트가 선택한 다음 작업을 나타낸다. 여기서 $\alpha$는 학습률을 나타내며 한 번의 학습에 갱신되는 보상 값의 크기를 결정하는 계수이다. $\min Q_{n}(j_{j},\:j_{k})-Q_{n}(j_{i},\:j_{j})$에서 $\min Q_{n}(j_{j},\:j_{k})$는 다음 상태의 작업 $j_{j}$에서 누적보상을 최소화하는 다음 작업 $j_{k}$를 수행할 때 예측되는 미래 보상을 나타내며, $Q_{n}(j_{i},\:j_{j})$과의 차를 통해 현재 예상되는 최적의 작업 순열 보상과 비교하여 기존의 예측 보상치를 갱신하게 된다. 이 논문에서는 공정시간을 최소화하는 정책을 학습하기 위해 $Q$ 함수는 최솟값 연산자를 사용하여 갱신된다.

상태 가치함수 $V$는 다음과 같이 수식으로 표현할 수 있다.

수식(10)의 $V$함수에는 개별 작업이 갖는 상태에 대한 가치가 포함되어 있다. 특정한 작업 상태 $j_{t}$에 대한 가치는 $j_{t}$에서 취할 수 있는 모든 행동 $a'$에 대한 예측 보상의 평균으로 결정되어 매번의 학습마다 갱신된다. 흐름 생산 공정 문제는 NP-hard 문제에 해당하지만 본 연구에서 고려하는 문제의 크기(벤치마크 데이터 기준 최대 500x20)가 심층 신경망을 사용할 만큼 복잡한 문제가 아니라고 판단하였으므로, 신경망 대신 테이블 형태의 $Q$와 $V$함수를 사용하였다.

4. DDQL 기반 흐름 생산 공정 최적화 기법

기존의 Q-learning을 기반으로 한 흐름 생산 공정 최적화 기법은 최적 정책에 따라서 에이전트는 오로지 최대 $Q$값에 의해 주어진 상태에서 최적이 아닌 행동을 하게 되는 경향이 보이는 과추정 문제를 일으킨다. 이는 추정된 $Q$ 값의 노이즈에 의해 발생하는데, 이는 실제 $Q$ 함수를 갱신하는 과정에서 높은 편향을 유발하게 되고 학습 과정도 함께 복잡해지게 된다. 또한, 기존의 Q-learning은 상태함수 $V$ 가 낮은 상황에 대해서도 보상을 계산하기 때문에, 이는 결론적으로 $Q$ 함수의 분산이 커지게 하고 연산량이 많아지게 된다. 이로 인해 흐름 생산 공정 최종시간이 다양한 공정 상황에서 기존 기법들과 비교해 좋은 성능을 보장할 수 없게 된다.

이 논문에서는 이러한 문제들을 해결하기 위해 에이전트가 $Q$ 함수를 학습하는 과정에 DDQL 기법을 적용하여 흐름 생산 공정에서의 최종 공정시간을 최소화할 수 있도록 하였다.

5. 실험 및 결과

본 연구에서 제안하는 DDQL기반 흐름 생산 스케줄링 기법의 최종 공정시간 성능을 다양한 공정 환경에 대해 평가한다. 이를 위해 ordinary Q-learning, double Q-learning, DDQL을 이용했을 때의 성능을 비교하였고, 최근까지 발표된 흐름 생산 공정 스케줄링 기법들인 L-HDE ⁽³⁰⁾, ODDE⁽³¹⁾, DBA ⁽³²⁾, HBSA⁽³³⁾, PSOVNS ⁽³⁴⁾, PSOMA ⁽³⁵⁾, HTLBO ⁽³⁶⁾, QDEA ⁽³⁷⁾, HGA⁽³⁸⁾, HBA ⁽³⁹⁾, HCS ⁽⁴⁰⁾, HWA ⁽⁴¹⁾의 기법들과 최종 공정시간 성능을 비교하였다. 다양한 공정 상황을 모의하기 위해 흐름 생산 공정 문제에 널리 활용되고 있고 다양한 공정상황에 대해 다룰 수 있는 총 세 가지의 벤치마크 데이터로 알고리즘의 공정 최적화 성능을 평가한다. Carlier⁽²⁸⁾와 Rec⁽²⁹⁾에서 제시하는 벤치마크 데이터는 각각 8개, 21개의 문제로 구성되어 있다. Taillard⁽²⁶⁾에서 제시하는 벤치마크 데이터는 n개의 작업과 m개의 기계에 대해 nxm의 다양한 규모를 20x5, 20x10, 20x20, 50x5, 50x10, 50x20, 100x5, 100x10, 100x20, 200x10 및 500x20으로 정의한 흐름 생산 공정을 담고 있다. 제안된 알고리즘은 파이썬으로 구현되어 검증되었으며 시뮬레이션에 사용된 컴퓨터의 사양은 i7-8750H 2.20GHz CPU와 GTX 1060이 장착된 일반적인 노트북 환경에서 수행되었다.

6. 결 론

본 연구는 다양한 흐름 생산 공정 환경에서 최종 공정시간 최소화를 보장할 수 있는 DDQL 기반 흐름 생산 공정 최적화 알고리즘을 제안한다. 강화학습 에이전트가 $Q$ 함수를 갱신하는 과정에서 double Q-learning 및 Dueling 구조를 적용함으로써 기존의 휴리스틱 기반 스케줄링과 Q-learning 기반 공정 최적화에서 발생할 수 있는 $Q$ 함수 분산증가, 탐색 편향 등의 문제를 해결하였다.

다양한 흐름 생산 공정을 모의할 수 있는 Car 및 Rec 벤치마크 데이터를 이용한 실험 결과 기존 강화학습 기반 흐름 생산 공정 최적화 기법보다 BRE 성능은 17%, ARE 성능은 22% 개선된 결과를 확인할 수 있었다. 또한, Taillard 벤치마크 데이터 기준 알고리즘이 도출한 최적의 작업 순열에서 기존의 휴리스틱 알고리즘 대비 최종 공정시간이 최대 18% 개선된 결과를 확인할 수 있었다. 특히, DDQL 알고리즘의 $Q$ 함수 학습에 따른 일반화 성능 개선으로 공정 규모가 큰 상황에서 다른 흐름 생산 공정 최적화 알고리즘보다 압도적인 성능을 나타냈다. DDQL 기법을 실제 공정에 적용하면 작업 공정의 최적화를 통해 기계 유휴시간을 감소시켜 공정 유지비용 절감의 효과를 얻을 수 있다.