💻 computer science

Modelling Reinforcement Learning Scheduling Agents: Action spaces, reward designs, and expert demonstrations

이 논문은 딥 강화 학습의 모델링 선택이 유연 생산 시스템(Flexible Job-shop Scheduling Problem)의 스케줄링 정책에 어떻게 영향을 미치는지 조사하며, 제약 프로그래밍(Constraint Programming)에서 도출된 최적성 경계와 전문가 시연을 멀티 에이전트 프레임워크에 통합하는 것이 보상 설계를 유의미하게 개선하고 우수한 실시간 스케줄링 성능을 달성하기 위한 수렴을 가속화한다는 것을 입증한다.

원저자: Alexandre Jesus, Arthur Corrêa, Miguel Vieira, Catarina Marques, Cristóvão Silva, Samuel Moniz

게시일 2026-09-07

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Alexandre Jesus, Arthur Corrêa, Miguel Vieira, Catarina Marques, Cristóvão Silva, Samuel Moniz

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 제조업의 중심부에서는 매 초마다 조용하고도 복잡한 퍼즐이 펼쳐집니다. 공장은 한정된 수의 기계에서 수천 개의 작업을 수행할 순서를 결정해야 합니다. 어떤 작업은 특정 기계에서만 수행할 수 있는 반면, 다른 작업은 여러 기계에서 처리될 수 있으며 각 기계마다 소요 시간이 조금씩 다릅니다. 목표는 말하기는 간단하지만 해결하기는 매우 어렵습니다. 바로 모든 작업을 최대한 빨리 끝내는 것입니다. 유연한 잡 숍 스케줄링(flexible job-shop scheduling) 문제로 알려진 이 과제는 효율성을 시험하는 고전적인 테스트입니다. 수십 년 동안 전문가들은 좋은 해결책을 찾기 위해 경직된 수학적 규칙이나 시행착오 방식에 의존해 왔습니다. 그러나 이러한 전통적인 방식은 공장 현장이 변하거나 계산해야 할 가능성의 수가 너무 방대해질 때 종종 어려움을 겪습니다. 최근 몇 년 사이, 새로운 접근 방식이 등장했습니다. 바로 컴퓨터에게 '행함으로써 배우는 법'을 가르치는 것입니다. 강화 학습이라고 불리는 이 방법은 인공지능이 수백만 개의 시나리오를 탐색하고 작업을 조직하기 위한 자신만의 전략을 발견하도록 하여, 이전보다 더 빠르고 적응력 있게 결정을 내릴 수 있도록 약속합니다.

포르투갈 대학 연구진은 이제 이러한 학습 기계가 어떻게 구축되는지를 더 자세히 살펴보며 근본적인 질문을 던졌습니다. 즉, 우리가 그들을 가르치는 방식이 기계 자체의 지능보다 더 중요한가 하는 점입니다. 그들은 설계자들이 이러한 스케줄링 에이전트를 만들 때 내리는 두 가지 구체적인 선택에 집중했습니다. 첫 번째 선택은 에이전트가 보는 정보의 상세 수준입니다. 에이전트가 전체 작업(job)을 보고 다음에 무엇을 시작할지 결정하나요, 아니면 모든 작업의 모든 단계(step)를 세밀하게 들여다보며 정확히 어떤 단계를 수행할지 결정하나요? 두 번째 선택은 피드백 루프인 보상 시스템입니다. 에이전트가 단순히 작업을 빠르게 끝냈을 때 칭찬을 받나요, 아니면 그 작업이 공장의 전체적인 그림에 어떻게 부합하는지에 따라 보상을 받나요? 답을 찾기 위해 연구진은 단순히 에이전트가 추측하게 두지 않았습니다. 대신, 강력한 전통적 수학 솔버(solver)를 사용하여 다양한 공장 시나리오에 대해 완벽하거나 완벽에 가까운 스케줄을 생성했습니다. 그런 다음 이 전문가의 솔루션을 기준점, 즉 황금 표준으로 사용하여 학습 에이전트가 실제로 얼마나 잘 수행하고 있는지를 측정했습니다.

연구진은 최선의 접근 방식이 전적으로 공장 현장의 성격에 달려 있다는 것을 발견했습니다. 작업들이 서로 매우 유사할 때는 더 단순한 관점이 가장 효과적입니다. 이런 경우, 에이전트가 전체 작업을 보고 다음 작업을 선택하는 것이 효율적이고 효과적입니다. 그러나 공장이 다양성으로 가득 차서, 어떤 작업은 길고 복잡한 반면 다른 작업은 짧고, 기계들의 속도가 매우 다를 때는 이야기가 달라집니다. 이러한 혼란스러운 환경에서는 에이전트가 세부 사항을 보아야 합니다. 에이전트는 모든 개별 작업(operation)을 살펴보고 정확히 어떤 기계가 이를 처리해야 하는지 결정해야 합니다. 연구는 복잡한 공장에서 이러한 세부 사항을 무시하는 것이 결과적으로 훨씬 더 나쁜 결과를 초집중한다는 것을 보여주었으며, 이는 학습 에이전트를 설계하는 데 있어 단 하나의 "만능형" 방식은 존재하지 않는다는 것을 입증했습니다.

