Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning

References

• Adams, Joseph, Egon Balas, and Daniel Zawack. 1988. “The Shifting Bottleneck Procedure for Job Shop Scheduling.” Management Science 34 (3): 391–401. doi: 10.1287/mnsc.34.3.391
   Web of Science ®Google Scholar
• Applegate, David, and William Cook. 1991. “A Computational Study of the Job-shop Scheduling Problem.” ORSA Journal on Computing 3 (2): 149–156. doi: 10.1287/ijoc.3.2.149
   Google Scholar
• Aydin, M. Emin, and Ercan Öztemel. 2000. “Dynamic Job-shop Scheduling Using Reinforcement Learning Agents.” Robotics and Autonomous Systems 33 (2–3): 169–178. doi: 10.1016/S0921-8890(00)00087-7
   Web of Science ®Google Scholar
• Battaglia, Peter W., Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, et al. 2018. “Relational Inductive Biases, Deep Learning, and Graph Networks.” arXiv preprint arXiv:1806.01261.
   Google Scholar
• Baykasoğlu, Adil, and Fatma S. Karaslan. 2017. “Solving Comprehensive Dynamic Job Shop Scheduling Problem by Using a Grasp-based Approach.” International Journal of Production Research 55 (11): 3308–3325. doi: 10.1080/00207543.2017.1306134
   Web of Science ®Google Scholar
• Caserta, Marco, and Stefan Voß. 2009. “Metaheuristics: Intelligent Problem Solving.” In Matheuristics, 1–38. Springer.
   Google Scholar
• Chen, Ruey-Maw, and Yueh-Min Huang. 2001. “Competitive Neural Network to Solve Scheduling Problems.” Neurocomputing 37 (1–4): 177–196. doi: 10.1016/S0925-2312(00)00344-1
   Web of Science ®Google Scholar
• Demirkol, Ebru, Mehta Sanjay, and Uzsoy Reha. 1998. “Benchmarks for shop scheduling problems.” European Journal of Operational Research 109: 137–141. doi: 10.1016/S0377-2217(97)00019-2
   Web of Science ®Google Scholar
• Fisher, Henry. 1963. “Probabilistic Learning Combinations of Local Job-shop Scheduling Rules.” Industrial Scheduling: 225–251.
   Google Scholar
• Gabel, Thomas, and Martin Riedmiller. 2008. “Adaptive Reactive Job-shop Scheduling with Reinforcement Learning Agents.” International Journal of Information Technology and Intelligent Computing 24 (4): 14–18.
   Google Scholar
• Gabel, Thomas, and Martin Riedmiller. 2012. “Distributed Policy Search Reinforcement Learning for Job-shop Scheduling Tasks.” International Journal of Production Research 50 (1): 41–61. doi: 10.1080/00207543.2011.571443
   Web of Science ®Google Scholar
• Garey, Michael R., David S. Johnson, and Ravi Sethi. 1976. “The Complexity of Flowshop and Jobshop Scheduling.” Mathematics of Operations Research 1 (2): 117–129. doi: 10.1287/moor.1.2.117
   Google Scholar
• Geiger, Christopher D., Karl G. Kempf, and Reha Uzsoy. 1997. “A Tabu Search Approach to Scheduling An Automated Wet Etch Station.” Journal of Manufacturing Systems 16 (2): 102–116. doi: 10.1016/S0278-6125(97)85674-9
   Web of Science ®Google Scholar
• Glorot, Xavier, Antoine Bordes, and Yoshua Bengio. 2011. “Deep Sparse Rectifier Neural Networks.” In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 315–323.
   Google Scholar
• Google or tools. 2019. version 7.3. https://github.com/google/or-tools.
   Google Scholar
• Gupta, Amit Kumar, and Appa Iyer Sivakumar. 2006. “Job Shop Scheduling Techniques in Semiconductor Manufacturing.” The International Journal of Advanced Manufacturing Technology 27 (11-12): 1163–1169. doi: 10.1007/s00170-004-2296-z
   Web of Science ®Google Scholar
• Hill, Ashley, Antonin Raffin, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, Rene Traore, Prafulla Dhariwal, et al. 2018. “Stable Baselines.” https://github.com/hill-a/stable-baselines.
   Google Scholar
