云计算下考虑截止期和服务时间约束的工作流调度方法

钱丽华¹，李小平²

（1.东南大学计算机科学与工程学院，南京，210089；2.东南大学计算机科学与工程学院，南京，210089）

摘  要：本文考虑的是云计算下服务带有时间区间约束的工作流调度。传统的DTCTP，是假设服务在任何情况下都是可行的，与实际情况不是很相符。事实上，服务在某些时间区间上可能被已有的租户请求所占用，考虑到实际的负载情况，只能提供给当前租户可行的时间区间。本文把这类新问题建模成DTCTP-TSC（Discrete Time-Cost tradeoff problem -Time Slot Constraint）。DTCTP-TSC也被证明是NP-hard。本文DTCTP-TSC优化的目标是最小化租户的总成本，满足截止期约束。提出了3种基于不同优先级规则的初始解构造策略EFTF，MGWF，CDRF；在初始解的基础上，结合问题的特点，提出了两个改进过程IG，IF，考虑初始解生成策略与改进过程的不同组合，对这6个方法EFTIG，MGWIG，CDRIG，和EFTIF，MGWIF，CDRIF进行实验评估。实验证明，MGWF和CDRF与EFTF相比，生成很好的初始解；EFTIF是上述6种方法中效果最好的。

关键词：工作流调度；DTCTP；最小化总成本；时间区间；云计算

Workflow Scheduling with Deadline and Time Slot Constraint in Cloud Computing

Qian Lihua¹, Li Xiaoping²

(1.School of Computer Science and Engineering, Southeast University, Nanjing, 211189;

2. School of Computer Science and Engineering, Southeast University, Nanjing, 211189)

Abstract: In this paper,workflow scheduling with time slot constraint in cloud computing is considered, which is different from traditional discrete time-cost tradeoff problem（DTCTP）,well studied during past decades.DTCTP is based on the assumption that the ability of services is unlimited, and can be used at any time.The assumption is seldom true because most services have limited capabilities in fact,and they may be occupyed by exsiting tenants.Therefore,they only can provide some time slots for new coming tenants based on remaining capabilities.Such a DTCTP is modeled as DTCTP-TSC（Discrete Time-Cost tradeoff problem-Time Slot Constraint）,also proved to be NP-hard.In this paper ,The objective of DTCTP-TSC is minimum total cost fufilling the given deadline. Three constructing inital solutions based on different prioroty（EFTF,MGWF,CDRF） and two improving phase（IG,IF） are proposed.Experiment shows MGWF,CDRF can construct better inital solutions than EFTF, and EFTIF is better than other heuristics.

Key words:Workflow scheduling; DTCTP; Minimum total cost; Time slot; Cloud computing

随着互联网技术和各种虚拟，并行，分布式技术的发展，使云计算成为了一种新的面向市场的，以提供高质量和低廉的信息服务为目标的商业模式^[1]。云环境下，资源是以服务的形式提供，尤其是在SaaS层体现的最明显。在文献^[2]提到有两种为用户提供软件应的云。一种是为用户提提供完整的应

作者简介：钱丽华,（1988-）,女,硕士研究生,E-mail: qianlihua_seu@163.com；李小平，（1970-）,男,教授,博导,E-mail: xpli@seu.edu.cn.

用服务，不需要做任何改变，例如：Google Apps 通过浏览器提供了许多在线的office 应用等。另一种是即用即付的形式，按需提供基本的网络服务，即用户租用基本的web服务组成更复杂的应用，例如 Xignite，StrikeIron。本文考虑的是第二种云模型。

云计算环境下，基本的云服务多种多样，相同功能的云服务也具有不同的属性。服务质量（Quality of Service，简称QoS）用来描述用户对于服务属性如对服务的响应时间，可靠性，安全性，代价等的需求，质量越高的服务，相应的代价也越大。