연구진은 또한 에이전트에게 보상을 주는 방식이 에이전트가 보는 정보의 상세 수준보다 훨씬 더 중요하다는 것을 발견했습니다. 많은 기존 연구는 모든 작업의 총 완료 시간이 변할 때만 에이전트가 피드백을 받는 '전역적 보상(global reward)'에 의존해 왔습니다. 이는 마치 최종 점수가 바뀔 때만 말을 거는 코치와 같아서, 경기 중간에 선수가 자신이 무엇을 잘했고 잘못했는지 알 수 없게 만듭니다. 연구진은 이러한 접근 방식이 특히 복잡한 환경에서 에이전트를 혼란스럽게 만든다는 것을 발견했습니다. 대신, 그들은 즉각적인 '지역적 피드백(local feedback)'을 제공하는 새로운 보상 시스템을 설계했습니다. 에이전트는 해당 특정 작업을 위해 사용 가능한 다른 기계들과 비교하여, 자신이 작업 중인 특정 기계를 얼마나 효율적으로 사용했는지에 따라 보상을 받았습니다. 이 지속적이고 즉각적인 피드백은 마치 어깨 위에 놓인 안정적인 손길처럼 에이전트를 단계별로 안내했습니다. 이 지역적 가이드와 전역적 그림을 결합했을 때, 에이전트는 훨씬 더 빨리 학습했으며 전통적인 수학 솔버가 찾아낸 완벽한 솔루션에 훨씬 더 가까운 스케줄을 만들어냈습니다.

성능을 더욱 높이기 위해 연구진은 하이브리드 방법을 도입했습니다. 그들은 에이전트가 아무것도 없는 상태에서 시작하게 하는 것이 비효율적이라는 점을 깨달았습니다. 따라서 에이전트가 스스로 학습 여정을 시작하기 전에, 전문가의 수학 솔버가 만든 천 개의 완벽한 스케줄 사례를 보여주었습니다. '시연으로부터의 학습(learning from demonstrations)'이라고 알려진 이 과정은 에이전트에게 출발점을 제공하여, 무작위로 추측하는 초기 단계의 서툰 과정을 건너뛰게 해주었습니다. 그 결과, 이 하이브리드 방식은 더 빠르게 학습할 뿐만 아니라 더 안정적이고 신뢰할 수 있는 시스템이 되었습니다. 테스트에서 이 하이브리드 접근 방식은 표준 학습 방법과 비교했을 때 에이전트의 스케줄과 완벽한 스케줄 사이의 격차를 약 5% 줄였습니다. 아마도 가장 중요한 점은, 이러한 높은 수준의 성능이 복잡하고 무거운 컴퓨터 구조를 필요로 하지 않고도 달성되었다는 것입니다. 시스템은 가볍고 빠르게 유지되었으며, 1초 미만 안에 결정을 내릴 수 있었습니다.

이 연구는 효과적인 스케줄링 에이전트를 구축하는 비결은 알고리즘 자체뿐만 아니라, 설계를 특정 문제에 정교하게 맞추는 데 있다는 결론을 내립니다. 전문가의 솔루션을 사용하여 학습 과정을 가이드하고, 기계와 작업의 혼합 구성에 맞춰 보상 신호를 조정함으로써, 강력하면서도 실용적인 지능형 시스템을 만드는 것이 가능하다는 것을 보여줍니다. 이러한 발견은 미래의 공장 관리가 불가능할 정도로 복잡한 AI를 요구하는 것이 아니라, 전통적인 수학적 정밀함과 현대적인 학습 기술의 사려 깊은 결합을 필요로 한다는 점을 시사합니다. 그 결과물은 공장이 변화에 실시간으로 적응하도록 도와, 주변 세상이 아무리 변동성이 크더라도 생산의 흐름이 원활하게 유지되도록 보장하는 도구가 될 것입니다.

기술 요약: 강화 학습 스케줄링 에이전트 모델링

문제 정의

