기술 요약: 임계 경로 그래프 가이드 DRL 기반의 전송을 고려한 다목적 분산 유연 작업 숍 스케줄링

1. 문제 정의

본 논문은 **다목적 분산 유연 작업 숍 스케줄링 문제(MO-DFJSP)**를 다룬다. 이 문제는 고전적인 유연 작업 숍 스케줄링 문제(FJSP)를 지리적으로 분산된 여러 워크숍이 포함된 분산 제조 환경으로 확장한 것이다. 핵심 과제는 두 가지 상충하는 목적 함수를 동시에 최적화하는 것이다:

1. 메이크스팬 ($Z_1$): 모든 작업의 최대 완료 시간을 최소화함.
2. 총 에너지 소비량 ($Z_2$): 가공 에너지, 대기 에너지, 그리고 운송 에너지(워크숍 간 및 워크숍 내 운송 모두 포함)의 합계를 최소화함.

이 문제는 NP-hard 복잡성을 특징으로 하며, 기계 할당, 작업 순서 결정, 그리고 워크숍 간 작업물 전송에 관한 결정들이 서로 밀접하게 결합되어 있다. 본 논문은 기존의 진화 알고리즘들이 다음과 같은 두 가지 체계적 결함을 겪고 있다고 지적한다:

• 세대 내(Intra-generational): 변이 연산자가 스케줄링 구조(예: 임계 경로 및 병목 현상)를 인지하는 능력이 부족하여, 비병목 작업에 계산 자원을 낭비하는 무작위 섭동(random perturbations)을 초래함.
• 세대 간(Cross-generational): 인구 정체(population stagnation) 문제가 고정된 임계값 규칙으로 처리되어, 다차원 지표에 기반한 계층적 대응 메커니즘이 결여됨.

2. 방법론: HENSGA-DRL

저자들은 HENSGA-DRL을 제안하며, 이는 NSGA-II 프레임워크에 두 가지 새로운 구성 요소인 임계 경로 그래프 가이드 심층 강화 학습(CGDRL) 연산자와 다중 지표 상태 인식 계층적 개입(MSHI) 전략을 통합한 하이브리드 알고리즘이다.

2.1 기본 프레임워크: NSGA-II

알고리즘은 NSGA-II를 진화적 백본으로 사용하여, 수렴성과 다양성을 유지하기 위해 빠른 비지배 정렬(fast non-dominated sorting)과 정규화된 혼잡 거리(normalized crowding distance) 메커니즘을 채택한다. 염색체 인코딩은 기계 순서(MS)와 작업 순서(OS)를 포함하는 2층 벡터를 사용한다.

2.2 핵심 구성 요소 1: CGDRL 연산자

CGDRL 연산자는 무작위 섭동을 구조 가이드형 직접 최적화로 대체하기 위해 변이 단계에 삽입된다.

• 분리 그래프(Disjunctive Graph) 구축: 염색체는 노드가 작업을 나타내고 에지가 기술적 선행 관계(정적)와 기계 자원 경합(동적)을 나타내는 분리 그래프로 변환된다.
• 특징 추출: 그래프 합성곱 신경망(GCN)이 그래프를 인코딩하여 노드 수준의 특징을 추출하며, 이를 통해 로컬 기계 부하와 글로벌 임계 경로 레이아웃을 모두 포착한다.
• 병목 탐지: 멀티 헤드 어텐션(multi-head attention) 메커니즘은 글로벌 스케줄링 상태와의 연관성을 바탕으로 "병목" 작업(개선 가능성이 가장 높은 작업)을 식별한다.
• 정책 네트워크: 근사 정책 최적화(PPO) 에이전트는 병목 작업의 상태(노드 임베딩 + 정규화된 기계 부하)를 입력받아 직접적인 기계 재할당 결정을 출력한다.
• 보상 함수: 에이전트는 메이크스팬과 에너지 소비량에 대한 정규화된 개선율의 가중 합으로 정의된 보상 신호를 사용하여 학습되며, 이는 단일 목적 편향보다는 트레이드오프를 장려한다.

2.3 핵심 구성 요소 2: MSHI 전략

MSHI 전략은 인구 정체를 방지하기 위해 세대 전반에 걸쳐 인구 건강 상태를 관리한다.

