首页 » 文章 » 文章详细信息
Computational Intelligence and Neuroscience Volume 2019 ,2019-07-10
Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional Transformation
Research Article
Zelin Zang 1 Wanliang Wang 1 Yuhang Song 2 Linyan Lu 3 Weikun Li 1 Yule Wang 1 Yanwei Zhao 1
Show affiliations
DOI:10.1155/2019/7172842
Received 2019-03-26, accepted for publication 2019-06-16, Published 2019-06-16
PDF
摘要

In this paper, a hybrid deep neural network scheduler (HDNNS) is proposed to solve job-shop scheduling problems (JSSPs). In order to mine the state information of schedule processing, a job-shop scheduling problem is divided into several classification-based subproblems. And a deep learning framework is used for solving these subproblems. HDNNS applies the convolution two-dimensional transformation method (CTDT) to transform irregular scheduling information into regular features so that the convolution operation of deep learning can be introduced into dealing with JSSP. The simulation experiments designed for testing HDNNS are in the context of JSSPs with different scales of machines and jobs as well as different time distributions for processing procedures. The results show that the MAKESPAN index of HDNNS is 9% better than that of HNN and the index is also 4% better than that of ANN in ZLP dataset. With the same neural network structure, the training time of the HDNNS method is obviously shorter than that of the DEEPRM method. In addition, the scheduler has an excellent generalization performance, which can address large-scale scheduling problems with only small-scale training data.

授权许可

Copyright © 2019 Zelin Zang et al. 2019
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

通讯作者

Wanliang Wang.College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310027, China, zjut.edu.cn.zjutwwl@zjut.edu.cn

推荐引用方式

Zelin Zang,Wanliang Wang,Yuhang Song,Linyan Lu,Weikun Li,Yule Wang,Yanwei Zhao. Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional Transformation. Computational Intelligence and Neuroscience ,Vol.2019(2019)

您觉得这篇文章对您有帮助吗?
分享和收藏
0

是否收藏?