用户根据自己的QoS需求，通过协商与云服务提供商签订云服务协议（SLA）,即用即付的去租用云服务。用户的复杂应用通常用工作流建模，从用户角度出发，如何选择合适的基本服务进行组合，完成复杂的应用，最大化用户利益，是云计算调度中一个非常实际有意义的问题。

云计算环境下云服务的服务能力通常认为是无限的，即请求即可用，然而，这并不完全符合实际情况。实际应用当中，一个云服务剩余的服务能力是随着工作的负载不同实时改变的，不可能在任何时刻都满足租户的需求，因为服务有可能在某些时间段内被已有的租户请求占用，考虑到实际负载的情况，只能提供给当前租户一些可行的服务区间，如图1所示，该项目有6个活动，每个活动有不同的执行时间，代价，以及相应的可行时间区间。

图1 DAG

图2 活动4具有可行服务区间的例子

上图2以图1的活动4为例，活动4有两个负载不同的可行候选服务，如服务1执行时间是4，代价是4，可行的时间区间是（0，4），（8，12），而区间（5，7）由于负载很大，不是可行时间区间。

因此，针云计算环境下考虑服务带有可行时间区间的工作流调度问题不仅是一个新问题，也是一个有实际价值的问题。

云计算工作流调度目标是为每个活动选择合适的服务，满足用户的QoS约束，最大化其利益。每个服务具有不同的属性，其中时间和成本是考虑最多的两个因素，在本文中，只关注时间和代价两个属性。

云环境下，只考虑时间和成本均衡的工作流调度问题可以建模成DTCTP（discrete time/cost trade off problem）。在DTCTP 中，用有向无环图（DAG）表示一个项目或（工作流），每个结点表示一个子活动，边表示活动之间的约束关系。每个活动有多个候选的服务供选择，为每一个活动选择一个合适的服务在满足截止期/总成本约束的前提下，最小化总成本/最小化总完成时间。DTCTP已经被证明是一个NP-hard ^[3]问题。DTCT 问题，考虑的目标主要有三类：1）截止期给定下，最小化总成（DTCTP-D）；2） 总成本给定下，最小化完工时间（DTCTP-B）；3）双目标问题，同时优化成本和完工时间。近几十年来DTCT得到了学术界广泛的研究，提出了许多确定性，启发式和元启发式的算法，这些方法也可以加以修改用来解决云计算下的的工作流调度问题。

常用的确定性的算法主要是使用枚举和动态规划方法^[4-5]，分支限界^[6]。由于DTCTP是NP-hard问题，因此寻找对任何问题规模都可行的确定性算法是不太可能的，目前存在的最好的确定性算法可以解决不超过200个活动，每个活动候选服务不超过20 个。所以设计有效的元启发式方法和启发式方法还是非常重要的。

一些元启发式的方法^[7-8]可以获得比较好的解，但是非常耗费时间。

一些启发式方法是基于截止日期划分的思想。在实用网格中，Yu,Buyya^[9]提出了DeadLine-MDP（简称DMDP）工作流调度方法。DMDP 依据项目的总截止时间和每个任务最小执行时间，把活动图划分成多个子图，为每个子图分配一个子截止时间。Yuan 在文献^[10]中提出了DET算法，根据一条关键路径，把活动分为关键活动，和非关键活动两类，首先调度关键活动，非关键活动依据他们的可浮动区间定义优先级进行调度。最近，文献^[11]（Abrishami 和Naghibzadeh，2012）提出了PCP算法，提出了部分关键路径的思想，所有的活动被划分到不同的部分关键路径中，部分关键路径的优先级由这些活动最早完成时间决定，越早完成，优先级越高，也越早被调度。实验证明PCP算法比DMDP和DET性能要好。Liu,Zhang,luo^[12]提出的基于路径平衡的工作流优化方法PBCO，给定截止期下，对工作流中各路径的长度进行调整，并采用逆向分层策略，对各层的任务按比例分配冗余时间，有效的增大了多数任务的费用优化空间，实验表明PBCO优于DET,DBL。

