臺灣博碩士論文加值系統

在不斷變化的製造業環境中，許多公司正面臨著在劇烈的全球競爭和客戶需求變化的情況下進行管理生產複雜性的艱難任務。在需要保持運營效率和盈利能力的條件下，這在很大程度上取決於如何有效解決工件的調度問題（JSSP）。然而，傳統方法往往難以跟上動態的製造環境步伐。在這些環境中，不可預測性和即時應用性的需求可能使靜態方法變得無效。為了迎接這些挑戰，本篇論文提出了一個創新的框架。利用深度強化學習（DRL）的特性來解決動態零工式排程問題的複雜性。通過將異構圖神經網絡（HGNN）與DRL結合，我們開發了一個全新的模型，能夠擷取JSSP問題中複雜的依賴關係，同時動態調整調度以適應現實世界製造系統的變化。我們模型的一個主要優勢在於其優異的泛化能力，使其能夠有效處理不同規模大小的JSSP問題。此外，我們引入了一種新的訓練方法，稱為Bootstrap Curriculum Learning（BCL），目的是提高模型學習效率。這種方法使我們的模型能夠從訓練數據中獲取更豐富的排程經驗，並能更有效地適應智能製造環境中遇到的各種調度情境。為了驗證本篇論文所提出模型的有效性，我們使用公開基準資料集和人工生成數據集進行實驗。結果顯示，我們的模型具有卓越的性能和顯著的泛化能力，鞏固了其作為解決智能製造中動態調度挑戰的穩健解決方案的地位。

In the constantly evolving manufacturing landscape, companies face the complex task of managing production intricacies amidst heightened global competition and shifting customer preferences. This requires maintaining operational efficiency and profitability, which is largely based on effectively addressing the Job-Shop Scheduling Problem (JSSP). However, traditional methods often struggle to keep up with dynamic manufacturing environments, where unpredictability and the need for real-time adaptability can render static approaches ineffective. To address these challenges, this study introduces an innovative framework that harnesses the power of Deep Reinforcement Learning (DRL) to navigate the complexities of dynamic JSSP. By seamlessly integrating heterogeneous graph neural networks (HGNNs) with DRL, we develop a sophisticated model capable of capturing the intricate interdependencies inherent in JSSP while dynamically adjusting to the evolving realities of real-world manufacturing systems. One of the key strengths of our model lies in its size-agnostic capabilities, enabling it to effectively handle JSSPs of varying problem sizes. Moreover, we introduce a novel training method called Bootstrap Curriculum Learning (BCL) designed to enhance learning efficacy. This approach allows our model to gain richer insight from training data and adapt more effectively to various scheduling scenarios encountered in smart manufacturing environments. To validate the effectiveness of our proposed model, we conduct comprehensive evaluations against both public benchmarks and synthetic datasets. The results demonstrate the superior performance and remarkable generalizability of our model, solidifying its position as a robust solution to the dynamic scheduling challenges prevalent in smart manufacturing.

Table of Contents
摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Research Aims . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Conventional Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Heuristics and Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Reinforcement and Deep Reinforcement Learning . . . . . . . . . . . . . . . . 7
2.4 Graph Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Proposed Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Problem Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 MDP Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Disjunctive Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Heterogeneous Graph Neural Network . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.6 Bootstrap Curriculum Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.7 Loss function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1 Comparison Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Performance on Public Benchmark . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Performance on Static Simulation . . . . . . . . . . . . . . . . . . . . . . . . 30
4.5 Performance on Dynamic Environment . . . . . . . . . . . . . . . . . . . . . 32
4.6 Ablation Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

