Mobile QR Code QR CODE : The Transactions of the Korean Institute of Electrical Engineers

  1. (Dept. of Information and Communication Engineering, Changwon National University, Korea.)



Reinforcement learning, Flow shop scheduling, Double Q-learning, Dueling architecture

1. 서 론

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

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

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

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

반면, 강화학습 기반의 흐름 생산 공정 최적화 방법은 일정 계획 정책을 탐색할 뿐만 아니라 $Q$ 함수의 정책을 조정하여 대규모 생산 작업상에서의 문제를 효율적으로 해결할 수 있다. 학습 과정에서 에이전트는 초기 탐색과정을 거친 후 $Q$ 함수를 이용해 예측되는 미래 보상을 기반으로 한 작업 순열을 도출하며 보상을 받는 과정을 반복한다. 학습이 진행되면서 에이전트는 현재 작업 상태에서 미래에 예상되는 누적 공정시간을 최소화하는 최적의 정책을 학습한다. Stefan(23)의 연구에서 흐름 생산 공정문제를 강화학습으로 해결하는 알고리즘이 처음으로 제안되었으며, 5개의 기계와 6개의 작업에서 최적해를 찾는 방식이 설명되었다. 이후 Reyna(24)는 강화학습 알고리즘에 사용되는 파라미터에 따른 알고리즘의 성능을 분석했다. 또한, Zhang(25)은 32개의 인스턴스와 다양한 규모의 흐름 생산 공정 문제를 포함하는 Taillard(26) 벤치마크 데이터셋을 기준으로 강화학습 기반 알고리즘을 적용하여 최적해 도출에 우수한 성능을 보였다. Lee(27)는 두 가지 부품이 처리되는 로봇 흐름 생산 공정에 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 (28)와 Reeves(29) 벤치마크 데이터에 대해 검증한 결과 기존 강화학습 기반 알고리즘 대비 최고 상대 오차 성능은 17%, 평균 상대 오차 성능은 22%의 성능 개선을 보였다. 또한, Taillard (26)벤치마크 데이터에 대해 최종공정시간 성능을 비교한 결과 다양한 규모의 공정상황에서 최적의 공정시간 결과를 나타내었으며, 특히, 큰 규모의 공정상황에서는 기존의 휴리스틱 알고리즘들의 결과 중 최소 공정시간 대비 18%의 성능 개선을 보였다.

그림. 1. 흐름 생산 공정 문제 예시 ($m=4,\:n=3$)

Fig. 1. Example of flow shop scheduling problem ($m=4,\:n=3$)

../../Resources/kiee/KIEE.2021.70.10.1497/fig1.png

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})=pt_{j_{1},\:i_{1}},\:k=1,\:h=1$

(2)
$c(j_{1},\:i_{h})=c(j_{1},\:i_{h-1})+pt_{j_{1},\:i_{h}},\:h=2,\:...m$

(3)
$c(j_{k},\:i_{1})=c(j_{k-1},\:i_{1})+pt_{j_{k},\:i_{1}},\:k=2,\:...n$

(4)
$c(j_{k},\:i_{h})=\max(c(j_{k-1},\:i_{h}),\:c(j_{k},\:i_{h-1}))+pt_{j_{k},\:i_{h}}$ $k=2,\:...n,\:h=2,\:...m$

수식(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)
$Q_{\pi}(s ,\:a)=E_{\pi}[R_{t}|S_{t}=s ,\: A_{t}=a]$

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

(6)
$Q^{*}(s,\:a)=\min Q_{\pi}(s,\:a)=\min E_{\pi}[R_{t}|S_{t}=s,\:A_{t}=a]$

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

(7)
$V^{*}(s)=\min V_{\pi}(s)=\min E_{\pi}[R_{t}|S_{t}=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을 통해 최적의 작업 순열이 결정된다.

그림. 2. Q-learning 기반 흐름 생산 공정 블록도

Fig. 2. Block diagram of Q-learning based flow shop scheduling

../../Resources/kiee/KIEE.2021.70.10.1497/fig2.png

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

알고리즘 1 Permutation algorithm

Algorithm 1 Permutation algorithm for the work sequence

../../Resources/kiee/KIEE.2021.70.10.1497/alg1.png

그림. 3. 작업 순열에 따른 공정시간 연산방법

Fig. 3. Calculation of processing time based on the work sequence

../../Resources/kiee/KIEE.2021.70.10.1497/fig3.png

그림 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)
$0\le c_{t+1,\:n}-c_{t,\:n+1},\:\sum_{n=1}^{i}c_{t+1,\:n}-c_{t,\:n+1}=Id\le time(j_{t},\:j_{t+1})$

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

