Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

이 논문은 유연 작업장 스케줄링 문제 (FJSP) 에 대해 이질적 불연속 그래프 표현, 메모리 강화 이질적 그래프 신경망, 그리고 병렬 탐욕 탐색 전략을 결합한 'MIStar'라는 새로운 프레임워크를 제안하여 기존 건설적 방법 및 전통적 휴리스틱보다 우수한 성능을 달성함을 보여줍니다.

핵심

🏭 배경: 혼란스러운 스마트 공장

4 차 산업혁명 시대에는 공장에서 주문이 쏟아져 들어옵니다. "이거 빨간색으로, 저거 큰 사이즈로"처럼 주문이 다르고, 기계도 여러 대가 있어서 어떤 기계가 어떤 작업을 할지 정하는 게 매우 복잡합니다. 이를 **'유연한 작업장 스케줄링 (FJSP)'**이라고 합니다.

기존의 인공지능 (AI) 은 **레고 블록을 하나씩 쌓아 올리는 방식 (구축 방식)**으로 해결책을 찾았습니다. 하지만 이 방법은 블록을 다 쌓고 나면 "아, 여기가 좀 비효율적이네?"라고 뒤늦게 깨닫는 경우가 많아서, 최적의 해답에 도달하기가 어렵습니다.

💡 이 연구의 핵심: "수정하는 전문가" (MIStar)

이 논문에서 제안한 MIStar는 처음부터 완벽하게 짓는 게 아니라, "이미 만들어진 집을 보고 고쳐서 더 좋게 만드는 (개선 방식)" 전문가입니다.

하지만 기존에 이 '고치기' 작업을 AI 에게 시키면 두 가지 큰 문제가 있었습니다.

1. 상황 파악 실패: 기계들이 지금 무엇을 하고 있는지, 어떤 순서로 일하는지 AI 가 제대로 이해하지 못함.
2. 망설임: 고칠 곳이 너무 많아서 (해결 공간이 너무 넓어서) 어디부터 고쳐야 할지 몰라 헤매거나, 작은 개선에만 만족하고 멈춰버림.

🚀 MIStar 가 해결한 3 가지 비밀 무기

이 연구는 이 문제를 해결하기 위해 세 가지 창의적인 방법을 썼습니다.

1. 🗺️ 새로운 지도 그리기 (이질적 그래프 표현)

기존의 지도는 기계와 작업의 관계를 복잡하게 그려서 AI 가 헷갈리게 했습니다.

• 비유: 마치 지하철 노선도에서 '역 (기계)'과 '열차 (작업)'를 따로 표시하지 않고 다 섞어놓은 것처럼요.
• MIStar 의 방법: 기계와 작업을 명확하게 구분하고, **"어떤 기계가 어떤 순서로 일하는지"**를 화살표로 깔끔하게 연결한 새로운 지도를 그렸습니다. 덕분에 AI 는 기계의 상태를 한눈에 파악할 수 있게 되었습니다.

2. 🧠 과거의 경험을 기억하는 메모리 (Memory-Enhanced)

AI 가 실수를 반복하거나 같은 길만 돌아다니는 것을 막기 위해 **'기억 장치'**를 달았습니다.

• 비유: 요리사가 실패한 레시피를 메모장에 적어두고, "어제 이걸 넣으니까 맛이 없었지, 오늘은 빼자"라고 생각하듯이요.
• MIStar 의 방법: AI 가 과거에 시도했던 해결책들을 간추려서 기억해 둡니다. 그리고 새로운 결정을 내릴 때, "어? 이 상황은 과거에 비슷했던 적이 있었네. 그때 어떤 선택이 좋았지?"라고 기억을 꺼내어 참고합니다. 이렇게 하면 같은 실수를 반복하지 않고 더 좋은 길을 찾을 수 있습니다.

3. ⚡ 여러 가지 시나리오를 한 번에 검토 (병렬 탐험)

기존 AI 는 "하나의 길만 골라서 가보고, 안 되면 다시 돌아와서 다른 길로 가"라고 했다면, MIStar 는 동시에 여러 길을 탐색합니다.

• 비유: 미로에서 길을 찾을 때, 한 명만 나가서 실패하면 다시 들어오는 게 아니라, 50 명의 탐험대를 동시에 보내서 가장 빠른 길을 가진 팀의 결과를 선택하는 것과 같습니다.
• MIStar 의 방법: 한 번에 여러 가지 개선 방법을 시도해 보고, 그중에서 가장 효과가 좋은 것만 골라 적용합니다. 덕분에 훨씬 적은 시간 안에 더 좋은 결과를 얻습니다.

🏆 결과: 왜 이것이 대단한가요?

이 방법을 실험해 보니, 기존의 수동적인 규칙을 따르는 방법이나 다른 AI 방법들보다 더 빠르고 더 좋은 결과를 냈습니다.

• 작은 문제: 아주 빠르게 최적의 답을 찾았습니다.
• 거대한 문제: 기존 AI 는 답을 찾지 못하거나 (실패), 하루 종일 계산해야 했던 거대한 공장 문제에서도 MIStar 는 10 분도 안 되어 훌륭한 답을 찾아냈습니다.

