项目多目标模糊调度优化模型及算法研究

第 1 章  绪论

1.1 选题背景及意义

1.1.1  选题背景

随着科学技术的进步，社会科学的发展，生产的规模性逐渐加大，生产技术复杂性也越来越高，对企业尤其是制造型企业的生产监控提出了更高的要求。企业只有通过最有效的方式并不断缩短加工时间才能生产出符合顾客满意的产品。与此同时，企业自身也需要不断降低生产成本从而保证利润最大化，长此以往，才能不断获得十足的发展动力。因此出现了以项目为中心的活动开展方式。

项目是组织进行的一个暂时性的活动，在一定的规定时间内，运用事先确定的资源，以产出一个独特的且可以事先约定俗成的结果为目标所进行的时效为一次性的活动。项目管理，简称（PM）就是指项目经理人，在现有的、有限的资源约束下，运用系统论的观点、方法和其他相关理论，对项目中的全部任务进行有效地统筹管理。从项目的生命周期来讲，就是从项目的决策开始到项目结束的整个过程进行计划、组织、指挥、协调、控制和评价，以实现项目的既定目标。项目管理是在组织整体活动上，运用管理的知识、技术和手段来达成解决项目的问题或达成项目的需求。项目管理的概念最早由美国提出，是 20 世纪 40 年代发展起来的具有重大革新意义的管理技术之一。

而项目调度问题是项目管理中的一个经典问题，它主要研究的是一系列具有相关性的项目完成的逻辑顺序，从而实现所规定的项目指标达到最优化的效果。项目调度问题是各种加工行业、制造业和交通运输业等领域中普遍存在的问题，根据所规定任务的开始顺序不同，所得到的结果往往差别是很大的。如果可以将调度理论和方法恰当地运用到工业生活中进行生产活动的调度，往往极有可能使得项目目标达到最优化或者让人满意的效果。在项目管理领域，资源受限项目调度问题（RCPSP)又是项目调度中被深入研究的一个经典问题。典型的资源受限型项目调度问题是以确定的工期、给定的资源和单一条件约束下的总工期最小为目标。自从 RCPSP 问题被提出以来，就受到项目经理人和广大研究人员的长久的广泛的关注。人们对不同约束条件下的 RCPSP 问题的研究分别做了大量的工作，还将其大致划分为单目标资源受限项目调度问题、多目标资源受限项目调度问题、多模式资源受限项目调度问题、模糊资源受限项目调度问题、资源受限项目的鲁棒优化问题。

........................

1.2 相关研究现状评析

1.2.1 传统项目调度的研究现状

传统项目调度问题，即经典 PCPSP 问题，是假设项目的完工时间和资源的使用是一个确定的值，以项目总工期最小为目标函数，同时满足三个约束条件：一是要满足任务之间的单一时序逻辑约束条件，即紧前约束或者紧后约束；二是要满足完成任务的资源约束条件，每项任务的完成都需要消耗一定数量的资源，这里提到的资源只考虑可更新资源；三是要满足时间约束条件，假定项目中每项任务的持续时间是事先已知的，并且假设项目中的每一项任务一旦开始就不能被中断（即不允许可抢占）。

用于求解经典 RCPSP 问题的算法有精确算法和启发式算法两大类，精确算法一般在规定时间内对小规模问题能够求得最优解，由于此问题属于 NP-hard问题，对于超过 60 个任务的项目此类算法则无法实施。启发式算法则适合于中大规模问题求解，但无法保证所求结果为最优解。

