（计算机应用技术专业论文）不确定资源约束下的项目调度问题研究.pdf

哈尔滨理工大学工学硕士学位论文 不确定资源约束下的项目调度问题研究 摘要 随着科学技术的发展，生产规模越来越大，市场竞争越来越激烈，企业 对项目管理的要求也越来越高，而有效地计划和控制工序( 活动) 、资源、时 间三个变量是确保项目成功的关键，从而项目调度在这种环境下迅速地发展 起来，而且成为广大学者研究的热点。在实际的生产环境中，项目的周期、 可用资源量等很难事先就十分精确的知道，不确定因素往往会导致项目调度 无法按预定方案正常执行，因此，产生了模糊项目调度问题。 现有的模糊项目调度的研究主要集中在模糊交货期和模糊工期两个方 面，而在现实中由于市场竞争、环境因素的影响会导致在项目调度过程中某 一类资源的供应量为模糊数，这种可用量不确定的资源称为不确定资源。不 确定资源约束下的项目调度是模糊调度的一种，为了更好地反映实际情况， 本文研究了具有模糊工期和模糊资源量的不确定资源约束下的项目调度问 题。 采用三角模糊数表示模糊工期和模糊资源量，提出了不确定资源约束的 概念，建立了不确定资源约束下的模糊项目调度模型，利用混合遗传算法 ( h y b r i dg e n e r a la l g o r i t h m ) ，以模糊总工期最小为优化目标，把变异设计成 邻域搜索对不确定资源约束下的项目调度问题进行了求解；以排序健壮性最 大为目标函数，设计一种基于任务链表的改进遗传算法求解该问题。 多目标优化问题一直是科学和工程研究领域的一个难点和热点问题，本 文是在认真研究目前项目调度、模糊理论及多目标理论的基础上建立了不确 定资源约束下的项目调度模型并确立了多目标函数，采用了n s g a i i ( n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m i i ，n s g a - i i ) 解决此类问题，实现了 资源的优化利用，并得到了较优的结果，有很强的健壮性。 关键词项目调度；不确定资源约束；模糊理论；遗传算法；多目标优化 哈尔滨理工大学t 学硕士学位论文 r e s e a r c ho np r o je c ts c h e d u l i n gw i t hu n c e r t a i n r e s o u r c ec o n s t r a i n t a b s t r a c t w i t ht h ed e v e l o p m e n to ft h es c i e n c e ，t h ep r o d u c t i o ns c a l eb e c o m eb i g e ra n d b i g g e r ，a n dt h e r ei sm o r ea n dm o r ec o m p e t i t i o ni nw o r l dm a r k e t ，s ot h er e q u e s to f e n t e r p r i s e s p r o je c tm a n a g e m e n tg e tm u c hh i g h e r t h ee f f e c t i v ep l a na n dc o n t r o l o fw o r k ( a c t i v i t y ) ，r e s o u r c ea n dt i m ea r et h r e ee l e m e n t st ot h es u c c e s so ft h e p r o je c t ，t h u st h ep r o je c ts c h e d u l i n gp r o b l e md e v e l o p sw e l li ns u c hc i r c u m s t a n c e ， a n db e c o m e st h eh o t s p o to ft h eg e n e r a ls c h o l a r s r e s e a r c h e s i na c t u a lp r o d u c t i o ne n v i r o n m e n t ，t h ep r o je c tc y c l eo rt h ea v a i l a b l er e s o u r c e c a nn o tb em a s t e r e de x a c t l y i n f l u e n c e db yt h eu n c e r t a i nf a c t o r s ，t h ef u z z y p r o j e c ts c h e d u l i n gc a n tb ec a r r i e do u tf o l l o w i n gt h ep l a nr e g u l a r l y , t h u st h e f u z z yp r o j e c ts c h e d u l i n gp r o b l e mi sp r e s e n t e d t h ee x i s t i n gr e s e a r c ho nf u z z y p r o j e c ts c h e d u l i n gm a i n l yc o n c e n t r a t ei nt h ef u z z yd u e d a t ea n dt h ef u z z yp r o c e s s t i m e b u ti nr e a l i t y , u n d e rt h ei n f l u e n c eo ft h em a r k e tc o m p e t i t i o no rt h e e n v i r o n m e n tf a c t o r , t h es u p p l yo fr e s o u r c ed u r i n gp r o j e c ts c h e d u l i n gp r o c e s si s u n c e r t a i n t h er e s o u r c ew h o s ea v a i l a b i l i t yi su n c e r t a i nc a l l e du n c e r t a i nr e s o u r c e t h eu n c e r t a i nr e s o u r c ec o n s t r a i n to fp r o je c ts c h e d u l i n gi sai m p o r t a n tf u z z y s c h e d u l i n g i no r d e rt ob e t t e rr e f l e c tt h er e a ls i t u a t i o n ，t h ef u z z yp r o c e s s i n gt i m e a n df u z z yr e s o u r c e sa r ee x t e n s i v e l yr e s e a r c h e di nt h i st h e s i s t h em a t h e m a t i c a l m o d e lb a s e do nt h i s p r o b l e mi sb u i l t ah y b r i dg e n e t i ca l g o r i t h m a n da n i m p r o v e dg e n e t i ca l g o r i t h ma r ed e s i g n e dt os o l v e t h i sp r o b l e m m u l t i o b je c t i v eo p t i m i z a t i o ni sa l w a y sad i f f i c u l ta n dh o tp o i n ti nt h es c i e n c e a n de n g i n e e r i n gr e s e a r c hr e a l m t h e r ea r ea l r e a d yal o to fc l a s s i c a lm e t h o d sf o r s o l v i n gm u l t i - o b je c t i v eo p t i m i z a t i o np r o b l e m sb e f o r ee v o l u t i o n a r ya l g o r i t h m s w e r ei n t r o d u c e d c l a s s i c a lm u l t i o b je c t i v eo p t i m i z a t i o nm e t h o d sh a v e b e e n t h o r o u g h l yd e v e l o p e d ，b u tt h e r ea r es t i l ll o t so fd e f e c t si ns o l v i n gh i g hd i m e n s i o n a n dl a r g e s c a l ep r o b l e m s ，w h i c hc a nb e s o l v e db yg a s a st os o m ec o n c r e t e i i 哈尔滨理工大学工学硕上学位论文 p r o b l e m s ，h o wt og r a d ea ni n d i v i d u a li nap o p u l a t i o nb ym u l t i o b je c t si st h ek e y i s s u ei nc o m b i n i n gg e n e t i ca l g o r i t h mw i t hm u l t i o b je c t i v eo p t i m i z a t i o n u n d e r t h es t u d yo ft h ep r o j e c ts c h e d u l i n g ，f u z z yt h e o r ya n dm u l t i o b j e c t i v et h e o r y , a m o d eo ff u z z yp r o je c ts c h e d u l i n gi se s t a b l i s h e d ，t h em u l t i o b je c t i v ef u n c t i o ni s f i x e d ，a n dt h en s g a i ii su s e dt or e s o l v et h ep r o b l e mw h i c ha c c o m p l i s h e dt o m a k ef u l lu s eo ft h er e s o u r c e ，a n dm a x i m i z e dt h es c h e d u l i n gr o b u s t n e s s k e y w o r d sp r o je c ts c h e d u l i n g ，u n c e r t a i nr e s o u r c ec o n s t r a i n t s ，f u z z ys e tt h e o r y ， g e n e t i ca l g o r i t h m ，m u l t i - o b j e c t i v eo p t i m i z a t i o n i i i - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文不确定资源约束下的项目调 度问题研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他 人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已 在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：衙、志、强 日期： 丫年多月i 。日 哈尔滨理工大学硕士学位论文使用授权书 不确定资源约束下的项目调度问题研究系本人在哈尔滨理工大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨 理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解 哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门 提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以 采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密r ，在年解密后适用授权书。 不保密f q 。 ( 请在以上相应方框内打4 ) 作者签名：陌、志、强日期：7 o o 年弓月，d 日 导师签名：强宅i 习 日期：z 们万年；月川日 哈尔滨理工大学丁学硕上学位论文 第1 章绪论 1 1 课题研究的背景及意义 本课题全名为“网络化制造环境下协同项目计划与控制系统研究”，来源 于哈尔滨市后备带头人基金项目( 2 0 0 4 a f x 0 3 9 ) 。 随着科学技术的发展，生产规模越来越大，复杂性越来越高，市场竞争也 越来越激烈，因此对企业的管理和对生产过程的监控都提出了更高的要求，企 业唯有在最短时间内以最有效的方式生产出最能满足顾客需要的产品，才能获 得持续的发展后劲。 项目是一项独特的或具有风险的一次性任务，这个任务应该按照一定的期 限、一定数量的费用，在预期的实施范围内来完成。项目管理( p r o j e c t m a n a g e m e n t ，p m ) 是在一定的约束条件下，以高效率地实现项目业主的目标为 目的，以项目经理个人负责制为基础、以项目为独立实体进行经济核算，并按 照项目内在的逻辑进行有效的计划、组织、协调、控制的系统管理活动。 项目管理通常被认为是第二次世界大战的产物( 如美国研制原子弹的曼哈 顿计划) ，在2 0 世纪四五十年代主要应用于国防和军工项目，随着科学技术的 发展，项目管理目前已被广为接受并应用于军事、软件、建筑等各个不同领域 中。项目型企业就是企业的一切生产活动，是围绕一个个的项目设计、研发、 生产为中心的企业。很多项目都具有的共同特点就是具有一次性、技术含量 高、重复率低、难以控制和管理等，因此通常采用协同项目管理方式对其进 度、成本、质量、资源、风险进行管理。 协同式项目管理是指针对市场机遇，两个或两个以上企业为了实现共同的 项目目标，在自愿互利原则下，以契约方式结成一种网络式的联合体，共同承 担项目工作，以减少项目的成本和风险，实现优势互补，提高企业群体竞争力 的项目管理模式乜1 。协同项目管理中，凡是涉及到多个工作任务，就存在如何 安排它们的执行顺序问题，这就是排序问题口1 。如果再要求给出各个工作任务 以开始执行时间，则成为项目调度问题。 项目调度问题是资源分配问题的一种特殊情况，它主要研究一系列项目的 一个加工顺序，使所采用的调度性能指标最优。项目调度问题是工农业生产、 交通运输等各行业普遍存在的问题，不同的工作任务安排顺序得出的结果差别 很大，若按照适当的调度理论和方法进行管理生产，可以得到最优或令人满意 的结果。此外，项目调度还具有以下特性“1 ： 哈尔滨理1 = 火学工学硕上学位论文 1 复杂性由于装卸作业、设备、库场、搬运系统之间相互影响、相互作 用、每个作业又要考虑它的到达时间、装卸时间、准备时间、操作顺序、交货 期等，因而相当复杂。由于调度问题是在等式或不等式约束下求性能指标的优 化，在计算量上往往是n p 完全问题，即随着问题规模的增大，对于求解最优 化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力。 2 不确定性在实际的生产调度系统中，：一些重要的数据信息( 例如加工 时间，资源量等) 通常不是一个非常精确的量值，往往是一个时间段或是一个 模糊量，这样使得传统的算法将不能很好的体现现实情况。 3 多目标实际的计划调度往往是多目标的，并且这些目标间可能发生冲 突。k i r a n 等人将调度目标分为三类：基于任务交货期的目标、基于任务完成 时间的目标、基于项目成本的目标。这种多目标性导致调度的复杂性和计算量 的急剧增加。 鉴于以上项目调度的新特性，传统的调度理论很难解决这种复杂的、不确 定的、多目标的问题，因此需要引进先进的理论、思想和方法并使其相互融入 与结合来适应以上新特性。智能调度是调度研究的新成果，是解决复杂实际生 产调度问题的有效手段和重要途径。智能调度一般是指在生产计划与调度决策 中运用智能管理的手段和方法。而智能管理是人工智能与管理科学、知识工程 与系统工程、计算技术与通信技术、软件工程与信息工程等多学科、多种技术 相互结合、相互渗透而产生的一门新技术、新科学。研究和进一步开发有效的 智能调度方法在实际生产中具有广泛的应用前景和很高的研究价值。 模糊项目调度是智能调度的一种，模糊项目调度问题也是一般的调度问 题，是工程设计中典型的问题之一，也是最具难度的一种调度问题哺1 。该类问 题的研究取得的成果比较少，无论理论上的深入，还是优化算法上的探索都对 于实际问题存在着局限性，只有个别特殊的问题找到了有效的算法。因此，模 糊项目调度问题的研究具有很大的理论和实际意义，同时模糊项目调度问题是 目前调度领域研究热点之一，它有着广泛的工业应用前景。 1 2 项目调度问题的研究现状 1 2 1 传统项目调度问题的研究状况 传统的项目调度问题是以时间和资源为确定值的前提下进行的，近年来， 随着研究的深入，将生物学、物理学、人工智能以及计算机科学等多种技术引 入到生产调度领域，提出了解决调度问题的新方法，各种智能算法的提出丰富 了解决问题的途径，成为了一个热门课题。其主要算法有以下几种： 哈尔滨理t 大学下学硕j 二学位论文 1 进化算法进化算法是基于生物界“物尽天择，适者生存”的进化思想 基础之上而发展起来的一种随机搜索技术。主要包括了遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、进化规贝j ( e v o l u t i o np r o g r a m m i n g ，e p ) 、进化策略( e v o l u t i o n s t r a t e g y ，e s ) 等。它通过模拟群体的进化过程，使得群体中的个体不断朝着好 的方向发展，由于算法不苛求待求解问题的具体表达形式以及动力学特性 ( 如：连续、可微等) ，因而具有较强的健壮性和适应性。利用遗传算法求解调 度问题已经成为各国学者广泛研究的热点哺1 。本文提出用混合遗传算法和改进 遗传算法分别求解不确定资源约束下的项目调度调度问题，取得了比较好的效 果。 2 禁忌搜索算法禁忌搜索( t a b us e a r c h ) 算法是局部邻域搜索算法的推 广，是人工智能在组合优化算法中的一个成功应用。g l o v e r 在l9 8 6 年首次提 出这一概念。t a i l l a r d e ( 1 9 9 0 ) 提出了解决f l o w - s h o p 调度问题的禁忌搜索算 法。c h a m b e r s 等提出了基于禁忌搜索求解具有柔性路径的j o b s h o p 类型调度 的方法。 3 模拟退火算法模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 算法是局部搜索算法 的扩展，它不同于局部搜索之处是以一定的概率选择邻域中费用值大的状态。 算法s a 模拟统计力学中的热平衡问题，模仿了晶体结晶的冷却过程，在较高 温度瓦下，系统状态为s ，能量( 即目标函数) 为e ，选择s 的一个领域s ，如 果e ( s7 ) e ( s ) ，则接受s 为下一状态，否则以概率e ( e ( s ) 坷( f ) ) 7 疋接受s 。经过 一定次数( 称为m a r k o v 链长) 的搜索，认为系统在此温度下达到平衡，则降低 温度瓦再进行搜索，直到满足结束条件。 h i s a ol e t a l 提出一种改进的模拟退火法，用来解决具有最小完成时问指标 的f l o w s h o p 排序问题，并与禁忌搜索法等进行了比较。 由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极 小，但它的收敛速度较慢，很难用于实时动态调度环境。 上述算法已经得到了广泛的研究，并取得了丰硕的成果，应该说，在这方 面经典调度理论已经比较成熟了，但是调度方法在生产实际中的应用一直很不 理想，人们发现把这些算法直接应用到生产环境中还存在很多局限性，主要表 现在以下几个方面口，： 1 模型过于简单经典调度理论在数学上虽然很完美，但在研究问题时对 真实环境进行了大量的简化，脱离了生产实际，因此其结论难以适应复杂的生 产环境，根据这些算法精心制定出来的生产计划随着时间的推移，往往与实际 的生产进度的偏差越来越大。 哈尔滨理工大学工学硕士学位论文 2 方法过于单一生产系统是一个复杂系统，其内部资源的合理配置涉及 到方方面面的许多因素，对这样的系统必须在不同层次上，用不同的方法和模 型进行研究才能解决问题。经典调度理论总是试图用简单系统的研究方法来解 决复杂系统，其结果当然是不成功的。 3 使用范围窄经典调度理论的每一个算法，基本上都只能适应于有限的 生产环境，环境一旦变化，原先的算法就不再适用，还得寻找新算法，经典调 度理论中，既缺乏通用的算法，也缺乏面对不同环境解决调度问题的机制。 4 动态性和适应性紧急事件和突发行为会导致系统状态的变化。系统状 态变化时，就需要调度做出相应地变化，但静态调度计划常常是离线的，既没 有读取系统运行时的信息，如资源( 机器、人力等) 当前的可用性、错误信 息、与供应销售相关的信息等，因此，事先作好的调度计划无法执行。例如 机器发生故障、紧急加工任务的下达等都会导致原先的调度计划作废，而需要 重新制定调度计划，即无法适应当前动态变化的生产环境。 因此，如何将经典调度理论的丰富成果更有效地应用于生产实际，是多年 来研究人员和企业界关注的问题，模糊理论的引入是解决这个问题的良好方案 之一。 1 2 2 项目调度中的不确定因素 虽然关于项目调度问题的研究成果非常多，但有相当一部分研究是基于这 样一种共同的假设，就是所有的参数都是确定的，而且在这种确定性调度的研 究领域内，普遍认为调度一旦下达到车间，就会按部就班的执行。但这种假设 并不现实，在实际项目调度中，存在大量的不确定因素，比如原料供应、产品 需求及加工时间等等，使得由各种确定性模型和方法得到的优化调度性能指标 降低甚至不再可行。此外，还有协同项目管理中，不同盟员企业加工时间的不 确定性、由于资源争用而造成的可用资源的不确定性等。这些不确定因素使项 目调度在本质上成为了一个动态的过程，很难获得精确的加工时间和资源量。 项目的管理者或决策者能提供的也只是一个大概数据以及数据的可能变化范 围。因此在处理项目调度问题的时候，这些存在的不确定因素是必须要考虑 的。 分析不确定性的来源大致有两种：一种是由于随机因素( 偶然因素) 的影 响：一种是由于人们对它认识得不精确，或者说来自模糊性。如果我们认真分 析一下，当人们从事一项工作时，对各活动的持续时间的估计究竟主要受什么 影响，就会发现，后一种影响占主要成分，特别是对从事前所未有的项目，同 哈尔滨理工大学t 学硕上学位论文 时，人们对复杂环境的认识只能带有约略、模糊的特点。在实际中，专家往往 使用“大致”、“大约”、“左右等词语来进行估计。而且，专家可能会这样表 述：“可能介于5 到1 0 天，但最可能是7 ，8 天”，这说明专家不仅不能确定他 的这两个估计值，对每个估计值的确定程度也不同。这种可能值的范围以及其 相应的置信程度可以通过模糊集理论得到最恰当的建模。所以，目前对于项目 调度中的不确定型问题，大多数研究者倾向于采用模糊集理论。因为在实际工 程中，由于缺少项目各活动的充分信息，项目各变量值通常是由专家估计出来 的，这些值大多是在模糊的或不充分的信息基础上得到的，这种信息可以通过 模糊集理论得到最好的建模而不是概率理论。 1 2 - 3 模糊项目调度问题的研究状况 对于不确定的情况，传统的项目调度方法就显得无能为力了，一般情况 下，传统的方法会把非精确数近似成一个精确的数，然后进行问题的求解，这 样求出的解就会出现与现实情况不相符的情况，所以，针对项目调度问题的特 殊情况以及近年来模糊技术的发展，应用模糊集合理论来表示和处理不确定参 数问题获得了广泛关注。这种方法显示出了其他方法所无法比拟的优越性和应 用前景。同时，将加工时间和可用资源量按模糊数处理也更加符合生产的实际 情况，这类项目调度问题我们称之为模糊项目调度问题。i s h i ih 等陋1 首次提出 将交货期视为模糊数，并对开环车间的双机调度问题和同型机调度问题作了相 关研究；h a ns 等1 研究了单机模糊交货期的调度问题；t s u j i m u r ay 等n 训运用 遗传算法求解了车间作业调度中的模糊加工时问问题；w a n ggy n 等研究了模 糊加工时间下准备时间的单机调度问题；p e n gj ，l i udb n 2 1 研究了模糊加工时 间下的并行机调度问题。就模糊加工时间与模糊交货期下的作业车间调度问题 设计了一个有效的遗传算法；l t o ht ，l s h i ih 将m o o r e 的调度模型模糊化，证 明了这种模糊化的可行性；c h a n a ss ，k a s p e r s k ia “3 1 引将l a w l e r 的算法引入模 糊调度中，并对单机调度、双机调度问题进行了研究。就目前来看，有关模糊 可用资源的调度问题大部分还只是停留在描述性研究阶段。 显而易见，一定时期的研究热点与当时的市场需求对制造业的要求紧密关 联。9 0 年代末期，市场竞争日益白热化，人们对商品多样化的需求越来越大， 产品的生命周期愈来愈短，制造业面临更多新产品的生产以及更多的订货式生 产，因此生产中加工时间和可用资源的不确定性愈来愈明显，并且二者之间相 互耦合，相互影响。为了适应这一市场需求，更快地响应市场，综合考虑模糊 加工时间与模糊资源的调度问题逐渐成为人们研究的热点。 哈尔滨理t 大学工学硕士学位论文 因此，不确定资源约束下的项目调度问题的研究是当今全球性竞争机制所 带来的必然趋势，具有极其广泛的应用价值和实际背景。目前，有关模糊调度 的研究，主要集中在模糊数的操作问题上，主要包括模糊数的求和、取大以及 模糊数之间的比较等方面的研究，这是研究模糊调度的一个关键问题。 1 2 4 多目标项目调度问题的研究现状 目前针对不确定资源约束下的项目调度问题研究的比较少，而且该问题研 究最多的模型是经典资源约束项目调度问题，这是一种确定性、单目标的项目 调度问题，即所给的数据都是已知的确定量，但在实际的项目调度中，应综合 考虑多个指标，单凭一个指标难以评价调度的优劣。此外不确定因素( 天气， 机器故障，工人的熟练程度，环境等) 往往会导致项目调度无法按预定的方案 正常执行。为使算法等能适合实际项目调度的需求，s l o w i n s k i 副采用目标加权 法将多目标问题转化为单目标问题进行求解多目标资源受限项目调度问题；随 后他又提出采用基于启发式方法的决策支持系统求解多目标资源受限项目调度 问题，该方法为首先利用基于优先规则的启发式算法或模拟退火算法产生一些 非支配解，然后利用交互操作产生最好的妥协解，该方法的缺点是不能保证所 产生的非支配解具有代表性。 综合以上的研究，我们发现目前国内外学者在调度方面的研究主要存在以 下问题： 1 大多数学者主要以单个任务的最小完工时间或单个任务的交货期满意度 最大为优化目标，这种单目标调度不能很好的满足目前社会上的多种要求。 2 现有的文献中对模糊交货期问题的研究比较多，但是在现实生活中资源 的不确定性是普遍存在的，所以，不确定资源约束下的项目调度问题的研究是 十分重要而且符合实际需要的。 本文本着一切从实际出发，综合考虑项目调度的整体性，最大程度上满足 企业的实际需求，给企业项目提供一个科学、合理的调度优化方案。 1 3 本论文的研究内容 模糊项目调度问题是智能调度问题的一种，也是目前调度领域研究热点之 一，它有着广泛的工业应用前景。在实际项目调度中，存在大量的不确定因 素，比如原料供应、产品需求及加工时间等等，使得由各种确定性模型和方法 得到的优化调度性能指标降低甚至不再可行。此外，协同项目管理中，不同盟 员企业加工时间的不确定性、由于资源争用而造成的可用资源的不确定性等。 这些不确定因素使项目调度在本质上成为了一个动态的过程，很难获得精确的 哈尔滨理工大学工学硕士学位论文 加工时间和资源量。 可用资源供应量是一个不确定的因素，这将导致项目调度中活动持续时间 的不确定。为了更好的反映实际情况，本文讨论一种不确定资源约束下的模糊 调度问题。 主要研究内容如下： 1 本文就项目调度中的模糊工期和模糊资源进行了研究，提出了不确定资 源的概念，给出了不确定资源约束下的项目调度的问题描述，建立了相应的数 学模型； 2 把模糊理论引入到论文中，将概率统计方法引进模糊调度计算中，先把 模糊数量化并给出模糊数大小比较的原则。详细地介绍了模糊数求和与取大运 算； 3 利用混合遗传算法( h y b r i dg e n e r a la l g o r i t h m ) ，以模糊总工期最小为优 化目标，并在基于邻域搜索的混合遗传算法中把变异设计成邻域搜索对不确定 资源约束下的项目调度问题进行了求解； 4 以排序健壮性最大为目标设计了一种基于任务链表的改进遗传算法求解 不确定资源约束下的项目调度问题； 5 设计了一种基于非支配性排序的多目标遗传算法( n s g a i i ) 来求解多目 标不确定资源约束下的模糊项目调度问题。 哈尔滨理工大学工学硕士学位论文 第2 章模糊理论及其在项目调度中的应用 2 1 模糊集合的相关概念 在经典集合中，一事物要么属于某集合，要么不属于某集合。而模糊概念 是不能用经典集合描述的，因而要定量地刻画模糊概念或模糊现象，就必须拓 广经典集合n 6 1 7 1 。 设有集合x 和】，若有一对应法则厂存在，对于集合x 中的任意元素x ， 有】，中唯一的元素y 与之对应，则称此对应法则厂为从x 到】，的一个映射，记 作f ：x 专y 。x 称为厂的定义域，而集合f ( x ) = f ( x ) ix x ) 称为厂的值域， 显然f ( x ) y ，y 称为x 在厂的作用下的象，而x 称为y 的一个原象。当研究 一个问题时，把所讨论的全体对象叫做论域。 定义2 1 设彳是论域u 的子集，这里定义映射x 。：u 专 0 ，1 ) 的一个特征 函数见式( 2 1 ) ，映射x 。称为集合彳的特征函数。 柏) = 器x x 叠e 盒 江， 所谓给定了论域u 上的一个模糊集合彳木，是指对于任意“u ，都指定了 一个数a 。0 ) o ，1 与之对应，a 。0 ) 叫做u 对于彳水的隶属度，映射t a ： u 专【o ，1 ，u l 专a ( 材) 叫做a ，c 的隶属函数。模糊集合完全由其隶属函数所刻 画。( “) 的大小反映了u 对于模糊集合的从属程度，接近1 则说明从属程度 高；反之，接近o 则说明从属程度低。 2 2 模糊数及隶属函数 无论研究何种模糊问题，首先必须要了解的一个概念就是模糊数的概念， 本节将对模糊数的类型，模糊数的运算，模糊数的比较作简要介绍。所谓模糊 数，实际上它就是数的一个模糊集合n8 。，例如“大约1 0 就是一个模糊数 l o ，而这样的一个数可以用它的隶属函数来表示，如图2 1 给出了模糊数的隶 属函数表示。 2 2 1 三角模糊隶属函数 根据工程项目调度的特点，对各工序作业时间及其总工期的估计一般采用 三点估计，即最短作业时间、最可能作业时间和最长作业时间，因此采用三角 模糊数来表示，一个三角模糊数彳可由公式( 2 2 ) q b 的隶属函数来定义。 哈尔滨理t 大学工学硕十学位论文 图2 1 隶属函数 f i g 2 1m e m b e r s h i pf u n c t i o n ( x ) = 0 ，0 x 一三 ， a ，一l x a m + r 一般来说，我们可用三个值来构造一个三角模糊数：a 。，a ：，a m 。分别 表示它的最小可能值，最大可能值和峰值，如图2 2 所示。所以可以用如下形 式表示一个三角模糊数：彳= ( q ，a m ，口：) 。 y 1 o 图2 - 2 三角形隶属函数 f i g 2 2t r i a n g l em e m b e r s h i pf u n c t i o n 2 2 2 梯形模糊隶属函数 一个梯形模糊数彳可由公式( 2 3 ) 中的隶属函数来定义。 从图2 3 可以看出，梯形模糊数实际上是具有平顶的模糊数的一个特例。 由四个给定的数值a 。，a ：，a m 和口就可以构造一个梯形模糊数，即 a = 【a 1 ，口m ，a ，a 2 】。 筮r 哈尔滨理工大学t 学硕士学位论文 ( x ) = 0 0 ，0 x a ，一l ，一l x a m ，a m x a ， ( 2 - 3 ) ， a x ! 吃玩，其中，s 表示活动从开始到结束的时间间隔，表示在时间t 时 j ” ” m ，6 吼 活动i 占用第k 类资源的总量，玩表示在时间t 第k 类资源的模糊总量。 2 5 本章小结 本章首先概述了模糊理论的发展及相关的模糊数学知识。现实社会中存在 很多不能确定的描述，即“亦此亦彼”的现象。为了描述这种“亦此亦彼现 象，从而我们需要引入模糊理论。紧接着，我们又介绍了有关模糊数及其隶属 函数的概念，并详细的说明了三角模糊数及梯形模糊数的运算与比较。最后， 把模糊理论应用到实际的项目调度中，为以后的研究奠定了基础。 哈尔滨理t 大学工学硕一1 ：学位论文 第3 章智能优化算法研究 3 1 智能优化算法的概述 3 1 1 项目调度问题的求解 项目调度问题本质上的组合特征，使得在调度问题中有许多问题都属于 n p h a r d 问题，即使是规模很小的问题，也在1 9 7 6 年由g a r e y ，j o h n s o n & s e t h i 等人证明是n p h a r d 问题，这个问题很难用一种确定的方法得到一个最优解。 经典的调度理论中解决调度问题的方法主要有三种：解析优化法、穷举优化法 和智能化算法。前两种都属于精确的求解方法，但受到问题的性质和规模的限 制；后_ 种方法在一般情况下只能得到近似最优解。事实上，由于计算最优解 的时间和花费非常大，没有人可以给出，因此在实际生产过程中很多情况下并 不需要最优解，只是找到一个接近目标函数的近似解就可以了。近年来，许多 智能化方法被提出，以满足实际问题的需要。而且，随着计算机技术的发展和 生命科学、工程科学的相互渗透，以获得近似解为目标的智能化算法开始应用 到调度优化领域，而项目调度又是一种规模大、情况复杂的调度问题，所以智 能化算法在这一领域显示了其解决问题的潜力。其中，遗传算法( g e n e t i c a l g o r i t h m ，g a ) 作为一种智能化算法应用尤为广泛。 3 1 2 智能优化算法提出 优化是管理的核心，既是管理的目的，又是管理的手段。优化的思想贯穿 在管理活动的全过程，优化的方法应用于管理活动的各个方面。在管理活动过 程中的各个环节，如规划、决策、指挥、调度、协调等方面都存在优化问题。 生产调度策略的选择过程就是对项目活动调度安排的优化过程。 现有的优化方法主要是基于数学模型。例如，基于代数方程( 线性、非线 性) 模型，运筹学中的线性规划、非线性规划等静态优化方法；基于微分方程 或差分方程模型的，最优控制理论中的极大值原理，动态规划等动态优化方法 等。由于在数学模型的描述能力和求解方法上有相当的局限性，使现有的最优 化方法在实际应用中受到了很大的限制，存在许多有待解决的难题。如人为因 素、多目标问题、局部解问题、不确定性、未确知性等问题心2 删。为了寻求解 决这些问题的新途径，提出了智能优化( a i b a s e do p t i m i z a t i o nm e t h o d ) 的概念 和方法。 本世纪五十年代中期创立了仿生学，许多科学家从生物的演化规律中获得 哈尔滨理t 大学工学硕士学位论文 了新的指导人造系统研究方法。智能优化算法就是基于生物进化的思想通过模 拟生物进化过程来设计、优化和控制人工体统的优化方法。 在生产计划与调度管理中采用计算机辅助管理系统进行现代化管理的主要 目的和任务就是实现最优化管理，即在有关的约束条件下取得管理目标的最优 化或次优化。 为了描述各种类型的优化管理问题，例如，优化规划、优化决策、优化调 度等，需要基于广义管理模型( 数学模型、网络模型) 的智能优化算法，求解各 种优化管理问题。 3 1 3 智能优化算法的特点 智能优化算法的特点有四个心7 1 ，如图3 1 所示。 智能优化方法的特点 应用范围广l 解题效率高il 组合爆炸延缓ll 求解结果满意 图3 - 1 智能优化算法的特点 f i g 3 - 1c h a r a c t e r i s t i c so fi n t e l l e g e n to p t i m i z a t i o nm e t h o d 1 应用范围广随着广义管理模型的应用范围的逐渐广大，智能优化算 法的应用范围将远远大于传统的最优化方法； 2 解题效率提高利用启发式知识进行推理，压缩可行解的空间，从而 减少了搜索时间，加快了解题速度，提高了优化问题的求解效率； 3 组合爆炸延缓对于复杂的优化问题，利用智能优化算法与“分解一协 调”多级优化方法相结合，可延缓求解过程的组合爆炸问题的发生； 4 求解结果满意对于多目标、多约束条件的最优化问题，利用智能优 化算法，可以有效地求得满意解或次优解。 3 2 遗传算法 遗传算法是模拟生物进化过程的计算模型，它作为一种新的全局优化搜索 算法，以其简单通用、健壮性好、适于并行处理以及应用范围广等显著特点， 奠定了它作为2 l 世纪关键智能计算之一的基础心8 。3 引。 3 2 1 遗传算法的发展历史 遗传算法研究的兴起是在二十世纪八十年代末和九十年代初期，但它的历 史起源可追溯到五十年代。 五十年代和六十年代，一些计算机科学家开始探索用模拟生物和人类进化 哈尔滨理工大学t 学硕十学位论文 的方式优化许多复杂的工程问题。六十年代，由l r e c h e n b e r g 和h p s c h w e f e l 等在进行风洞实验时，提出了进化策略( e v o l u t i o n a r ys t r a t e g y , e s ) 。由l j f o g e l 等在设计有限自动机( f i n i t es t a t em a c h i n e ，f s m ) 时提出了进化规贝j j ( e v o l u t i o n a r y p r o g r a m m i n g ，e p ) 。早期的研究形成了遗传算法的雏形。 到1 9 7 5 年，美国的j h o l l a n d 总结了自己的成果，发表了遗传算法领域内 具有里程碑意义的著作自然系统和人工系统的适应性( a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ) 。在本书中，h o l l a n d 为所有适应性系统建立了一 种通用理论框架，并展示了如何将自然界的进化过程应用到人工系统中去。后 由a d b e t h k e 、d ej o n g 、t e d a v i s 等人作进一步研究。1 9 8 5 年召开了第一届 国际遗传算法学术会议，使遗传算法得到很大发展，并迅速渗透到人工智能、 神经网络、运筹学等领域。 人们通常把h o l l a n d 所提出的遗传算法称为简单遗传算法( s i m p l eg e n e t i c a l g o r i t h m ，s g a ) ，在h o l l a n d 的简单遗传算法基础上，人们不断对它进行各种 改进和完善，并将s g a 与其他算法相结合，以解决各种不同领域的问题。本 文将在分析遗传算法和项目调度算法的基础上，从理论及实际应用中进行一些 研究及改进的工作，在分析研究的基础上，提出了遗传算法设计方面的一些原 则，并对s g a 进行了有效的改进。 3 2 2 遗传算法基本用语 由于遗传算法起源于自然遗传学和计算机科学，因此遗传算法文献中的术 语是自然与人工系统语言的混合b 引。 在生物学中表明生物体构成的编码结构称为染色体，描述一个完整的生物 体可能需要一种或多种染色体。一套完整的染色体称为基因型( g e n e t y p e ) ，而 生成的生物体称为表现型( p h e n o t y p e ) 。每个染色体由一些称为基因的个体结构 组成，每个基因表达了生物体的一种特性，基因在染色体结构中的分布，或称 为位置，决定了基因表达的特性。在各个特殊的位置上一个基因可能具有几个 表达不同特征的特殊值，基因的这些不同的值称为基因位值( a l l e l e s ) 。遗传算 法的术语和最优化术语的对应关系见表3 1 。 3 2 3 遗传算法的特点 遗传算法在几个基本方面不同于传统的优化方法。g o l d b e r g 总结为如下： 1 遗传算法运算的对象是编码后的解集，而不是解集本身； 2 遗传算法的搜索始于解的一个种群，而不是单个解； 3 遗传算法只使用适应度函数，而不是使用导数或其他辅助知识； 哈尔滨理工大学工学硕上学位论文 染色体( 位串、个体) 基因( 位) 位置 基因位值 表现型 基因型 解( 编码) 解的部分 基因的分布 基因的取值