📝 한 줄 요약

"MIStar 는 공장의 복잡한 상황을 새로운 지도로 그리고, 과거의 실패 경험을 기억하며, 동시에 여러 가지 해결책을 검토하는 '초지능 공장 관리자'입니다. 덕분에 기존 방법들보다 훨씬 빠르고 똑똑하게 일을 정리해냅니다."

이 연구는 앞으로 공장뿐만 아니라 물류, 배송 경로 등 복잡한 자원 배분 문제를 해결하는 데 큰 도움이 될 것으로 기대됩니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 산업 4.0 시대의 스마트 제조 환경은 대량 맞춤 생산과 동적 생산을 요구하며, 이에 따라 유연한 스케줄링 기법이 필수적입니다.
• 문제 (FJSP): 유연 작업장 스케줄링 문제 (Flexible Job Shop Scheduling Problem, FJSP) 는 각 작업 (Operation) 을 여러 대의 호환 가능한 기계 중 하나에 할당하고, 기계 내에서의 작업 순서를 결정하여 **최대 완료 시간 (Makespan, $C_{max}$)**을 최소화하는 NP-난해 (NP-hard) 조합 최적화 문제입니다.
• 기존 접근법의 한계:
  • 구성 기반 (Constructive) 방법: 기존 DRL 기반 방법들은 대부분 작업을 하나씩 할당하며 해를 구성하는 방식을 사용합니다. 그러나 부분 해 (Partial Solution) 의 불완전성으로 인해 중요한 상태 정보 (예: 미할당 작업 간의 관계, 진행 중인 작업의 상태) 를 누락하기 쉽고, 최적 해에 도달하는 데 한계가 있습니다.
  • 개선 기반 (Improvement) 방법의 부재: 초기 완전 해 (Complete Solution) 에서 시작하여 이웃 해를 탐색하며 점진적으로 개선하는 방법은 최적화에 유리하지만, FJSP 의 복잡한 기계 할당 유연성으로 인해 상태 표현, 정책 학습, 효율적인 탐색 전략 설계가 어렵습니다. 기존 개선 기반 DRL 연구들은 대부분 비유연한 JSP 에 국한되어 있었습니다.

2. 제안 방법론 (Methodology: MIStar)

저자들은 FJSP 를 해결하기 위해 **MIStar (Memory-enhanced Improvement Search framework)**를 제안했습니다. 이는 DRL 기반의 개선 휴리스틱 프레임워크로, 다음과 같은 핵심 구성 요소로 이루어져 있습니다.

2.1. 이종 방향성 비분리 그래프 (Directed Heterogeneous Disjunctive Graph)

• 기존 비분리 그래프 (Disjunctive Graph) 는 기계 노드가 없어 기계 상태를 직접 표현하기 어렵습니다.
• MIStar 는 작업 노드와 기계 노드를 모두 포함하는 이종 그래프를 설계했습니다.
• 기계의 처리 순서를 명시적으로 인코딩하기 위해 **방향성 하이퍼 엣지 (Directed Hyper-edges)**를 도입하여, 기계 노드에서 해당 기계에서 처리되는 작업 시퀀스로 연결됩니다. 이를 통해 완전한 스케줄링 해를 정확하게 표현하고 상태 정보를 손실 없이 전달합니다.

2.2. 메모리 강화 이종 그래프 신경망 (MHGNN)

• 특징 추출: 작업 노드와 기계 노드의 위상적, 시퀀스적 제약 정보를 인코딩하기 위해 GIN(Graph Isomorphism Network) 과 GAT(Graph Attention Network) 를 결합한 이종 GNN 을 사용합니다.
• 메모리 모듈: 방문한 해 (History) 를 압축된 형태로 저장하고, 현재 상태와 유사한 과거 해를 검색 (KNN) 하여 소프트 보팅 (Soft Voting) 메커니즘을 통해 통합된 히스토리 임베딩을 생성합니다.
• 효과: 이 히스토리 정보는 현재 상태 임베딩과 결합되어 정책 네트워크에 입력되며, 과거의 경험을 바탕으로 의사결정을 개선하고 국소 최적점 (Local Optima) 에 빠지는 것을 방지하는 탐색 능력을 향상시킵니다.

2.3. 행동 공간 및 탐색 전략

• 행동 공간 ($N_{opt2}$): 작업 순서 변경과 기계 할당 변경을 동시에 수행할 수 있는 $N_{opt2}$ 이웃 구조를 기반으로 합니다. 기존 JSP 에 사용되던 $N_5$ 구조는 FJSP 에서는 비실용적이거나 비효율적이므로, 최적 삽입 구간 (Optimal Insertion Interval) 을 찾아 이웃 크기를 줄이고 탐색 효율을 높였습니다.
• 행동 차원 축소: FJSP 제약 조건 (작업은 할당된 기계에서만 처리됨) 을 활용하여 행동 공간의 차원을 $O(|O|^2|M|)$에서 $O(|O|^2)$로 축소하여 학습 난이도를 낮추고 수렴 속도를 높였습니다.
• 병렬 탐욕적 탐색 (Parallel Greedy Exploration): 매 단계에서 $P$개의 후보 행동을 병렬로 샘플링하고, 가장 큰 개선을 가져오는 행동을 선택하여 실행합니다. 이는 적은 반복 횟수로 고품질 해를 찾을 수 있게 합니다.