• 엘리트 솔루션 아카이브 (ESA): 고품질 개입의 원천 역할을 하는 비지배 솔루션의 이력을 유지한다.
• 다중 지표 성능 추적기 (MPT): 하이퍼볼륨 변화율과 목적 공간의 다양성을 기반으로 종합적인 건강 점수($\Phi_t$)를 계산한다.
• 적응형 개입 메커니즘 (AIM): 정체 심각도에 따라 3단계 개입 시스템을 활성화한다:
  1. 1단계 (배경): 탐색에서 착취(exploitation)로 전환하기 위해 선형적으로 감소하는 동적 변이율 스케줄링을 수행한다.
  2. 2단계 (엘리트 주입): 완만한 정체 시 트리거되며, 현재 인구 중 최악의 개체들을 ESA의 다양한 엘리트 솔루션으로 교체한다.
  3. 3단계 (함정 탈출): 심각한 정체 시 트리거되며, 국소 최적해를 탈출하기 위해 일정 기간 동안 변이율을 강제로 높인다.

3. 주요 기여

본 논문은 세 가지 주요 기여를 명시한다:

1. 수학적 모델링: 가공, 대기, 운송 에너지를 명시적으로 고려하는 완전한 다목적 수학적 모델을 구축하여 알고리즘 설계의 통일된 형식적 기초를 제공한다.
2. CGDRL 연산자 설계: 분리 그래프 구조 인지와 PPO 정책 네트워크를 진화적 변이 연산자에 직접 통합하였다. 이를 통해 알고리즘은 단순한 무작위 섭동에 의존하는 대신, 스케줄링 토폴로지 병목을 인지하고 유전자 수정 과정에서 방향성 있는 결정을 내릴 수 있다.
3. MSHI 전략: 다차원 지표(하이퍼볼륨 및 다양성)에 의해 구동되는 계층적 개입 메커니즘을 제안하여 세대 간 인구 정체 문제를 해결하였으며, 이를 통해 세대 내 유전자 조작과 세대 간 상태 조절 사이의 시너지를 창출하였다.

4. 실험 결과

알고리즘은 분산 워크숍, 전송 시간 및 에너지 파라미터를 포함하도록 표준 LA 인스턴스를 확장한 자체 구축 벤치마크 데이터셋(DLA)에서 평가되었다(10~20개의 작업을 포함하는 20개 인스턴스).

• 절제 연구(Ablation Study): 전체 HENSGA-DRL과 변형 모델(CGDRL 또는 MSHI 제거) 간의 비교를 통해, CGDRL 연산자가 수렴 정확도의 주요 동력(변형 모델 대비 메이크스팬 약 6.4%, 에너지 약 5.5% 개선)이며, MSHI가 탐색 능력을 유지하는 데 필수적인 지원을 제공함을 입증하였다.
• 비교 연구: HENSGA-DRL을 최신 알고리즘인 MOEA/D, SPEA-II, HMOMA와 비교하였다.
  • 성능: HENSGA-DRL은 대다수의 인스턴스에서 메이크스팬과 총 에너지 소비량 모두에서 우수한 결과를 달了.
  • 지표: 일관되게 가장 높은 하이퍼볼륨(HV) 값을 획득하여 더 나은 수렴성과 다양성을 보여주었다.
  • 유의성: 윌콕슨 순위합 검정(Wilcoxon rank-sum tests)을 통해 세 가지 베이스라인 모델과 비교했을 때 개선 사항이 통계적으로 유의미함($p < 0.05$)을 확인하였다. 성능 격차는 HMOMA와 비교했을 때 가장 두드러졌다(메이크스팬 평균 14.8%, 에너지 평균 13.1% 개선).

5. 의의 및 주장

본 논문은 HENSGA-DRL이 기존 진화 방법론의 구체적인 한계를 해결함으로써 MO-DFJSP를 해결하는 데 있어 중요한 진전을 이루었다고 주장한다.

• 구조적 인지: 강화 학습이 하이퍼파라미터 튜닝에 국한되었던 이전 연구들과 달리, 본 논문은 구조적 인지(GCN을 통해)를 유전자 조작 과정에 성공적으로 내재화하였다. 이를 통해 알고리즘은 개선 가능성이 가장 높은 결정 차원에 집중하여 탐색 압력을 가할 수 있다.
• 계층적 대응: MSHI 전략은 고정된 임계값 규칙보다 더 정교한 접근 방식을 제공하며, 실시간 건강 모니터링을 통해 적절한 개입 수준을 트리거한다.
• 그린 제조: 분산 환경에서 메이크스팬과 함께 에너지 소비를 명시적으로 모델링하고 최적화함으로써, 지속 가능한 그린 제조 시스템으로의 전환을 지원한다.

저자들은 CGDRL 연산자와 MSHI 전략의 협력적 추진력이 복잡한 분산 다목적 스케줄링 문제의 고품질 파레토 프런트(Pareto front)를 효율적으로 근사할 수 있게 한다고 결론짓는다.