본 연구는 현대 제조 공정의 핵심인 조합 최적화 문제인 **유연 작업 숍 스케줄링 문제(Flexible Job-shop Scheduling Problem, FJSP)**를 다룹니다. FJSP는 작업을 여러 후보 기계에서 처리할 수 있도록 허용함으로써 고전적인 작업 숍 스케줄링 문제(JSP)를 확장하며, 작업 할당(기계 선택)과 기계 순서 결정(순서 결정)이라는 두 가지 의사결정 계층을 도입합니다. 목표는 마지막 작업의 완료 시간인 **메이크스팬(makespan, $C_{max}$ )**을 최소화하는 것입니다.

혼합 정수 선형 계획법(MILP) 및 제약 프로그래밍(CP)과 같은 정밀 방법론은 최적해를 찾을 수 있지만, 대규모 또는 동적 환경에서는 계산 비용 문제에 직면하곤 합니다. 반면, 심층 강화 학습(DRL)은 낮은 추론 시간과 적응성을 제공하지만, 모델링 선택(행동 공간, 보상 함수)이 특정 문제 구조(예: 작업 이질성, 기계 유연성)와 어떻게 상호작나는지에 대한 체계적인 이해가 부족하다는 단점이 있습니다. 기존의 DRL 연구들은 종종 시행착오 방식의 설계나 휴리스틱 베이스라인에 의존하며, 최적성 경계(optimality bounds)와의 엄격한 연결성이 결여되어 있습니다.

방법론

저자들은 중앙 집중식 학습 및 분산 실행(Centralized Learning with Decentralized Execution, CLDE) 패러다임 하에서 작동하는 멀티 에이전트 심층 Q-러닝(Multi-agent Deep Q-Learning, DQL) 프레임워크를 제안합니다. 각 에이전트는 공장의 기계를 나타내며, 부분적인 관측을 바탕으로 로컬 결정을 내립니다.

1. 제약 프로그래밍(CP) 통합

최첨단 인터벌 기반 CP 모델(IBM CP Optimizer 사용)은 두 가지 뚜렷한 역할을 수행합니다.

분석적 베이스라인: CP는 최적성 경계(하한값)와 벤치마크 인스턴스에 대한 고품질 솔루션을 계산하는 데 사용됩니다. 이는 DRL 정책의 최적성 격차(optimality gap)를 평가하기 위한 그라운드 트루스(ground truth) 역할을 합니다.
전문가 시연(Expert Demonstrations): CP 솔루션은 DRL 에이전트를 사전 학습시키기 위해 상태-행동 전이(state-action transitions)로 분해되며, 이는 "전문가 시연" 역할을 합니다.

2. 멀티 에이전트 DQL 아키텍처

본 프레임워크는 에이전트들이 단일 심층 Q-네트워크(DQN) 정책을 공유하는 가치 기반 접근 방식을 활용합니다.

상태 표현: 에이전트는 대기 중인 작업, 처리 시간, 행동 이력, 남은 작업, 기계 가동률, 큐 밀도 등을 포함한 부분적인 시스템 상태를 관찰합니다.
행동 공간: 두 가지 세분화 수준이 평가됩니다.
- 작업 단위( $L_O$ ): 에이전트가 큐에서 특정 작업을 선택합니다.
- 잡(Job) 단위( $L_J$ ): 에이전트가 잡을 선택하면 환경이 다음 작업을 스케줄링합니다.
보상 설계: 다음과 같은 다양한 보상 함수를 체계적으로 평가합니다.
- 글로벌 신호: 메이크스팬 증가에 대한 페널티 부여 ( $r_{MI}$ ).
- 로컬 신호: 행동 사이의 총 시간( $r_{TBA}$ ) 또는 유휴 시간( $r_{IT}$ )에 대한 페널티 부여.
- 제안된 하이브리드 신호: 선택된 처리 시간을 해당 작업의 가장 빠른 가용 후보와 비교하여 비효적인 기계 선택를 페널티로 부과하는 새로운 보상 ( $r_Q$ , $r_{OE}$ ).

3. 하이브리드 학습 전략 (DQL-D)

저자들은 **시연으로부터의 심층 Q-러닝(Deep Q-Learning from Demonstrations, DQLfD)**을 포함하는 하이브리드 방법인 DQL-D를 도입합니다.

사전 학습: DQN은 CP 솔루션(인스턴스당 상위 5개 솔루션)에서 유도된 전이를 사용하여 초기화됩니다.
우선순위 경험 재생(Prioritized Experience Replay): 리플레이 버퍼에는 전문가의 시연과 자체 생성된 RL 전이가 모두 포함됩니다. 전이는 손실(loss)에 따라 샘 sampling되며, 에이전트가 아직 전문가의 행동을 숙달하지 못한 상태를 우선시합니다.
학습: 에이전트는 표준 DQL을 통해 학습을 지속하여, 전문가의 가이드로부터 안정성을 얻는 동시에 전문가의 정책을 넘어 탐색할 수 있도록 합니다.

