（计算机应用技术专业论文）跨企业项目调度优化方法研究.pdf

哈尔滨理工大学工学硕士学位论文 跨企业项目调度优化方法研究 摘要 跨企业项目是一项较复杂的系统工程，实施中受到各种资源和工序逻辑 关系的约束，同时存在较多的不确定因素，这就要求项目调度具备一定的鲁 棒性。但生产系统的运行却很难维持在一个一成不变的项目调度上，从而在 线调整在所难免，使得调度问题成为一个需要不断优化的动态过程。需要制 定合理、可行的调度计划，以保障项目的按时完工。 本文结合国内外研究问题的背景，指出关键链技术对于科研及工程项目 的重要意义；然后综述了前摄策略与反应式策略相关的一些基础理论知识， 针对基于前摄策略与反应式策略的跨企业项目调度优化方法进行了深入系统 地研究。本文针对项目调度的鲁棒性问题提出了如下方法： 首先，引入基于约束理论的关键链技术，采用基于最晚开始时间优先规 则的启发式算法得到近优调度算法。在综合考虑资源紧张度和项目复杂度的 情况下，对各个工序所在的链路分别设置缓冲区，得到较适中的关键链和非 关键链缓冲大小，使得整个项目的完工率得到保证。运用灰色关联分析计算 冲突工序获得资源的优先级，使得资源得到合理的配置。 其次，将得到的缓冲大小分别加到各个链路上，按照“越迟开工越好 的原则，以各工序最晚开始时间为准则，从后向前检测工序间是否存在紧后 关系和资源冲突，在此基础上调整各工序的开始时间，得到最终项目调度 图。并以产品水平和净成本最低为目标建立了数学模型，证明了该策略的鲁 棒性。 最后，本文提出_ 种基于前摄与反应式策略的鲁棒调度新策略。针对工 序处理时间不确定这一问题，给出了如下实现策略：通过包含不确定处理时 间参数的优化调度模型，获取目标期望值最优的前摄调度策略；然后根据模 型中的相应约束和生产现场反馈的实际信息确定后序任务的开始时间，依次 类推实现调度的在线调整。仿真验证表明该策略可以保证整个调度的鲁棒 性，达到项目的综合优化。通过系统功能的实现验证了算法有效性。 关键词跨企业项目；调度优化方法；前摄策略；反应式策略；关键链 哈尔滨理工大学工学硕士学位论文 r e s e a r c ho nc r o s s - - e n t e r p r i s ep r o je c ts c h e d u l i n g o p t i m i z a t i o nm e t h o d s a b s t r a c t t h ec r o s s - e n t e r p r i s ep r o j e c ti sac o m p l i c a t e ds y s t e m se n g i n e e r i n g i ti su n d e r t h ec o n s t r a i n t so fa l lk i n d so fr e s o u r c e sa n d w o r k i n gp r o c e d u r el o g i c a l r e l a t i o n s h i pd u r i n gi m p l e m e n t a t i o n ，a n ds i m u l t a n e o u s l y h a sm a n yu n c e r t a i n e l e m e n t so fu n c e r t a i n t i e s ，w h i c hm e a n sc e r t a i nr o b u s t n e s so fp r o je c ts c h e d u l i n g w i l lb er e q u i r e d b u tt h em o v e m e n to fp r o d u c t i o ns y s t e mi sa c t u a l l yd i f f i c u l tt o k e e p i na ni n v a r i a b l ep r o je c ts c h e d u l i n g ，s oi ti sh a r dt oa v o i dt h eo n - l i n e a d j u s t i n g ，w h i c hm a k e ss c h e d u l i n gp r o b l e m b ead y n a m i cp r o c e s sw i t h c o n t i n u o u so p t i m i z a t i o n i no r d e rt oe n s u r et h ep r o j e c tt ob ef i n i s h e do nt i m e ，t h e s c h e d u l i n gp l a nm u s tb er e a s o n a b l ea n df e a s i b l e t h i sd i s s e r t a t i o np o i n t e so u tt h ei m p o r t a n tm e a n i n go ft h ec r i t i c a lc h a i n t e c h n o l o g yt ot h es c i e n c er e s e a r c ha n dp r o je c t sb a s e do nt h eb a c k g r o u n do f p r o b l e ms t u d i e d ；t h eb a s i cp r i n c i p l e s ，f e a t u r e sa n dp r o b l e m so ft h ep r o a c t i v ea n d r e a c t i v e s t r a t e g y a r es u m m a r i z e d c r o s s - e n t e r p r i s ep r o je c ts c h e d u l i n g o p t i m i z a t i o n s b a s e do nt h ep r o a c t i v ea n dr e a c t i v e s t r a t e g y a r er e s e a r c h e d t h o r o u g h l ya n dd e e p l y t h ea l g o r i t h m sa r ep u tf o r w a r di nt h i sd i s s e r t a t i o nf o rt h e p r o b l e m so fp r o je c ts c h e d u l i n gr o b u s t n e s s f i r s t l y ，t h i sd i s s e r t a t i o ni n t r o d u c e st h et e c h n o l o g yo fc r i t i c a lc h a i nw h i c hi s b a s e do nt h et h e o r yo fc o n s t r a i n t s ，a n da d o p t st h eh e u r i s t i ca l g o r i t h mw h i c hi s b a s e do nt h er e g u l a t i o no ft h el a t e s ts t a r tt i m ew i t hh i g hp r i o r i t yt oo b t a i nt h e n e a r o p t i m a ls c h e d u l i n ga l g o r i t h m b u f f e ro ft h el i n k i se s t a b l i s h e di ne a c h w o r k i n gp r o c e s sr e s p e c t i v e l yu n d e rt h e ，o v e r a l l c o n s i d e r a t i o no ft e n s i t yo f r e s o u r c e sa n dc o m p l e x i t yo fp r o je c t s oc r i t i c a lc h a i na n dt h en o n - c r i t i c a lc h a i n o b t a i nt h em o d e r a t eb u f f e rs i z e s ，a n dt h ef i n i s hr a t eo ft h ee n t i r ep r o je c ti s e n s u r e d t h ep r i o r i t yo fr e s o u r c e si so b t a i n e db yu s i n gt h eg r a yc o n n e c t i o n - i i - 哈尔滨理工大学工学硕士学位论文 a n a l y s i st oc o m p m et h ec o n f l i c tw o r k i n gp r o c e d u r e ，w h i c he n a b l e st h er e s o u r c e s c o n f i g u r e dr e a s o n a b l y s e c o n d l y ，b u f f e rs i z ei sa b l et ob ea d d e dt oe a c hc h a i ns e p a r a t e l y t h ew o r k i n g p r o c e s s e sa r ee x a m i n e df r o me n dt of r o n tt oc o n f i r mw h e t h e rt h et i g h tr e l a t i o n s a n dt h er e s o u r c e sc o n f l i c th a v eo ra c c o r d i n gt o “al a t e ro p e r a t i o ni sb e t t e r ” p r i n c i p l ew i t ht h el a t e s ts t a r tt i m ea sc r i t e r i o n t h es t a r tt i m eo fw o r k i n gp r o c e s s i sa d j u s t e do nt h i sb a s i ss oa st oo b t a i nt h ef i n a lp r o j e c ts c h e d u l i n gc h a r t s i m u l t a n e o u s l yt h em a t h e m a t i c a lm o d e li sb u l i tw i t ht h el e v e lo fp r o d u c ta n dt h e l o w e s tn e tc o s ta st h eg o a l ，w h i c hp r o v e st h er o b u s t n e s so ft h es t r a t e g y f i n a l l y ，an e wr o b u s ts c h e d u l i n gs t r a t e g yi sp r o p o s e db a s e do nt h ep r o a c t i v e s t r a t e g ya n dr e a c t i v es t r a t e g y i nv i e wo f t h ep r o b l e mt h a tt h ep r o c e s s i n gt i m eo f w o r k i n gp r o c e s s e s i s u n c e r t a i n ，t h e r e a l i z e d s t r a t e g y s h o w s ：t h ep r o a c t i v e s c h e d u l i n gs t r a t e g yw i t ht h eh i g h e s tg o a le x p e c t e dv a l u e i so b t a i n e db yt h e o p t i m i z a t i o ns c h e d u l i n gm o d e l w h i c hc o n t a i n s t h ei n d e f i n i t e p r o c e s st i m e p a r a m e t e r a n dt h e nt h es t a r tt i m eo f s u c c e s s o rp r o c e s st a s ki sd e t e r m i n e db yt h e c o r r e s p o n d i n gr e s t r a i n t si nt h em o d e la n dt h ea c t u a li n f o r m a t i o nr e f l e c t e df r o m p r o d u c t b ya n a l o g y t h eo n l i n e a d j u s t m e n t i sr e a l i z e d t h es i m u l a t i o n c o n f i r m a t i o ns h o w e st h a tt h i ss t r a t e g yg u a r a n t e e st h er o b u s t n e s so ft h ee n t i r e s c h e d u l i n g ，e n h a n c e st h er e a c t i o n r a t eo ft h eo n l i n ea d j u s t m e n t ，a n dt h e n a c h i e v e st h es y n t h e s i so p t i m i z a t i o no ft h ep r o j e c t t h ei m p l e m e n t a t i o no fs y s t e m f u n c t i o n a l i t yv e r i f i e st h ev a l i d i t yo ft h ea l g o r i t h m s k e y w o r d sc r o s s e n t e 印r i s ep r o je c t ，s c h e d u l i n go p t i m i z a t i o na l g o r i t h m ，p r o a c t i v e s t r a t e g y ，r e a c t i v es t r a t e g y ，c r i t i c a lc h a i n - h i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文跨企业项目调度优化方法研 究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰 写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方 式注明。本声明的法律结果将完全由本人承担。 作者签名：椭 日期： 2 卯尸年争 月 彦 日 哈尔滨理工大学硕士学位论文使用授权书 跨企业项目调度优化方法研究系本人在哈尔滨理工大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大 学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子 版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或 其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密 口， 在年解密后适用授权书。 不保密f - v i 。 ( 请在以上相应方框内打) 作者签名：刮黼 日期： 导师签名：缎害阅 日期： 潮、 ， d 口p ， 年华月矿日 年年月寥日 哈尔滨理工大学工学硕士学位论文 1 1 课题来源 第1 章绪论 本课题来源于哈尔滨市后备带头人基金项目( 2 0 0 4 a f x x j 0 3 9 ) “网络化制 造环境下协同项目计划与控制系统研究”。 1 2 课题的研究背景及意义 随着全球网络化经济的发展，世界市场的竞争变得越来越激烈，企业项目 的规模越来越大，对项目管理的要求也越来越高。项目调度是项目管理的一个 重要方面，合理的调度计划是降低成本、提高质量、缩短周期的重要保证。所 以系统、全面、合理的项目调度方法不仅有助于提高企业的综合自动化水平， 而且可以为企业部门带来显著的经济效益“，。 跨企业项目管理是一种新的项目管理模式。面对机遇产品的竞争环境，企 业要在短时间内，不确定因素和合理的资源限制下组织完成机遇产品的研制与 开发，以最大的敏捷性响应市场需求，通过具有敏捷性的企业间协作，将各个 企业的核心资源进行共享，组成动态联盟，并以项目管理理念进行管理才可以 提高企业对于市场机遇的响应速度，降低新产品的开发成本，提高产品的市场 竞争力。 如何安排多企业的生产计划、如何进行跨企业项目调度成为多企业生产顺 利、有效进行的关键问题。有效的调度方法与优化技术的研究和应用，对于制 造企业提高生产效率、降低生产成本等方面起着重要作用心1 。国外的实施状况 也表明，单纯提高生产装置的控制水平，寻求局部最优的投入产出比，远远低 于提高整体管理水平的投入产出比。因此，对项目调度所采用的算法的改进是 提高企业综合收益的最有利手段，这样就涉及到了项目调度优化算法的研究。 调度优化就是指设计出性能更优的调度算法，使顾客的满意度极大化，从而在 企业项目的竞争中处于不败之地。因此，在当今企业竞争日益激烈的情况下， 调度优化显的尤为重要强钔。 由于不确定因素的存在，项目调度具备一定的鲁棒性成为必须的条件，但 生产系统的运行依然很难维持在一个一成不变的项目调度上( 这里的项目调度 哈尔滨理工大学工学硕士学位论文 一般是指一个调度方案) ，在线的调整在所难免，这使得调度问题成为一个需 要不断优化的动态过程哺1 。所以本课题的研究目标是采用前摄调度优化方法实 现项目调度的鲁棒性目标，并且采用反应式调度策略使得优化方法在项目执行 过程中对于不确定性带来的扰动做到最小的改动，研究出上述目标的优化方法 是本课题研究目的即研究基于前摄与反应式策略的跨企业项目调度优化方法。 1 3 项目调度问题的研究现状 项目调度问题就是如何安排生产过程中的资源( 包括机器、时间等) ，使得 各个项目可以有序，极大化的利用资源和时间的同时按时完成任务。项目调度 问题广泛存在于建筑工程、软件开发、飞机及轮船制造等各种单件和小批量生 产方式的企业中，属于非常复杂的优化问题。 实施项目调度的基础是建立正确的调度模型，运用各种优化技术来实现最 优调度方案目标：项目周期最短、资源消耗水平最低、时间成本平衡以及最 大净现值等。传统的项目计划与调度方法已经无法完全满足现代项目管理的实 际需求。针对不确定环境下的项目优化调度方法直到近几年才开始引起学术界 的关注和研究。资源受限项目调度和跨企业项目调度的研究如下。 1 3 1 资源受限项目调度问题 项目在执行过程中需要各种各样的资源，资源的使用都是受限的。因此如 何充分利用各种有限资源完成项目就成为项目管理过程中的一个重要的问题。 关键路径法( c r i t i c a lp a t hm e t h o d ，c p m ) 和计划评审技术( p e r f o r m a n c ee v a l u a t i o n r e v i e wt e c h n i q u e ，p e r t ) 被广泛应用于项目计划和控制过程中，但忽略了对资 源的限制，所以根据这两种方法编制的计划在资源受限的情况下一般不能够得 到保证，由此产生了资源受限项目调度问题1 ( r e s o u r c e c o n s t r a i n e dp r o j e c t s c h e d u l i n gp r o b l e m s ，r c p s p s ) 。 r c p s p s 理论上属于n p ( n o n p o l y n o m i a lc o m p l e t e ，n p 完全) 困难问题盯1 ， 该问题模型丰富，许多问题都是r c p s p s 的特殊情形，例如作业车间( j o bs h o p ) 调度，流水车间( f l o ws h o p ) 调度等。此外r c p s p s 广泛存在于建筑工程，软 件开发，计算机行业( 如操作系统中的资源管理、处理器的任务调度) ，飞机及 轮船等单件或小批量生产方式的企业中，企业可利用有限资源，合理地安排生 产任务降低生产成本，以提高经济效益。因此研究r c p s p s 具有重要的理论和 现实意义阻】。 哈尔滨理工大学工学硕士学位论文 r c p s p s 可分为确定性资源受限项目调度问题；随机资源受限项目调度问 题；模糊资源受限项目调度问题嘲。在后续章节主要讨论确定性资源受限项目 调度问题。 随着禁忌搜索n ( t a b us e a r c h , t s ) ，模拟退火1 ( s i m u l a t e da n n e a l i n g ， s a ) 、遗传算法“羽( g e n e t i ca l g o r i t h m ，g a ) 和蚁群算法n 阳( a n tc o l o n ya l g o r i t h m ， a c a ) 等现代优化方法的出现，大型资源受限项目调度问题得到了更加有效的 求解。但调度计划是在确定环境中进行的，在项目执行的动态环境中存在着许 多不确定性，这些不确定性往往会导致项目无法按计划完成，资源受限项目调 度理论对这个问题没能给出有效的处理方法。针对这一问题，1 9 9 7 年高德拉特 ( e l i y a h um g o l d r a t t ) 博士将约束理论( t h e o r yo fc o n s t r a i n t s ，t o c ) 应用于项目 管理领域，建立了关键链( c r i t i c a lc h a i n ，c c ) n 们项目管理理论。关键链项目管 理理论在世界上己有成功应用，但对关键链理论研究时间并不长，在理论和应 用中还有许多地方需要进一步深究和完善。 1 3 2 跨企业项目调度研究 跨企业项目调度的特性就表现在动态联盟的定义上，建立在机遇产品基础 上；由多个各有专长的敏捷型企业组成的临时联盟，这些敏捷型企业利用各自 的特长联合起来进行机遇产品的经营生产；产品生命周期一旦结束，联盟也自 行解体n 朝。 文献 1 6 】针对动态联盟的建立与运行方式、敏捷企业的管理与决策问题， 提出集成化动态联盟建立支撑环境，从而支持动态联盟的快速建立与经营管 理。文献 1 7 】提出跨企业信息集成的基本框架，解决了传统平台技术在实现企 业间信息集成的固有限制。文献 1 8 】提出了一种适应i n t e m e t 环境下协同产品 开发的工作流管理体系结构。文献 1 9 】提出以满足资金流约束为目标的动态联 盟项目计划优化算法。 1 3 3 前摄策略调度方法研究 一种前摄调度的目标是产生一个鲁棒调度，方法是产生一个调度方案，在 执行的时候，可以确定项目周期，使干扰或各种不确定因素对最初调度策略性 能指标的影响最小。对于鲁棒性有质量鲁棒性和解决方案鲁棒性两类啪1 。文献 中已研究出的前摄调度策略有以下几种。 1 3 3 1 基于关键链的项目管理方法关键链项目管理( c r i t i c a lc h a i na r o j e c t m a n a g e m e n t ，c c p m ) 是2 0 世纪9 0 年代末出现的全新的项目管理理论与方法， 哈尔滨理工大学工学硕士学位论文 它与传统的项目管理理论相比在多方面具有较大优越性，能够有效缩短工期， 减少w i p ( w b r ki np r o c e s s ，w m ) ，提高项目的执行效率和效益堙。因此，研究 c c p m 对提升我国的项目管理水平具有重大的理论意义和实践意义。 文献 2 2 】提出的方法能够有效缩短工期、提高项目管理效率、有效应对项 目执行过程中的不确定性，不足之处是关键链的识别十分困难。文献 2 3 】提出 了一种用蒙特卡罗模拟技术确定项目缓冲区大小的方法，并认为自由时差可充 当汇入缓冲区的角色。文献 2 4 】提出了一种改进的关键链项目调度方法，并与 传统项目管理、关键链项目管理进行比较，指出了各自的优缺点。刘士新等乜5 1 对关键链项目管理理论进行了系统的介绍，并讨论了关键链项目管理的优点和 不足，指明了进一步的研究方向。蔡晨和万伟乜们在p e r t c p m 的基础上，引入 t o c 的核心思想，提出了一种基于三点估计的关键链管理方法。 1 3 3 2 启发式算法从实用的角度来看，启发式算法( h e u r i s t i ca l g o r i t h m ) 易于 实现、计算复杂度低，但它们一般不具有全局优化的特点。 1 基于优先规则的启发式算法基于优先调度规则的启发式算法由两个要 素组成：计划生成方案和优先规则。计划生成方案可分为串行调度方案和并行 调度方案，两种方法都是对一个不完全计划进行扩展，直至生成一个完全计 划。工作的优先权系数是根据优先规则计算的，目前尚没有一种优先规则对所 有类型的问题实例都能求出令人满意的解，因此，根据问题实例的参数特点来 选择一种或几种启发式规则的组合来对问题进行求解，并选择最优解形成调度 计划是此类算法的一个较好策略。 2 智能优化算法r c p s p s 的智能优化方法主要包括编码方式和解码规 则、相邻解的定义以及初始解产生三个要素。求解r c p s p s 的智能优化算法主 要区别在编码方式和解码规则上。文献 2 7 】用了紧前关系相容链表编码方式， 文献【2 8 】采用了优先权系数向量编码方式，文献 2 9 】采用了优先规则链表编码 方式，用并行调度方案和专门设计的双向解码规则解码，得到了较好的效果。 由于上述三类编码方式和解码规则都存在冗余编码，这样就会降低算法的求解 效果和执行效率。所以，结合问题特点设计更好的编码方式和解码规则是改进 此类算法的关键所在。 1 3 3 3 具有计算智能的局域搜索算法近年来，一些高级局域搜索法由于具有 普遍适用性和较低的经验复杂性等优点，得到了广泛的重视和应用。 1 遗传算法由于g a 原理和操作简单，通用性强，不受限制条件的约 束，且具有隐含并行性和全局解空间的搜索能力，在机器学习、运输问题、模 式识别、控制工程等领域，尤其是在优化调度领域得到了广泛的应用。虽然 哈尔滨理工大学工学硕士学位论文 g a 能以大概率搜索到全局最优点，但g a 的收敛速度很慢和搜索效率低问题 是它的主要缺陷。 对于解决项目调度这类多约束的优化问题，在使用传统的遗传算法时将会 产生很多不可行解，为了找到比较优秀的解，众多学者对传统的遗传算法进行 了很多改进。比如遗传算法与其他算法的结合。方剑和席裕庚嘲研究了遗传算 法和分派规则的结合，处理与操作序列有关的工件安装时间和到期时间约束的 复杂调度问题。通过考虑不可行解在优化过程种的作用，文献【3 1 】提出了分组 比较遗传算法。该算法可以在搜索过程中保持一定数量的不可行解，可以更好 的解决调度问题。 2 禁忌搜索算法、模拟退火算法、蚁群算法提供了一种解决调度优化问 题的新途径。但也存在着一定程度的缺点：收敛到最优解很慢，并且对于判断 解的最优性也很困难，在这方面也需要做进一步的研究。 1 3 3 4 分支定界算法分支定界算法的基本思想是先用搜索树将问题的解空间 按照一定的规则分割成子空间( 分支过程) ，再利用合理的定界方法排除那些不 包含最优解的子空间( 定界过程) ，从而实现缩小有效搜索空间的目的。 l a m b r e c h t s 等曲在分支定界算法中引进了最小延迟替代集的概念，解决资 源冲突。 1 3 3 5 其他优化方法如文献 3 3 】，采用情景分析的方法，或者基于最坏情景 建模，求取最优的性能指标。由于项目调度问题中含有的很多不确定因素与人 的主观认识有关，比如对交货期，延迟时间及处理时间的估计等，所以有的学 者认为采用模糊集理论来描述更为合理。l i n 等m 1 提出的基于鲁棒优化的鲁棒 调度框架，用于不确定参数有界的情况下，选择一种对参数变化免疫的调度方 案。另外，s r i n v a s a n 等5 - 剐把优化过程定义为对最优性条件的跟踪，从而 提出基于动态优化的鲁棒调度方法。 1 3 4 反应式调度方法研究 反应式调度( r e a c t i v es c h e d u l i n g ) 是早期处理不确定性因素主要采用的方 法，就是当不确定的事件发生之后再决定应该怎么做，根据实际情况对初始调 度进行动态的修改，也可以称为在线调度，这也曾经被认为是处理调度中的不 确定情况的最好的方法。对于动态不确定环境下的调度问题，反应式调度可归 类为完全反应式、预测反应式两种典型的调度策略。 1 3 4 1 完全反应式调度不生成预调度，根据在决策时刻的可得信息采用某种 哈尔滨理工大学工学硕士学位论文 策略来调度工序，这种方法一般采用分派规则或者其它的启发式方法来对等待 执行的工序按照优先权顺序排队，其实质是一种在线调度方式。通常分派规则 以执行时间和交货期为依据，信息处理量少，计算量很小，反应迅速。调度决 策基于系统的当前状态，所以完全反应式调度与实时信息获取密切相关。 1 3 4 2 预测反应式调度预测反应式调度是执行层反应式调度的常用策略，它 有两个基本步骤：第一步，不考虑执行层未来的干扰事件生成优化某一目标的 预调度；第二步，更新调度响应干扰或者其它动态事件来保持调度的可行性或 者改善调度性能。该方法的关键在于判断是否对干扰进行反应式调度和采用何 种方式进行反应式调度。由于不希望进行完全的再调度，因而反应式调度的研 究内容主要集中在怎样修改初始调度，才能对调度的其他部分影响最小，以及 希望尽量的保持生产的连续性，并经常采用各种启发式方法。 在动态反应式调度环境下，v i e i r a 等1 提出了等待任务数目达到一定阂 值引发反应式调度的事件驱动反应式调度，h u e r c i o 等啪1 和h o n k o m p 等啪1 提出一种处理时间不确定和设备故障的反应式调度框架，将一个基于确定模型 的调度优化器和一个过程仿真器结合在一起，以应对不确定事件的发生； i e r a p e t r i t o u 和f l o a d a s “们提出的基于连续时间描述的批处理过程短期调 度模型，虽然在描述存储方面存在不足，但简单且结构特点鲜明，有利于本文 所提出策略的实现。文献 4 l 】研究的是前摄与反应式策略的分类研究；类似的 研究文献还有 4 2 4 4 等。 1 3 5 考虑干扰影响的反应式调度方法 反应式调度是对干扰的必要响应，简单反应式调度方法花费计算成本小且 容易实施，但是可能导致较差的鲁棒性和稳定性。在过去几十年里，出现了一 些预先考虑干扰影响的方法。除了经典的性能指标，引入了两种新的指标：鲁 棒性和稳定性。一个调度在干扰情况下依然保持良好的性能称该调度是鲁棒 的。一个调度与干扰情况下的实际调度之间的偏差很小，则称该调度是稳定 的，这种偏差又分为时间偏差和顺序偏差。如果干扰的发生时刻是有限确定 的，则很容易计算调度鲁棒性和稳定性指标。然而，在实际生产中，很多干扰 发生时刻是不确定的，造成了计算鲁棒性和稳定性的困难性，此时需要采用合 理的代理指标并设计有效的调度算法。从优化指标类型划分，鲁棒调度方法可 以分为最小化期望指标和最小化最坏指标两类。 1 3 5 1 采用期望性能指标的调度方法采用期望指标的方法，适用于存在较小 哈尔滨理工大学工学硕士学位论文 范围的扰动或者干扰源可以较准确地以概率形式描述的调度环境。 w u 等5 1 研究了机器故障情况下兼顾稳定性的单机反应式调度算法，此时 调度问题是一个兼顾效率指标和稳定性指标的双目标优化问题，分别采用了成 对交换算法和遗传算法有效确定双目标问题的p a r e t o 前沿面，对单次故障的仿 真结果表明在牺牲效率指标的情况下极大改善了调度的稳定性。l e o n 等m 3 分 析了执行环境中干扰如何延迟工序的问题，采用遗传算法寻找以期望延迟和期 望的最大完成时间为目标的鲁棒预调度。文献 4 7 】比较了动态不确定环境中多 种调度规则的鲁棒性。m e t h a 等h 引分别设计了针对单机和在机器随机故障情 况下的预调度算法，通过在完全不考虑故障的调度中插入适当的空闲时间生成 具有稳定性的预调度，并设计了相关的代理指标。针对机器随机故障的单机调 度环境，o d o n o v a n 等m 1 设计了一种鲁棒调度和反应式调度方法，其生成预 调度的算法与文献 4 8 】相似。 1 3 5 2 最小化最坏性能指标的调度方法以最小化最坏性能为指标的鲁棒调度 方法，其目的是保证调度在不确定参数的所有可能实现情况下的性能都比较 好，适用于存在较大范围扰动的调度环境。 文献【5 0 】从最优调度的不变性角度出发研究调度的鲁棒性问题，定义了最 优调度的区间摄动鲁棒性。 1 4 目前研究存在的问题 尽管对于项目调度优化的方法很多，但兼顾到鲁棒调度和反应式调度这两 级的调度方法并不是很多，并且已研究出的调度方法存在收敛速度很慢、计算 复杂性高、判断解的最优性困难等缺陷，所以研究出能实现多目标或单目标更 鲁棒的调度优化方法尤为重要。 1 5 本文的主要工作与结构安排 1 5 1 主要研究内容 为了确保不确定性对项目工程造成尽可能小的干扰和项目工程所采用的项 目调度方法的鲁棒性，在国内外跨企业项目调度优化方法研究发展现状的基础 上，结合前摄与反应式策略项目调度优化方法研究的最新动态，提出性能更优 越的新的或改进的基于前摄与反应式策略的跨企业项目调度优化方法。主要做 哈尔滨理工大学工学硕士学位论文 了如下几方面工作： 1 跨企业项目调度的研究不确定性因素对跨企业项目调度的鲁棒性和稳 定性带来的不可忽视的影响，采取怎样的调度策略进行企业间的项目调度，这 是研究内容之一。 2 前摄调度及模型的研究研究关键链技术，在综合考虑项目资源紧张 度、网络图结构复杂度等因素影响的前提下，对关键链和非关键链分别添加适 当时间缓冲，目标是减小不确定性因素带来的扰动，提高项目调度的鲁棒性。 并提出以在制品水平和净成本最低为目标的项目调度优化方法。建立的数学模 型应该尽量准确的反应调度过程的客观事实，容纳一定的不确定因素。如何利 用各种不确定条件下的优化技术来建立不确定调度的数学模型，并将决策者的 态度包含在内，同时将模型的求解过程与调度方案的实施过程结合在一起，是 一个十分有意义的问题，也是本课题的主要研究内容之一。最后通过大量仿真 验证本文方法的有效性。 3 反应式调度及模型的研究在前摄策略调度方法的基础上，对不确定性 带来的扰动采用反应式调度策略来消除这些不确定因素的影响。针对工序处理 时间不确定这一问题，通过包含不确定时间参数的优化调度模型，获取目标期 望值最优的前摄调度策略；然后根据模型中的相应约束和生产现场反馈的实际 信息确定后序任务的开始时间，依次实现调度的在线调整。仿真验证该策略可 以保证整个调度的鲁棒性、提高在线调整的反应速度、达到项目的综合优化。 决策者在制定调度策略时尽可能考虑各方面不确定性，以降低对不确定性 带来的扰动的敏感程度，保证调度计划的鲁棒性，这样在项目的执行过程中能 够确保反应式调度所做的改动是最小的。 4 跨企业项目调度系统实现采用多个企业合作来完成项目开发为例，构 造了跨企业项目调度系统的体系结构，将本文提出的两种策略均添加到项目进 度管理中，来验证前摄策略和基于前摄策略与反应式策略的调度优化方法的性 能。采用前摄策略方法生成静态调度计划方案，采用反应式策略方法生成动态 调度方案。系统中项目进度管理功能的实现证明本文方法具有较好的鲁棒性和 完工率，能够实现计算复杂度低和项目净成本低等目标。 1 5 2 论文组织结构 第1 章介绍了课题来源、研究背景及意义、项目调度问题的研究现状以及 目前存在的不足。 哈尔滨理工大学工学硕士学位论文 第2 章分析了跨企业项目调度的特点和给出跨企业项目调度体系，确定调 度体系采用的关键技术，结合网络计划技术和关键链技术给出调度思想。 第3 章建立问题模型，详细描述了项目调度中的前摄调度思想、前摄策略 所用到的核心技术，包括关键链的确定、时间缓冲策略缓冲位置及大小的确 定，算法描述以及对算例得到的验证结果分析比较。 第4 章针对第3 章建立的问题模型提出了采用反应式调度策略的必要性， 并针对前摄调度提出的优化方法来提出处理时间不确定的反应式调度方法模 型，给出算法描述。最后仿真验证调度方法的有效性。 第5 章项目调度系统的实现，包括系统结构和功能设计，实现的开发工具 和平台，采用本文提出的方法实现了项目进度中调度管理功能。 哈尔滨理工大学工学硕士学位论文 第2 章跨企业项目调度体系研究 自2 0 世纪后期以来，市场和竞争的全球化已成为重要的发展趋势。一方 面，全球化的市场竞争以要求企业能够快速响应市场机遇，有效地提供高质 量、低成本的产品或服务。而单个企业很难满足这种要求，这就需要企业间针 对市场机遇迅速组成联盟，发挥各自核心能力优势，共同实现市场机遇。这就 形成了跨企业项目调度。 2 1 跨企业项目调度的特点 许多大型项目不是一个企业所能够承担的，必须由多个企业协作完成。另 外，一些大型复杂产品结构和工艺复杂性、工装的多样性及新产品开发过程的 多样性和偶发性等特点使得新产品的开发周期比较长，产品开发成本难以进行 控制。企业在发现机遇产品后，往往很难在短时间内，合理的成本控制下组织 完成机遇产品的研制与开发。对于这样产品的生产要求企业以最大的敏捷性响 应市场要求，以最完善的进度成本控制方法保证产品的开发周期和开发成本。 但是单一企业的能力毕竟有限，单凭一个企业很难以最快的速度响应市场的需 求。面对这样竞争环境，企业逐渐意识到，通过具有敏捷性的企业间协作，将 各个企业的核心资源进行共享，组成动态联盟( v i r t u a le n t e r p r i s e s ) ，而联盟在 机会出现时结成，在机会完成后解散，并以项目管理理念进行管理才可以提高 企业对于市场机遇的响应速度，降低新产品的开发成本，提高产品市场竞争力 叫，这就形成了跨企业项目调度。跨企业项目调度管理具有如下特点啾1 。 1 面向目标性目标是实现机遇，也是项目完成所达到的最终状态。 2 时效性项目是有生命周期的，因此，以项目为依托结成的企业联盟具 有时效性，它始于项目的产生，终于项目的完成。 3 分布性承担项目的多个企业是临时组成的企业联盟，因此，在地理位 置上是分散的，同时由于不同企业承担项目的不同子项目或任务，因此，在时 间上也具有分布特性。 4 紧密协作和高度自治性由于项目的子项目( 或任务) 之间具有时间上和 逻辑上的依赖关系，因此，要求伙伴企业之间必须进行紧密的协作才能完成项 目的总体目标。然而，联盟内的各企业都是一个独立的经济实体，他们之间是 平等的伙伴关系，而不形成递阶控制结构。 哈尔滨理工大学工学硕士学位论文 如何安排多企业的生产计划、如何进行跨企业项目调度成为多企业生产顺 利、有效进行的关键问题。有效的调度方法与优化技术的研究和应用，对于制 造企业提高生产效率、降低生产成本等方面起着重要作用。 2 2 项目调度体系 在整个项目调度体系中，项目管理包括项目进度管理、资源管理等，在进 度管理中用到了网络计划、关键链技术和调度优化方法。根据跨企业项目管理 特点，确定的项目调度体系流程图如图2 1 所示。 图2 1 跨企业项目调度体系流程图 f i g 2 一lt h ef l o wc h a r to fc r o s s - e n t e r p r i s ep r o j e c ts c h e d u l i n gs y s t e m - l l - 哈尔滨理工大学工学硕士学位论文 实现项目全过程的动态管理是指在项目的周期内，不断进行资源的配置和 协调，不断做出科学决策，从而使项目执行的全过程处于最佳运行状态，产生 最佳的效果。所谓项目的综合协调与优化是指项目管理应综合协调好时间、费 用及功能等约束性目标，在相对较短时间内成功地达到一个特定成果性目标。 2 3 项目调度体系的关键技术 最早用于项目调度的方法是1 9 1 7 年由h e n r r yl g 锄t t 提出的甘特图法。甘 特图法形象直观，简单易懂，绘图简单，便于检查和计算资源需求量。但甘特 图法有着明显的缺陷：不能显示工作间的相互依赖关系；不能显示工作早开始 或晚开始所带来的后果；只能用于解决小规模问题。 2 0 世纪5 0 年代在美国出现了关键路径法和计划评审技术。c p m 和p e r t 在制定调度计划时，不考虑资源的约束，即认为项目所用的所有资源随时随地 都是能得到满足的。这两种方法所用的概念基本相同，差别只在项目中各个工 作的执行时间的估计方法上。六十年代，我国开始使用c p m 和p e r t ，根据其 基本原理与计划的表达形式，称它们为网络技术或网络方法。 2 3 1 网络计划技术 网络计划是在网络图上加注任务的时间参数等编制成的调度计划。网络计 划主要由网络图和网络参数两大部分组成。网络图是由有向弧和节点组成的， 用来表示任务流程的有向，有序的网状图形：网络参数是根据项目中各项任务 的工期和网络图所计算的各种时间参数。 关键路径法可以计算出项目各任务的最早、最晚开始和完工时间，