自从凯利提出调度产生方案(SGS)的概念后，人们陆续地提出了其他不同的启发式算法。对于规模较大的项目而言，启发式算法虽然不能保证求得目标函数的最优解，但其优势在于计算速度快，同时还可以兼顾计算质量和计算效率两方面。启发式算法的类型主要包括基于优先规则的简单算法；分离弧的概念；局部搜索技术；智能优化算法等。近年来人们发现用启发式搜索算法求解经典的RCPSP  问题的有效性，启发式搜索算法主要包括以遗传算法（GA）；模拟退火（SA）；禁忌搜索（TS）为典型代表的智能优化算法。Boctor（1996）提出用模拟退火算法求解经典 RCPSP 问题。该方法采用任务链表编码，运用串行调度产生方案进行解码，采用插入式的邻域函数。Kim 等人（2003）提出了一种带有模糊控制器的混合遗传算法，此算法可以大大加快遗传算法的收敛速度，并能保留遗传算法的现有优点。

1.2.2 项目模糊调度的研究现状传统项目调度问题将项目中每项任务的持续时间和所占用的资源看成确定值的前提下进行求解的，而在实际的生产或者工程类问题中，由于企业生存的内外环境的不断变化，以及供给资源的不确定等不确定因素的存在，使得企业受到一系列不确定因素的影响。对于这些不确定因素，通常的处理方法有两种，一是把这些确定因素看成是确定值进行求解，这种方法会使得问题模型发生变化，从而求得的问题解也会产生偏差，而且求的解的形式不符合传统的表达。二是运用概率学理论描述参数的分布，目前针对概率函数，多用随机优化的方法来解决不确定约束下的项目调度问题。这种处理方法要求参数的数据是已知的，但是项目具有非重复性，并且项目采用的新技术降低了项目经验数据的可靠程度。另外，由于各项活动执行时间的概率分布是未知的，所以应用随机优化方法是十分困难的。在这种情况下，采用模糊数来表示活动执行时间比采用随机数更符合实际情况。

..........................

第 2 章  相关理论基础

2.１ 多目标优化理论概述

在同一个系统内，在给定的区域上优化两个或者两个以上问题叫做多目标优化问题，多目标优化问题提出之后就获得了强烈地关注，已经广泛应用到学术理论研究和工程实践以及工业生产等领域。比如，我们在解决项目调度问题时，必须考虑许多因数，产品的可制作性，产品的可靠性，产品的安全性，产品的可控成本，以及产品的模糊交货期和模糊工期等等。但是这些目标之间又往往存在着很大的矛盾，如果保证成本最低，那么产品的可靠性和安全性又无法保证，若同时保证成本最低，可靠性最大，安全性最高的话，交货日期和工期又很难保证。在求解上述问题时，无论是目标函数和目标函数之间，还是各种不同的约束条件之间往往都存在着各种错综复杂的关系，所以，仅仅依靠简单的单目标优化并不能很好地解决所有问题，因此必须从多目标优化思路进行考虑。

区分单目标优化问题和多目标优化问题在本质的地方在于多目标优化问题的解是一个解集的形式，它里面可能包含多个最优解，并不存在唯一的全集最优解，这个集合被称为 Pareto 最优解。所谓的 Pareto 最优可以解释为，在对一个或者一个以上的目标进行优化之后，不存在其余的目标可以不朝着更坏的方向退化的更理想解的形式。也就是说，在对其中的某一个或者某几个目标函数进行优化的同时，势必会削弱其他目标函数保持最优的趋势。对全部的目标函数来说，Pareto 最优解集中的各个元素相互之间是可以进行比较的。而单目标优化问题，则必须通过对单目标函数的求解优化操作得到全局的最优解或者是满意解。

2.2.1 多目标优化问题的数学模型

要求解多目标优化问题，首先应当建立数学模型。建立数学模型不仅是求解问题提供必要的前提，同时也是进行对  优化问题进行定性研究的一种重要方法。建立数学模型，既可以从理论角度进行分析，又可以给具体的实践活动提供适当的计算方法，从而从更大范围给实践活动或者生产活动作出相应的指导。

......................

2.2单目标项目模糊调度描述与模型

2.2.1 单目标项目模糊调度问题描述

