虚拟工作流约束的时间-精确率迭代规约优化算法

罗智勇; 朱梓豪; 尤波; 刘嘉辉

doi:10.11999/JEIT171038

虚拟工作流约束的时间-精确率迭代规约优化算法

doi: 10.11999/JEIT171038

罗智勇^{*①②朱梓豪},
朱梓豪¹,
尤波,
刘嘉辉¹

(哈尔滨理工大学计算机科学与技术学院哈尔滨 150080) ②(哈尔滨理工大学机械动力工程学院哈尔滨 150080)

基金项目:

国家自然科学基金青年项目(61403109)

计量
- 文章访问数: 1417
- HTML全文浏览量: 167
- PDF下载量: 58
- 被引次数: 0
出版历程
- 收稿日期: 2017-11-03
- 修回日期: 2018-04-16
- 刊出日期: 2018-08-19

Virtual Workflow Constrained Time-accuracy Optimization Algorithm Scheduling by Iterative Reduction

LUO Zhiyong^{*①②朱梓豪},
ZHU Zihao¹,
YOU Bo,
LIU Jiahui¹

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

Funds:

The National Natural Science Foundation of China (61403109)

摘要

摘要: 针对复杂产品生产业务调度这一问题，该文运用工作流技术并以完工时间为约束，提出一种虚拟迭代归约算法，能较好地在完工时间约束下优化生产精确率。通过将各制约任务抽象虚拟成一个虚拟节点，采用逆向迭代的求解方式，确定了一条兼顾完工时间与生产精确率的调度路径。对比发现，虚拟迭代归约算法对全局生产精确率有较大幅度的提高，且通过改变截止期、任务数等参数可以提高算法的效率。
- 生产调度 /
- 工作流 /
- 虚拟迭代 /
- 优化精确率
Abstract: For the problem of the production of complex operations, this paper uses workflow technology and takes the completion time as constraint, and proposes a Virtual Iterative Reduction Algorithm (VIRA) to achieve better production accuracy in the constraint completion time. By virtualizing tasks in mutual constraint into a virtual node, the algorithm uses inverse iterative way to determine a path that completion time and production accuracy get balance. By comparison, the virtual iterative reduction algorithm can increase the production accuracy in the constraint completion time, and it is found to improve the accuracy of the algorithm by changing the deadline, the number of tasks and other parameters.
- Production scheduling /
- Workflow /
- Virtual iterative /
- Accuracy optimization

HTML全文

参考文献(14)

DE P, DUNNE E J, GHOSH J B, et al. Complexity of the discrete time-cost trade-off problem for project networks[J]. Operations Research, 1997, 45(2): 302-306.　doi: 10.1287/ opre.45.2.302.

KUMAR A, DIJKMAN R, and SONG M. Optimal resource assignment in workflows for maximizing cooperation[C]. 11th International Conference, BPM 2013, Beijing, China, 2013: 26-30. doi: 10.1007/978-3-642-40176-3_20.

BUYYA R, GIDDY J, and ABRAMSON D. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications [C]. Proceedings of the 2nd International Workshop on Active Middleware Services, Pittsburgh, USA, 2000: 221-230. doi: 10.1007/978-1-4419-8648-1_19.

DELDARI A, NAGHIBZADEH M, and ABRISHAMI S. CCA: A deadline-constrained workflow scheduling algorithm for multicore resources on the cloud[J]. The Journal of Supercomputing, 2017, 73(2): 756-781. doi: 10.1007/s11227- 016-1789-5.

ALKHANAK E N, LEE S P, REZAEI R, et al. Cost optimization approaches for scientific workflow scheduling in cloud and grid computing: A review, classifications, and open issues[J]. Journal of Systems and Software, 2016, 133: 1-26. doi: 10.1016/j.jss.2015.11.023.

VIRIYAPANT K and SMANCHAT S. A deadline- constrained scheduling for dynamic multi-instances parameter sweep workflow[C]. 2016 IEEE/ACIS 15th International Conference on Computer and Information Science (ICIS), Okayama, Japan, 2016: 1-6. doi: 10.1109/ ICIS.2016.7550820.

ARABNEJA H, BARBOSA J G, and PRODAN R. Low-time complexity budget-deadline constrained workflow scheduling on heterogeneous resources[J]. Future Generation Computer Systems, 2016, 55: 29-40. doi: 10.1016/j.future.2015.07.021.

VERMA A and KAUSHAL S. Cost-time efficient scheduling plan for executing workflows in the cloud[J]. Journal of Grid Computing, 2015, 13(4): 1-12. doi: 10.1007/s10723-015- 9344-9.

冯复剑. 时间约束工作流的可调度性分析[J]. 计算机工程与应用, 2016, 52(12): 26-30. doi: 10.3778/j.issn.1002-8331.1511- 0313. FENG Fujian. Schedulability analysis of timing constraint workflows[J]. Computer Engineering and Applications, 2016, 52(12): 26-30. doi: 10.3778/j.issn.1002-8331.1511-0313.

武星, 卓少剑, 张武. 成本最优化工作流技术驱动的研发协同软件即服务应用[J]. 计算机集成制造系统, 2013, 19(8): 1748-1754. WU Xing, ZHUO Shaojian, and ZHANG Wu. Cost optimization workflow-driven SssS for collaborative research and development[J]. Computer Integrated Manufacturing Systems, 2013, 19(8): 1748-1754.

张佩云, 凤麒. 一种云计算环境下的工作流双向调度算法[J]. 计算机科学, 2015, 42(11): 425-430. ZHANG Peiyun and FENG Qi. Method of workflow bi-directional scheduling in cloud computing environment[J]. Computer Science, 2015, 42(11): 425-430.

梁合兰, 杜彦华, 李苏剑. 时序约束下科学工作流的动态调度研究[J]. 系统工程理论与实践, 2015(9): 2410-2421. doi: 10.12011/1000-6788(2015)9-2410. LIANG Helan, DU Yanhua, and LI Sujian. Research on dynamic scheduling of scientific workflows with temporal constraints [J]. Systems Engineering-Theory Practice, 2015(9): 2410-2421. doi: 10.12011/1000-6788(2015)9-2410.

曹斌, 王小统, 熊丽荣, 等. 时间约束云工作流调度的粒子群搜索方法[J]. 计算机集成制造系统, 2016, 22(2): 372-380. CAO Bin, WANG Xiaotong, XIONG Lirong, et al. Searching method for particle swarm optimization of cloud workflow scheduling with time constraint[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 372-380.

刘中金, 卓子寒, 何跃鹰, 等. 一种基于动态配额的虚拟网带宽公平调度算法[J]. 电子与信息学报, 2016, 38(10): 2654-2659. doi: 10.11999/JEIT151485. LIU Zhongjin, ZHUO Zihan, HE Yaoying, et al. Dynamical weighted scheduling algorithm supporting fair bandwidth allocation of virtual networks[J]. Journal of Electronics Information Technology, 2016, 38(10): 2654-2659. doi: 10.11999/ JEIT151485.

施引文献

资源附件(0)

访问统计