云计算中基于关键路径的迭代启发式工作流调度

148 浏览量更新于2024-07-15 收藏 319KB PDF 举报

"本文探讨了在公用计算和云计算环境下的工作流调度问题，提出了一种基于关键路径的迭代启发式算法。" 在公用计算和云计算的背景下，工作流调度是一个重要的研究领域，因为它涉及到如何有效地分配任务到合适的资源，以最小化所有资源的租赁成本，同时满足任务之间的先决条件约束并确保工作流的截止日期得以满足。作者 Zhicheng Cai、Xiaoping Li 和 Jatinder N.D. Gupta 在这篇研究论文中详细阐述了这个问题。首先，他们建立了一个混合整数线性规划（MILP）模型来解决小规模的问题实例。MILP模型能够考虑各种复杂的约束条件，如任务间的依赖关系、资源限制和成本因素，以求得最优解。然而，由于工作流调度问题的NP难性，对于大规模问题实例，直接使用MILP模型求解是不现实的。因此，研究人员开发了一种称为Critical Path-based Iterative (CPI) 的启发式算法。该算法通过动态编程方法迭代构建多个完整的关键路径。对于已经安排的活动，根据服务分配构建这些路径；而对于未安排的活动，则选择最长（最便宜）的服务。每个关键路径优化问题被松弛为一个更易处理的问题，从而能够在有限时间内找到接近最优的解决方案。 CPI启发式算法的工作流程如下： 1. 初始化：识别工作流中的关键路径。 2. 动态规划：根据当前服务分配和未分配的任务，构造并更新关键路径。 3. 路径优化：对每个关键路径进行优化，寻找能降低总成本的资源分配。 4. 迭代：重复步骤2和3，直到满足预设的停止条件（如达到一定的优化水平或达到最大迭代次数）。这种方法的优点在于它可以在保证一定程度的效率和近似最优性的同时，处理大规模工作流调度问题。然而，启发式算法可能无法保证找到全局最优解，但其快速的计算速度和实用性使其在实际应用中具有较高的价值。这篇论文提供了一种有效应对云和公用计算环境中的工作流调度挑战的方法，通过结合理论建模和实用的迭代启发式策略，为实际系统的设计者和操作者提供了有价值的工具。

Workﬂow Scheduling in Cloud Computing 209





 







Fig. 2. An Illustrative Example for the Workﬂow

problems, MDP [6], DET [7], and PCP [8] are single or partial critical-path based.

Meta-heuristics, such as [9,10,11] are time-consuming for complex applications

(such as workﬂows with thousands of activities).

DET [7] and PCP [8] schedule activities of a workﬂow by partitioning them

into diﬀerent types of critical paths and assigning a priority to each critical

path. The procedures used to assign services to activities and to schedule (par-

tial) critical paths immensely impact the performance of a scheduling algorithm.

Therefore, in this paper, CPI (Critical Path based Iterative) heuristic is devel-

oped. CPI heuristic generates complete critical paths as opposed to the partial

ones produced by PCP. The proposed CPI heuristic iteratively generates multi-

ple critical paths, which is distinct from the single critical path way adopted in

DET. All unscheduled activities are assigned to the longest services. Assignment

of all scheduled activities are kept unchanged to generate new complete critical

paths. As soon as a new critical path is found, its cost is minimized. In order to

simplify the optimization process, the critical path optimization problem is re-

laxed to the Multi-stage Decision Process (MDP) problem, which can be solved

by a dynamic programming algorithm in pseudo-polynomial time.

The rest of the paper is organized as follows. Section 2 describes the workﬂow

scheduling problem in detail and constructs its mathematical model. Section 3

presents the proposed CPI, the complexity analysis and an illustrative example.

Experimental results are given in Section 4, followed by conclusions in Section 5.

2 Problem Description

Workﬂows in Utility and Cloud Computing environments can be depicted by a

Directed Acyclic Graph (DAG),G = {V, E} where V = {V

,...,V

} is the

set of activities of the workﬂow, E = {(i, j)|i<j} is the precedence constraints

of activities, which indicates that V

cannot start until V

completes, P

and

represents the immediate predecessor set and the immediate successor set of

,andpath(i, j) = 1 means that there exists a path from V

to V

,otherwise,

path(i, j) = 0. Figure 2 depicts a workﬂow example with ﬁve activities (V

and

are dummy source and sink nodes).

As shown in Figure 1, diﬀerent types of Virtual Machines (with distinct price

per hour) are provided by diﬀerent IaaS or even Grid providers. For every ac-

tivity, there are several candidate services, each of which has diﬀerent types and

numbers of VMs with distinct execution times and costs. The candidate services

剩余14页未读，继续阅读

weixin_38650150

粉丝: 5
资源: 910

云计算中基于关键路径的迭代启发式工作流调度

Quality evaluation-based iterative seam estimation论文源码

Real-time Iterative Learning Control

High-Precision, Consistent EKF-based Visual-Inertial Odometry.pdf

Quasi-Polynomial Mapping-based Root-Finder

6-2 iterative mergesort

6-1 iterative mergesort

自伴随梯度法（Self-Adjoint Iterative Eigensolver, SAEI）代码

Low-density parity-check codes constructed from protographs

用Python实现文献[6] J.-H. Syu, S.-J. Wang, and L.-C. Wang, “Hierarchical image segmentation based on iterative contraction and merging,” IEEE Transactions on Image Processing, vol. 26, no. 5, pp. 2246–2260, May 2017.d

最新资源