（管理科学与工程专业论文）网格工作流环境下多关键资源的任务调度策略研究.pdf

摘要 摘要 目前，我国大部分地区政府部门的电子政务建设，对外信息化的交流仅处于 信息发布基础平台建设阶段。孤立封闭的系统架构，致使信息资源不能共享，数 据格式不统一，数据在不同的系统中重复存在，互相不一致，也致使本该协同一 致的完整业务过程被人为分割和打碎。这些问题阻碍了政府协同、监管工作效率 和公共服务水平的提高，已成为制约中国电子政务发展的瓶颈。 网格技术的出现，为解决这些问题带来了契机，因为网格技术的核心就是信 息和资源的共享及协同。但单纯的网格系统还缺乏一种有效地构建和处理具有关 联的复杂网格应用的方法，由于工作流技术能够使过程自动化和协同工作，提高 工作效率，自然让人联想网格与工作流技术的结合，从而网格工作流这一概念被 提出。由于目前已有的网格工作流系统大多是根据高能物理或者生物信息学等专 用网格系统中的工作流程复用等需求而设计的，它们更偏重于工作流程建模，而 且其用户群体较为单纯，所以很少考虑任务调度方面的问题，相应的调度策略也 没有优先性。对于用户群体比较复杂的电子政务网格工作流系统而言，由于资源 的有限性，用户提交的任务则需要一定的机制来保证其能在合理的时间内完成。 本文首先从网格开始，着重介绍了网格资源管理与任务调度，并指出任务调 度策略是影响网格系统效率的最重要因素，在此基础上结合传统工作流，指出研 究网格工作流的必要性，并对网格工作流以及基于网格工作流的电子政务的关键 内容进行介绍；接着对比了几种工作流过程建模方法，经过分析后选用p e t r i 网对 一个电子政务中常见的行政审批业务的例子建立网格工作流网，并通过对该网格 工作流网的分析，得出关键部门误工数最少的次序调度对基于网格工作流的电子 政务系统的巨大影响；接着结合排序论中误工数最小问题的算法，抽象出数学模 型，并结合实际运用中出现的问题给出算法的改进；接着在单个关键资源的任务 调度基础之上，建立一个把整体工期划分到各个阶段工期的动态规划模型，讨论 多个关键资源的任务调度算法，并讨论了相关算法的时间复杂度，利用逐次近似 法降低复杂度，得到一个在多项式时间内可解的动态规划算法；最后利用j a 、队实 现一个利用该算法与先进先执行算法比较的仿真系统，通过多次运算得到仿真的 广东工业大学管理学硕士学位论文 结果，证实了本文提出的算法确实可以减少总误工数。 关键字：电子政务；网格工作流；p e t r i 网；动态规划；任务调度策略；j a v a a b s t r a c t a bs tra c t n o w a d a y s ，t h ee s t a b l i s h m e n to fe - g o v e r n m e n ta n di n f o r m a t i v ec o n t a c ta m o n g m o s td i s t r i c t si no u rc o u n t r ya r em e r e l ya tt h ef o u n d a t i o n a ls t a g eo ft h er e l e a s eo f i n f o r m a t i o n i s o l a t e ds y s t e me n c l o s u r eb l o c kt h es h a r eo fi n f o r m a t i v er e s o u r c e s ，i n a d d i t i o n ，t h ed i s i n t e g r a t e do fd a t ef o r m a t sa n dt h er e - e x i s t e dd a t ei nd i f f e r e n ts y s t e m s s e p a r a t et h ew h o l en o r m a lb u s i n e s s ，w h i c hs h o u l db ei n t e g r a t et o g e t h e r , i n t od i f f e r e n t p a r t s t h e s ep r o b l e m s ，i n t e r f e r i n gt h eg o v e r n m e n t a lc o o r d i n a t i o n ，t h ew o r ke f f i c i e n c y o fs u p e r v i s i o na n dt h ei m p r o v e m e n to fp u b l i cs e r v i c e ，r e s t r a i nt h ed e v e l o p m e n to ft h e c h i n e s ee - g o v e r n m e n t t h ee m e r g e n c eo fg r i dt e c h n o l o g yp r o v i d e sa ne x c e l l e n to p p o r t u n i t yf o rs o l v i n g t h e s ep r o b l e m s ，a st h ec o r eo fg r i di st h ei n t e g r a t i o no fi n f o r m a t i o na n dr e s o u r c e s d u e t ot h ew o r k f l o wt e c h n o l o g ym a k e st h ep r o c e s sa u t o m a t i ca n di n t e g r a t e d ，a n di m p r o v e s w o r ke f f i c i e n c y , s p o n t a n e o u s l yl e tu sa s s o c i a t ew i t ht h e i n t e g r a t i o no fg r i da n d w o r k f l o wt e c h n o l o g y t h e r e f o r e ，t h ec o n c e p to fg r i d w o r k f l o wc o m e so u t n e v e r t h e l e s s ， m o s to ft h ee x i s t i n gg r i d w o r k f l o ws y s t e ma tp r e s e n ti sd e s i g n e df o rt h ed e m a n d so f w o r k f l o wm u l t i p l e x i n g ，b a s e do nt h ep e c u l i a rg r i ds y s t e mo fh i g h e n e r g yp h y s i c sa n d b i o i n f o r m a t i c s n o to n l ya r et h e yh e a v yo nw o r k f l o wm o d e l i n g ，b u ta l s o r a r e l y c o n s i d e r i n gt a s ks c h e d u l i n ga st h es i m p l i f i e du s e rg r o u p ，c o n s e q u e n t l yt h e r ei sn o p r i o r i t yo nr e l a t i v es c h e d u l i n gs t r a t e g y f o re - g o v e r n m e n tg r i d w o r k f l o ws y s t e mw h i c h h a sm o r ec o m p l i c a t e du s e rg r o u p ，r e s o u r c e sl i m i t i n g ，t h et a s k ss u b m i t t e db yt h eu s e r g r o u pn e e ds o m em e c h a n i s m st om a k es u r e t h a tt h e ym u s tb ef i n i s h e dw i t h i na r e a s o n a b l ep e r i o do ft i m e t h i sp a p e rb e g i n sw i t hg r i d ，i n t r o d u c e sg r i d r e s o u r c em a n a g e m e n ta n dt a s k s c h e d u l i n g ，a n di n d i c a t e st h a t t h es t r a t e g yo ft a s ks c h e d u l i n gi st h ek e yf a c t o r i n f l u e n c i n gt h ee f f i c i e n c yo fg r i ds y s t e m o nt h i sb a s i s ，c o n n e c t i n gw i t ht r a d i t i o n a l w o r k f l o w ，i tp o i n t so u tt h en e c e s s i t yo fs t u d y i n gg r i d w o r k f l o w ，t h u sm a k e sab r i e f i n t r o d u c t i o no fg r i d w o r k f l o wa n de g o v e r n m e n tm o d e lb a s e do nt h eg r i d w o r k f l o w s e c o n d l y , a f t e rc o m p a r i n ga n da n a l y z i n gs e v e r a lm o d e l i n gm e a n so fw o r k f l o w ，i t i i i 广东工业大学管理学硕士学位论文 a d o p t sp e t r in e tt ob u i l dg r i d - w o r k f l o wn e tf o rt h ea v e r a g ec a s eo fa d m i n i s t r a t i v e p r o c e d u r e sf o re x a m i n a t i o na n da p p r o v a li ne g o v e r n m e n t t h r o u g ht h i sc a s e ，i th e l p s t oa n a l y z et h ef u n c t i o no fo r d e rs c h e d u l i n gt h a th a st h em i n i m u ml o s so fw o r kt i m ei n k e yd e p a r t m e n t ，w h i c hi sb a s e do ne g o v e r n m e n ts y s t e mo fg r i d - w o r k f l o w t h i r d l y , l i n k i n gu pt h ea l g o r i t h mo fm i n i m u ml o s so fw o r kt i m ei nt h et h e o r yo fs c h e d u l i n g ，i t a b s t r a c t sm a t h e m a t i c a lm o d e l ，a n d i m p r o v e s t h e a l g o r i t h mu n d e rt h ep r a c t i c a l c o n d i t i o n s o nas i n g l ek e y - r e s o u r c et a s ks c h e d u l i n gm a t t e r s ，i te s t a b l i s h e sad y n a m i c p r o g r a md i v i d i n gt h ew h o l ed u ed a t ei n t os e v e r a ls t a g e s ，d i s c u s s e st a s ks c h e d u l i n g a l g o r i t h mo fm a n yk e yr e s o u r c e sa n dt i m ec o m p l e x i t yo fr e l a t i v ea l g o r i t h m ，l a t e ri t u t i l i z e ss u c c e s s i v ea p p r o x i m a t i o nt os i m p l yt h ec o m p l e x i t yi no r d e rt og e tad y n a m i c p r o g r a m m i n ga l g o r i t h mi np o l y n o m i a lt i m e l a s tb u tn o tt h el e a s t ，i tt a k e sa d v a n t a g e o fj a v at or e a l i z eae m u l a t i n gs y s t e mc o m p a r i n gt h i s a l g o r i t h ma n df i r s ti nf i r s t e x e c u t e da l g o r i t h m a f t e rm a n yo p e r a t i o n s ，i tg e tae m u l a t e dr e s u l te v e n t u a l l y , w h i c h a p p r o v e st h a ta l g o r i t h mc o n c e r n e db yt h i sp a p e rh e l p se l i m i n a t i n gt h el o s so fw o r k i n g t i m e k e yw o r d s ：e g o v e r n m e n t ；g r i dw o r k f l o w ；p e t r in e t ；d y n a m i cp r o g r a m m i n g ；t a s k s c h e d u l i n gs t r a t e g y ；j a v a 独创性声明 独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或者撰写过的研究成果，不 包含本人或者其他用途使用过的成果。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文和资料若有不实之处，本人承担一切相关责任，特此声明。 指导老师签字：张主乏莹 论文作者签字：石倍t 叩旨年 3 。月f 譬日 第一章绪论 1 1 研究背景 第一章绪论 电子政务是指政府机构借助电子媒介如网络技术或移动通信设施来实现管理 行为，它主要目的是推进政府部门办公自动化、网络化、电子化全面信息共享等 工作进程，从而营造运用信息及通信技术打破行政机关的组织界限的电子化虚拟 机关，实现广泛意义的政府机关间及社会各界间经由各种电子化渠道进行相互沟 通，并依据人们的需求、人们可以使用的形式、人们要求的时间和地点，提供给 人们以个性化的服务选择【- 1 。 近些年来，我国电子政务建设取得了长足进展，然而从整体上看，电子政务 的发展还很不平衡，在电子政务方面还存在着诸如三个“孤岛”( 即信息孤岛、应 用孤岛、用户孤岛) ，以及资源分散、应用水平低等因特网无法避免的问题。当前 的电子政务采用门户、数据交换等技术来实现各部门间的互连、互通，解决存在 的“孤岛”问题。门户为用户提供了接入政务的手段，但它仅仅支持某一部门、 领域的简单应用，跨部门和跨领域的服务很难实现。而且由于安全和数据规范的 问题，政务的各个部门之间不能直接共享，导致一些跨部门的业务只能使用传统 的手工方式。电子政务中核心的工作流应用，也被局限在部门的范围内，不能发 挥其作用【2 】。用户需要的是简单、方便、省时的一体化服务，即用户只需提供所 需的电子版证明材料，系统就可以自行在各个部门完成各项审批。要实现一体化 服务，需要实现各部门协同作业。上述出现的这些问题都是受当前技术自身限制 而无法避免的，因此需要采用一门新技术来对其进行完善和改进。目前，以共享 和协同为特点的网格工作流技术开始出现，并逐渐成为人们关注的焦点。结合工 作流技术的电子政务网格可以帮助政府整合和管理分散在各部门的信息化资源， 实现网格虚拟环境下的资源共享和协同工作，从而为用户提供一体化服务i ”。 本文将针对电子政务行政审批业务中的部门协同和任务调度开展“网格工作 流环境下多关键资源的任务调度策略 研究，着重于对网格工作流过程模型、动 态调度等方面问题。 广东工业人学管理学硕士学位论文 1 2 研究现状 1 2 1 国外研究现状 目前，在国外网格工作流的研究主要包括两个方面的内容，一是有关研究组 织和联盟提出的关于网格工作流的建议和规范，二是一些实际的网格项目和系统 采用网格工作流或具有工作流的特征的服务来构建与管理复杂网格应用。 g s f l ( g r i ds e r v i c ef l o wl a n g u a g e ) t g j 分析了w s f l 技术，力图利用它们结合网 格服务来解决网格服务流程；g s f l 利用己有的网格服务集成新的网格服务，或者 成为其它网格服务中的组成部分，描述网格的执行顺序和网格服务之间的交互。 采用w s f l 的思想，描述w e b 服务的流程语言，采用流程模型和全局模型。流程 模型指定了行为的执行顺序和行为间的数据交换。w s f l 全局模型将w e b 服务操 作绑定到由聚集服务定义的操作，包括导出的操作和生命周期操作。由于网格服 务自身的特点，采用w e b 服务的流程方法不能很好的解决点对点的通信问题，在 w s f l 中流程引擎作为桥梁与每一个w e b 服务通信形成w e b 服务的通信，由于在 w e b 服务中通信量不大，没有什么影响，但是在网格环境中，有可能通信量很大， 则w e b 服务引擎成为通信的瓶颈。因此在g s f l 中要引入点对点的通信，使单个 网格服务能够在网格服务引擎协同下直接通信，减少网格服务与引擎之间的通信 量。 g w a ( g r i d w o r k f l o w a r c h i t e c t u r e ) g c e ( g r i dc o m p u t i n ge n v i r o n m e n t ) 和 g s m ( g r i ds e r v i c em a n a g e m e n t ) 研究小组提出了一个网格工作流管理系统的体系结 构d o ，指出了网格工作流的生命周期包含工作流过程描述和验证，工作流实例的执 行。g w a 的目标是：定义一个网格工作流的公开架构，与g c f 和w f m c 一致， 采用已经存在的标准和实践来实现；确定在g c f 和其它组织的工作流管理系统的 公共特征和区别；确定一套研究网格工作流管理的公共问题。g w a 严格限制讨论 架构和机制而不是实现，并且还确定了网格工作流生命周期：工作流过程描述 ( w p d ) 的创建，w p d 的验证，工作流实例描述( w c d ) 创建，实例的执行。g w a 的 体系结构和各部分的关系如图1 1 所示： 2 第一章绪论 i 过程描述 d 嘭j 是对任务z 误工的单位惩罚。 三元组记号： 三元组记号由三个域组成：口l 1 7 。它们有如下涵义： 口域表示处理机的数量，类型和环境；域表示任务的性质，加工要求和限制 等约束条件；y 域表示要优化的目标函数。 第五章单个关键资源的建模与任务调度算法 5 2 2 单关键资源最少误工数调度算法 在许多情况下，延误的时问长短并不重要，只要有延迟发生，造成的影响都 是一样的，例如网格工作流中的任务，在资源的容量以及任务完成时间限制下， 很有可能在规定时间内无法全部完成，对资源的调用时间未充分满足，那只能认 为尚未完成的，从而需要进行远程调用或者增加服务能力等，在这种情况下，目 标应使得无法完成的任务数最少。而许多任务要在同一台处理机上处理，每个任 务的处理时间与工期都是已知的，如何安排处理顺序，使延误的任务数最少，这 个就是求误工任务数最少问题一l l i ：u ，。 对于这个问题有如下算法： ( 1 ) 把任务按e d d 规则排序，即任务工期最早排在最前； ( 2 ) 计算各任务完工时间，如无延误任务，则转( 5 ) ，否则转( 3 ) 找到第 一个延误任务z ； ( 3 ) 前i 任务中选取并删除加工时间最长任务，得到一部分排序，转( 2 ) ； ( 4 ) 将删除的任务以任何顺序排在所得部分排序之后，排序完毕。 将这算法应用至本文任务调度中，则删除的任务将作为需要进行远程资源调 用的任务而放入另外一个任务集中，伪代码如图5 1 ： 4 9 广东工业大学管理学硕上学位论文 5 3 算法的改进 f i g u r e5 - 1p s e u d o c o d e 上节的算法在理想状态是最优的，但放在实际应用中却有一些问题存在： ( 1 ) 现实中业务的出现很可能是突发且源源不断的，因此到达时间并非一致。 ( 2 ) 某些业务对关键资源的调用可能只是简单的数据拷贝，而有些业务却有 可能是比较运算甚至是指数级的调用。 问题( 1 ) 会因为新的原来未能估计到的任务出现而导致算法的失效； 5 0 第五章单个关键资源的建模与任务调度算法 问题( 2 ) 则是由于参考的标准仅仅只是对关键资源点的调用时间长短，而并 未考虑利用率等容易导致负担增长的相关因素，可能出现如图5 2 中的极端例子： 独 占 时 间 a b o 表示调用或者更新 图5 - 2 示意图 f i g u r e 5 2 s k e t c hm a p 在这种情况下，是增加对业务a 还是业务b 的网格服务能力，这就不是一个特 别直观的选择，因为很有可能出现，虽然调整后只有一个业务需要增加网格服务 能力，但这个业务的调整对整个网格工作流系统需付出的代价所带来的影响却大 于两个甚至多个业务。 根据上述两个问题，提出一个新的改进的启发式算法： 为解决问题1 ，应该在一个尽可能短的时间间隔中多次调用算法，这里选择的 是当每个任务完成的时刻。 为解决第2 个问题，引入优先因子w 这个权值。在网格工作流环境下，根据实 际情况不同，有诸多不同因素影响性能，在该电子政务的例中所使用的判断标准 可为资源的利用率e 、增加单位网格服务能力的代价b 、以及任务的时间p 。w 的 大小与p 成正比，b 成正比，p 成反比，即w ：一e b 。 p 新算法过程便变为如下： ( 1 ) 把任务按e d d 规则排序，即任务工期最早排在最前； 广东工业人学管理学硕士学位论文 ( 2 ) 计算各个任务完工时间，如无延误任务，则转( 6 ) ，否则转( 3 ) ； ( 3 ) 找到第一个延误任务正： ( 4 ) 前j 任务中选取并删除m 最小任务，得到一部分排序，转( 2 ) ； ( 5 ) 将删除的任务放入另一个任务集； ( 6 ) 在当前某个任务完成时重新调用一次本算法。 伪代码如图5 3 ： 图5 3 伪代码 f i g u r e5 - 3p s e u d o e o d e 5 2 第五章单个关键资源的建模与任务调度算法 5 4 本章小结 本章针对单个关键资源的任务调度误工数最少的问题建立了数学模型，对排 序论中的现有算法进行了分析，并结合实际运用给出了算法的改进。 广东t 业大学管理学硕士学位论文 第六章多个关键资源的动态规划模型及任务调度算法 6 1 问题的提出 在网格工作流中，更常见的是存在多个关键资源点的现象，继续观察4 4 2 所 举的例子，不光城建局存在多个业务交汇的情况，招商局、交通局、人事局、劳 动局等等均存在业务交汇，在这情况下交汇点对业务提供审批网格服务的次序调 度将是一个极为动态的过程，举个例子，假设招商局对业务l 的处理时间较长， 那么在城建局处理完业务2 后，业务2 需要在招商局做较长的等待，那么将又会 影响业务2 在下一步变迁的时间。当业务进入种类以及数量较多时，很有可能出 现某些业务在很早的环节等待时间就已经超过其规定的工作日期这种情况，这将 导致为确保业务按时完成所付出的代价高昂。为解决这个问题，需要对问题进行 更深一步的研究。 6 2 多个关键资源的动态规划模型的建立 尽管其他非关键资源点也有可能存在任务冲突的现象，但是为了整个模型简 化，这里作个假设：其他非关键资源点的处理能力无限，即不会发生冲突现象。 通过关键路线的求解，很容易就得出在两个相临的关键资源点之间的间隔时间是 固定不变的结论，具体过程由于篇幅，这里就不多解释。在上述结论中再做一个 简化一一忽略在非关键资源的处理时间，问题就变成如图6 1 所示： 第六章多个关键资源的动态规划模型及任务调度算法 任务一 任务二 任务三 任务四 心 资 源 各项 资 ，一一- - - - - b - ，7 源 图6 1 模型 f i g u r e6 - 1m o d e l 这个模型是阶段性、动态的，前后的任务调度相互影响。 6 2 1 问题的相关背景 在该问题中，各个任务依次在处理机外伤上完成任务的各个工序，但 对于同一台处理机来说，各任务在其上的加工顺序可能不同，由于每台处理机上j 道工序的可能排序数为，! ，因此全部可能的排序数为( 川”，这是一个非常恐怖的 指数增长。 在向下探讨之前，先介绍相关知识。 贝尔曼的最优化原理f h l ： 一个最优的策略( 卧x 2 、扣、) 所具有的性质是，不论初状态气和初决策 而如何，剩余的决策( 恐、恐、吒) ，对于从第一次决策z 。产生的状态丑开始的， 那个伽一1 ) 级过程，也构成一个最优策略。最优化原理具有两个充要条件一一目标 函数“可分性 和马尔可夫性质 目标函数“可分性”： 目标函数的可分性是指，在下述意义下，目标函数是可分的，即对所有k ，一 个甩级过程的最后k 级对目标函数的作用，仅取决于状态友一。和最后k 个决策 一t + l 、矗一i + 2 、o 状态可分性质一一马尔可夫性质： 广东工业大学管理学硕上学位论文 状态可分性是指，在级s + l 做决策t + ，之后，得到的状态o ，仅取决于忍和t + 。， 而与以前的状态九、a 、以一，无关。简单来讲，就是系统为“无记忆的”，即在任 何级，状态只取决于当前的状态和当前的决策，并且能够完全忽略导致当前状态 的所有过去的状态和决策。 6 2 2 动态规划模型的建立 可以发现，该问题依据处理机个数m ，则拥有m 个状态空间维数，即可分为m 个决策过程，前面提及，假设使用枚举的方法，则拥有( 巾“种排列方式，即使在 计算机中实现也是不可取的。而最优化以及它衍生出的方法一一动态规划可以把 一个m 维最优化问题，变换为m 个一维最优化问题去一个一个求解，从而极大的 减少了计算量。 为了满足最优化原理的充要条件，选择一个合适的级划分、状态变量、决策 变量及其收益函数则是一个需要多加考虑衡量的问题。 首先，很容易判断，级划分依据关键资源点，一个关键资源点代表一次决策， 关键资源点的顺序代表着决策次序。接下来考虑，在该问题中比较容易想到利用 各个任务在关键资源点的等待时间集合作为决策变量，但可惜选择它作为决策变 量而建立起的模型不满足马尔可夫性质。为符合最优化原理的两个条件，可选择 各个关键资源点的工期集作为决策变量，所谓的工期集是根据最后的工期划定的 在每个关键资源应该限定的完成时间，最后，规定每个关键资源点均做一次是否 应远程调用的决策，因此选择作为收益函数为在各个关键点总误工的个数之和的 最小。 为使得上述模型符合最优策略原则，还需做两个关键的假设：( 1 ) 在各个关 键资源点的工期规定的情况下，也规定了这个任务对经过下个关键资源点的到达 时间，即在中途任务完成后，应等到在这个关键资源点工期结束后方可进入下一 步；( 2 ) 任务在预期误工后，应该通过付出一定代价后在处理时间内完成。最后 得到的模型如下： 5 6 笙奎兰丝耋丝型丝型些丝墼垒些型二一 目标函数： 约束为： m i n ( z ) = 厂( ) 十厂( 而) + 厂( ) ：c a + 而+ d 五# ，恐罡，只 玉，恐oo o 均为整数集 ( 6 1 ) ( 6 2 ) ( 6 3 ) ( 6 4 ) ( 1 ) 在这里时间均为离散的整数； ( 2 ) 其中五，恐，为各个任务在各个关键资源点拟订最迟应完成时间的集 合，d 为各任务工期集合； ( 3 ) 应假设工期大于等于各个任务在各个关键资源点的处理时间之和； ( 4 ) 式( 6 3 ) 表示各个关键资源点所定工期至少应大于等于任务在各个关键 资源点的处理时间； ( 5 ) 在工期与到达时间确定情况下，厂( x ) 为单关键资源排序时的误工数； ( 6 ) m i n ( z ) ：厂( 五) + 厂( 屯) + 厂( 靠) 为各个任务在各个关键资源点经过排序后 误工任务数最小。 ( 7 ) 任务在预期误工后，可通过付出一定代价后在处理时间内完成。 示意图如图6 2 ： 厂一l 时间到阶段工 ，。、 ：工j 工： 。 期后才能继续 l 期 期 各项任务 +资资 源 源 图6 - 2 动态规划模型 f i g u r e6 - 2d y n a m i cp r o g r a m m i n gm o d e l 5 7 广东工业大学管理学硕士学位论文 6 3 动态规划模型下多关键资源任务调度算法 为求解问题，可先假设已知五、而、一。的最优值记为寸、屯+ 、一。这种 情况下，可只解一个单变量问题，将五+ 、屯+ 、一。代入式( 6 1 ) - ( 6 4 ) 中，问题变 为： 目标函数： m i n ( z ) = ( 五+ ) + 厂( 恐) + 厂( ) ( 6 5 ) 约束为： d 一五一一l ( 6 6 ) + 日，x 2 + 昱，己 ( 6 7 ) 玉，x 2 。，l 0 均为整数集 ( 6 8 ) 五，2 吲刀拦鳅果 【6 芍) 由于m i n ( z ) = 夕( 五) + 厂( 恐+ ) + 厂( 一。) 在五+ 、恐+ 、x m 一。已知的情况下是个常 数，目标函数变成： 啦i n f ( x m ) ( 6 9 ) 晶 而这时x t + 、0 、一。却是未知的，不过x t 、0 、靠一。必须满足： d 一只一昱一己一l d 一五+ 一屯+ 一一l + 己 ( 6 1 0 ) 这样才能保证问题( 6 5 ) - ( 6 8 ) 可解。若这时设定一个变量厶，这个变量通常被 称为状态变量，那么可将公式( 6 6 ) 写成为： 以( d 一只一只己一l 丸乞) ( 6 11 ) 其中厶可为只到d 一露一昱i0 之一。问任何一个整值，因为实际上 0 、而+ 、一。是未知的。 现在来求由式( 6 9 ) 以及( 6 1 1 ) 给出的问题，即： 目标函数： m i n 厂( ) ( 6 1 2 ) 晶。、 。 约束条件： 丸( d 一暑一只。匕一l 丸只)( 6 1 3 ) 换而言之，在这个特定问题上，可以看为一个单个关键资源排序问题，所不 同的是这个排序问题是排序方式与各个任务处理时间已定，而工期与到达时间不 5 8 第六章多个关键资源的动态规划模型及任务调度算法 定。 若给出一个厶值，则可以计算出m b a 2 n 。厂( ) ，在这里下个定义： g m ( 丸) _ m 捌i n 厂( ) ( 6 1 4 ) x m + ( 九) - x m ( 6 1 5 ) 上式中( 6 1 4 ) 定义( 丸) 为f ( x 。) 的最小值，而式( 6 1 5 ) 中定义x m ( 丸) 为当厂( ) 为最小时的值。如此g m ( 2 m ) 、( 厶) 皆为厶的函数，因此1 o l 题的解将限定在丸的 某些特定值上。若对全部的丸求解式( 6 1 2 ) 和( 6 1 3 ) ，可得到一个列表，见表6 1 ： 表6 1 解列表 t a b l e 6 1s o l u t i o nl i s t 厶己 + 1出 争晶一州晶 g m ( 丸)万( 只)t o ( p + 1 )刃( d 一号一昱一0 。一1 ) w ( d 一写一昱一霉：一) x m + ( 丸)仃( 己)以己+ 1 )a ( d 一日一e 一z 一1 )o - ( d 一暑一昱己一。) 当厶= 己时兄有1 7 种组合，当丸= 己+ 1 时丸有2 种组合，依次类推至 丸= d - p , - 8 已一。时丸有( d 一日一罡己一。一己) 7 种组合，其中为任务数， 而万( 屯) 仃( 以) 均为( 丸) ( 丸) 关于厶映射列表。 在得到表6 1 后，接下来考虑如下问题： 目标函数： 一- ( 以一t ) 暑铀m i n 艘厂( ) 】+ 厂( 一一) ) ( 6 1 6 ) 约束条件： 以一l x m l( d 一露一只。己一2 以一l 己一l + 乞) ( 6 1 7 ) 根据最优原则，可以这么认为，式( 6 1 6 ) 0 0 可行解即为一。( 厶一。) 的可行解，那 么把公式( 6 1 4 ) 代入( 6 1 6 ) p ，把式子变换成： 一，( 丸一。) = 叫孕 ( 以一。一一。) 】+ 厂( 一。) ( 6 1 8 ) 4 舸一l 工o m i 而由于己，根据式( 6 17 ) 可得如下式： 只一。x m 一。( 丸一。一己) ( d 一日一只己一2 厶一。只一l + 乞)( 6 1 9 ) 把( 6 1 9 ) 代入( 6 1 8 ) 则生成如下式： 5 9 广东工业大学管理学硕上学位论文 g 肼一l ( 厶一1 ) 2 足- 。铂m ；i ( n 厶- 昂) 【g m ( 丸一l 一一1 ) + ( 一1 ) ) ( 6 2 0 ) 其中d 一露一e 只一：厶一。己一。+ 只。 经过转化，现在可以求解式( 6 2 0 ) ，对于全部可能的( 以一。) 丸一。= 以- 1 一。的值， 在表6 2 1 中已经全部列出，因此，求( 厶一。一一。) 是一个仅仅需要对照表的过程， 举个例子：假设丸一。= 以一，则己一。一。( 厶一。+ 一己) ，换句话说，一。可以取得在己一。 与丸一，一己之间的任意一个集合，将两个参数代入式( 6 2 0 ) 得： 一l ( 以一l “= 。铂m s i ( n 厶。一昂) ( 岛( 丸一i 一一1 ) 】+ f ( x m 1 ) ) ( 6 21 ) = m i n g 。( 丸一l 一已一。) + 厂( 己一。) ， g 埘( 丸一，一只一。一1 ) + 厂( 己一，+ 1 ) ， ( 己) + 厂( 丸一。一己) 】 对于固定的厶一。而言，则式子( 6 2 1 ) 是- - 个单变量最优化问题，类似地便可以 得到表6 2 的全部项，具体如下： 表6 - 2 解列表 t a b l e 6 2s o l u t i o nl i s t 厶一l 乞一。+ 己喘+ l如档l _ 出p - 争如 鼬)疗( 乞一l + )哦。+ 己+ 1 )刃( d 一号一昱- 露吨一1 )机d 一日一昱一己一：) 钿+ ( 钆)盯( 巴一。+ 己)哦l + 己+ 1 ) o ( d 一日一昱一乞吨一1 )盯( d 一露一最乞一：) 当厶一。= 乞一。+ 己时以一。有1 7 种组合，当以一。= 己一，+ 巴+ 1 时丸一，有2 7 种组合，依 次类推至丸一，= d - p , 一己一：时丸一。有( d 一只一只己一。一只) 。种组合，其中歹 为任务数，而万( 以一，) 仃( 丸一。) 均为一。( 厶一，) 一。+ ( 丸一。) 关于砧。映射列表。 重复上述的推导，把所有推导过程中的列表一一求出，得到所一1 个列表。在 上述的基础上，现在来考虑最后一个单变量问题： g t ( a ) 。椒氧 寝r 玛) 【9 2 ( a 一五) 】+ 厂( 五) ) 6 2 2 ) 其中极小化是在曰五( 五一只一巴一。一罡) 中五取整数的条件下考虑的。 那么把之前所有推导出的如( 6 9 ) ( 6 2 1 ) 等类似公式带入( 6 2 2 ) 中并合并，可得： 第六章多个关键资源的动态规划模型及任务调度算法 g 。( a ) = m i n g ：( 丑一五) + 厂( 五) 】 x i = m i n m i n 一9 3 ( 丑一五一屯) + 厂( 屯) 】+ 厂( 五) ) 2 【以一五一屯) + 【屯月+ 【五，j x i恐 ( 6 2 3 ) = m i n m i n m i n 9 4 ( ；q 一五一x 2 一毛) + 厂( b ) 】+ 厂( 恐) ，厂( 五) 而j 血 = m i n m i n m i n m i n g 。( a 一五一恐- 1 ) + 厂( 一1 ) 】厂( 而) ) 厂( ) 而也而h 这时的状态变量a 已经包含了n ，x 2 的所有最小求值可能，因此可以这么认 为，当令a = d 时，公式( 6 2 3 ) r i 为原问题( 6 1 ) - ( 6 4 ) 的解，把公式( 6 2 3 ) 转换如下： ( d ) 2 概蜊一挛k 岛) 【( d 一) + 厂( 五) 】 6 2 4 ) = m i n g ：( d 一日) - i - 厂( # ) ， 9 2 ( d 一日一1 ) + 厂( 曰+ 1 ) ， g ：( + b 己) + ( d 一只一b 只) 】 根据公式( 6 2 4 ) ，查询前面生成的m 一1 个列表，把表中的数据代入，得出一个 最小的值，很有可能有多个最小值相同，在这种情况下可以只取其中一组并得到 这一组的五的取值五+ 。把五= + 代入公式( 6 2 3 ) 可得到这个时候g ：( 五) 的值，对比相 应的列表，这时也可能有多个相同的g ：( a ) 的值，任取一个可求得x 2 = 屯， 依次类 推，得到所有的玉+ ，x 2 , 毛+ 并可得到相应的排列顺序，至此，问题已经解决。 上述模型以及解题可用图6 3 表示如下： 6 1 广东工业大学管理学硕上学位论文 恐 厂( 工。)f ( x ：)f ( x 。一。)厂( z ，) 图6 3 动态规划模型演算过程 f i g u r e 6 3c a l c u l u sp r o c e d u r eo fd y n a m i cp r o g r a m m i n g 6 4 算法的改进 最坏情况的2 彬2 1 ，+ 2 ，+ + ( a - 8 一昱只一。一乞) 7 】( 其中2 为单机排序的 时间复杂度) ，即时间复杂度为d ，虽然相比枚举的方式( ! ) ”而言，确实改进不少， 但由于其时间复杂度仍然为指数级，究其原因，主要是状态变量名是一组集合从而 导致整个问题的状态变化复杂，为此可采用逐次近似法来降低状态的维数。方法 的要点是先保持部分状态变量的不变，对其余变量实现最优化后，以迭代的形式 反复进行这样的过程，直到获得某种程度的收敛为止。 这次将把集合拆分，过程简单描述如下： 目标函数： m i n ( z ) = 厂( 五l ，x 2 l 弓1 ) + 厂( 五2 ，巧2 ) + 厂( 五。，x j m ) ( 6 2 5 ) 约束为： 玉i + x m 2 + 。吐 ( 6 2 6 ) 而l + 恐2 + x 2 。d 2 6 2 第六章多个关键资源的动态规划模型及任务调度算法 x i i + x j 2 七x m d i x 枷厶 ( j = 1 ，2 ，j ；m = 1 ，2 ，m ) 对于状态变量工拥( j = 2 ，3 ，j ；m = 1 ，2 ，m ) ，选定随机的符合约束条件的 值记为z 加。( j = 2 ，3 ，j ；m = 1 ，2 ，m ) ，x j m + 代入式( 6 2 5 ) 以) f l t 2 ( 6 2 6 ) ，这时状态变量 只有五。( j = 2 ，3 ，j ；m = 1 ，2 ，m ) 未知，原问题变为： 目标函数： m i n ( z ) = 厂( 五1 ) + f ( x t 2 ) + 厂( 五。