어텐션 기반 심층 강화학습을 활용한 액티비티 스케줄링 최적화 연구 = Attention based Deep Reinforcement Learning for Activity Scheduling Optimization|RISS 상세보기

다국어 초록 (Multilingual Abstract)

Mid-term project scheduling in shipyards is a large-scale project scheduling problem where hundreds to thousands of activities form complex network structures. Resource leveling problem is an optimization problem that minimizes the variability of resource usage during the project period to maximize resource utilization efficiency. Uneven resource usage causes resource overload during specific periods, leading to additional costs and project delays. Resource leveling problem is classified as NP-hard, and as project size increases, the solution space grows exponentially, making optimal solutions practically impossible for large-scale projects. Existing studies attempted to solve this problem using Meta heuristic algorithms and exact algorithms. However, Meta heuristic algorithms suffer from degraded solution quality and local optimal trapping as problem complexity increases, while exact algorithms face scalability issues with non-linear increases in computation time as problem size grows, making it difficult to obtain solutions within reasonable timeframes in large-scale projects like actual shipyards.
This paper proposes a two-stage approach combining an enhanced Kahn's Algorithm and attention-based deep reinforcement learning to effectively solve the resource leveling problem in large-scale projects. Project scheduling decision-making is divided into activity sequencing, which determines execution sequence of activities, and activity scheduling, which determines the timing of each activity. The first stage uses an enhanced Kahn's algorithm that considers priority based on total resource usage to determine the execution sequence satisfying precedence relationships between activities. While the original Kahn's algorithm only considers topological sorting, this research derives more efficient sequences by reflecting resource usage patterns. The second stage applies deep reinforcement learning with an Attention mechanism to determine the optimal start time for each activity. The attention mechanism integrates activity characteristics and resource status at the scheduling moment through state representation, simultaneously considering possible start time candidates, and the agent selects optimal actions based on learned policies that align with resource leveling objectives. This research proposes a methodology based on the REINFORCE algorithm while utilizing existing heuristics as a baseline to gradually improve policies, reducing instability in early learning stages and enabling robust performance even in large-scale problems.
Performance verification of the proposed model was conducted through experimental evaluation using the PSPLIB benchmark dataset and actual shipyard mid-term scheduling data. Experimental results demonstrate that the proposed methodology consistently outperforms existing methods including exact algorithms, meta heuristics, and heuristics in reducing resource usage variance for large-scale projects ranging from 299 to 5,800 activities. Notably, the algorithm implements robust scheduling without constraint violations even in highly complex real world problems considering both precedence and time range constraints, while maintaining practical computation times. Ablation experiments validate the contribution of the attention mechanism and enhanced Kahn's algorithm, confirming that the combination of these two components plays a critical role in performance improvement.
This paper presents the first attention-based deep reinforcement learning approach for the resource leveling problem. By establishing a learning environment that satisfies precedence relationships while minimizing solution space constraints, the global optimum reachability is improved. The algorithm demonstrates high generalization performance, overcoming computation time limitations in various large-scale projects and providing solutions within practical timeframes. Through this achievement, this research provides a practical solution applicable to production planning optimization in large-scale manufacturing industries including shipyards and demonstrates the feasibility of applying deep reinforcement learning in industrial practice.

번역하기

국문 초록 (Abstract)