• Holthaus, Oliver, and Chandrasekharan Rajendran. 1997. “Efficient Dispatching Rules for Scheduling in a Job Shop.” International Journal of Production Economics 48 (1): 87–105. doi: 10.1016/S0925-5273(96)00068-0
   Web of Science ®Google Scholar
• Kaempfer, Yoav, and Lior Wolf. 2018. “Learning the Multiple Traveling Salesmen Problem With Permutation Invariant Pooling Networks.” arXiv preprint arXiv:1803.09621.
   Google Scholar
• Khalil, Elias, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. “Learning Combinatorial Optimization Algorithms Over Graphs.” Advances in Neural Information Processing Systems 30: 6348–6358.
   Google Scholar
• Kingma, Diederik P., and Jimmy Ba. 2014. “Adam: A Method for Stochastic Optimization.” arXiv preprint arXiv:1412.6980.
   Google Scholar
• Kool, Wouter, Herke van Hoof, and Max Welling. 2018. “Attention, Learn to Solve Routing Problems!” arXiv preprint arXiv:1803.08475.
   Google Scholar
• Lawrence, S. 1984. Resouce Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (supplement). Pittsburgh, PA: Graduate School of Industrial Administration, Carnegie-Mellon University.
   Google Scholar
• Li, Zhuwen, Qifeng Chen, and Vladlen Koltun. 2018. “Combinatorial Optimization With Graph Convolutional Networks and Guided Tree Search.” In Advances in Neural Information Processing Systems, 539–548.
   Google Scholar
• Lin, Chun-Cheng, Der-Jiunn Deng, Yen-Ling Chih, and Hsin-Ting Chiu. 2019. “Smart Manufacturing Scheduling with Edge Computing Using Multi-class Deep Q Network.” IEEE Transactions on Industrial Informatics 15: 4276–4284. doi: 10.1109/TII.2019.2908210
   Web of Science ®Google Scholar
• Lomnicki, Z. A. 1965. “A “branch-and-bound” Algorithm for the Exact Solution of the Three-machine Scheduling Problem.” Journal of the Operational Research Society 16 (1): 89–100. doi: 10.1057/jors.1965.7
   Google Scholar
• Manne, Alan S. 1960. “On the Job-shop Scheduling Problem.” Operations Research 8 (2): 219–223. doi: 10.1287/opre.8.2.219
   Web of Science ®Google Scholar
• Mittal, Akash, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2019. “Learning Heuristics Over Large Graphs Via Deep Reinforcement Learning.” arXiv preprint arXiv:1903.03332.
   Google Scholar
• Mnih, Volodymyr, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013. “Playing Atari With Deep Reinforcement Learning.” arXiv preprint arXiv:1312.5602.
   Google Scholar
• Ong, Chung Sin. 2013. “Hybrid Genetic Algorithm With Multi-Parents Recombination for Job Shop Scheduling Problems/Ong Chung Sin.” PhD thesis, University of Malaya.
   Google Scholar
• Ozturk, Gurkan, Ozan Bahadir, and Aydin Teymourifar. 2019. “Extracting Priority Rules for Dynamic Multi-objective Flexible Job Shop Scheduling Problems Using Gene Expression Programming.” International Journal of Production Research 57 (10): 3121–3137. doi: 10.1080/00207543.2018.1543964
   Web of Science ®Google Scholar
• Panwalkar, Shrikant S., and Wafik Iskander. 1977. “A Survey of Scheduling Rules.” Operations Research 25 (1): 45–61. doi: 10.1287/opre.25.1.45
   Web of Science ®Google Scholar
• Park, Junyoung, and Jinkyoo Park. 2019. “Physics-induced Graph Neural Network: An Application to Wind-farm Power Estimation.” Energy 187: 115883.
   Web of Science ®Google Scholar
• Pinedo, M. 2008. “Scheduling: Theory, Algorithms, and Systems Multi-Coloring”.
   Google Scholar
• Prates, Marcelo, Pedro H. C. Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y. Vardi. 2019. “Learning to Solve np-Complete Problems: A Graph Neural Network for Decision tsp.” In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 4731–4738.
   Google Scholar
• Roy, Bernard, and B. Sussmann. 1964. “Scheduling Problems with Disjunctive Constraints.” Note ds 9.
   Google Scholar
• Sanchez-Gonzalez, Alvaro, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. 2018. “Graph Networks as Learnable Physics Engines for Inference and Control.” arXiv preprint arXiv:1806.01242.
   Google Scholar