目前云计算环境下工作流调度问题大部分都只考虑租户的QoS约束，详情见综述^[13],而同时考虑租户的QoS和带有不可行服务区间约束的工作流调度的文献还没有。Zhicheng Cai，Xiaoping Li，Long Chen^[14] 在分布式协同制造系统中第一次提出了带有开始时间约束的服务调度问题，把问题建模成DTCTP-STC，证明了DTCTP-STC是NP-hard 问题，实验表明动态规划方法在解决DTCTP-STC小规模问题的时候是有效的。但是在他们的模型中，服务的开始时间是一个确定的时间点，并没有考虑上图中提到的服务带有不可行时间区间约束，所以对带有不可行时间区间约束的工作流调度问题进行研究是非常具有实际意义和研究价值。

本文把带有不可行时间区间约束，只考虑时间和代价均衡的工作流调度问题称为DTCTP-TSC（discrete time—cost tradeoff problem with time slot constraint），对此新问题进行建模，证明DTCTP-TSC是NP-hard问题。由于DTCTP-TSC与传统DTCTP考虑的约束不同，所以DTCTP的方法不能直接拿来解决DTCTP-TSC问题，本文考虑设计新的方法来解决DTCTP-TSC。

论文的结构如下：第二章描述DTCTP-TSC的数学模型；第三章介绍提出的启发式方法；第四章对实验实现及实验结果进行总结和分析。第五章是总结。

1 数学模型

租户的需求任务被拆分成子任务以后，一般用工作流进行建模，用一个有向无环图G（V，E）表示，V={V₁，V₂，…V_n}是图G中所有子任务,即活动的集合。

表示活动之间的约束关系，表明V_i必须在V_j之前完成，并且i<j。每个结点V_i需要一种云服务，而由不同的云服务提供商（CSP，cloud service provider）提供相同功能不同属性的云服务为活动V_i组成了一个候选池

,

服务M_i^j有一个相对应的可行服务区间列表，用表示，其中 表示第i个活动第j个可行服务的第t_ij个时间槽，t_ij =|S_ij|。每个时间槽S_ijk定义了一个时间区间（sb_ijk，sf_ijk），其中sb_ijk表示此时间槽的开始时刻，，sf_ijk表示此时间槽结束时刻。所以,每种可行服务用三元组{S_ij，e_ij，c_ij}表示。e_ij，c_i分别表示活动V_i选择服务M_i^j 的执行时间和代价。

本文考虑的工作流调度即各个任务在对应的可行服务池中选择一个服务,从该服务的可行时间区间列表内选择一个合适的时间槽来完成，假定任务不可以中断，即不考虑任务在同一个服务的跨时间槽上执行的情况，并且满足执行时间越短的服务，代价越大。工作流中所有任务的服务的时间槽选定后，工作流的执行时间和代价就确定了。表1给出了对于图1中每个活动的服务池的列表，其中活动1和活动6是虚拟活动。

表1 工作流活动的服务列表

对于传统的DTCTP，是假设活动的可行服务在任何情况下都是可用。表1中的活动，如果不考虑服务的可行时间区间约束，如活动2，有两个可行服务M₁和M₂，M₁的执行时间是3，代价是6；M₂执行时间是4，代价是5，可以看成每个服务的可行时间区间都是（0，+∞）。决策变量X_ij表示活动i选择可行服务j。给定截止期12, 则调度X₁={x₁₁=1，x₂₂=1，x₃₂=1，x₄₂=1，x₅₂=1，x₆₁=1}，得到最小的成本C_min= 18；

而对于DTCTP-TSC，决策变量X_ijk表示活动i选择可行服务j的第k个时间槽。给定同样的截止期12，则在调度X₂={x₁₁₁=1，x₂₁₁=1，x₃₂₁=1，x₄₂₂=1，x₅₂₁=1，x₆₁₁=1}下得到最小的成本C_min=19，比没有考虑可行服务时间约束的成本要大一些。因此可以看出DTCTP-TSC与传统的DTCTP问题是有明显的区别的。

1.1   符号表

在介绍数学模型之前，先定义如下符号表示：

