원문정보
Scheduling Algorithm, Based on Reinforcement Learning for Minimizing Total Tardiness in Unrelated Parallel Machines
초록
영어
This paper proposes an algorithm for the Unrelated Parallel Machine Scheduling Problem(UPMSP) without setup times, aiming to minimize total tardiness. As an NP-hard problem, the UPMSP is hard to get an optimal solution. Consequently, practical scenarios are solved by relying on operator's experiences or simple heuristic approaches. The proposed algorithm has adapted two methods: a policy network method, based on Transformer to compute the correlation between individual jobs and machines, and another method to train the network with a reinforcement learning algorithm based on the REINFORCE with Baseline algorithm. The proposed algorithm was evaluated on randomly generated problems and the results were compared with those obtained using CPLEX, as well as three scheduling algorithms. This paper confirms that the proposed algorithm outperforms the comparison algorithms, as evidenced by the test results.
목차
1. 서론
2. 문제 및 수리모형
2.1 문제 설명
2.2 수리모형
3. 기존 일정계획 알고리즘
3.1 우선순위 규칙
3.2 메타휴리스틱 알고리즘
4. 강화학습 기반 일정계획 알고리즘
4.1 강화학습 알고리즘
4.2 정책 네트워크
5. 성능 평가 실험
5.1 실험 방법
5.2 실험 결과
6. 결론
7. References