项目决策者在项目周期的初始计划阶段无法获得各项活动的准确执行时间，所以需要根据以往经验给定各项活动一个估计时间，本文假定完工时间是一个模糊值，称之为模糊完工时间。同时，一个企业在一段时间内所拥有的资源是固定的，同一资源又可能同时被多项活动所占用，因此各项活动的资源消耗量的大小和资源在项目中每个任务的可用时间也具有了不确定性，资源的可用时间也变为一个估计的模糊值。正是由于这种外在因素的不确定性，导致了项目原定计划的不准确，因此在执行过程中项目原有调度极有可能会被多次更改，从而导致成本增加，施工时间增加，这就有可能会导致项目不能按时完工。这就要求项目决策者在项目计划阶段，必须合理安排各项活动的所占用资源的时间，并确保项目中的各项活动都满足前后逻辑约束关系，以项目完工时间的最小化作为现代调度中的首要性能指标。

遗传算法是一种基于全局所进行的随机优化算法，它的算法原理主要是模拟了达尔文的进化论中提到的自然界生物进化的适者生存的过程。在运用遗传算法进行项目调度问题的优化求解，第一步要做的是把项目调度优化模型中目标函数的运算和约束条件中所涉及到的参数指标通过编码操作而转化成程序语言，得到我们接下来要进行遗传操作的染色体。接着需要做的是通过不同染色体之间的遗传操作（包括交叉和变异两个过程），从而达到在被编码的染色体遗传空间进行高效迭代搜索寻求最优解的目的。迭代次数达到之前所设定的最大值时终止算法流程，对所得到的染色体解进行解码和评价，从而可以保证解空间朝着更优化的方向进化。

染色体编码的实质是在算法进行过程中主要是在编码空间中对染色体进行多次重复的遗传交叉和遗传变异操作，从而达到种群向着更优化进化的目的。解码过程则是把遗传空间中所挑选出的染色体再重新翻译成解空间中的特征解的形式，然后对解空间中所得的特征解进行评价和选择。用遗传算法来解决项目调度问题时，需要重复地在搜索空间和解空间中进行反复交替操作，如图 3.1 所示。

...........................

第 3 章 单目标项目模糊调度算法设计 ....................... 21

3.1 单目标项目模糊调度描述与模型 ....................... 21

3.1.1 单目标项目模糊调度问题描述 ..................... 21

第 4 章 多目标项目模糊调度算法设计 ....................... 37

4.1 多目标项目模糊调度描述和模型构建 ................... 38

4.1.1 多目标项目模糊调度问题描述 ..................... 38

第 5 章 结论及展望 ........ 51

5.1  研究结论 ............ 51

5.2 研究展望 ......... 52

第 4 章  多目标项目模糊调度算法设计

在项目进行的过程中，往往不只是对一个方面进行约束，而是同时对多个条件加以限制，要求在各方面都达到最好的前提条件下来解决项目调度问题。因此就出现了多目标项目调度问题。多目标问题往往由于所构成目标函数的不同而出现不同的求解方法，常见的目标函数包括项目工期最小、成本最小，项目拖期/完工的最小化，，常见的项目调度问题中对以上单个目标都做出比较深入的研究，但是在现实的求解项目调度问题，往往需要综合考虑多个目标函数，单凭其中一项目标函数的求解很难进行调度结果的好坏评价，而这些指标之间通常又不具有可比性，有些指标往往还是呈现负相关的联系。因此，怎么在这些指标之间进行权衡比较和筛选，从而找到一个解决问题的平衡点。求解这类问题叫做多目标项目调度问题（MOCPSP)。举一个具体例子，比如增加资源的投入量，可以缩短项目的完工时间，但是同时还会是得项目资源成本增大。对于项目决策者而言，他们当然希望尽可能地缩短项目的总工期，但与此同时，他们也不愿意项目资源成本过大，这就需要在项目完工时间和项目资源成本之间进行权衡，从而找到最佳的平衡点。

4.1 多目标项目模糊调度描述和模型构建

4.1.1 多目标项目模糊调度问题描述