2.4. MDP 공식화 및 학습

• 상태: 완전한 해를 그래프로 표현한 임베딩.
• 행동: $N_{opt2}$ 이웃 내의 로컬 무브 (작업 재배치 및 기계 변경).
• 보상: 해의 개선 정도 ($C_{max}$ 감소) 를 긍정적으로 보상하고, 중복된 해 탐색에 대해서는 페널티를 부과하여 다양성을 유도합니다.
• 학습 알고리즘: $n$-step PPO(Proximal Policy Optimization) 를 사용하여 학습합니다.

3. 주요 기여 (Key Contributions)

1. 최초의 FJSP DRL 개선 휴리스틱 프레임워크: MIStar 는 FJSP 에 적용된 최초의 DRL 기반 개선 (Improvement) 휴리스틱 프레임워크로, 기존 수동 설계 휴리스틱 및 최신 DRL 구성 (Constructive) 방법보다 우수한 성능을 보입니다.
2. 새로운 상태 표현 및 행동 공간: FJSP 의 완전한 해를 표현하기 위한 방향성 이종 비분리 그래프와 작업 순서 및 기계 할당을 동시에 조정할 수 있는 $N_{opt2}$ 기반 행동 공간을 설계했습니다.
3. 메모리 강화 GNN (MHGNN): 과거 해의 경험을 메모리 모듈에 저장하고 재사용하여 정책의 의사결정 능력을 향상시키고 국소 최적점 탈출을 돕는 새로운 아키텍처를 제안했습니다.
4. 효율적인 병렬 탐색 전략: 병렬 탐욕적 탐색을 통해 탐색 효율을 극대화하고, 반복 횟수를 줄이면서도 높은 품질의 해를 도출합니다.

4. 실험 결과 (Results)

• 데이터셋: 합성 데이터 (SD1, SD2) 와 공개 벤치마크 (Hurink, Brandimarte) 를 사용했습니다.
• 성능 비교:
  • 구성 방법 대비: 기존 DRL 구성 방법 (HGNN, DANIEL) 보다 모든 인스턴스에서 더 낮은 Makespan 을 기록했습니다. 특히 SD2 와 같은 복잡한 분포에서 개선 폭이 컸습니다.
  • 휴리스틱 대비: 그리디 (GD), 최선 개선 (BI), 첫 개선 (FI) 과 같은 전통적인 휴리스틱보다 더 짧은 시간 내에 더 나은 해를 찾았습니다.
  • OR-Tools 대비: 작은 규모에서는 OR-Tools 와 유사한 성능을 보였으나, 대규모 인스턴스 (예: 50x30, 100x10) 에서는 OR-Tools 가 시간 제한 내에 해를 찾지 못하거나 (Infeasible) 매우 느린 반면, MIStar 는 짧은 시간 내에 고품질 해를 제공했습니다.
• 일반화 능력: 작은 인스턴스 (10x5) 로 학습된 모델이 30x10, 40x10, 심지어 100x10 과 같은 훨씬 큰 규모의 인스턴스에서도 우수한 성능을 발휘하여 뛰어난 일반화 능력을 입증했습니다.
• 초기 해 의존성: 다양한 초기 해 (랜덤, 우선순위 규칙, DRL 구성 해) 로부터 시작하더라도 MIStar 는 일관된 개선을 보여주며, 초기 해의 품질에 덜 의존하는 강건성을 가집니다.

5. 의의 및 결론 (Significance)

• 스마트 제조의 실용성: Industry 4.0 환경에서 요구되는 동적이고 유연한 생산 스케줄링 문제를 해결하기 위해, 기존 구성 방식의 한계를 극복하고 개선 기반 접근법을 DRL 에 성공적으로 적용했습니다.
• 확장성: 메모리 메커니즘과 병렬 탐색 전략을 통해 FJSP 의 복잡한 해 공간에서도 효율적으로 탐색할 수 있음을 증명했습니다.
• 미래 전망: 이 연구는 대규모 FJSP 에 대한 신경망 기반 최적화의 새로운 방향을 제시하며, 향후 더 큰 이웃 구조 (Disruptive Local Moves) 로의 확장이나 동적 탐색 규모 조절 등으로 발전할 수 있는 기반을 마련했습니다.

요약하자면, MIStar는 FJSP 의 복잡성을 해결하기 위해 이종 그래프 표현, 메모리 강화 신경망, 그리고 병렬 탐색 전략을 결합한 혁신적인 DRL 프레임워크로, 기존 방법론들보다 더 빠르고 더 정확한 스케줄링 해를 제공합니다.