조선소의 중기 일정 계획은 수백 개에서 수천 개의 액티비티가 복잡한 네트워크 구조를 형성하는 대규모 프로젝트 스케줄링 문제이다. 특히 자원 평준화 문제는 프로젝트 기간 동안 자원 사용량의 변동성을 최소화하여 자원 활용의 효율성을 극대화하는 최적화 문제로서, 불균등한 자원 사용은 특정 기간에 자원 과부하를 초래하며 이는 추가 비용 발생과 프로젝트 지연으로 이어진다. 자원 평준화 문제는 NP-hard 문제로 분류되며, 프로젝트 규모가 증가할수록 해 공간이 지수적으로 증가하여 대규모 프로젝트에서는 최적해 도출이 현실적으로 불가능하다는 근본적 한계를 가진다. 기존 연구들은 메타 휴리스틱 알고리즘과 정확해 알고리즘을 활용하여 이 문제를 해결하고자 하였으나, 메타 휴리스틱 알고리즘들은 문제의 복잡도가 높아질수록 해의 품질이 낮아지고 지역 최적해에 빠지는 한계를 가지며, 정확해 알고리즘들은 문제의 크기가 증가함에 따라 계산 시간이 비선형적으로 증가하여 실제 조선소와 같은 대규모 프로젝트에서 합리적인 시간 내에 해를 구하기 어려운 확장성 문제를 갖는다.
본 논문에서는 대규모 프로젝트의 자원 평준화 문제를 효과적으로 해결하기 위해 개선된 Kahn's Algorithm과 어텐션 기반 강화학습을 결합한 2단계 접근법을 제안한다. 프로젝트 스케줄링을 위한 의사결정 단계는 액티비티의 순서를 결정하는 activity sequencing과 각 액티비티의 일정을 결정하는 activity scheduling으로 구분된다. 첫 번째 단계에서는 액티비티 간의 선후행 관계를 만족하는 실행 순서를 결정하기 위해 총 자원 사용량에 따른 우선순위를 고려한 개선된 Kahn's 알고리즘을 사용한다. 기존 Kahn's 알고리즘은 위상 정렬만을 고려하였으나, 본 연구에서는 자원 사용 패턴을 반영하여 보다 효율적인 순서를 도출한다. 두 번째 단계에서는 각 액티비티의 최적 시작 시간을 결정하기 위해 Attention 메커니즘을 활용한 심층 강화학습을 적용한다. 어텐션 메커니즘은 액티비티의 특성과 스케줄링 시점의 자원 상태를 통합한 상태 표현을 통해 가능한 시작 시간 후보들을 동시에 고려하며, 에이전트가 학습된 정책에 기반하여 자원 평준화 목적에 부합하는 최적의 행동을 선택한다. 본 연구에서는 REINFORCE 알고리즘을 기반으로 하되, 기존 휴리스틱을 baseline으로 활용하여 정책을 점진적으로 개선하는 방법론을 제안함으로써 학습 초기 단계에서의 불안정성을 줄이고 대규모 문제에서도 robust한 성능을 가능하게 한다.
제안 모델의 성능 검증을 위해 PSPLIB 벤치마크 데이터셋과 실제 조선소 중기 일정 데이터를 활용한 실험 평가를 수행하였다. 실험 결과, 본 연구에서 제안한 방법론은 299개에서 5,800개의 액티비티를 가지는 대규모 프로젝트 규모에서 자원 사용량 분산 감소에 있어 정확해 알고리즘, 메타 휴리스틱, 휴리스틱을 포함한 기존 방법론들을 일관되게 능가하는 우수한 성능을 보인다. 특히, precedence constraint와 time range constraint를 모두 고려한 높은 복잡도를 가진 현실 문제에서도 제약 조건 위반 없는 일정을 결정하는 robust한 알고리즘을 구현하였으며, 계산 시간 측면에서도 실용적인 수준을 유지하였다. Ablation 실험을 통해 어텐션 메커니즘과 개선된 Kahn's 알고리즘 각각의 기여도를 검증하였으며, 두 구성요소의 결합이 성능 향상에 핵심적인 역할을 함을 확인하였다.
본 논문에서는 자원 평준화 문제에 대한 어텐션 기반 심층 강화학습 접근법을 최초로 제시하였다. 선후행 관계를 만족하는 동시에 해 공간 제한을 최소화하는 학습 환경을 통하여 전역 최적해 도달 가능성을 높였으며, 높은 일반화 성능으로 다양한 대규모 프로젝트에서 계산 시간의 한계를 극복하여 실용적 시간 내에 해를 도출하는 알고리즘을 제시하였다. 이를 통해 조선소를 포함한 대규모 제조 산업의 생산 계획 최적화에 활용될 수 있는 실용적인 해결 방안을 제공하고, 심층 강화학습의 산업 현장 적용 가능성을 입증하였다.

번역하기

조선소의 중기 일정 계획은 수백 개에서 수천 개의 액티비티가 복잡한 네트워크 구조를 형성하는 대규모 프로젝트 스케줄링 문제이다. 특히 자원 평준화 문제는 프로젝트 기간 동안 자원 사...

목차 (Table of Contents)