[1] M. L. Pinedo, Scheduling. Springer, 2012, vol. 29.
[2] H. Xiong, S. Shi, D. Ren, and J. Hu, “A survey of job shop scheduling problem: The types
and models,” Computers & Operations Research, vol. 142, p. 105731, 2022.
[3] I. Echeverria, M. Murua, and R. Santana, “Solving large flexible job shop scheduling in-
stances by generating a diverse set of scheduling policies with deep reinforcement learn-
ing,” arXiv preprint arXiv:2310.15706, 2023.
[4] K.-C. Ying, P. Pourhejazy, C.-Y. Cheng, and R.-S. Syu, “Supply chain-oriented permu-
tation flowshop scheduling considering flexible assembly and setup times,” International
Journal of Production Research, vol. 61, no. 1, pp. 258–281, 2023.
[5] X. Wen, Y. Sun, H.-L. Ma, and S.-H. Chung, “Green smart manufacturing: energy-
efficient robotic job shop scheduling models,” International Journal of Production Re-
search, vol. 61, no. 17, pp. 5791–5805, 2023.
[6] E. Ghaedy-Heidary, E. Nejati, A. Ghasemi, and S. A. Torabi, “A simulation optimization
framework to solve stochastic flexible job-shop scheduling problems—case: Semiconduc-
tor manufacturing,” Computers & Operations Research, vol. 163, p. 106508, 2024.
[7] B. Jiang, Y. Ma, L. Chen, B. Huang, Y. Huang, and L. Guan, “A review on intelligent
scheduling and optimization for flexible job shop,” International Journal of Control, Au-
tomation and Systems, vol. 21, no. 10, pp. 3127–3150, 2023.
[8] Z. Dai, S. C. Perera, and J.-J. Wang, “Adopting a hierarchical diagnosis and treatment
system to optimize elective surgery scheduling,” Computers & Operations Research, vol.
159, p. 106342, 2023.
[9] C.-H. Lee, C.-L. Liu, A. J. Trappey, J. P. Mo, and K. C. Desouza, “Understanding digital
transformation in advanced manufacturing and engineering: A bibliometric analysis, topic
modeling and research trend discovery,” Advanced Engineering Informatics, vol. 50, p.
101428, 2021.
[10] B. W. Shaheen and I. Németh, “Integration of maintenance management system functions
with industry 4.0 technologies and features—a review,” Processes, vol. 10, no. 11, p. 2173,
2022.
[11] C. Destouet, H. Tlahig, B. Bettayeb, and B. Mazari, “Flexible job shop scheduling problem
under industry 5.0: A survey on human reintegration, environmental consideration and
resilience improvement,” Journal of Manufacturing Systems, vol. 67, pp. 155–173, 2023.
[12] J. Shahrabi, M. A. Adibi, and M. Mahootchi, “A reinforcement learning approach to pa-
rameter estimation in dynamic job shop scheduling,” Computers & Industrial Engineering,
vol. 110, pp. 75–82, 2017.
[13] D. Ouelhadj and S. Petrovic, “A survey of dynamic scheduling in manufacturing systems,”
Journal of scheduling, vol. 12, pp. 417–431, 2009.
[14] X. Wu, X. Yan, D. Guan, and M. Wei, “A deep reinforcement learning model for dynamic
job-shop scheduling problem with uncertain processing time,” Engineering Applications
of Artificial Intelligence, vol. 131, p. 107790, 2024.
[15] Z. Liu, H. Mao, G. Sa, H. Liu, and J. Tan, “Dynamic job-shop scheduling using graph re-
inforcement learning with auxiliary strategy,” Journal of Manufacturing Systems, vol. 73,
pp. 1–18, 2024.
[16] M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop
scheduling,” Mathematics of operations research, vol. 1, no. 2, pp. 117–129, 1976.
[17] Q. Wang and C. Tang, “Deep reinforcement learning for transportation network combina-
torial optimization: A survey,” Knowledge-Based Systems, vol. 233, p. 107526, 2021.
[18] R. Zhang, A. Prokhorchuk, and J. Dauwels, “Deep reinforcement learning for traveling
salesman problem with time windows and rejections,” in 2020 International Joint Confer-
ence on Neural Networks (IJCNN). IEEE, 2020, pp. 1–8.
[19] W. Pan and S. Q. Liu, “Deep reinforcement learning for the dynamic and uncertain vehicle
routing problem,” Applied Intelligence, vol. 53, no. 1, pp. 405–422, 2023.
[20] L. Wang, X. Hu, Y. Wang, S. Xu, S. Ma, K. Yang, Z. Liu, and W. Wang, “Dynamic job-
shop scheduling in smart manufacturing using deep reinforcement learning,” Computer
Networks, vol. 190, p. 107969, 2021.
[21] C. Zhang, W. Song, Z. Cao, J. Zhang, P. S. Tan, and X. Chi, “Learning to dispatch for
job shop scheduling via deep reinforcement learning,” Advances in neural information
processing systems, vol. 33, pp. 1621–1632, 2020.
[22] C. Zhang, D. Song, C. Huang, A. Swami, and N. V. Chawla, “Heterogeneous graph neural
network,” in Proceedings of the 25th ACM SIGKDD international conference on knowl-
edge discovery & data mining, 2019, pp. 793–803.
[23] G. A. Kasapidis, S. Dauzère-Pérès, D. C. Paraskevopoulos, P. P. Repoussis, and C. D.
Tarantilis, “On the multiresource flexible job-shop scheduling problem with arbitrary
precedence graphs,” Production and Operations Management, vol. 32, no. 7, pp. 2322–
2330, 2023.
[24] S. Fatemi-Anaraki, R. Tavakkoli-Moghaddam, M. Foumani, and B. Vahedi-Nouri,
“Scheduling of multi-robot job shop systems in dynamic environments: mixed-integer lin-
ear programming and constraint programming approaches,” Omega, vol. 115, p. 102770,
2023.
[25] J. Mohan, K. Lanka, and A. N. Rao, “A review of dynamic job shop scheduling tech-
niques,” Procedia Manufacturing, vol. 30, pp. 34–39, 2019.
[26] J. Branke, S. Nguyen, C. W. Pickardt, and M. Zhang, “Automated design of produc-
tion scheduling heuristics: A review,” IEEE Transactions on Evolutionary Computation,
vol. 20, no. 1, pp. 110–124, 2015.
[27] H. Ingimundardottir and T. P. Runarsson, “Discovering dispatching rules from data using
imitation learning: A case study for the job-shop problem,” Journal of Scheduling, vol. 21,
pp. 413–428, 2018.
[28] C. D. Geiger, R. Uzsoy, and H. Aytuğ, “Rapid modeling and discovery of priority dis-
patching rules: An autonomous learning approach,” Journal of Scheduling, vol. 9, pp.
7–34, 2006.
[29] J. C. Bean, “Genetic algorithms and random keys for sequencing and optimization,” ORSA
journal on computing, vol. 6, no. 2, pp. 154–160, 1994.
[30] I. Sabuncuoglu and M. Bayiz, “Job shop scheduling with beam search,” European Journal
of Operational Research, vol. 118, no. 2, pp. 390–412, 1999.
[31] M. Saidi-Mehrabad and P. Fattahi, “Flexible job shop scheduling with tabu search algo-
rithms,” The international journal of Advanced Manufacturing technology, vol. 32, pp.
563–570, 2007.
[32] J. Hakim, S. Rekiek, and K. Reklaoui, “Solving the job shop scheduling problem by the
multi-hybridization of swarm intelligence techniques,” International Journal of Advanced
Computer Science and Applications, vol. 13, no. 7, 2022.
[33] Z. Wang, J. Zhang, and S. Yang, “An improved particle swarm optimization algorithm for
dynamic job shop scheduling problems with random job arrivals,” Swarm and Evolution-
ary Computation, vol. 51, p. 100594, 2019.
[34] A. R. Da Silva, “Solving the job shop scheduling problem with ant colony optimization,”
arXiv preprint arXiv:2209.05284, 2022.
[35] S. Mirjalili and A. Lewis, “The whale optimization algorithm,” Advances in engineering
software, vol. 95, pp. 51–67, 2016.
[36] L. Wang, G. Zhou, Y. Xu, S. Wang, and M. Liu, “An effective artificial bee colony al-
gorithm for the flexible job-shop scheduling problem,” The International Journal of Ad-
vanced Manufacturing Technology, vol. 60, pp. 303–315, 2012.
[37] D. Pythaloka, A. T. Wibowo, and M. D. Sulistiyo, “Artificial fish swarm algorithm for
job shop scheduling problem,” in 2015 3rd International Conference on Information and
Communication Technology (ICoICT). IEEE, 2015, pp. 437–443.
[38] J. Zhang, G. Ding, Y. Zou, S. Qin, and J. Fu, “Review of job shop scheduling research and
its new perspectives under industry 4.0,” Journal of Intelligent Manufacturing, vol. 30, pp.
1809–1830, 2019.
[39] N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev, “Reinforcement learning for
combinatorial optimization: A survey,” Computers & Operations Research, vol. 134, p.
105400, 2021.
[40] B. M. Méndez-Hernández, E. D. Rodríguez-Bazan, Y. Martinez-Jimenez, P. Libin, and
A. Nowé, “A multi-objective reinforcement learning algorithm for jssp,” in Artificial Neu-
ral Networks and Machine Learning–ICANN 2019: Theoretical Neural Computation:
28th International Conference on Artificial Neural Networks, Munich, Germany, Septem-
ber 17–19, 2019, Proceedings, Part I 28. Springer, 2019, pp. 567–584.
[41] M. Zhang, Y. Lu, Y. Hu, N. Amaitik, and Y. Xu, “Dynamic scheduling method for job-
shop manufacturing systems by deep reinforcement learning with proximal policy opti-
mization,” Sustainability, vol. 14, no. 9, p. 5177, 2022.
[42] C.-L. Liu, C.-C. Chang, and C.-J. Tseng, “Actor-critic deep reinforcement learning for
solving job shop scheduling problems,” Ieee Access, vol. 8, pp. 71 752–71 762, 2020.
[43] Y. Turgut and C. E. Bozdag, “Deep q-network model for dynamic job shop schedul-
ing problem based on discrete event simulation,” in 2020 Winter Simulation Conference
(WSC). IEEE, 2020, pp. 1551–1559.
[44] H. Wang, B. R. Sarker, J. Li, and J. Li, “Adaptive scheduling for assembly job shop with
uncertain assembly times based on dual q-learning,” International Journal of Production
Research, vol. 59, no. 19, pp. 5867–5883, 2021.
[45] B. Luo, S. Wang, B. Yang, and L. Yi, “An improved deep reinforcement learning approach
for the dynamic job shop scheduling problem with random job arrivals,” in Journal of
Physics: Conference Series, vol. 1848, no. 1. IOP Publishing, 2021, p. 012029.
[46] Z. Liu, Y. Wang, X. Liang, Y. Ma, Y. Feng, G. Cheng, and Z. Liu, “A graph neural
networks-based deep q-learning approach for job shop scheduling problems in traffic man-
agement,” Information Sciences, vol. 607, pp. 1211–1223, 2022.
[47] J. Juros, M. Brcic, M. Koncic, and M. Kovac, “Exact solving scheduling problems accel-
erated by graph neural networks,” in 2022 45th Jubilee International Convention on Infor-
mation, Communication and Electronic Technology (MIPRO). IEEE, 2022, pp. 865–870.
[48] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey
on graph neural networks,” IEEE transactions on neural networks and learning systems,
vol. 32, no. 1, pp. 4–24, 2020.
[49] B. Roy and B. Sussmann, “Scheduling problems with disjunctive constraints,” Note ds,
vol. 9, 1964.
[50] K.-H. Ho, J.-Y. Cheng, J.-H. Wu, F. Chiang, Y.-C. Chen, Y.-Y. Wu, and I.-C. Wu, “Resid-
ual scheduling: A new reinforcement learning approach to solving job shop scheduling
problem,” IEEE Access, 2024.
[51] C.-L. Liu, C.-J. Tseng, and P.-H. Weng, “Dynamic job-shop scheduling via graph attention
networks and deep reinforcement learning,” IEEE Transactions on Industrial Informatics,
pp. 1–11, 2024.
[52] J.-P. Huang, L. Gao, and X.-Y. Li, “An end-to-end deep reinforcement learning method
based on graph neural network for distributed job-shop scheduling problem,” Expert Sys-
tems with Applications, vol. 238, p. 121756, 2024.
[53] K. Lei, P. Guo, W. Zhao, Y. Wang, L. Qian, X. Meng, and L. Tang, “A multi-action deep
reinforcement learning framework for flexible job-shop scheduling problem,” Expert Sys-
tems with Applications, vol. 205, p. 117796, 2022.
[54] M. Zhang, L. Wang, F. Qiu, and X. Liu, “Dynamic scheduling for flexible job shop with in-
sufficient transportation resources via graph neural network and deep reinforcement learn-
ing,” Computers & Industrial Engineering, vol. 186, p. 109718, 2023.
[55] W. Song, X. Chen, Q. Li, and Z. Cao, “Flexible job-shop scheduling via graph neural
network and deep reinforcement learning,” IEEE Transactions on Industrial Informatics,
vol. 19, no. 2, pp. 1600–1610, 2022.
[56] K. Bhatta and Q. Chang, “An integrated control strategy for simultaneous robot assign-
ment, tool change and preventive maintenance scheduling using heterogeneous graph neu-
ral network,” Robotics and Computer-Integrated Manufacturing, vol. 84, p. 102594, 2023.
[57] Y. Zhao, X. Luo, and Y. Zhang, “The application of heterogeneous graph neural network
and deep reinforcement learning in hybrid flow shop scheduling problem,” Computers &
Industrial Engineering, vol. 187, p. 109802, 2024.
[58] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional net-
works,” arXiv preprint arXiv:1609.02907, 2016.
[59] P. Casanova, A. R. P. Lio, and Y. Bengio, “Graph attention networks,” ICLR. Petar Velick-
ovic Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Liò and Yoshua Bengio,
2018.
[60] B. Xu, N. Wang, T. Chen, and M. Li, “Empirical evaluation of rectified activations in
convolutional network,” arXiv preprint arXiv:1505.00853, 2015.
[61] D.-A. Clevert, T. Unterthiner, and S. Hochreiter, “Fast and accurate deep network learning
by exponential linear units (elus),” arXiv preprint arXiv:1511.07289, 2015.
[62] J.Schulman, F.Wolski, P.Dhariwal, A.Radford, and O.Klimov, “Proximal policy optimiza-
tion algorithms. arxiv preprint arxiv:1707.06347.” 2017.
[63] R. Chen, W. Li, and H. Yang, “A deep reinforcement learning framework based on an
attention mechanism and disjunctive graph embedding for the job-shop scheduling prob-
lem,” IEEE Transactions on Industrial Informatics, vol. 19, no. 2, pp. 1322–1331, 2022.
[64] E. Taillard, “Benchmarks for basic scheduling problems,” european journal of operational
research, vol. 64, no. 2, pp. 278–285, 1993.
[65] E. Demirkol, S. Mehta, and R. Uzsoy, “Benchmarks for shop scheduling problems,” Eu-
ropean Journal of Operational Research, vol. 109, no. 1, pp. 137–141, 1998.