주요 기여

모델링 선택의 체계적 분석: 본 논문은 행동의 세분화 정도와 보상의 범위가 문제의 구조적 특성(작업 이질성, 기계 유연성, 처리 시간 가변성)과 어떻게 상호작용하는지에 대한 엄격한 평가를 제공합니다.
새로운 보상 함수: 저자들은 기계 이질성을 명시적으로 고려하는 보상 함수( $r_Q$ 및 $r_{OE}$ )를 설계했습니다. 이러한 신호는 기존의 글로벌 또는 순수 로컬 보상보다 우수한 성능을 보였으며, 고이질성 시나리오에서 최적성 격차를 약 10% 줄였습니다.
하이브리드 DQL-D 프레임워크: CP 유도 시연을 멀티 에이전트 DQL 아키텍처에 통합함으로써, 복잡한 그래프 인코더나 어텐션 메커니즘 없이도 수렴 속도를 높이고 안정성을 개선했습니다.

실험 결과

방법론은 규모와 유연성 수준이 다른 세 가지 표준 FJSP 벤치마크 데이터셋(FMJdata, BRdata, DPdata)에서 테스트되었습니다.

행동 세분화: 동질적인 작업 구조를 가진 인스턴스에서는 잡 단위 행동( $L_J$ )이 작업 단위 행동( $L_O$ )과 유사한 성능을 보였습니다. 그러나 이질적인 작업 구조(BRdata 및 DPdata에서 흔함)에서는 작업 단위 행동( $L_O$ )이 현저히 낮은 최적성 격차(중앙값 오차 약 5% 개선)를 나타냈습니다.
보상 설계:
- 표준 글로벌 보상( $r_{MI}$ ) 및 총 시간 보상( $r_{TBA}$ )은 종종 더 높은 최적성 격차를 초래했습니다.
- 제안된 **로컬 효율성 보상( $r_Q$ )**이 지속적으로 가장 우수한 성능을 보였으며, 모든 인스턴스에 대해 CP 대비 평균 **13.62%**의 격차를 달야냈고, 고이질성 시나리오에서는 표준 베이스라인 대비 최적성 격차를 약 10% 감소시켰습니다. 이 보상은 서로 다른 워크로드를 가진 에이전트 간의 행동 품질을 효과적으로 정규화합니다.
DQL-D의 성능:
- 수렴: DQL-D는 표준 DQL보다 빠른 수렴과 낮은 분산을 달성했습니다. 표준 DQL 베이스라인 대비 최적성 격차를 약 5% 줄였습니다.
- 비교: DQL-D는 최첨단 그래프 기반 DRL 방법들(HGNN 및 MPGN)과 경쟁력 있는 성능을 보였으며, 해당 방법들이 적합하지 않은 인스턴스에서 종종 더 나은 성능을 보였습니다.
- 효율성: 경량화된 DQL-D 프레임워크는 복잡한 그래프 기반 아키텍처보다 3~9배 빠른 추론 시간(1초 미만)을 달성하여, 실시간 스케줄링에 매우 적합합니다.

의의 및 주장

본 논문은 최적성 가이드 DRL 모델링을 전문가 시연과 결합함으로써 경량화되고 빠르며 신뢰할 수 있는 스케줄링 에이전트를 구축할 수 있다고 주장합니다.

모델링 통찰: 본 연구는 "원 사이즈 핏 올(one-size-fits-all)" 방식의 DRL 접근법이 불충분함을 입증합니다. 즉, 행동 공간과 보상 함수는 스케줄링 인스턴스의 특정 구조적 특성(예: 이질적 작업을 위한 작업 단위 행동 및 이질적 기계를 위한 로컬 효율성 보상)에 맞춰 조정되어야 합니다.
실무적 타당성: CP를 통한 사전 학습과 단순한 가치 기반 아키텍처를 활용함으로써, 저자들은 복잡한 표현 학습(GNN과 같은)이 최첨단 성능을 달하는 데 반드시 필수적인 것은 아님을 보여줍니다. 이는 엄격한 실시간 제약 조건이 있는 분산 의사결정 지원이 필요한 제조 시스템에 실질적인 솔루션을 제공합니다.
향후 방향: 본 연구는 정밀 방법(CP)과 DRL을 결합한 하이브리드 프레임워크가 이론적 최적성과 실제 배포 사이의 간극을 메울 수 있음을 시사하며, 이는 동적 및 온라인 스케줄링 변형을 위한 길을 열어줍니다.