Workflow optimization algorithm based on virtualization and
nonlinear production quality under time constraints

doi:10.19682/j.cnki.1005-8885.2023.2016

中国邮电高校学报(英文) ›› 2023, Vol. 30 ›› Issue (4): 55-66.doi: 10.19682/j.cnki.1005-8885.2023.2016

• Artificial Intelligence • 上一篇下一篇

Workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints

Luo Zhiyong, Tan Shanxin, Xu Haifeng, Liu Xintong

School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China

收稿日期:2022-09-23 修回日期:2023-03-31 接受日期:2023-08-31 出版日期:2023-08-31 发布日期:2023-08-31
通讯作者: Luo Zhiyong, E-mail: luozhiyongemail@sina.com E-mail:luozhiyongemail@sina.com
基金资助:
This work was supported by Heilongjiang Provincial Natural Science Foundation of China (LH2021F030).

Workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints

Luo Zhiyong, Tan Shanxin, Xu Haifeng, Liu Xintong

School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China

Received:2022-09-23 Revised:2023-03-31 Accepted:2023-08-31 Online:2023-08-31 Published:2023-08-31
Contact: Luo Zhiyong, E-mail: luozhiyongemail@sina.com E-mail:luozhiyongemail@sina.com
Supported by:
This work was supported by Heilongjiang Provincial Natural Science Foundation of China (LH2021F030).

摘要/Abstract

摘要： Balancing time, cost, and quality is crucial in intelligent manufacturing. However, finding the optimal value of production parameters is a challengingnon-deterministic polynomial (NP)-hard problem. In the actual production process, the production process has the characteristics of multi-stage parallel. Therefore, aiming at the difficult problem of multi-stage nonlinear production process optimization, this paper proposes a workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints (T-OVQT). The algorithm proposed in this paper first abstracts the actual production process into a virtual workflow model, which is divided into three layers: The bottom production process collection layer, the middle layer of service node partial order composition layer, and the high level of virtual node collection layer. Then, the virtual technology is used to reconstruct the node set and divide the task interval. The optimal solution is obtained through inverse iterative normalization and forward scheduling, and the global optimal solution is obtained by algorithm integration. Experimental results demonstrate that this algorithm better meets actual production requirements than the traditional minimum critical path (MCP) algorithm.

关键词: work-flow, optimize scheduling, virtual node, production quality, virtual technology

Abstract: Balancing time, cost, and quality is crucial in intelligent manufacturing. However, finding the optimal value of production parameters is a challengingnon-deterministic polynomial (NP)-hard problem. In the actual production process, the production process has the characteristics of multi-stage parallel. Therefore, aiming at the difficult problem of multi-stage nonlinear production process optimization, this paper proposes a workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints (T-OVQT). The algorithm proposed in this paper first abstracts the actual production process into a virtual workflow model, which is divided into three layers: The bottom production process collection layer, the middle layer of service node partial order composition layer, and the high level of virtual node collection layer. Then, the virtual technology is used to reconstruct the node set and divide the task interval. The optimal solution is obtained through inverse iterative normalization and forward scheduling, and the global optimal solution is obtained by algorithm integration. Experimental results demonstrate that this algorithm better meets actual production requirements than the traditional minimum critical path (MCP) algorithm.

Key words: work-flow, optimize scheduling, virtual node, production quality, virtual technology

Luo Zhiyong, Tan Shanxin, Xu Haifeng, Liu Xintong. Workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints[J]. The Journal of China Universities of Posts and Telecommunications, 2023, 30(4): 55-66.

参考文献

References

[1] XIE Z Q, WANG Q. Flexible integrated scheduling algorithm based on reverse order layer priority. Journal of Electronics and Information Technology, 2022, 44(5): 1554 - 1562 (in Chinese).

[2] DOOSTALI S, BABAMIR S M, EINI M. CP-PGWO: Multi-objective workflow scheduling for cloud computing using critical path. Cluster Computing, 2021, 24(4): 3607 - 3627.

[3] ZHOU X M, ZHANG G X, SUN J, et al. Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based HEFT. Future Generation Computer Systems, 2019, 93: 278 - 289.

