基于虚拟归约工作流三层决策模型的时间-质量优化算法
|
摘要
工作流的调度问题因为含有多个目标的限制因素,属于非确定性(NP)问题.本文通过将工作流模型分层,提出一种优化调度算法.算法分为两大阶段,检测阶段通过循环加工提高生产质量;虚拟阶段将各制约节点不断迭代虚拟成一个虚拟节点,将服务抽象化,最终简化服务的选择问题.对比发现,在相同实验环境下,本算法相比传统最小关键路径算法具有一定优越性.
The scheduling of workflows is a well-known non-deterministic( NP) problem because it contains multiple targets constraints. This paper proposed a time-quality optimization scheduling algorithm by layering the workflow model into three layers, such as mapping layer,dominant layer, and decision layer, respectively. The algorithm has two stages, stage one is called detection, it can improve the production quality by means of cycle machining in this stage; another stage is virtualization,which uses iterative way to virtualize nodes in mutual constraints into a new virtual node, abstracts the services,and simplifies the selection of services eventually. In comparison, the proposed algorithm was more effective than the traditional minimum critical path algorithm in the same experimental environment.
The scheduling of workflows is a well-known non-deterministic( NP) problem because it contains multiple targets constraints. This paper proposed a time-quality optimization scheduling algorithm by layering the workflow model into three layers, such as mapping layer,dominant layer, and decision layer, respectively. The algorithm has two stages, stage one is called detection, it can improve the production quality by means of cycle machining in this stage; another stage is virtualization,which uses iterative way to virtualize nodes in mutual constraints into a new virtual node, abstracts the services,and simplifies the selection of services eventually. In comparison, the proposed algorithm was more effective than the traditional minimum critical path algorithm in the same experimental environment.
引文
[1]LIU J,PACITTI E,PATRICK V,et al. A survey of data-intensive scientific w orkflow management[J]. Journal of Grid Computing,2014,13(4):457-493.
[2] VERMA A,KAUSHAL S. Bi-criteria priority based particle sw arm optimization w orkflow scheduling algorithm for cloud[A]. Recent Advances in Engineering and Computational Sciences(RAECS)[C]. Chandigarh India:IEEE,2014. 1-6.
[3] ARABNEJAD H,BARBOSA J G. A budget constrained scheduling algorithm for w orkflow applications[J]. Journal of Grid Computing,2014,13(4):665-679.
[4]KIANPISHEH S,CHARKARI N M,KARGAHI M. Reliability-driven scheduling of time/cost-constrained grid w orkflow s[J]. Future Generation Computer Sytems,2016,55:1-16.
[5]ZENG L,VEERAVALLI B,ZOMAYA A Y. An integrated task computation and data management scheduling strategy for w orkflow applications in cloud environments[J]. Journal of Netw ork and Computer Applications,2015,50:39-48.
[6]MACIEJ M,KAMIL F,MARIAN B,et al. Cost optimization of execution of multi-level deadline-constrained scientific w orkflow s on clouds[A]. Parallel Processing and Applied M athematics[C]. Berlin:Springer,2014,8384:251-260.
[7]KIM S H,JOO K N,HA Y G,et al. A phased workflow scheduling scheme w ith task division policy in cloud broker[A]. International Conference on Cloudcomp[C]. Berlin:Springer,2014,142:76-86.
[8] STAVRINIDES G L,KARATZA H D. A cost-effective and qos-aw are approach to scheduling real-time w orkflow applications in paas and saas clouds[A]. Proceedings of the 3rd International Conference on Future Internet of Things and Cloud,Rome[C]. US:ACM,2015. 231-239.
[9] ARABNEJAD V,BUBENDORFER K. Cost effective and deadline constrained scientific w orkflow scheduling for commercial clouds[A]. IEEE 14th International Symposium on Netw ork Computing and Applications[C].,Cambridge,M A:IEEE,2015. 106-113.
[10]沈虹,李小平.带准备时间和截止期约束的云服务工作流调度算法[J].通信学报,2015,36(6):187-196.SHEN Hong,LI Xiao-ping. Algorithm for the cloud service w orkflow scheduling w ith setup time and deadline constraints[J]. Journal on Communications,2015,36(6):187-196.(in Chinese)
[11]苑迎春,李小平,王茜,等.基于优先级规则的网格工作流调度[J].电子学报,2009,37(7):1457-1464.YUAN Ying-chun,LI Xiao-ping,WANG Qian,et al.Gridw orkflow s schedule based on priority rules[J]. Acta Electronica Sinica,2009,37(7):1457-1464.(in Chinese)
[12]肖鹏,胡志刚.截止时间约束下独立网格任务的协同调度模型[J].电子学报,2011,39(8):1852-1857.XIAO Peng,HU Zhi-gang. Co-scheduling model for independent tasks w ith deadline constraint in computational grid[J]. Acta Electronica Sinica,2011,39(8):1852-1857.(in Chinese)
[2] VERMA A,KAUSHAL S. Bi-criteria priority based particle sw arm optimization w orkflow scheduling algorithm for cloud[A]. Recent Advances in Engineering and Computational Sciences(RAECS)[C]. Chandigarh India:IEEE,2014. 1-6.
[3] ARABNEJAD H,BARBOSA J G. A budget constrained scheduling algorithm for w orkflow applications[J]. Journal of Grid Computing,2014,13(4):665-679.
[4]KIANPISHEH S,CHARKARI N M,KARGAHI M. Reliability-driven scheduling of time/cost-constrained grid w orkflow s[J]. Future Generation Computer Sytems,2016,55:1-16.
[5]ZENG L,VEERAVALLI B,ZOMAYA A Y. An integrated task computation and data management scheduling strategy for w orkflow applications in cloud environments[J]. Journal of Netw ork and Computer Applications,2015,50:39-48.
[6]MACIEJ M,KAMIL F,MARIAN B,et al. Cost optimization of execution of multi-level deadline-constrained scientific w orkflow s on clouds[A]. Parallel Processing and Applied M athematics[C]. Berlin:Springer,2014,8384:251-260.
[7]KIM S H,JOO K N,HA Y G,et al. A phased workflow scheduling scheme w ith task division policy in cloud broker[A]. International Conference on Cloudcomp[C]. Berlin:Springer,2014,142:76-86.
[8] STAVRINIDES G L,KARATZA H D. A cost-effective and qos-aw are approach to scheduling real-time w orkflow applications in paas and saas clouds[A]. Proceedings of the 3rd International Conference on Future Internet of Things and Cloud,Rome[C]. US:ACM,2015. 231-239.
[9] ARABNEJAD V,BUBENDORFER K. Cost effective and deadline constrained scientific w orkflow scheduling for commercial clouds[A]. IEEE 14th International Symposium on Netw ork Computing and Applications[C].,Cambridge,M A:IEEE,2015. 106-113.
[10]沈虹,李小平.带准备时间和截止期约束的云服务工作流调度算法[J].通信学报,2015,36(6):187-196.SHEN Hong,LI Xiao-ping. Algorithm for the cloud service w orkflow scheduling w ith setup time and deadline constraints[J]. Journal on Communications,2015,36(6):187-196.(in Chinese)
[11]苑迎春,李小平,王茜,等.基于优先级规则的网格工作流调度[J].电子学报,2009,37(7):1457-1464.YUAN Ying-chun,LI Xiao-ping,WANG Qian,et al.Gridw orkflow s schedule based on priority rules[J]. Acta Electronica Sinica,2009,37(7):1457-1464.(in Chinese)
[12]肖鹏,胡志刚.截止时间约束下独立网格任务的协同调度模型[J].电子学报,2011,39(8):1852-1857.XIAO Peng,HU Zhi-gang. Co-scheduling model for independent tasks w ith deadline constraint in computational grid[J]. Acta Electronica Sinica,2011,39(8):1852-1857.(in Chinese)