Resource Collaborative Integrated Scheduling Algorithm Considering Multi-process Equipment Weight
-
摘要: 针对多品种、小批量复杂产品综合调度研究中，没有考虑加工较多工序设备上的工序间调度空隙会对调度结果产生重要影响的问题，该文提出考虑多工序设备权重的资源协同综合调度算法。该算法在综合调度中首先提出多工序设备和工序权重值的定义，其次提出以权重值为主的调度策略，提高了工序纵向连续加工的紧密度；最后提出最佳调度时刻的调整策略，提高了工序横向并行优化的力度。实验结果表明，该算法在提高综合调度设备整体利用率和减少复杂产品时间成本等方面，具有更优性。Abstract: In order to solve the problem that scheduling gaps between processes on equipment with many processes will have important influence on scheduling results in the integrated scheduling research of multi-variety and small batch complex products, a resource cooperative integrated scheduling algorithm considering the weight of equipment with many processes is proposed. In the integrated scheduling, the definition of multi-process equipment and process weight value is proposed for the first time, and then the scheduling strategy based on weight value is proposed to improve the tightness of longitudinal continuous processing. Finally, the optimal scheduling time adjustment strategy is proposed to improve the intensity of horizontal parallel optimization. Experimental results show that the algorithm has better performance in improving the overall utilization rate of the integrated scheduling equipment and reducing the time cost of complex products.
-
Key words:
- Integrated scheduling /
- Resource collaboration /
- Equipment /
- Multi-process /
- Weight
-
表 1 考虑多工序设备权重的资源协同综合调度算法
Weight-value (A) 输入： Input S(A)，S(M)； 输入： Set(P) Compute Layerpriority to Ai; 输入： Set(M) Compute Machine to Mi; 输入： Set(C) Compute Constraint to Ai; 输入： Set(W) Compute Weight-value to Ai; 输出： Output Dispath(A) For each node Ai∈A do If unique Ai to Max(Pi) then dispath Ai ; Else if { If same Weight-value Ai then optimal scheduling time adjustment(Ai); Else if dispath Ai by Weight-value Descending order } End if If root node process Ai Exit; Else if i--; End if 
下载: 导出CSV
表 3 复杂产品A工序权重值统计
工序号 设备
优先级设备优先级数据标准化 层优
先级层优先级
数据标准化约束度 约束度数
据标准化权重值 最佳调度时刻 A1 3 1.063410138 1 –1.85933936 1 –0.729324957 –1.52525418 t=29 A2 2 –0.096673649 2 –1.183215957 5 2.771434838 1.491545233 t=28 A3 1 –1.256757436 3 –0.507092553 1 –0.729324957 –2.493174946 t=11 A4 3 1.063410138 3 –0.507092553 2 0.145864991 0.702182577 t=17 A5 3 1.063410138 3 –0.507092553 2 0.145864991 0.702182577 t=20 A6 1 –1.256757436 3 –0.507092553 1 –0.729324957 –2.493174946 t=0 A7 1 –1.256757436 4 0.169030851 2 0.145864991 –0.941861593 t=11 A8 2 –0.096673649 4 0.169030851 2 0.145864991 0.218222194 t=13 A9 1 –1.256757436 5 0.845154255 3 1.02105494 0.609451759 t=6 A10 3 1.063410138 5 0.845154255 1 –0.729324957 1.179239435 t=6 A11 2 –0.096673649 6 1.521277659 1 –0.729324957 0.695279052 t=0 A12 3 1.063410138 6 1.521277659 1 –0.729324957 1.855362839 t=0
下载: 导出CSV
表 4 复杂产品A调度过程
调度时刻 M1 设备 M2 设备 M3 设备 M4 设备 t=0～t=1 加工工序A11 – 加工工序A12 加工工序A6 t=1～t=6 – – 工序A12加工完毕 加工工序A6 t=6～t=8 – 加工工序A9 加工工序A10 工序A6加工完毕 t=8～t=11 – 工序A9加工完毕 加工工序A10 – t=11～t=13 – 加工工序A3 工序A10加工完毕 加工工序A7 t=13～t=17 加工工序A8 加工工序A3 – 工序A7加工完毕，
加工结束t=17～t=18 工序A8加工完毕 加工工序A3 加工工序A4 – t=18～t=20 – 工序A3加工完毕，
加工结束工序A4加工完毕 – t=20～t=28 – – 工序A5加工完毕 – t=28～t=29 工序A2加工完毕，加工结束 – – – t=29～t=30 – – 工序A1加工完毕，
加工结束–
下载: 导出CSV
表 5 前者小于后者时两种算法的设备利用率对比分析
M1
利用率(%)M1相对
提高率(%)设备总体
利用率(%)总体利用率
相对提高率(%)产品B
加工用时本文算法 59.3 20.3 60.9 20.6 27 关键设备工
序紧凑算法39 40.3 41
下载: 导出CSV
-
[1] 王卓昊, 杨冬菊, 徐晨阳. 基于ISE算法的分布式ETL任务调度策略研究[J]. 计算机科学, 2019, 46(12): 1–7. doi: 10.11896/jsjkx.190100023WANG Zhuohao, YANG Dongju, and XU Chenyang. Research on distributed ETL tasks scheduling strategy based on ISE algorithm[J]. Computer Science, 2019, 46(12): 1–7. doi: 10.11896/jsjkx.190100023 [2] 胡致远, 胡文前, 李香, 等. 面向业务可达性的广域工业互联网调度算法研究[J]. 电子与信息学报, 2021, 43(9): 2608–2616. doi: 10.11999/JEIT200583HU Zhiyuan, HU Wenqian, LI Xiang, et al. Research on wide area industrial internet scheduling algorithm based on service reachability[J]. Journal of Electronics &Information Technology, 2021, 43(9): 2608–2616. doi: 10.11999/JEIT200583 [3] 王萍, 陆岩, 王帅, 等. 一种基于预留-重用联合的C-V2X通信Q学习型半持续调度算法[J]. 电子与信息学报.待发表. doi: 10.11999/JEIT210543.WANG Ping, LU Yan, WANG Shuai, et al. A reservation and reuse combined Q-learning semi persistent scheduling for C-V2X communication[J]. Journal of Electronics & Information Technology. To be published. doi: 10.11999/JEIT210543. [4] WEN Hubin. On the innovative practice of intelligent manufacturing technology in precision mold design and manufacture[C]. 2021 8th International Conference on Machinery, Mechanics, Materials, and Computer Engineering, Huhhot, China, 2021(27): 82–85. doi:10.25236/MMMCE.2021. [5] 邓世龙, 赵士杰, 赵雪娇, 等. 多核并行实时仿真平台多任务调度管理系统研究与设计[C]. '21全国仿真技术学术会议论文集, 贵阳, 2021: 48–52.DENG Shilong, ZHAO Shijie, ZHAO Xuejiao, et al. The design of multi-task management system based on multi-core parallel real-time simulation platform[C]. Conference on '21 National Conference on Simulation Technology, Guiyang, China, 2021: 48–52. [6] SHI Hongyan and JING Dongxu. Research on the construction and key technologies of cloud manufacturing platform for intelligent manufacturing[C]. The 2021 10th International Conference on Applied Science, Engineering and Technology, Qingdao, China, 2021: 51–55. [7] 苏命峰, 王国军, 李仁发. 边云协同计算中基于预测的资源部署与任务调度优化[J]. 计算机研究与发展, 2021, 58(11): 2558–2570. doi: 10.7544/issn1000-1239.2021.20200621SU Mingfeng, WANG Guojun, and LI Renfa. Resource deployment with prediction and task scheduling optimization in edge cloud collaborative computing[J]. Journal of Computer Research and Development, 2021, 58(11): 2558–2570. doi: 10.7544/issn1000-1239.2021.20200621 [8] 唐伦, 魏延南, 谭颀, 等. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略[J]. 电子与信息学报, 2020, 42(5): 1244–1252. doi: 10.11999/JEIT190439TANG Lun, WEI Yannan, TAN Qi, et al. Joint congestion control and resource allocation dynamic scheduling strategy for network slices in heterogeneous cloud Raido access network[J]. Journal of Electronics &Information Technology, 2020, 42(5): 1244–1252. doi: 10.11999/JEIT190439 [9] 赵铖泽, 张延华, 李萌, 等. 无人机辅助的物联网系统中计算资源优化调度研究[C]. 第十四届全国信号和智能信息处理与应用学术会议论文集, 北京, 2021: 184–190.ZHAO Chengze, ZHANG Yanhua, LI Meng, et al. Computing resource optimization and allocation for internet of thing systems assisted by unmanned aerial vehicle[C]. The 14th National Conference on Signal and Intelligent Information Processing and Applications, Beijing, China, 2021: 184–190. [10] KHORSAND R and RAMEZANPOUR M. An energy-efficient task-scheduling algorithm based on a multi-criteria decision-making method in cloud computing[J]. International Journal of Communication Systems, 2020, 33(9): e4379. doi: 10.1002/dac.4379 [11] 唐红亮, 吴柏林, 胡旺, 等. 基于粒子群优化的地震应急物资多目标调度算法[J]. 电子与信息学报, 2020, 42(3): 737–745. doi: 10.11999/JEIT190277TANG Hongliang, WU Bolin, HU Wang, et al. Earthquake emergency resource multiobjective schedule algorithm based on particle swarm optimization[J]. Journal of Electronics &Information Technology, 2020, 42(3): 737–745. doi: 10.11999/JEIT190277 [12] DONG Hui. Research on the transformation and upgrading path of traditional industries based on intelligent manufacturing[C]. 2020 8th International Education, Economics, Social Science, Arts, Sports and Management Engineering Conference, Chengdu, China, 2020(64): 142–146. doi: 10.25236/IEESASM.2020.027. [13] 赵宝锋, 赵倩倩, 赵均, 等. 事件驱动的联产空分装置月调度系统[C]. 2020中国自动化大会(CAC2020)论文集, 上海, 2020: 290–295.ZHAO Baofeng, ZHAO Qianqian, ZHAO Jun, et al. Event-driven Monthly Scheduling System for Multiple Air Separation Units[C]. Conference on 2020 China Automation Conference (CAC2020), Shanghai, China, 2020: 290–295. [14] CHUA P C, MOON S K, NG Y T, et al. Prediction of production performance in smart manufacturing using multivariate adaptive regression spline[C]. ASME 2021 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Virtual, Online, 2021. [15] 李小林, 司佳佳, 尹传传, 等. 考虑工件释放时间和柔性维护的单机调度问题[J/OL]. 计算机集成制造系统. http://kns.cnki.net/kcms/detail/11.5946.TP.20210621.1722.004.html, 2021.LI Xiaolin, SI Jiajia, YIN Chuanchuan, et al. Single-machine scheduling problem considering jobs’ release times and flexible maintenances[J/OL]. Computer Integrated Manufacturing System. http://kns.cnki.net/kcms/detail/11.5946.TP.20210621.1722.004.html, 2021. [16] 谢志强. 工件间有约束的复杂产品工序调度研究[D]. [博士论文], 哈尔滨理工大学, 2009.XIE Zhiqiang. Study on operation scheduling of complex product with constraint among jobs[D]. [Ph. D. dissertation], Harbin University of Science and Technology, 2009. [17] XIE Zhiqiang, YANG Dan, MA Mingrui, et al. An improved artificial bee colony algorithm for the flexible integrated scheduling problem using networked devices collaboration[J]. International Journal of Cooperative Information Systems, 2020, 29(01n02): 2040003. doi: 10.1142/S0218843020400031. [18] GAO Yilong, XIE Zhiqiang, LIU Xinyang, et al. Integrated scheduling algorithm based on the priority constraint table for complex products with tree structure[J]. Advances in Mechanical Engineering, 2020, 12(12): 1–15. doi: 10.1177/1687814020985206 [19] 谢志强, 邵侠. 一种考虑资源状态动态反馈的云计算调度算法[J]. 北京理工大学学报, 2019, 39(6): 624–631,637. doi: 10.15918/j.tbit1001-0645.2019.06.012XIE Zhiqiang and SHAO Xia. A scheduling algorithm for the cloud computing system with the dynamical feedback of server state[J]. Transactions of Beijing Institute of Technology, 2019, 39(6): 624–631,637. doi: 10.15918/j.tbit1001-0645.2019.06.012 [20] 谢志强, 滕宇峥, 杨静. 紧密衔接工序组联动的综合调度算法[J]. 自动化学报, 2011, 37(3): 371–379. doi: 10.3724/SP.J.1004.2011.00371XIE Zhiqiang, TENG Yuzheng, and YANG Jing. Integrated scheduling algorithm with no-wait constraint operation group[J]. Acta Automatica Sinica, 2011, 37(3): 371–379. doi: 10.3724/SP.J.1004.2011.00371 [21] 谢志强, 张晓欢, 高一龙, 等. 考虑串行工序紧密度的择时综合调度算法[J]. 机械工程学报, 2018, 54(6): 191–202. doi: 10.3901/JME.2018.06.191XIE Zhiqiang, ZHANG Xiaohuan, GAO Yilong, et al. Time-selective integrated scheduling algorithm considering the compactness of serial processes[J]. Journal of Mechanical Engineering, 2018, 54(6): 191–202. doi: 10.3901/JME.2018.06.191 [22] 谢志强, 辛宇, 杨静. 基于设备空闲事件驱动的综合调度算法[J]. 机械工程学报, 2011, 47(11): 139–147. doi: 10.3901/JME.2011.11.139XIE Zhiqiang, XIN Yu, and YANG Jing. Integrated scheduling algorithm based on event-driven by machines' idle[J]. Journal of Mechanical Engineering, 2011, 47(11): 139–147. doi: 10.3901/JME.2011.11.139 [23] 谢志强, 辛宇, 杨静. 可回退抢占的设备驱动综合调度算法[J]. 自动化学报, 2011, 37(11): 1332–1343. doi: 10.3724/SP.J.1004.2011.01332XIE Zhiqiang, XIN Yu, and YANG Jing. Machine-driven integrated scheduling algorithm with rollback-preemptive[J]. Acta Automatica Sinica, 2011, 37(11): 1332–1343. doi: 10.3724/SP.J.1004.2011.01332 [24] 谢志强, 李树生, 刘胜辉. 关键设备工序紧凑的调度算法[J]. 哈尔滨理工大学学报, 2003, 8(1): 37–41,45. doi: 10.3969/j.issn.1007-2683.2003.01.011XIE Zhiqiang, LI Shusheng, and LIU Shenghui. A scheduling algorithm based on key equipment compact procedures[J]. Journal of Harbin University of Science and Technology, 2003, 8(1): 37–41,45. doi: 10.3969/j.issn.1007-2683.2003.01.011 [25] 谢志强, 郑翘, 刘胜辉. 关键设备工序紧凑的动态调度算法[J]. 哈尔滨理工大学学报, 2003, 8(2): 50–53. doi: 10.3969/j.issn.1007-2683.2003.02.016XIE Zhiqiang, ZHENG Qiao, and LIU Shenghui. A dynamic scheduling algorithm based on key equipment’s compact procedures[J]. Journal of Harbin University of Science and Technology, 2003, 8(2): 50–53. doi: 10.3969/j.issn.1007-2683.2003.02.016 [26] XIE Zhiqiang, YANG Guang, and TAN Guangyu. An algorithm of JSSP with dynamic collection of job with priority[C]. The International Technology and Innovation Conference 2006, Hangzhou, China, 2006: 398–402. [27] 谢志强, 杨静, 杨光, 等. 可动态生成具有优先级工序集的动态Job-Shop调度算法[J]. 计算机学报, 2008, 31(3): 502–508. doi: 10.3321/j.issn:0254-4164.2008.03.016XIE Zhiqiang, YANG Jing, YANG Guang, et al. Dynamic job-shop scheduling algorithm with dynamic set of operation having priority[J]. Chinese Journal of Computers, 2008, 31(3): 502–508. doi: 10.3321/j.issn:0254-4164.2008.03.016 [28] LUOR D C. A comparative assessment of data standardization on support vector machine for classification problems[J]. Intelligent Data Analysis, 2015, 19(3): 529–546. doi: 10.3233/IDA-150730 -
下载:
图(14) / 表(6)
计量
- 文章访问数: 887
- HTML全文浏览量: 454
- PDF下载量: 59
- 被引次数: 0