• Schulman, John, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. 2015. “Trust Region Policy Optimization.” In International Conference on Machine Learning, 1889–1897.
   Google Scholar
• Schulman, John, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. “Proximal Policy Optimization Algorithms.” arXiv preprint arXiv:1707.06347.
   Google Scholar
• Seo, Sungyong, and Yan Liu. 2019. “Differentiable Physics-Informed Graph Networks.” arXiv preprint arXiv:1902.02950.
   Google Scholar
• Storer, Robert H., S. David Wu, and Renzo Vaccari. 1992. “New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling.” Management Science 38 (10): 1495–1509. doi: 10.1287/mnsc.38.10.1495
   Web of Science ®Google Scholar
• Sutton, Richard S, and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. Cambridge, MA: MIT Press.
   Google Scholar
• Sutton, Richard S., Doina Precup, and Satinder Singh. 1999. “Between Mdps and Semi-mdps: A Framework for Temporal Abstraction in Reinforcement Learning.” Artificial Intelligence 112 (1–2): 181–211. doi: 10.1016/S0004-3702(99)00052-1
   Web of Science ®Google Scholar
• Taillard, Eric. 1993. “Benchmarks for Basic Scheduling Problems.” European Journal of Operational Research 64 (2): 278–285. doi: 10.1016/0377-2217(93)90182-M
   Web of Science ®Google Scholar
• Tay, Joc Cing, and Nhu Binh Ho. 2007. “Designing Dispatching Rules to Minimize Total Tardiness.” In Evolutionary Scheduling, 101–124. Springer.
   Google Scholar
• Tay, Joc Cing, and Nhu Binh Ho. 2008. “Evolving Dispatching Rules Using Genetic Programming for Solving Multi-objective Flexible Job-shop Problems.” Computers & Industrial Engineering 54 (3): 453–473. doi: 10.1016/j.cie.2007.08.008
   Web of Science ®Google Scholar
• van Hoorn, Jelke J. 2018. “The Current State of Bounds on Benchmark Instances of the Job-shop Scheduling Problem.” Journal of Scheduling 21 (1): 127–128. doi: 10.1007/s10951-017-0547-8
   Web of Science ®Google Scholar
• Wang, Tingwu, Renjie Liao, Jimmy Ba, and Sanja Fidler. 2018. “Nervenet: Learning structured policy with graph neural networks.” International Conference on Learning Representations.
   Google Scholar
• Weckman, Gary R., Chandrasekhar V. Ganduri, and David A. Koonce. 2008. “A Neural Network Job-shop Scheduler.” Journal of Intelligent Manufacturing 19 (2): 191–201. doi: 10.1007/s10845-008-0073-9
   Web of Science ®Google Scholar
• Willems, T. M., and L. E. M. W. Brandts. 1995. “Implementing Heuristics As An Optimization Criterion in Neural Networks for Job-shop Scheduling.” Journal of Intelligent Manufacturing 6 (6): 377–387. doi: 10.1007/BF00124064
   Web of Science ®Google Scholar
• Xinyi, Zhang, and Lihui Chen. 2018. “Capsule graph neural network.” International conference on learning representations.
   Google Scholar
• Xu, Keyulu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. “How Powerful are Graph Neural Networks?” arXiv preprint arXiv:1810.00826.
   Google Scholar
• Yamada, Takeshi. 2003. “Studies on Metaheuristics for Jobshop and Flowshop Scheduling Problems”.
   Google Scholar
• Yamada, Takeshi, and Ryohei Nakano. 1992. “A Genetic Algorithm Applicable to Large-Scale Job-Shop Problems.” In PPSN, Vol. 2, 281–290.
   Google Scholar
• Yang, Zhilin, Jake Zhao, Bhuwan Dhingra, Kaiming He, William W. Cohen, Ruslan Salakhutdinov, and Yann LeCun. 2018. “Glomo: Unsupervisedly Learned Relational Graphs as Transferable Representations.” arXiv preprint arXiv:1806.05662.
   Google Scholar
• Yim, Seong Jin, and Doo Yong Lee. 1999. “Scheduling Cluster Tools in Wafer Fabrication Using Candidate List and Simulated Annealing.” Journal of Intelligent Manufacturing 10 (6): 531–540. doi: 10.1023/A:1008904604531
   Web of Science ®Google Scholar