(9)
$Q_{n+1}\left(j_{i},\:j_{j}\right)=Q_{n}\left(j_{i},\:j_{j}\right)+\alpha\left(r+\gamma\min Q_{n}\left(j_{j},\:j_{k}\right)-Q_{n}\left(j_{i},\:j_{j}\right)\right)$

수식(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})=E[Q(j_{t},\:a')|S_{t}=j_{t}]$

수식(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 기법을 적용하여 흐름 생산 공정에서의 최종 공정시간을 최소화할 수 있도록 하였다.

4.1 Double Q-learning

앞서 언급했듯이 Q-learning에서는 최대 $Q$ 값만을 고려해 행동을 선택하고 $Q$ 함수를 갱신하게 되는데, 이는 $Q$ 함수의 노이즈로 인한 과추정 문제를 일으킬 수 있다. 이 문제를 해결하기 위해 두 개의 상태-행동 가치함수 $Q$ 와 $Q_{t\arg}et$을 동시에 활용하는 Double Q-learning 방법을 적용한다. $Q$ 함수는 다음 상태의 최대 $Q$ 값을 가질 수 있는 최선의 행동을 선택하기 위한 것이고, $Q_{t\arg}et$함수는 선택된 행동을 사용하여 $Q$ 기댓값을 계산하기 위한 것이다. 즉, $Q_{t\arg}et$에서 얻은 기댓값을 이용해 $Q$ 함수의 갱신을 수행한다. 이를 통해 두 함수중에서 잡음이 포함되어 있다 할지라도, 그들의 잡음은 uniform distribution형태로 나타나므로 $Q$ 값 갱신 과정에서 생길 수 있는 과추정 문제를 해결해줄 수 있다. 여기서 $Q_{t\arg}et$함수는 주기적으로 $Q$함수의 값으로 동일하게 설정된다. 두 개의 상태-행동 가치함수 $Q$와 $Q_{t\arg}et$를 동시에 활용하는 Double Q-learning을 기반으로 한 $Q$ 함수 갱신 과정을 수식으로 표현하면 다음과 같다. (8)

(11)
$Q_{n+1}(j_{i},\:j_{j})=Q_{n}(j_{i},\:j_{j})+$ $\alpha(r+\gamma Q_{n}(j_{i},\:\arg\min Q_{t\arg et}(j_{j},\:j_{k}))-Q_{n}(j_{i},\:j_{j}))$

수식(11)에서 볼 수 있듯이 $Q_{t\arg}et$을 $Q$ 함수 갱신 과정에 도입함으로써 최적의 행동을 선택하는 과정과 정책 자체를 평가하는 과정을 나눌 수 있고, 이를 통해 $Q$ 함수의 노이즈 문제로 인한 과추정 문제를 해결할 수 있다. 흐름 생산 공정 과정에서 편향된 행동 선택을 방지하게 함으로써 보다 안정적인 학습이 가능하게 되고 궁극적으로 최적의 흐름 생산 공정 솔루션을 얻을 수 있다.

4.2 Dueling Architecture

Dueling 구조는 $Q$ 값을 구하기 전에 가치함수 $V$ 와 이득 함수 $A$ 로 나누어 결괏값을 얻은 후 다시 합쳐지는 형태이다. 여기서 $A$ 는 행동별로 계산되는데 이는 총 누적되는 보상 값에는 연관이 없으므로, Dueling 구조를 통해 에이전트는 결론적으로 높은 가치함수 $V$ 값이 이끄는 상태로 최대한 가려고 하고, 낮은 가치함수 $V$ 값을 주는 행동을 피하도록 학습이 수행된다. 이를 통해 학습 과정에서 발생할 수 있는 불필요한 연산을 방지하고 $Q$ 함수의 분산이 감소하여 더욱 안정적인 학습을 가능하게 한다. Dueling 구조에서의 $Q$ 함수는 다음과 같이 표현할 수 있다. (9)

(12)
$Q(s,\:a)=V(s)+\left(A(s,\:a)-\dfrac{1}{| A |}\Sigma A(s,\:a')\right)$

수식(12)에서 $V(s)$는 모든 작업에 대한 상태 가치를 포함하며, $A(s,\:a)$는 $Q$ 함수에 존재하는 행동의 가치 값을 포함한다. $1/|A|∑A(s,\:a')$는 어떤 상태 $s$에서 선택할 수 있는 행동 $a'$들에 대한 예측 보상 합의 평균이고, 이 성분은 $Q$ 함수에서 최적의 행동이 취해졌을 때 A의 값을 0으로 만들어주므로 분산을 감소시켜 기존의 강화학습 기법보다 $Q$ 함수의 일반화 성능을 개선할 수 있다.

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

앞서 설명한 double Q-learning과 Dueling 구조를 둘 다 사용하는 DDQL 기법은 각각의 장점을 통합하여 흐름 생산 공정에 대한 최적화 솔루션을 제공할 수 있다. DDQL 기법은 알고리즘 1의 Permutation 과정이 수행되어 보상을 얻은 다음 그림 1의 상태-가치함수의 갱신방법에 적용할 수 있다. DDQL 기법을 이용해 $Q$ 함수를 갱신하기 위해서는 먼저 이득 함수 $A$ 와 상태 가치함수 $V$ 로 쪼개어 계산 후 통합하는 과정을 거치게 된다. 그다음 최적의 행동을 선택하는 $Q$ 함수와 정책 자체를 평가하는 $Q_{t\arg}et$함수를 동시에 고려하여 $Q$ 함수의 갱신이 수행된다. 이를 통해 기존의 강화학습 기법보다 낮은 분산과 편향의 가치함수를 갖는 에이전트의 학습이 가능하여 최적의 흐름 생산 공정 솔루션을 제공할 수 있다.

5. 실험 및 결과

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

표 1. 강화학습 알고리즘의 매개 변수

Table 1. Parameters of reinforcement learning algorithm

Parameter

Value

Learning Rate

0.1

Discount Factor

0.8

Epoch

50

Loop

100,000

$Q_{target}$ Update Period

50

5.1 학습방법

DDQL이 적용된 강화학습 기반 흐름 생산 공정 최적화 알고리즘 에이전트의 학습 매개 변수는 표 1에 나타내었다. 강화학습 에이전트는 100,000번의 반복 작업을 수행하면서 총 50회의 epoch를 거친 최적의 가치함수에 의한 작업 순열을 도출한 결과로 성능이 검증된다. 이때 한 번의 epoch가 완료되면 에이전트의 가치함수는 초기화되어 새로운 학습을 수행하도록 설정하였는데, 이는 탐색과정에서 발생할 수 있는 편향을 방지하고 다양하게 학습된 에이전트 중에서 가장 우수한 성능을 보이는 에이전트를 식별하기 위함이다.검증용 가치함수 $Q_{t\arg}et$의 갱신주기는 50회로 설정되어 주기마다 $Q$ 값으로 갱신한다.

100,000번의 반복되는 학습 과정에서 에이전트가 도출해낸 보상 그래프를 그림 4에 나타내었다. 표 1에 나타낸 벤치마크 데이터의 problem 중 rec33을 기준으로 제안된 DDQL 알고리즘 에이전트의 학습에 따른 보상을 확인하였다. 여기서 MVA(1000)은 에이전트가 1000번의 학습 동안 발생한 보상의 평균을 나타낸다. 그림 4를 통해 알 수 있듯이 제안된 강화학습 알고리즘으로 학습된 에이전트가 초기 탐색과정을 거치며 보상을 최소화하는 방향으로 점차 수렴하는 모습을 확인할 수 있다. 이를 통해 흐름생산 공정에 대한 학습을 위해 정해진 보상이 적절히 설정되었고, DDQL 강화학습 에이전트가 보상을 최소화하는 방향으로 학습을 원활히 수행했음을 확인할 수 있다. 대략 30,000회의 학습 때 최소지점을 거쳐 학습 후반으로 갈수록 보상이 약간 증가하는 것을 확인할 수 있는데 이는 학습이 진행될수록 강화학습 에이전트가 $Q$ 함수의 갱신 과정에서 과적합 되기 때문이다. 이 점을 고려하여 본 연구에서는 학습과정에서 에이전트에 반환된 보상 값 중 최저지점을 선택하여 강화학습 알고리즘의 성능 검증을 수행하였다.

그림 5에서는 서로 다른 강화학습 알고리즘(Q-learning, double Q-learning 및 DDQL)으로 학습된 에이전트가 도출해낸 최종 공정시간의 분포도를 Boxplot으로 나타내었다. 그림에서 알 수 있듯이 DDQL기법이 Q-learning과 DoubleQ 보다 상한과 하한의 폭이 좁고 박스의 위치가 상대적으로 아래에 있는 것을 확인할 수 있다. 이는 두 개의 함수를 사용함으로써 탐색과정에서 발생하는 노이즈로 인한 과추정을 방지함과 동시에 이득 함수를 사용하여 상태 행동 가치함수의 분산을 감소시킨 Dueling 구조에 기인한 결과이다. 이를 통해 DDQL 기법이 다른 기법들과 비교해 유휴시간 최소화를 통한 최소의 최종 공정시간을 제공할 수 있는 더 나은 방식임을 알 수 있다.

그림. 4. DDQL 에이전트의 학습에 따른 보상 분포

Fig. 4. Distribution of the reward of DDQL agent according to learning process

../../Resources/kiee/KIEE.2021.70.10.1497/fig4.png