项目多目标模糊项目调度（FRCPSMOOP）是对经典资源受限项目调度问题的进一步拓展，是对第三章项目单目标模糊调度问题的进一步深入展开。首先从模型来说，本文所研究的多目标问题是在第三章以项目工期为目标函数的基础上，又引入了项目资源成本这一目标，从而将其转化成项目多目标模糊调度优化模型。通过这一模型，希望能在项目完工时间和资源都是不确定的条件下，运用三角模糊数的理论，能够同时优化项目完工时间和资源成本及分配。在算法设计方面，延续了第三章对单目标项目模糊调度的求解的遗传算法的基本步骤，并对其进行了改进，使得算法更具有效性。

.......................

第 5 章  结论及展望

5.1  研究结论

资源受限型项目调度问题（RCPSP）是项目调度问题中的一类非常重要的问题，一直以来受到人们的广为关注和系统研究。本文通过对传统 RCPSP问题的论述和总结前人的研究成果，从中找出传统 RCPSP 问题在求解不确定资源约束条件下的项目调度问题中存在的不足。而企业实际的生产过程中往往会出现许多不确定因素，比如各项任务工期的不确定，资源需求的不确定。为尽量减少这些不确定因素对项目调度的影响，我们首先从随机优势的角度来考虑这些因素的建模。但由于我们是通过以往的经验判断各任务的概率值，使得结论非常不具有客观性和通用性。然后我们又考虑将模糊数学的理论引入到资源受限型项目调度问题中，形成一种全新的调度问题——项目模糊调度问题，并建立相应的数学模型，并运用模糊数学、多目标优化等理论，相应地给出不确定资源约束条件下针对单目标问题和多目标问题的不同的求解方法，并得出以下结论：

1.本文在解决项目调度问题时引入模糊数学的理论，运用三角模糊数来表示项目的模糊最大完工时间和模糊资源使用量，将确定的任务持续时间和日均资源使用量转化为资源使用量的下界、中值和上界的形式，从而结果变成可持续的一组区间值，使结果具有一定的灵活性和机动性。

2.本文首先求解了项目单目标模糊项目调度问题，在问题描述方面，将项目模糊完工时间作为需要求解的目标函数，给出其他约束条件，给出项目单目标模糊项目调度问题的优化模型。在求解算法方面，首先使用的是传统的遗传算法，包括对编码和解码方案的设计、产生第一代种群、确定适应度函数，进行轮盘赌选择、单点交叉和变异等操作。然后由于遗传算法的某些局限性，本文考虑对传统的遗传算法进行改进，在遗传算法的基础上，引入模拟退火步骤，将原算法改进为遗传-模拟退火算法，并对其他方面同时进行改进，具体体现在将原来的二进制编码变为格雷编码方案，产生初始种群时由原有的轮盘赌选择改进为混沌遍历搜索的办法，适应度函数的设计更加数值化，变异操作也由单点变异改进为两点变异。通过一个对具体实例的数值实验，可以看出改进的遗传-模拟退火方法比传统的遗传算法更加有效。

本文第四章在第三章的基础上，将项目单目标模糊调度优化问题拓展为项目多目标模糊调度优化问题。首先在问题描述方面，将模糊资源成本从约束条件中拿出来，与模糊最大完工时间一起作为目标函数，同时对两个目标函数进行最小化，从而建立起项目多目标模糊调度优化模型，在算法的设计方面，以基于非支配性排序的多目标遗传算法（NSGA-II)为基础，并引入基于模式、任务双链表，设计了求解该问题的算法，包括算法的编码与解码方案设计，种群初始化的方案，适应度函数值的计算，以及传统遗传算法的选择操作、交叉操作和变异操作等。最后通过一个具体的案例求解，验证了本文提出的项目多目标模糊调度优化模型以及所设计的 NSGA-II 算法同时求解模糊完工时间和模糊资源成本两个目标函数的合理性和有效性。

参考文献（略）