V: 用户所有活动的集合，

n: 活动数

_: 活动

: ，即所有活动之间的偏序关系集合

: 表示对于活动 对应的候选的服务池，服务集合

:表示对于活动有个服务可选

:表示对于活动的第个可用服务

:用户给定的截止日期

: 表示活动第个可用服务对应的可行时间槽列表，

: 表示活动第个可用服务的第k个时间槽

:表示活动第个可用服务有个时间槽

:活动选择服务，第k个时间槽的开始时刻

:活动选择服务，第k个时间槽的结束时刻

:活动选择服务，第k个时间槽的执行

:活动选择服务，第k个时间槽的代价

：活动的完成时间

：活动的一个直接前驱结点

：活动的一个直接后继结点

1.2          具体数学模型

DTCTP-TSC数学模型描述如下：DTCTP-TSC的目标可以是最小化工作流的总成本在给定的截止期约束下，用DTCTP-TSC-T表示；或者最小化工作流完工时间，在给定总成本约束下，用DTCTP-TSC-B表示。DTCTP-TSC-T的数学模型如下：

目标函数：

              (1)

S.t.:

            (2)

  (3)

       (4)

(5)

(6)

             (7)

其中公式1描述了工作流费用优化目标；公式2，3,4,6述了工作流的每个活动只能选择一个服务的一个空槽执行，不能超过所选空槽的开始时刻和结束时刻；公式5 描述了工作流的偏序关系；公式7表示不能超过截止日期。对于DTCTP-TSC-B的数学模型，除了上述的2-6的约束外，还有下面的目标函数8以及约束9

min      (8)

         (9)

传统的DTCT问题，可以看成每个服务提供的可行时间区间是（0，+∞），规约为上述问题的特例。在文献^[3]，DTCT的判定问题已经证明是强NP完全问题，因此服务带可行时间区间约束的工作流调度（DTCTP-TSC）问题也是NP-hard问题。本文主要从用户角度出发，给定截止期D情况下最小化租户的总成本C。

2 基本定义

对于一个工作流，进行拓扑排序，1...n,其中1和n为虚结点，执行时间和代价都为0，可行服务区间为（0，+∞），活动的服务和slot下标从0开始。一个调度指的是对工作流中的每个活动分配服务。如果X_ijk=1可行服务i的第k 个slot，则一个调度可以表示为：

由于服务带有可行时间区间约束，所以一个活动的所有前驱结点完成后，并不一定能立刻执行该任务，需要等待选择合适的时间槽进行分配。E(i，j，t) 表示活动i选择服务 在时刻t 时可选的最早的时间槽,若不存在，E(i，j，t)为null值。E_s(i，j，t)表示此时间槽上该任务的最早可行开始时刻,通过遍历M_i^j对应的slot列表可以得到。

对于任何一个任务，定义它最早的开始时间E_st(i)和最早的结束时间E_ft(i)，A_et(i)定义的是活动i所有前继活动最大的最早结束时刻。

 = 0                    (10)

 = 0                     (11)

 =          (12)

=

(13)

          

=

(14)

同理，如果L(i，j，t)表示活动i选择服务j在时刻t之前完成最晚完成的时间槽，若不存在，L(i，j，t)为null值。L_f(i，j，t)表示此时间槽上该任务的最晚完成时间。L(i，j，t)的计算过程与E(i，j，t) 类似。

对任何一个任务，定义它最晚的开始时间L_st(i)和最晚的结束时间L_ft(i)，A_ft(i)表示活动i的所有后继活动最小的最大开始时刻，计算公式如下：

 = D                      （15）

 = D;                      （16）

 =           （17）

 =   （18）

=

(19)

定理1 如果最快调度不可行，即最后一个活动n的E_ft(n)>D,则此实例没有可行解。

很明显，如果每个活动都选择最早完成的服务，即每个活动i的完成时刻都等于E_ft(n)，那么此调度一定是最快执行完的。如果E_ft(n)>D，则说明最快调度都不能满足截止期，此实例无解。

定理2 如果一个调度是可行的，则此调度下每个活动i的f_i满足E_ft(i)≤f_i≤L_ft(i)。

与传统的DTCTP相比，由于服务带有可行时间区间约束，很明显，DTCTP-TSC中最快的调度不一定是每个活动选择执行时间最短，代价最大的服务，即最快的调度不一定是代价最大的调度。

3 启发式方法

DTCTP假定服务在任何情况下都是可用的，所以一个活动越靠后执行，并不会影响下一个活动服务的选择，即下一个活动每个可行服务都是可选的。PCP，DET，CPI方法是目前解决经典的DTCTP 最好的启发式方法，但是并不能直接用来解决DTCTP-TSC。

因为DTCTP-TSC是NP-hard问题,考虑到云计算环境的特点，工作流中的活动通常成百上千，因此提出有效的启发式方法很有必要。

本文提出的启发式方法主要有三个部分：预处理，初始解生成，和解的改进。在介绍这三者之前，先介绍一下DTCTP-TSC-T解的表示。

3.1 解的表示

对工作流中的活动进行拓扑排序，从1..n进行标识。一个可行的解用

= (20)

表示，其中表示活动i的完成时间，X_ijk表示活动i选择可行服务j的第k个slot槽。如果此调度是可行的，则每个活动i只要记录选择了的服务j，slot只要选择当前满足前继约束下的E(i，j，t)，很明显也是可行解。由于本文生成的初始解都是可行解，所以解的表示可以简化为

= (21)

3.2 预处理

如果最快调度E_ft(n)>截止日期D,则说明此实例不存在可行解;否则，先根据D和服务的执行时间过滤服务slot列表上无效的slot槽。

如果，此slot槽无效；如果，此slot槽无效。

再根据每个活动V_i的E_ft(i)， E_st(i)， L_ft(i)， L_ft(i)

，如果,此slot槽无效；如果，此slot槽无效。最后，并对每个活动的可行服务按照执行时间从小到大，即代价从大到小进行排序。

3.3 初始解生成策略

DTCTP的初始解，如果不考虑截止期D约束，则随机为每个活动分配一个可行服务，这个解都是可行的；DTCTP-TSC问题有时间区间的约束，不能直接这样构造可行解。本文提出了三种基于不同优先级规则的初始解生成策略，分别是最早完成活动优先，活动和其后继活动的代价均值最小优先，和活动相邻可行服务代价上升最小优先。

3.3.1最早完成活动优先

如果活动的E_ft值越小，优先级越高，则先为该活动分配选择使其能够最早完成的可行服务，即分配E_ft对应服务上最早的slot槽。此调度序列 就是我们之前说的最快调度，这种初始解构造策略称为 EFTF(Earliest Finish Time First)。如果实例有解的话，EFTF 得到的一定是可行解。可以看出，最早完成活动优先本质是按照拓扑顺序为每个活动选择最早完成的服务，因为活动标识越小，则该活动E_ft越小，优先级越高。

3.3.2 活动及其后继活动代价均值最小优先

活动及其后继活动代价均值最小优先规则是一个迭代的构造解的过程，由于该方法权重的计算考虑了当前活动和所有直接后继活动的组合，该规则称为MGWF(Min Group Weight First)。预处理时对每个活动V_i的服务集按照代价从小到大进行排序，当前活动i选择第j个服务，如果该服务是可行的，即该活动的完成时间f_ij 在[E_ft(i)， L_ft(i)]范围内并且该活动的开始时间s_ij在[E_st(i)， L_st(i)]，否则，不是可行的服务。假设活动i的第j个服务可行，

，

更新每个后继活动的,即如果，则，是当前代价最小的可行服务，表示后继活动的数目，M（i,j）权值 ，

我们选择当前活动所有可行服务中GW(i,j)，最小值作为该活动权值，即GW(i)=min GW(i,j)。如果一个活动GW(i,j)越小，说明此活动及其直接后继代价比较小，考虑优先为此活动确定可行服务。

下面是依据MGWG原则构造解的过程：

首先，把工作流中的活动分为已调度S和未调度US集合，GW(w)表示未调度活动权值数组。初始化虚活动1和n已调度，选择第一个服务的第一个slot，其余活动V_i∈US。已调度的活动选择该服务下最早完成的slot，未调度的活动选择最早完成的可行服务，来计算E_ft(i)，L_ft(i)；已调度的活动选择该服务下最晚开始的slot，未调度的活动选择最晚开始的可行服务，来计算L_ft(i)，L_st(i)。 对于US中的每个活动计算权重GW(i)，选择GW(i) 最小的活动，为其选择相应权值对应的服务；后继活动集中GW(s_i)最大的活动j，如果权值GW(j) 大于GW（w）中一半的活动，则为活动j选择相应权值对应的服务。更新S和US集合,重新计算每个活动i的E_ft(i)，L_ft(i)，更新权值，选择服务，迭代此过程，直到所有活动都确定了服务，此构造过程结束。

3.3.3   活动相邻可行服务代价上升率最小优先

预处理时对每个活动V_i的服务集按照代价从小到大进行排序，当前活动i选择第j个服务，如果该服务是可行的，即该活动的f_ij在[E_ft(i)， L_ft(i)]范围内，否则，不是可行的服务。假设M_ij是活i代价最小的可行服务，M_ij’是代价次小的可行服务，这两个服务称为活动V_i的相邻服务。相邻可行服务代价上升率

；如果CAR(i)越大，说明如果当前活动没有选择可行服务M_ij时，则选择其CAR(i)越大，该活动首先分配服务的优先级越高。如果该活动不存在代价次小的可行服务，C_min表示当前工作流不考虑可行时间区间每个活动选择最便宜服务的代价总和，则

基于CAR 的优先级规则构造解与上述基于MGWF 规则构造解过程类似。

如果在初始解优先级计算中考虑随机因素，则可以作为元启发方法的生成初始解的过程。

3.4 改进策略

对于得到的初始解，提出了两种改进的规则，分别是基于贪心的改进IG(ImprovebyGreedy)和基于公平原则的改进IF(ImprovebyFair)。

3.4.1 贪心规则改进策略

贪心规则改进策略思想是：按照拓扑排序从后往前进行调整，后继活动在满足截止期约束下，尽可能往后执行，计算当前活动最晚的完成时间L_ft(i)；不影响前驱活动调度情况下，计算当前该活动的最早的可行开始时间E_st(i)，在此区间内，为活动i选择最便宜的服务。

3.4.2 公平规则改进策略

       贪心规则的改进策略，对于活动i在（est_i，lft_i）区间内选择满足条件的最便宜的服务替换当前服务，虽然可以降低整体的代价，但后面的活动选择最便宜的服务后，可能导致前面活动可选的服务大大降低，不利于整体工作流代价的优化，因此提出基于公平的原则来改进。思想：按照拓扑排序从后往前进行调整，后继活动在满足截止期约束下，尽可能往后执行，计算当前活动最晚的完成时间lft_i，不影响前驱活动调度情况下，计算当前该活动的最早的可行开始时间est_i，在此区间内，为活动i选择次便宜的服务。当走到第1个活动后，判断上次调整有没有改变过活动的服务，如果有改变，再继续这个过程，直到无法改变任何一个活动的服务停止。实验结果

4.1 数据生成

本节对前面提的三种EFTF，MGWF，CDRF优先级规则构造初始解方法进行实验比较，上面三种初始解构造方法与前面介绍的两种改进策略IG，IF组合，得到6种启发式方法EFTIG，MGWIG,CDRIG，和EFTIF，MGWIF，CDRIF。并对这六种启发式方法进行评估。所有比较的算法都是用java代码编写，运行环境是RAM 2G,单核CPU3.1GHZ，WindowXP。由于实例的参数会对算法的性能有影响，所以需要对不同的参数进行测试。其中N表示工作流中活动的个数，M 表示每个活动的服务数目。OS 反映工作流结构的复杂度，CF定义的是代价与执行时间的函数类型，可以是凸函数，凹函数，或者混合函数。

DTCTP-TSC数据生成分两步:(1)生成不考虑可行时间区间约束的实例，即DTCT问题的实例。由于目前没有针对活动数大于200的基于OS测量的benchmark。服务代价函数生成策略采用[15]提的方法。N 取值范围是{200,400,600,800,1000},M从三个集合U[2,10]，U[11,20]，U[21,30]中取值。OS取值{0.1,0.2,0.3}。(2)为每个活动的每个服务构造可行时间区间。MinMakespan表示不考虑服务约束，为每个活动选择执行时间最短的服务，计算的最早完成时间。CP表示每个服务考虑的最大的时间范围因子,取值范围是{2,4,6}，TimeHorizan=CP* MinMakespan，LoadNum反映不可用的区间占整个TimeHorizan的比重，取值范围是{0,0.3,0.6}中。每组参数生成1个实例，一共有12150 个实例。DF是截止期范围因子，取值{0.2,0.4,0.6}，D_min表示最快调度的完工时截止期

D=D_min+（TimeHorizan-D_min）*DF      (22)

4.2 实验结果

为了比较算法的效果，需要考虑一些评价标准。假设H表示方法名，C_i^H表示方法H在实例i上计算的代价，W表示实例规模，best_i表示所有比较算法中得到的最小代价值，C(H)表示该算法H在一组实例中与所有算法相比找到的最好的解值，ARD_H表示该方法H的平均相对误差，

   (23)

表2给出了三种优先级规则的实验结果。从表中可以看出，就初始解生成来看，无论在参数N，M，还是loadNum，df下，CARF和MGWF可以得到比较好的初始解，EFTF的ARD是三种规则中最大的，CDRF的ADR是三者中最好的，其次是MGWF，表明就初始解的效果来看，MGWF和CARF规则生成的解比EFTF规则要好，CARF比MGWF 生成的解要好一些。

因为改进规则IF比IG效果好，所以表3只给出这三种规则结合IF改进策略得到的启发式方法的实验结果，其中EFTIF是所有比较算法中ARD值最小的，而MGWIF与MGWIG的ARD值相差不大，CDRIF,CDRIG两者ARD值相差也不大，意味着改进过程IG和IF对于MGWF和CDRF得到的初始解优化的区别不明显，影响不大。但是对于EFTF 初始解的优化有显著的提高。CDRIF，CDRIG的ARD都比MGWIG和MGWIF小，说明CDRIF 和CDRIG比MGWIG，MGWIF效果好。

表4给出的是EFTIF，MGWIF，CDRIF启发式方法时间代价，,表明EFTF 是所比较算法中最快的。

从三张表中可以总结出，想要构造比较好的初始解，可以考虑使用CDRF和MGWF规则；使用IF，IG 的改进规则对于这三种初始解都有改进，IF改进过程比IG要好，尤其是针对是EFTF 规则的初始解，考虑IF 过程，改进解最明显。

表2 三种优先级规则的平均相对误差比较

表3 3个启发式方法平均相对误差比较比较

表3 3个启发式方法时间（ms）比较

4      总结

本文研究了云计算环境下考虑截止期和服务可行时间区间约束的工作流调度的一个新问题（DTCTP-TSC），与传统的DTCTP相比，该问题更符合实际应用场景，并对DTCTP-TSC 建模，分析了DTCTP-TSC与DTCTP一些性质不同。本文的优化目标是满足截止期约束下，最小化总成本，考虑到该问题是NP-hard，且在云计算环境下，活动规模可能很大的特点，提出了3种基于不同优先级规则的初始解生成策略（EFTF,MGWF,CDRF），和2种解的改进过程（IG,IF），并对这三种初始解生成策略与改进过程进行组合，得到EFTIF,MGWIF,CDRIF，EFTIG,MGWIG,CDRIG六个启发式方法。实验表明：就初始解生成而言，CDRF和MGWF规则要优与EFTF，其中CDRF生成的初始解是三种中最好的；使用IF，IG 的改进策略后，对于这三种初始解都有改进，IF 改进过程优于IG过程，尤其是针对是EFTF规则的初始解，考虑IF过程后，初始解有明显的提高，EFTIF是所本文提出的方法中最好的。