参考文献
[1] D. J. M. R. Garey. (1979). Computers and Intercatability: A Guide to the Theory of NP-Completeness. DOI: 10.1007/s10845-008-0073-9.
[2] Y. Fu, J. Ding, H. Wang, J. Wang. et al.(2018). Two-objective stochastic flow-shop scheduling with deteriorating and learning effect in Industry 4.0-based manufacturing system. Applied Soft Computing Journal.68:847-855. DOI: 10.1007/s10845-008-0073-9.
[3] T. Jiang, C. Zhang. (2018). Application of grey wolf optimization for solving combinatorial problems: job shop and flexible job shop scheduling cases. IEEE Access.6:26231-26240. DOI: 10.1007/s10845-008-0073-9.
[4] J. Salamon, J. P. Bello. (2017). Deep convolutional neural networks and data augmentation for environmental sound classification. IEEE Signal Processing Letters.24(3):279-283. DOI: 10.1007/s10845-008-0073-9.
[5] J. Park, Y. Mei, S. Nguyen, G. Chen. et al.(2018). An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling. Applied Soft Computing Journal.63:72-86. DOI: 10.1007/s10845-008-0073-9.
[6] P. Azad, N. J. Navimipour. (2017). An energy-aware task scheduling in the cloud computing using a hybrid cultural and ant colony optimization algorithm. International Journal of Cloud Applications and Computing.7(4):20-40. DOI: 10.1007/s10845-008-0073-9.
[7] S. Lawrence. (1984). An Experimental Investigation of heuristic Scheduling Techniques. Supplement to Resource Constrained Project Scheduling. DOI: 10.1007/s10845-008-0073-9.
[8] A. Coates, A. Ng. The importance of encoding versus training with sparse coding and vector quantization. . DOI: 10.1007/s10845-008-0073-9.
[9] T. Yamada, R. Nakano. (1997). Job shop scheduling. IEEE Control Engineering Series,:134. DOI: 10.1007/s10845-008-0073-9.
[10] J. Adams, E. Balas, D. Zawack. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science.34(3):391-401. DOI: 10.1007/s10845-008-0073-9.
[11] G. R. Weckman, C. V. Ganduri, D. A. Koonce. (2008). A neural network job-shop scheduler. Journal of Intelligent Manufacturing.19(2):191-201. DOI: 10.1007/s10845-008-0073-9.
[12] M. Kurdi. (2016). An effective new island model genetic algorithm for job shop scheduling problem. Computers and Operations Research.67:132-142. DOI: 10.1007/s10845-008-0073-9.
[13] A. Krizhevsky, I. Sutskever, G. Hinton. ImageNet classification with deep convolutional neural networks. :1106-1114. DOI: 10.1007/s10845-008-0073-9.
[14] G. Marcus. (2018). Deep learning: A critical appraisal. . DOI: 10.1007/s10845-008-0073-9.
[15] I. González-Rodríguez, C. R. Vela, J. Puente. (2010). A genetic solution based on lexicographical goal programming for a multiobjective job shop with uncertainty. Journal of Intelligent Manufacturing.21(1):65-73. DOI: 10.1007/s10845-008-0073-9.
[16] M. A. F. Pérez, F. M. P. Raupp. (2016). A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem. Journal of Intelligent Manufacturing.27(2):409-416. DOI: 10.1007/s10845-008-0073-9.
[17] Y.-R. Shiue, R.-S. Guh, K.-C. Lee. (2011). Study of SOM-based intelligent multi-controller for real-time scheduling. Applied Soft Computing.11(8):4569-4580. DOI: 10.1007/s10845-008-0073-9.
[18] G. Metan, I. Sabuncuoglu, H. Pierreval. (2010). Real time selection of scheduling rules and knowledge extraction via dynamically controlled data mining. International Journal of Production Research.48(23):6909-6938. DOI: 10.1007/s10845-008-0073-9.
[19] M. Haddadzade, M. R. Razfar, M. H. Zarandi. (2014). Integration of process planning and job shop scheduling with stochastic processing time. International Journal of Advanced Manufacturing Technology.71(1–4):241-252. DOI: 10.1007/s10845-008-0073-9.
[20] T. Yang, J. C. Lu. (2010). A hybrid dynamic pre-emptive and competitive neural-network approach in solving the multi-objective dispatching problem for TFT-LCD manufacturing. International Journal of Production Research.48(16):4807-4828. DOI: 10.1007/s10845-008-0073-9.
[21] R. M. Karp, Y. Zhang. (1993). Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM.40(3):765-789. DOI: 10.1007/s10845-008-0073-9.
[22] H. M. Wagner. (1959). An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly.6(2):131-140. DOI: 10.1007/s10845-008-0073-9.
[23] L. Schrage. (1968). Letter to the editor–a proof of the optimality of the shortest remaining processing time discipline. Operations Research.16(3):687-690. DOI: 10.1007/s10845-008-0073-9.
[24] N. Sharma, H. Sharma, A. Sharma. (2018). Beer froth artificial bee colony algorithm for job-shop scheduling problem. Applied Soft Computing Journal.68:507-524. DOI: 10.1007/s10845-008-0073-9.
[25] . DOI: 10.1007/s10845-008-0073-9.
[26] M. Martí, A. Maki. (2017). A multitask deep learning model for real-time deployment in embedded systems. . DOI: 10.1007/s10845-008-0073-9.
[27] H. Fisher, G. L. Thompson. (1963). Probabilistic learning combinations of local job-shop scheduling rules. Industrial Scheduling.3(2):225-251. DOI: 10.1007/s10845-008-0073-9.
[28] D. A. Koonce, S.-C. Tsai. (2000). Using data mining to find patterns in genetic algorithm solutions to a job shop schedule. Computers & Industrial Engineering.38(3):361-374. DOI: 10.1007/s10845-008-0073-9.
[29] L. Tang, W. Liu, J. Liu. (2005). A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment. Journal of Intelligent Manufacturing.16(3):361-370. DOI: 10.1007/s10845-008-0073-9.
[30] K. H. Jin, M. T. McCann, E. Froustey, M. Unser. et al.(2017). Deep convolutional neural network for inverse problems in imaging. IEEE Transactions on Image Processing.26(9):4509-4522. DOI: 10.1007/s10845-008-0073-9.
[31] M. M. Nasiri, R. Yazdanparast, F. Jolai. (2017). A simulation optimisation approach for real-time scheduling in an open shop environment using a composite dispatching rule. International Journal of Computer Integrated Manufacturing.30(12):1239-1252. DOI: 10.1007/s10845-008-0073-9.
[32] P. J. Huber, E. Ronchetti. (2009). Robust statistics. Wiley Series in Probability and Statistics. DOI: 10.1007/s10845-008-0073-9.
[33] B. Waschneck, A. Reichstaller, L. Belzner. (2018). Optimization of global production scheduling with deep reinforcement learning. Procedia CIRP.72:1264-1269. DOI: 10.1007/s10845-008-0073-9.
[34] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng. et al.(2018). Learning scheduling algorithms for data processing clusters. . DOI: 10.1007/s10845-008-0073-9.
[35] J. Shahrabi, M. A. Adibi, M. Mahootchi. (2017). A reinforcement learning approach to parameter estimation in dynamic job shop scheduling. Computers and Industrial Engineering.110:75-82. DOI: 10.1007/s10845-008-0073-9.
[36] C. A. Secondary, M. M. Nasiri, S. Salesi, A. Rahbari. et al.(2000). Soft Computing A data mining approach for population-based methods to solve the JSSP. Soft Computing.11:1-16. DOI: 10.1007/s10845-008-0073-9.
[37] S. Mirshekarian, D. N. Šormaz. (2016). Correlation of job-shop scheduling problem features with scheduling efficiency. Expert Systems with Applications.62:131-147. DOI: 10.1007/s10845-008-0073-9.
[38] T. R. Ramanan, R. Sridharan, K. S. Shashikant, A. N. Haq. et al.(2011). An artificial neural network based heuristic for flow shop scheduling problems. Journal of Intelligent Manufacturing.22(2):279-288. DOI: 10.1007/s10845-008-0073-9.
[39] H. Mao, M. Alizadeh, I. Menache, S. Kandula. et al.Resource management with deep reinforcement learning. :50-56. DOI: 10.1007/s10845-008-0073-9.
[40] M. A. Adibi, J. Shahrabi. (2014). A clustering-based modified variable neighborhood search algorithm for a dynamic job shop scheduling problem. International Journal of Advanced Manufacturing Technology.70(9–12):1955-1961. DOI: 10.1007/s10845-008-0073-9.
[41] A. Yahyaoui, N. Fnaiech, F. Fnaiech. (2011). A suitable initialization procedure for speeding a neural network job-shop scheduling. IEEE Transactions on Industrial Electronics.58(3):1052-1060. DOI: 10.1007/s10845-008-0073-9.
[42] P. Geurts, D. Ernst, L. Wehenkel. (2006). Extremely randomized trees. Machine Learning.63(1):3-42. DOI: 10.1007/s10845-008-0073-9.
[43] L. Asadzadeh. (2015). A local search genetic algorithm for the job shop scheduling problem with intelligent agents. Computers & Industrial Engineering.85:376-383. DOI: 10.1007/s10845-008-0073-9.
[44] V. Podgorelec, M. Zorman. (2015). Decision tree learning. Encyclopedia of Complexity and Systems Science. DOI: 10.1007/s10845-008-0073-9.
[45] S. S. S. Kruthiventi, K. Ayush, R. V. Babu. (2017). DeepFix: a fully convolutional neural network for predicting human eye fixations. IEEE Transactions on Image Processing.26(9):4446-4456. DOI: 10.1007/s10845-008-0073-9.
[46] X. Chen, X. Hao, H. W. Lin, T. Murata. et al.Rule driven multi objective dynamic scheduling by data envelopment analysis and reinforcement learning. :396-401. DOI: 10.1007/s10845-008-0073-9.
[47] N. S. Altman. (1992). An introduction to kernel and nearest-neighbour nonparametric regression. American Statistician.46(3):175-185. DOI: 10.1007/s10845-008-0073-9.
[48] P. Murugan. (2017). Feed forward and backward run in deep convolution neural network. . DOI: 10.1007/s10845-008-0073-9.
[49] F. Zhao, J. Tang, J. Wang. (2014). An improved particle swarm optimization with decline disturbance index (DDPSO) for multi-objective job-shop scheduling problem. Computers & Operations Research.45:38-50. DOI: 10.1007/s10845-008-0073-9.
[50] J. Jin, A. Dundar, E. Culurciello. (2014). Flattened convolutional neural networks for feedforward acceleration. . DOI: 10.1007/s10845-008-0073-9.
[51] B. Peng, Z. Lü, T. C. E. Cheng. (2015). A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers & Operations Research.53:154-164. DOI: 10.1007/s10845-008-0073-9.
[52] E. G. Coffman. (1976). Computer and Job Shop Scheduling Theory. DOI: 10.1007/s10845-008-0073-9.
[53] C. Cortes, V. Vapnik. (1995). Support-vector networks. Machine Learning.20(3):273-297. DOI: 10.1007/s10845-008-0073-9.
[54] A. Maroosi, R. C. Muniyandi, E. Sundararajan, A. M. Zin. et al.(2016). A parallel membrane inspired harmony search for optimization problems: a case study based on a flexible job shop scheduling problem. Applied Soft Computing Journal.49:120-136. DOI: 10.1007/s10845-008-0073-9.
[55] (2019). ZLP problem set. . DOI: 10.1007/s10845-008-0073-9.
文献评价指标
浏览 11次
下载全文 0次
评分次数 0次
用户评分 0.0分
分享 0次