虛擬工作流約束的時(shí)間-精確率迭代規(guī)約優(yōu)化算法
doi: 10.11999/JEIT171038
-
(哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080) ②(哈爾濱理工大學(xué)機(jī)械動(dòng)力工程學(xué)院 哈爾濱 150080)
基金項(xiàng)目:
國(guó)家自然科學(xué)基金青年項(xiàng)目(61403109)
Virtual Workflow Constrained Time-accuracy Optimization Algorithm Scheduling by Iterative Reduction
-
(School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China)
Funds:
The National Natural Science Foundation of China (61403109)
-
摘要: 針對(duì)復(fù)雜產(chǎn)品生產(chǎn)業(yè)務(wù)調(diào)度這一問(wèn)題，該文運(yùn)用工作流技術(shù)并以完工時(shí)間為約束，提出一種虛擬迭代歸約算法，能較好地在完工時(shí)間約束下優(yōu)化生產(chǎn)精確率。通過(guò)將各制約任務(wù)抽象虛擬成一個(gè)虛擬節(jié)點(diǎn)，采用逆向迭代的求解方式，確定了一條兼顧完工時(shí)間與生產(chǎn)精確率的調(diào)度路徑。對(duì)比發(fā)現(xiàn)，虛擬迭代歸約算法對(duì)全局生產(chǎn)精確率有較大幅度的提高，且通過(guò)改變截止期、任務(wù)數(shù)等參數(shù)可以提高算法的效率。
-
關(guān)鍵詞:
- 生產(chǎn)調(diào)度 /
- 工作流 /
- 虛擬迭代 /
- 優(yōu)化精確率
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.-
Key words:
- Production scheduling /
- Workflow /
- Virtual iterative /
- Accuracy optimization
-
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. 馮復(fù)劍. 時(shí)間約束工作流的可調(diào)度性分析[J]. 計(jì)算機(jī)工程與應(yīng)用, 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. 武星, 卓少劍, 張武. 成本最優(yōu)化工作流技術(shù)驅(qū)動(dòng)的研發(fā)協(xié)同軟件即服務(wù)應(yīng)用[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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ì)算環(huán)境下的工作流雙向調(diào)度算法[J]. 計(jì)算機(jī)科學(xué), 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. 梁合蘭, 杜彥華, 李蘇劍. 時(shí)序約束下科學(xué)工作流的動(dòng)態(tài)調(diào)度研究[J]. 系統(tǒng)工程理論與實(shí)踐, 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. 曹斌, 王小統(tǒng), 熊麗榮, 等. 時(shí)間約束云工作流調(diào)度的粒子群搜索方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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. 劉中金, 卓子寒, 何躍鷹, 等. 一種基于動(dòng)態(tài)配額的虛擬網(wǎng)帶寬公平調(diào)度算法[J]. 電子與信息學(xué)報(bào), 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. -
計(jì)量
- 文章訪問(wèn)數(shù): 1487
- HTML全文瀏覽量: 187
- PDF下載量: 58
- 被引次數(shù): 0
下載:
