一种基于项目特性的关键链缓冲调整方法

摘要

一种基于项目特性的关键链缓冲调整方法，包括以下步骤：步骤1、生成初始可行调度方案；步骤2、计算任务的自由时差，识别关键链；步骤3、采用两种经典量化方法计算缓冲大小，选择较优者通过调整策略对缓冲大小进行调整；步骤4、生成缓冲调度方案，输出结果。本发明考虑了影响调度方案鲁棒性的两个重要因素，网络复杂度和资源松紧度。将其引入到缓冲量化方法中，使调度方案能更好地应对项目中的不确定性。该方法可以在保证调度方案的可行性的基础上得到合理的缓冲插入方案。它在优化调度技术领域里具有实用价值和广阔的应用前景。

主权项

1.一种基于项目特性的关键链缓冲调整方法，其特征在于：它包括以下步骤：步骤一：生成初始可行调度方案采用最晚开始时间即Last Start Time，LST作为优先规则计算任务的优先权，采用串行调度方法生成调度方案；设任务i的开始时间为ST_i，结束时间为FT_i，紧后任务集合为S(i)，任务数为n算法具体步骤为：(一)不考虑任务间资源约束，从最后一个任务开始依次往前调度任务，各任务的结束时间等于其最早开始的紧后任务的开始时间；记录任务的开始时间作为其最晚开始时间LST，初始化各任务最早开始时间EST为0；(二)根据LST值从小到大对任务进行排序即最晚开始时间小的任务先进行调度，生成优先调度集合E(S)；(三)从E(S)中选取第一个任务i进行调度，令其开始时间ST_i＝EST_i，判断任务i执行时间段[ST_i，FT_i]内是否产生资源冲突；若资源使用量超过可用量，则令ST_i＝ST_i+1，FT_i＝FT_i+1重新进行判断；(四)若时间段[ST_i，FT_i]内无资源冲突，任务i调度完成，更新其所有紧后任务的最早开始时间：if    FT_i＞EST_jthen EST_j＝FT_i，j∈S(i)(五)从优先调度集合E(S)中删除任务i；若E(S)非空，转(三)；否则，调度结束；步骤二：计算任务的自由时差，识别关键链使用任务左右移操作来计算任务的自由时差，进而识别项目的关键链；对于任务i，若改变其开始时间ST_i，在不产生任何冲突即包含时序约束与资源约束的情况下，项目中其他任务的开始时间均不发生变化，那么此操作就可以定义为任务移动；基于这样的定义，固定项目的执行时间段为[ST₀，FT_n+1]，任务0和任务n+1为虚任务；即对于任务i，有ST₀≤ST_i≤ST_n+1且FT₀≤FT_i≤FT_n+1，识别关键链的具体步骤为：(一)对于第一步生成的调度方案，从开始时间最晚的任务开始，从后往前依次选择任务i；(二)单步右移任务：令任务i的开始时间ST_i＝ST_i+1，FT_i＝FT_i+1，判断时间段[ST_i，FT_i]内是否产生时序冲突与资源冲突；若产生冲突，取消此次右移操作，即ST_i＝ST_i-1，FT_i＝FT_i-1，任务i移动结束，选择下一个任务；若无冲突产生，对任务i继续执行单步右移操作；(三)当所有任务右移结束，记录此时任务的开始时间为最晚开始时间LST_i＝ST_i，i＝1，2，...，n；(四)对于此时的右移调度方案，从开始时间最早的任务开始，从前往后依次选择任务j；(五)单步左移任务：令任务j的开始时间ST_j＝ST_j-1，FT_j＝FT_j-1，判断时间段[ST_j，FT_j]内是否产生时序冲突与资源冲突；若产生冲突，取消此次左移操作，即ST_j＝ST_j+1，FT_j＝FT_j+1，任务j移动结束，选择下一个任务；若无冲突产生，对任务j继续执行单步左移操作；(六)当所有任务左移结束，记录此时任务的开始时间为最早开始时间EST_i＝ST_i，i＝1，2，...，n；(七)计算任务的自由时差TS_i＝LST_i-EST_i，i＝1，2，...，n；若TS_i＝0，则任务i为关键链任务；否则为非关键链任务；步骤三：缓冲量化与调整缓冲的量化与调整分为以下几步：(一)计算网络复杂度与资源松紧度网络复杂度定义为网络中存在的优先关系数目与理论存在的最大优先关系数目的比值，用于表示网络中的时序约束强度；其中，网络中存在的优先关系数目为每个任务的所有前驱结点包括间接前驱结点之和，最大优先关系数目为n(n-1)/2，其中n表示非虚任务个数，因此网络复杂度表示为：资源松紧度定义为资源的平均使用量与总量之间的比值，表示资源的约束强度：${\mathrm{RC}}_k=\frac{{\bar{r}}_k}{a_k}$其中，a_k表示可更新资源k的总量，则表示资源k的平均使用量，即${\bar{r}}_k=\underset{i=1}{\overset{n}{\Sigma }}{r}_{\mathrm{ik}}/\underset{i=1}{\overset{n}{\Sigma }}m,$$m=\left\{\begin{array}{cc}1,& r_{\mathrm{ik}}>0\\ 0& r_{\mathrm{ik}}=0\end{array}\right.$(二)缓冲量化采用经典缓冲量化方法计算缓冲大小，包括剪切-粘贴法以及根方差法；设任务的i安全时间估计为S_i，表示任务90％概率完成所对应工期；平均时间估计为A_i，表示任务50％概率完成所对应的工期，则任务i工期为D_i＝A_i；假设任务k～k+m属于同一任务链，则该链的缓冲大小B设置为：剪切-粘贴法：根方差法：$B_{\mathrm{RSEM}}=\mathrm{sqrt}\left(\underset{i=k}{\overset{k+m}{\Sigma }}{(S_i-A_i)}^2\right);$(三)缓冲调整采用上面的两种方法计算项目的项目缓冲以及汇流缓冲，选择项目缓冲较小者进行调整；不同项目的鲁棒性是不同的，与广义的鲁棒性概念不同，这里的鲁棒性特指项目执行中，某些因素发生改变时，项目工期发生改变的概率；如任务鲁棒性表示任务发生延期时，项目工期发生延期的概率；当任务间约束强的时候，一个任务的延期会导致相关任务的连环效应，导致总工期的延期；当任务约束弱的时候，某些任务的延期可能不会对项目造成任何影响；使用网络复杂度OS和资源松紧度RC分别描述项目的任务鲁棒性R_task和资源鲁棒性R_resource；由于OS和RC分别表示了时序约束以及资源约束的大小，因此采用这两种指标描述项目对于任务改变和资源改变的抵抗力是合理的；项目缓冲PB由关键链上的任务数以及任务长短所决定，汇流缓冲FB则由非关键链任务决定；一般来说，关键链长于非关键链，任务也较多；故项目缓冲对于不确定性的抵抗能力往往强于汇流缓冲，能对项目缓冲进行较大的削减，对汇流缓冲进行小幅度减少；因此，根据项目的任务鲁棒性R_task以及资源鲁棒性R_resource设置调整权重ω_F和ω_P，分别调整汇流缓冲以及资源缓冲，从而在保证项目按期完工的基础上减小交付日期，增大缓冲利用比例；ω_F＝max{OS，RC}ω_P＝min{OS，RC}FB′＝ω_F×FBPB′＝ω_P×PB步骤四：生成缓冲调度方案；根据步骤三的调整结果，将非关键链任务左移，更新其开始时间，得到缓冲调度方案。