基于蚁群算法的多模式资源受限项目调度问题研究.doc

湖南大学硕士学位论文基于蚁群算法的多模式资源受限项目调度问题研究姓名：张冠群申请学位级别：硕士专业：工商管理指导教师：单汨源20090420基于蚁群算法的多模式资源受限项凋度问题研究摘要自上世纪年代，项目管理理论产生以来，伴随着社会经济的发展，项目管理所涉及的领域愈来愈广泛，其所研究问题的深度也日益增加。如何在资源受限制的前提下，通过对项目中各活动作出合理安排从而确保项目如期按质完成已经是企业管理领域普遍关注的问题。研究结果显示，资源受限项目调度问题（，）已经成为了广大学者的研究热点。随着社会经济的发展，企业在临时面对某一不确定性要求时，由于受资源、工艺等各类环境因素影响，项目中某一活动可能允许采用多种模式来执行，并且每一种模式对应着不同的工期和资源需求量，因此，对于项目管理者而言，为了尽可能完善地实现企业目标，往往需要灵活地选择最合理的执行模式，以便在满足资源和工期要求的前提下，高效地实现既定的项目管理目标。然而，目前国内学者对问题的研究大都基于一个活动只有一种固定工期的执行模式等假设之上，对多模式资源受限项目调度问题（，）研究得还很少。因此，本文对多模式资源受限项目调度问题展开研究，以期能在一定程度上用于指导实际。首先，在对多模式瓷源受限项目调度问题（，）特点进行界定以及对项目调度优化模型回顾的基础之上，构建了基于活动存在多种执行模式，每一个活动执行模式对应着不同工期和资源需求量的问题的数学模型；为了求解上述模型，本文在详细阐述蚁群优化算法的基本原理以及当前的改进研究成果的基础上，提出了一种新的改进蚁群算法，并对其在问题的应用过程进行了设计；最后，为了检验模型的有效性及算法的优越性，采用了在学术界广泛使用的中的标准多模式算例集进行了仿真试验。实验结果证明了本文模型的有效性及算法的优越性。本文的研究成果，不仅拓展了问题的研究领域，而且也为项目管理者如何在项目持续时间和成本间实现均衡提供了一定的指导借鉴意义。同时将在很多组合优化问题中得到成功应用的新型智能算法一蚁群算法应用于问题，既拓展了蚁群算法的应用领域，也为等组合优化问题的求解提供了全新的思路和方法。关键词：资源受限；项目调度；多模式；蚁群优化算法，：，；，基于蚁群算法的多模式资源受限项目调度问题研究，：；硕。学位论文插图索引图研究框架图项目管理研究进程图网络节点图图网络节点图图单代号网络示意图图双代号网络图图基本蚁群算法运算流程图活动模式链一基于蚁群算法的多模式资源受限项目调度问题研究表表表表附表索引程一计一进统一展果据发结数术解关技求相组划例果数计算结参络验验应网实实对湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：旅研日期：删肛日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于、保密口，在年解密后适用本授权书。、不保密昭。（请在以上相应方框内打“）作者签名：导师签名：功伽月月年叩年年竹仉时争盆期期硕一：学位论文研究背景及意义第章绪论项目（）是一个特殊的将被完成的有限任务集合，它是在一定时间内，满足一系列特定目标的多项相关工作的总称。项目管理（）是以项目为对象的系统管理方法，通过一个临时性的专门柔性组织，对项目进行高效率的计划、组织、指导和控制，以实现项目全过程的动态管理和项目目标的综合协调和优化【。随着社会经济的迅速发展，项目管理在生产经营等社会经济活动中的重要性日益凸显。特别是进入上世纪年代以来，随着信息系统工程、网络工程、软件工程、大型建设工程以及高科技项目开发等项目管理新领域的出现，项目管理在理论和方法等方面不断发展和现代化，项目管理进入了现代项目管理阶段。在此阶段，项目管理的应用领域迅速扩展到社会生产和生活的各个领域和各行各业，并在企业的战略发展和日常经营中的作用越来越重要，现代项目管理已成为发展最快和使用最为广泛的管理方式之一。项目管理有三个重要目标：成本、工期和质量要求【】。其中，项目调度管理是项目管理的重要组成部分，合理有效的项目调度计划是决定项目成败的关键因素之一。它在工程建设、软件开发等行业中尤其有着广泛的应用。在一个项目运行过程中，能否对它实施有效的调度管理，直接关系到项目能否按预定工期完成，最终影响到项目的成本及其最终盈利能力。项目调度（，）是为实现项目预定目标而确定和实施恰当策略的过程，在项目管理中占有极其重要的作用。近年来，无论在研究和实践中，它日益引起人们的关注。实践和理论研究均显示，项目调度问题是整个项目实施过程中最容易引发各类冲突，对成功实现项目目标影响最为重要的关键因素之一。项目调度问题是指在一定的约束条件下，将既有资源合理地分配给所要调度的活动，从而达到预定项目目标的过程（一般是以项目完工时间最小化为目标）。项目调度管理包括为确保项目按期完成所必须执行的一系列活动，其主要内容可以概括为：活动定义和排序，作业工期估计，编制调度计划以及调度控制等。调度问题，简单来说，就是以一个或多个项目为研究对象，在满足一定约束条件的基础上合理地安排活动执行顺序。项目调度问题中的约束条件是指在对各活动进行调度时要满足活动与活动之间的逻辑先后顺序和资源限制双重约束。项目调度中的资源通常是一种泛指，通常包括资金、机器、人力资源、材料和能源等在现实生活中具有稀缺性的资源。然而，在关键路线法（）和计划评审技术（）等基于蚁群算法的多模式资源受限项目调度问题研究经典项目调度计划方法中，出于简化问题的需要，通常假定项目中每一组成活动所需的资源供给是不受限制的，项目管理者仅需要依据工序间的逻辑先后关系确定项目的关键路线，所有活动均可以在其直接紧前活动结束后立即启动。但是，在实际的工作环境下，由于资源具有稀缺性，任何一个行业、任何一个企业，其所拥有的资源数量都是受到不同程度限制的，其结果就使得在实际项目调度过程中，一些原本依据活动逻辑关系可以并行操作的活动由于某些稀缺资源为关键线路和关键线路上的活动所共享而不得不推迟开工，最终导致其所在的项目延期。伴随着社会进步和项目的复杂化，尤其是信息时代的来临和高新技术产业的飞速发展，资本、服务、信息、技术、劳务人才在全球范围内流动空前加快，项目的特点发生了显著变化，项目本身和执行环境的不确定性及复杂性不断增多和增强，传统的项目调度方法越来越难以适应现代项目管理的实际需求。因此，结合项目实际情况对资源约束下的项目调度问题进行研究就具有十分重要的理论和实践意义。资源受限项目调度问题（，）是指在满足项目时序和资源双重约束的条件下，为项目中的所有活动分配资源并合理安排所有任务的开始和结束时间，以达到某一既定目标的最优化（如工期最短，成本最小，资源均衡等）【。该问题在建筑工程、软件开发等单件或小批量生产方式的企业中有着较为广泛的应用，如作业车间（）调度，流水车间（）调度等。理论研究证明，该问题属于问题，模型多样，是一类重要的组合优化问题，且涉及生产制造，科技研发等众多行业，与实践结合紧密，因此吸引了国内外众多学者在此领域进行研究，其中，、等学者都在此领域取得了一定成果。目前，国内外学者对的研究主要从两个方面进行展开：一方面是通过研究新的求解算法或对原有算法进行改进来对关于调度问题的结果进行优化，如利用粒子群算法、蚁群算法等智能算法来对各类型问题进行求解。另一方面则从企业生产运作实际出发，对模式不断进行改进，通过不断将新的与企业实际运营相关的项目特征纳入研究范畴来对项目调度理论研究进行改进。上述两个方面的研究共同推动了项目调度研究理论的发展。伴随着经济全球化导致市场竞争的日趋激烈，现代项目日趋复杂，其对项目工期、质量、成本的要求越来越苛刻，因此，越来越多的学者开始从事后一方面的研究并提出了一些新的具有实际指导意义的模型，从而大大加速了项目管理研究的现代化、科学化和合理化。其中多模式资源受限项目调度问题（，）就是在此背景下结合生产实际所提出的一种新的模型。多模式资源受限项目调度问题（硕：学位论文，）又可以称为多执行模式资源受限项目调度问题，所谓多模式（又称多执行模式）指的是在实际的项目管理中，由于受资源分配不同等项目环境影响，项目中某一活动可能允许采用多种模式来执行，该活动的每一种模式对应着不同的工期和资源需求量，因此，是对普通资源受限项目调度问题模型的扩展。该问题模型在资源受限项目调度问题的基础之上考虑了不可更新资源限制，并且假定每一种活动可能有多种可供选择的执行模式【】。在实际的项目管理过程中，资源总是稀缺的，为了提高资源利用率，项目负责人出于某种考虑，往往会依据项目中各活动的轻重缓急程度来决定对各个活动的资源投入量，而在实际工作过程中，各工作所获得的实际资源投入量影响着该活动的工期：当活动比较紧急时，通过加大对该活动的资源投入量，可以缩短完成该活动所需要的工期；当活动可以适当延缓且不会对整个项目工期产生延误时，可以考虑通过减少对该活动的资源投入量以便降低项目成本，获得更大收益。所以，在一般的实践工作中，各活动会由于所获得的资源不同而具有不同的工期，即同一活动可以有多种执行模式活动，不同的活动执行模式会有不同的活动工期以及相应的资源需求量，最终会形成不同的工期，因此，与传统的资源受限项目调度问题模型相比，模型更贴近项目管理实践工作，更有可能解决好项目管理实际工作中的问题，因此，也就更具有理论与实践价值。研究思路与框架通过对资源受限项目调度问题研究现状进行阐述，结合目前项目管理工作的实际要求与未来的发展趋势，本文指出了对多模式资源受限项目调度问题进行研究的必要性和意义；然后在对任务多模式特征进行界定和分析的基础上，对多模式资源受限项目调度问题进行了数学建模研究；针对普通蚁群优化算法在解决组合优化问题时所存在的不足，提出用改进的蚁群优化算法求解上述模型，即在阐述蚁群优化算法的原理、流程、优缺点的基础上，对蚁群算法进行了改进并结合问题实际特征设计了算法结构；最后，为了验证本文所提出的模型和蚁群优化算法的优越性，选择了有关多模式资源受限项目调度问题的的标准算例集进行了仿真实验并对实验结果进行了分析。本文的研究框架如图所示：基于蚁群算法的多模式资源受限项目调度问题研究图研究框架本文通过结合项目管理实际情况，在总结已有资源受限项目调度问题研究成果的基础上，提出了多执行模式活动概念，并对其特征进行了描述和界定，构建了多模式资源受限项目调度问题数学模型，并且对其进行了仿真研究，本文主要创新之处在于：（）结合国内外研究的最新成果，从项目本身的特点出发，对多模式项目调度问题进行了研究。该研究是在项目管理日趋复杂化的背景下，针对企业在实际工作中所面临的实际环境所提出来的，适应性更强，对项目管理实践工作也更具有借鉴和指导意义。（）模型所阐述的多执行模式活动理念是在结合企业实际运营情况基础之上对传统资源受限项目调度问题的拓展，本文中所构建的多模式资源受限项目调度问题模型，丰富了传统的理论与实践内涵，为更好地研究相关调度问题提供了一定的理论准备。（）本文提出运用元启发式算法一改进蚁群优化算法来求解模型。在对蚁群优化算法特征进行分析基础上，提出了多模式资源受限项目调度问题的活动模式表达方式以及活动模式列表的生成方式并设计了针对问题的求解步骤，并且采用编程进行了实现。将改进蚁群优化算法应用于求解问题，在充分利用蚁群算法搜索能力强、鲁棒性强等优点的基础上，结合问题实际，通过借鉴文献【】和文献【】中提出的转移概率准则和信息素更新策略有效地克服蚁群算法易陷入局部最优解的缺陷，从而确保了蚁群算法硕二学位论文关于问题求解的全局最优。最后通过仿真实验证明了该算法求解的有效性，因此，这种改进蚁群算法是一种有效的解决资源受限项目调度问题的新思路。基于蚁群算法的多模式资源受限项日调度问题研究第章理论基础与文献综述本章对相关研究成果以及求解进行了总结。其中，节对项目调度问题进行了分类；节对有关研究进行了综述；节对有关研究进行了较为详尽的论述；节对有关的求解方法进行了论述。多模式资源受限项目调度问题的提出资源受限项目调度理论是在考虑资源受限前提下对项目调度问题进行相关研究，被提出以来，一直受到国内外学者的关注。随着社会经济的飞速发展以及项目管理工作的日益复杂，尤其是网络信息技术、经济全球化所导致的项目自身特点显著改变以及项目所处环境不确定性及复杂性的不断增强，使得资源受限项目调度理论得到了很大的发展。目前，针对该领域的研究范畴已经由最初只研究资源不受限条件下的项目调度问题（）逐步扩展至对各种类型的资源受限条件下项目进行调度，研究内容日益丰富，具体包括多项目调度问题、多模式调度问题、活动可拆分调度问题等，这些研究越来越与实践中的项目具体特征相符合，因此更具理论研究和实践指导意义。概括而言，关于项目调度问题的研究历程可概括如下：资源不受限的项目调度问题（，），即图中的最低层，是各类型资源受限项目调度问题研究的基础。针对该问题，在研究中一般采用关键路径法（）和计划评审技术（）等传统方法进行求解。和方法都仅仅考虑活动的时序约束而不考虑资源约束，即都假定项目中的任何活动所需资源的供给都是无限的，项目中的某一活动在其所有直接紧前活动都完成后就可以马上开始。但项目管理实践表明，资源总具有稀缺性，在对项目实施调度的过程中，对于在技术上可同时开工的几项活动，为了确保项目调度的顺利执行，必须对资金、机器等有限资源进行合理考虑。即如果多项可同时开工的活动所需资源量超过所能提供的资源量，那么就必须推迟若干可同时进行的活动从而导致整个项目的结束时间可能晚于在不考虑资源约束时的项目关键路径长度。伴随着这类在经典项目调度模型中加入资源约束因素，传统的也就逐步拓展至更具实际意义的研究领域。即图中的第二层。第三层则是在充分考虑了不同项目所具有的不同特征和执行环境下的问题，主要涉及多项目调度问题、多模式问题等。如图中第三层所示。硕学位论文图项目管理研究进程在本文中，为了研究的简明，按照项目中活动是否具有多种执行模式，可以将项目调度问题分为单执行模式项目调度问题和多执行模式项目调度问题。通常，所有的资源不受限项目调度问题都属于单执行模式项目调度问题；资源受限项目调度问题类型多样，总体而言，依据其所研究涉及的实际问题，可以分为单模式资源受限项目调度问题（，）和多模式资源受限项目调度问题（，）。单模式项目调度问题资源不受限项目调度问题有关项目调度问题的研究源于上世纪年代，最初是研究资源不受限项目调度问题（），较早用于解决项目调度问题的工具是苷特图（，又称条形图）。苷特图是由于上世纪设计开发出来的。该方法具有绘画简单，明了易懂，容纳信息多，适合于项目管理人员随时检测和计算资源需求量的优点。但苷特图作为一种简单的应用工具，在解决实际项目调度问题时，存在着不能准确全面反映各项活动间相互关系以及不能准确表示整个项目中各关键活动和非关键活动之间的联系等诸多缺陷。因此，苷特图般只适用于小而较简单的项目调度而很难满足现代项目管理工作的要求。针对苷特图存在的上述不足，世纪年代末，网络计划技术应运而生。网络计划技术是一种运用网络计划对活动的工作调度进行安排和控制，以保证实现既定目标的计划管理技术。一般而言，运用网络计划技术来解决时应包括如下步骤：（）将项目中各活动的先后顺序及其相互关系以网络图形式表示出来；基于蚁群算法的多模式资源受限项目调度问题研究（）按某种方法来确定计划中的关键活动以及关键路径，并通过不断改善优化，选择最合理调度方案并付诸实施；（）对计划执行过程实行严格监督和有效控制，以确保有效利用资源和尽快好省的完成目标任务。网络计划技术的种类很多，如果依据项目中各任务的工期和逻辑关系来划分，通常可归纳为四种类型。表网络计划技术发展进程关键路径法（）：该方法由兰德公司和杜邦公司于年提出。通过该方法可以确定出项目中每个活动的最早、最晚开始和结束时间，并通过计算最早时间和最晚时间的时差可确定出各个活动的完工紧迫性及重要性。在中，一般将时差为零的活动称为关键活动。运用来解决项目调度问题的实质就是根据重点论思想，通过确定项目的关键活动和关键线路来重点解决项目调度过程中的主要问题，从而确保项目的顺利实施。计划评审技术（）是在美国海军制定的北极星导弹研制计划基础上发展起来的，该方法是一种活动工期具有不确定性的网络计划图，其基本形式与网络计划基本相同。图形评审技术（）是研究者充分考虑了项目执行过程中所存在的随机性，把概率论引入到中产生的一种网络计划技术。与等方法相比，该方法的网络逻辑和任务工期都是不确定的，即除了活动工期的不确定外，该方法还允许项目中的活动存在概率分支，即项目中活动的完成结果不是唯一的，而是存在多种结果。上世纪年代初，人们又通过把风险决策理论引入提出了风险评审技术（），该技术能够对项目活动的质量、时间、费用三坐标进行综合仿真和决策，但由于在对上述三坐标进行仿真和决策的过程中必须涉及到某些很难解决的数学难题，所以大大限制了风险评审技术（）在实践中的运用。单模式资源受限项目调度问题（）资源受限项目调度问题的产生及描述在项目管理实践中，对项目中每一个活动进行执行都是需要耗费多种类型的资源的，一般来说，资源都具有稀缺性，所以资源的使用都受到一定程度的制约。因此，如何在有效利用各种有限资源的前提下确保项目顺利完成就成为了一个具有积极现实指导意义的理论问题。硕一学位论文上述网络计划技术，如玎等作为非常有效的项目调度工具，被广泛应用于项目管理中，但由于忽略了资源稀缺性的限制，所以根据这些方法编制的计划和控制方案在资源受限的情况下很难确保其实际可行性，在此背景下，资源受限项目调度问题（。）就应运而生了。单模式资源受限项目调度问题（，）通常是指个项目由一系列相互关联的活动组成，这些活动一般只采用一种执行模式来完成，每一活动对应着相应确定的工期和资源需求量，关于此类问题的解是在满足紧前关系和资源双重约束条件下产生的一种能使某些项目管理目标实现最优的调度方案。研究表明，在理论上属于问题，是一类重要的组合优化问题，同时也是工程管理中最常涉及的问题类型之一，关于这类问题的模型十分丰富，实际工作中的许多问题，如作业车间（）调度，流水车间（）调度等都是的特殊情形【。此外在建筑工程，软件开发等以单件或小批量作为生产模式的企业中也有广泛应用，因此研究具有重要的理论和现实意义。资源受限项目调度问题的组成要素在问题中，依据问题中相关数据在进行调度前是否已知，可以分为确定性资源受限项目调度问题和模糊性资源受限项目调度问题。本文讨论的是有关确定性项目调度问题的分类。资源受限项目调度问题由资源、活动、目标函数三要素组成【。实质上，正是由于资源的不同数量和类型、与任务相关的错综复杂的约束条件，再加上用来度量不同指标的目标函数，才构成了种类繁多的问题。（）资源按照文献【】的分类方式，在项目调度中，资源可分为可更新资源、不可更新资源和双重资源三种类型。可更新资源是指该种资源的使用量在项目工期的每个时段都受到约束；不可更新资源则是指某类资源在整个项目工期内受限；双重约束资源是指某类资源使用量既在整个项目工期内受限，同时又在每个时段内受到限制。在项目管理的日常工作中，依据上述定义，通常把劳动力、机器设备等视为可更新资源，将能源、原材料等划为不可更新资源，而将双重约束资源分配问题转化成对应的可更新资源和不可更新资源分配问题来进行解决。（如：资金，当项目投资总量为定值时，其被看作为不可更新资源，而在每个阶段运作的资金流又被认为是可更新资源。随着研究理论的日益深入，有学者提出了部分可更新资源定义，用来定义那些处在某特定时间段内的可更新资源或不可更新资源。（）活动活动是项目最基本的组成要素，也是项目调度管理的对象。依据所研究项目基于蚁群算法的多模式资源受限项日调度问题研究特征的差异，活动又可称为作业、任务、工序等。在模型中，除了事先设定的虚活动，其它活动的执行都需要消耗一定数量的资源和时间。依据所描述活动的特征差异，活动可分为多种类型。依据活动在执行过程中是否可被中断可分为可拆分活动和不可拆分活动，其中，不可拆分活动是指活动一旦开始就不允许被中断，直至完工，而可拆分活动在加工过程中允许被中断，然后在中断点处可继续加工，任务中断前后加工时间的总和等于不中断情况下的活动加工时间；依据活动的执行工期是否确定，活动又可以定义为确定性活动和不确定性活动，确定性活动的资源需求量为常量而不确定性活动的资源需求量通常为变量；依据活动对于资源需求的特性，活动又可以分为资源需求确定型活动和资源需求变量型活动。此外，在进行项目调度时，一般都需要考虑活动与活动之间的时序关系（逻辑关系）。所谓活动间的时序关系是指项目中各活动被执行的时间先后顺序，如果活动必须在活动完工之后，则称活动和之间存在时序约束关系，其中活动就是活动的紧前活动。项目管理中，通常用网络图来表示活动与活动之间的时序关系。（）目标函数目标函数是项目管理者进行项目调度所希望达到的优化目标，能否按计划成功达到既定的目标是衡量项目管理绩效优劣的重要指标，一般而言，关于的目标函数可以分为两类。一类主要包括项目总工期最小、项目总成本最低、项目延误最小等，这类目标函数通常满足两个条件：（）目标函数是求最小值；（）目标函数是完工时间的单调非降函数。另一类则通常包括最大净现值、提前完工费用和误工费用最小等目标。资源受限项目调度问题的分类如上所述，一般是由活动、资源、目标函数三要素组成的，因此，依据上述三要素分类的不同，也可以归纳为不同的类型。依据主要约束条件之一的资源类型的不同，调度问题可以分为可更新资源问题，不可更新资源问题以及双重约束资源问题。依据调度过程同时处理的项目个数，可以分为单项目资源受限项目调度问题和多项目资源受限项目调度问题。与单项目（）相比，多项目是一个更为复杂的问题，其不但要求满足每个项目内部各任务的时序约束和资源约束，还需要考虑在资源和时序双重约束下，对所有项目活动进行调度安排以实现项目总工期的最小化。目前，关于资源受限单项目排序问题研究国内外学者已经取得了丰富的研究成果，而对资源受限多项目排序问题的相关研究还比较少，很难满足解决实际工作中存在的各种不同类型的多项目资源受限项目调度问题的需要。依据项目中正在执行的活动能否可被中止，可分为抢占式硕七学位论文（）和非抢占式（）。前者规定项目中的活动一旦启动，就必须不问断地执行下去直至最后完成，后者则假定项目中所包含的活动在项目环境发生变化时，可以暂停某些正在执行的活动，待条件重新满足时再继续执行该活动。依据项目管理目标的差异，调度问题又可具体分为离散时间成本权衡项目调度问题、项目工期最短问题、现金流优化问题、以最大净现值为目标的资源受限项目调度问题、带最小最大时间滞后的资源受限项目调度问题等。根据活动工期是否确定，可划分为确定性问题和随机分布问题。多模式资源受限项目调度问题依据上述单模式资源受限项目调度问题（，）和多模式资源受限项目调度问题（，）的分类，两者的根本区别在于项目中活动可执行模式的个数，前者假设项目中每个活动都只有一种执行模式且不考虑不可更新资源，一般是在满足活动问紧前关系约束和可更新资源约束的情况下，求达到项目工期最短这一优化目标的调度方案；后者则在单模式资源受限项目调度的基础上增加了不可更新资源约束，并且认为同一活动有多种执行模式，但同时认为活动的执行模式一旦确定下来，多模式资源受限项目调度问题就转变成为了单模式资源受限项目调度问题。本文就是针对活动多执行模式来进行项目调度的相关研究。在多模式资源受限项目调度问题中，同一活动所选择的执行模式不同，所需要的资源需求量和活动工期也往往不同，本文就是研究活动具有多种执行模式的项目调度问题。依据上述关于资源受限项目调度问题的分类，多模式资源受限项目调度问题属于图中的第三个层次。该层次充分考虑了项目管理实际过程中，资源供给量的不同对项目活动工期的影响，并进而对整个项目工期造成影响。因此，与一般的调度问题相比，具有更高的理论和实践研究意义。是项目调度中一项十分重要的研究内容，该类型问题在一般基础上假设活动一般都有多种执行模式，不同的活动执行模式对应着不同的资源需求量和工期，但一个活动的执行模式确定就意味着该活动工期、对各类资源的需求量都已经确定】。多模式项目调度问题可以描述为：一个项目是由多个活动组成的，其中每个活动都可能有多种执行模式，通常，对于不同的执行模式，同一活动对应不同的工期与资源需求量。活动与活动之间由于工艺、技术条件等因素的影响，往往存在着一定的逻辑先后关系。与单模式项目调度问题相比，由于充分考虑了活动执基于蚁群剪法的多模式资源受限项目调度问题研究行方式的多样性以及由此对活动工期和资源需求量所产生的影响，因此，在项目管理工作中，更具有实际指导意义。多模式项目调度问题在生产实践中普遍存在，其中生产制造车间的某些模具零部件制造就可视为一个典型的多模式问题。例如，在模具生产过程中，某零部件需要铣削加工并被抛光，结合车间生产实际，理论上该活动至少可以有两种执行模式：一种模式是先采用铣削加工机床对其进行铣削加工，再利用抛光机对其打磨抛光；另外一种模式是直接磨床，在使该零件尺寸变小的同时对该零件表面进行抛光。在此不难看出，完成同一个活动，如果选择的执行模式不同，其所需要的资源和对应工期也会相应不同。在项目管理研究中，对多模式项目进行调度就是在满足资源和时序双重约束的条件下，通过为每一活动选择合理的执行模式，然后再按照一般调度方法在满足资源和时序双重约束条件下对这一系列模式己定的活动组进行合理排序，从而达到既定的项目管理目标（一般是项目工期最短）一】。多模式资源受限项目调度计划问题组成要素及分类如上所述，多模式资源受限项目调度问题（）属于图的第个层次，更有针对性，属于一类特殊的资源受限项目调度问题，其组成要素包括活动、资源、目标函数、执行模式。其中执行模式因素的提出考虑了在项目实际施工过程中，同一活动由于所采取工艺以及在不同技术条件下可能采取的不同完成方式，因此，与单模式资源受限项目调度问题（）相比，无疑具有更高的理论和实践研究意义。作为一种特殊的资源受限项目调度问题，与单模式资源受限项目调度问题分类相似，多模式资源受限项目调度问题同样可以依据活动、资源、目标函数三要素分类的不同，相应地归纳为不同的类型。资源受限项目调度问题求解算法研究学者等人证明了问题属于问题，即难以设计一种普遍适应的算法来在多项式时间内对所有的实例都求得一个最优解，使其满足目标函数的要求【】。研究表明，问题类型通常都随着所涉及项目特征的不同而有所不同，因此对应建立的模型及求解算法也会有所区别。因此，一般而言，求解方法会随着拟解决的项目调度问题类型不同而有所区别。由于问题是在同时满足时序约束和资源约束双重约束条件对活动执行先后顺序进行排列，所以，它比资源不受限制调度问题更难进行求解。从上个世纪年代项目调度研究开始多年来，资源受限项目调度问题已吸引了大量学者对其进行研究，并取得一些成果。硕士学位论文如上所述，自问题被提出至今，学者们已经提出了多种类型的优化方法来求解该问题。概括而言，这些方法可分为两大类：一类是精确解算法（），它包括动态规划法、分枝定界法以及数学规划中的规划算法等，运用此类方法求解问题通常都是可以取得最优解；另一类是启发式（）算法，自从调度产生方案（，）的概念由首次提出后，多种多样的启发式算法相继被提了出来。归纳起来，启发式算法在求解时，虽然不能确保求得最优解，但往往具有计算速度快，易于在求解质量和求解效率上取得良好平衡的优点，尤其是对于规模较大的项目来说，这些优势更加突出。启发式算法主要包括分离弧（）概念、基于优先规则的启发式算法、局部搜索技术、智能优化算法（）等。下面将对这些问题进行简要的论述。精确解方法在目前理论研究中，主要采取动态规划法（）、规划法（）和基于隐含枚举的分枝定界精确算法（）等精确解方法对求解。实验结果显示，精确类算法对于中小规模项目调度问题效果较好，往往可以得到最优解，但对于规模较大的项目，求解效果很难保障。在已有的精确算法中，以基于隐含枚举的分枝定界精确算法效果最佳，应用也最为广泛。整数规划整数规划是将调度优化目标和各种限制条件先转化成为线形等式或不等式，然后通过求解整数规划问题得出最优解【。从理论上说，只要存在最优解，通过整数规划方法就可以得到最优解，但由于在运用多种规划方法进行求解时往往会涉及许多约束关系，从而导致“组合爆炸问题的出现，因此，该方法在实际运用中效果并不明显。基于隐含枚举的分枝定界精确解法分枝定界法是一种搜索技术，其中分支指的是每一活动可能延迟的调度计划，边界则是指项目中各活动所受到的资源和时序关系双重限制。在最早将分支定界法运用于求解资源受限项目调度问题领域之后，许多学者在该领域进行了深入研究，并依据所研究调度问题的类型的不同，提出了类型多样的分支定界方法。这类算法绝大多数都是利用与所求解问题相关联的部分调度方案来进行求解，通过连续地在表示部分调度方案的解决方案树中利用多种方法建立节点（每一个这样的节点表示项目调度安排过程中相应的子决策），来对部分调度方案进行不断延伸。在部分调度方案中，每一个方案都是可行的，即都满足时序关系和资源基于蚁群算法的多模式资源受限项目调度问题研究的双重约束。通常，分支定界方法都由大要素组成：分支方案、定界规则以及搜索方法。所谓分支方案是指在出现资源约束时，在确保问题取得最优解的前提下，为解决资源冲突，该算法对存在资源竞争的活动的分类、对分支方法、数量以及对需要推迟活动的确定；定界规则则是指求解上界和下界的方法，通过该规则确定的上下界可对即将进行的求解进行合理评价，提早删除不能产生最优解的分支，这样就可以避免出现无效解的枚举，确保算法的搜索方向尽可能地集中在能产生最优解的分支上，从而大大提高求解效率。实验结果表明，对于规模较小的项目调度问题，基于隐枚举分支定界算法是一种有效的精确算法，目前已经有许多学者进行了深入的研究，并取得了许多成果。与（）设计了一种将问题转化为一个求解最短路径问题的分枝定界法【。该算法中，所有在给定时刻都可以被同时调度的可行活动子集与有向图中的每个顶点相对