Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2014, Vol. 15 Issue (6): 401-422    DOI: 10.1631/jzus.C1300270
    
具有动态变化服务可用性的工作流应用程序调度算法比较
Pawe? Czarnul
Department of Computer Architecture, Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Gdansk 80-233, Poland
Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability
Pawe? Czarnul
Department of Computer Architecture, Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Gdansk 80-233, Poland
 全文: PDF 
摘要： 研究目的：在服务可用性和相关参数可变的环境中，选取合适的工作流应用程序调度算法，在预算范围内，尽可能降低工作流的执行时间。根据不同算法的比较，提出一个在具有动态变化服务可用性的环境中获取最优调度方案的模型。
研究方法：在服务可用性和其他服务质量参数动态变化的环境中，比较不同调度算法--包括整数线性规划算法（ILP）、启发式整数线性规划算法（ILPHEU）、分治算法（DaC）、遗传算法（GA）以及收益算法（GAIN）--在不同条件下的性能和成本（图6-图23），得出相应条件下各算法的性能排序（图24），并在实际环境（BeesyCluster）中测试。
重要结论：得出不同算法的执行时间（表5）和优缺点（表6）以及处理不同尺度问题时的性能排序--（1）对于小工作流（如6个节点），性能排序（由高至低）：ILP>DaC>GAIN>GA；（2）对于中等工作流（如40个节点），性能排序：ILPHEU>GAIN>DaC>GA；（3）对于大工作流（如100多个节点、几百项服务），性能排序：ILPHEU>DaC>GAIN>GA。
关键词： 工作流应用程序动态调度;  工作流管理环境;  调度算法    
Abstract: This paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task, one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and keep the cost of service within the budget. During the execution of a workflow, some services may become unavailable, new ones may appear, and costs and execution times may change with a certain probability. Rescheduling is needed to obtain a better schedule. A solution is proposed on how integer linear programming can be used to solve this problem to obtain optimal solutions for smaller problems or suboptimal solutions for larger ones. It is compared side-by-side with GAIN, divide-and-conquer, and genetic algorithms for various probabilities of service unavailability or change in service parameters. The algorithms are implemented and subsequently tested in a real BeesyCluster environment.
Key words: Dynamic scheduling of workflow applications    Workflow management environment    Scheduling algorithms
收稿日期: 2013-09-29 出版日期: 2014-06-06
CLC:  TP302  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Pawe? Czarnul

引用本文:

Pawe? Czarnul. Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability. Front. Inform. Technol. Electron. Eng., 2014, 15(6): 401-422.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/jzus.C1300270    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2014/V15/I6/401

[1] Zhi-xiang Chen, Zhao-lin Li, Shan Cao, Fang Wang, Jie Zhou. 同构多核处理器中考虑制造差异的调度优化[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(12): 1018-1033.
[2] Hong-ze Leng, Jun-qiang Song, Fu-kang Yin, Xiao-qun Cao. Notes and correspondence on ensemble-based three-dimensional variational filters[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(8): 634-641.
[3] Dan Wu, Xue-cheng Zou, Kui Dai, Jin-li Rao, Pan Chen, Zhao-xia Zheng. Implementation and evaluation of parallel FFT on Engineering and Scientific Computation Accelerator (ESCA) architecture[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(12): 976-989.
[4] Che-Wei Lin, Chang Hong Lin, Wei Jhih Wang. [J]. Frontiers of Information Technology & Electronic Engineering, 2011, 12(8): 629-637.
[5] Ai-lian Cheng, Yun Pan, Xiao-lang Yan, Ruo-hong Huan. A general communication performance evaluation model based on routing path decomposition[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(7): 561-573.