DTCTP-STC问题进一步的研究，(1)考虑使用元启发式方法来解决，把本文的初始解生成策略作为初始解构造的一个算子，改进策略也可以用于元启发方法改进解的过程。(2) 挖分析DTCTP-STC的本质，提出更有效的启发式方法。

参考文献

[1]     Rajkumar Buyya, Chee Shin Yeo, and Srikumar Venugopal.  Market-oriented cloud computing: Vision, hype, and reality for delivering it services as computing utilities[J]. In  High Performance Computing and Communications, 2008. HPCC’08. 10th IEEE International Conference on, pages 5–13. IEEE.

[2]     C. Weinhardt, A. Anandasivam, B. Blau, et al. Business models in the service world. IT professional[J], 2009, vol. 11, no .2, pp. 28-33.

[3]     Prabuddha De, E James Dunne, Jay B Ghosh, et al.  Complexity of the discrete time-cost tradeoff problem for project networks. Operations research[J], 1997, 45(2):302–306.

[4]     Thomas J Hindelang, John F Muth, A dynamic programming algorithm for decision cpm networks[J]. Operations Research, 1979, 27(2):225–241.

[5]     Prabuddha De, E James Dunne, Jay B Ghosh, et al. The discrete time-cost tradeoff problem revisited[J]. European Journal of Operational Research, 1995, 81(2):225–238.

[6]     Erik L Demeulemeester, Willy S Herroelen, and Salah E Elmaghraby. Optimal procedures for the discrete time/cost trade-off problem in project networks[J]. European Journal of Operational Research, 1996, 88(1):50–68.

[7]     Rifat Sonmez and Önder Halis Bettemir. A hybrid genetic algorithm for the discrete time-cost trade-off problem[J]. 2012, Expert Systems with Applications.

[8]     Hadi Mokhtari, R Baradaran Kazemzadeh, and Ali Salmasnia, Time-cost tradeoff analysis in project management: An ant system approach[J].Engineering Management, IEEE Transactions on, 2011,  58(1):36–43.

[9]     Jia Yu, Rajkumar Buyya, and Chen Khong Tham.  Cost-based scheduling of scientific workflow applications on utility grids[A]. In e-Science and Grid Computing[C]. First International Conference on, pages 8–pp. IEEE. 2005.

[10]  Yingchun Yuan, Xiaoping Li, Qian Wang, et al. Deadline division-based heuristic for cost optimization in workflow scheduling[J].Information Sciences.2009. 179(15).

[11]  Saeid Abrishami, Mahmoud Naghibzadeh, and Dick HJ Epema. Cost-driven scheduling of grid workflows using partial critical paths. Parallel and Distributed Systems, IEEE Transactions on, 2012. 23(8):1400–1414..

[12]  张卫民, 骆志刚. 基于路径平衡的工作流费用优化方法[J]. 软件学报, 2013.

[13]  Anju Bala and Inderveer Chana.A survey of various workflow scheduling algorithms in cloud environment[C].  In  IJCA Proceedings on 2nd National Conference on Information and Communication Technology NCICT, New York, USA, pages 26–30, 2011.

[14]  Zhicheng Cai, Xiaoping Li, and Long Chen. Dynamic programming for services scheduling with start time constraints in distributed collaborative manufacturing systems[C].  In  Systems, Man, and Cybernetics (SMC), 20## IEEE International Conference on, pages 803–808, 2012.

[15]  Erik Demeulemeester, Mario Vanhoucke.Willy Herroelen.  Rangen:A random network generator for activity on the node networks[J]. Journal of Scheduling, 2003,6(1):17–38.