[4] GONG G L, DENG Q W, CHIONG R, et al. An effective memetic algorithm for multi-objective job-shop scheduling. Knowledge-Based Systems, 2019, 182: Article 104840.

[5] PRAKASH V, BAWA S, GARG L. Multi-dependency and time based resource scheduling algorithm for scientific applications in cloud computing. Electronics, 2021, 10(11): Article 1320.

[6] WU Q W, ISHIKAWA F, ZHU Q S, et al. Deadline-constrained cost optimization approaches for workflow scheduling in clouds. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(12): 3401 - 3412.

[7] MA X J, GAO H H, XU H H, et al. An IoT-based task scheduling optimization scheme considering the deadline and cost-aware scientific workflow for cloud computing. EURASIP Journal on Wireless Communications and Networking, 2019(1): Article 249.

[8] ZHOU N Q, LIN W W, FENG W, et al. Budget-deadline constrained approach for scientific workflows scheduling in a cloud environment. Cluster Computing, 2023, 26: 1737 - 1751.

[9] MBOULA J E N, KAMLA V C, DJAMEGNI C T. Cost-time trade-off efficient workflow scheduling in cloud. Simulation Modelling Practice and Theory, 2020, 103: Article 102107.

[10] DAN Y R, LIU G W, FU Y. Optimized flowshop scheduling for precast production considering process connection and blocking. Automation in Construction, 2021, 125: Article 103575.

[11] YUAN Y C, LI X P, WANG Q, et al. Deadline division-based heuristic for cost optimization in workflow scheduling. Information Sciences, 2009, 179(15): 2562 - 2575.

[12] ARABNEJAD V, BUBENDORFER K, NG B. Budget and deadline aware e-science workflow scheduling in clouds. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(1): 29 - 44.

[13] HUANG X B, YANG L X. A hybrid genetic algorithm for multi-objective flexible job shop scheduling problem considering transportation time. International Journal of Intelligent Computing and Cybernetics, 2019, 12(2): 154 - 174.

[14] HOSSEINZADEH M, GHAFOUR M Y, HAMA H K, et al. Multi-objective task and workflow scheduling approaches in cloud computing: A comprehensive review. Journal of Grid Computing, 2020, 18: 327 - 356.

[15] LIU C R, LI J X, LIU J, et al. A survey on dynamic multi-objective optimization. Chinese Journal of Computers, 2020, 43(7): 1246 - 1278 (in Chinese).

[16] HAN S F, ZHU K, ZHOU M C, et al. A novel multiobjective fireworks algorithm and its applications to imbalanced distance minimization problems. IEEE/CAA Journal of Automatica Sinica, 2022, 9(8): 1476 - 1489.

[17] ZHANG L X, ZHOU L Q, SALAH A. Efficient scientific workflow scheduling for deadline-constrained parallel tasks in cloud computing environments. Information Sciences, 2020, 531: 31 - 46.

[18] LIU G, WANG E, ZHANG F. Convergence analysis of job shop scheduling problem based on critical path. Computer Integrated Manufacturing Systems, 2014, 20(5): 1078 - 1087 (in Chinese).

[19] CAI Y J, WANG Q, CHENG S. Cloud workflow scheduling algorithm based on partial critical path and deadline distribution. Computer Applications and Software, 2019, 36(8): 220 - 229 (in Chinese).

[20] LUO Z Y, WANG J Y, XIE Z Q. Multi-objective optimization algorithm for non-linear manufacturing process based on three-tier virtual workflow model. Acta Automatica Sinica, 2022, 48(3): 896 - 908 (in Chinese).

[21] TAN W H, YUAN X F, WANG J L, et al. A fatigue-conscious dual resource constrained flexible job shop scheduling problem by enhanced NSGA-II: An application from casting workshop. Computers and Industrial Engineering, 2021, 160: Article 107557.

[22] LEI D M, LI M, WANG L. A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold. IEEE Transactions on Cybernetics, 2019, 49(3): 1097 - 1109.

[23] STRNAD D, KOHEK S. Constrained multi-objective optimization of simulated tree pruning with heterogeneous criteria. Applied Sciences, 2021, 11(22): Article 10781.

Workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints

Workflow optimization algorithm based on virtualization and nonlinear production quality under time constraints

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价