基于拍卖谈判机制的分布式多技能多项目调度

求解分布式多项目调度问题的关键是设计有效的资源协调机制以解决项目间的全局资源冲突。当全局资源为多技能人力资源时,调度项目活动开始时间的同时还需要满足“活动-技能-资源”的匹配关系,从而为多项目制定高质量的调度计划与全局资源指派方案。基于多Agent系统,建立局部调度优化与全局协调决策的双层模型;采用基于正向逆向调度改进的遗传算法求解初始局部调度计划;以人力资源各时段的使用权作为拍卖品,设计考虑人力资源多技能异质特点的拍卖谈判机制协调全局资源冲突。改编MPSPLIB算例集并开展实验研究,研究结果表明：本文设计的拍卖谈判机制与改进的遗传算法相结合可以有效协调不同规模问题的全局资源分配;拍卖谈判机制在测试问题集上的求解结果优于序贯博弈谈判机制;问题规模越大或资源冲突程度越强,项目协调调度难度越大,全局资源分配过程越复杂。     

一种改进的多模式项目反应性调度问题

既有的项目反应性调度问题只关注了基准调度方案的稳定性,而忽略了项目调度目标的最优实现。本文提出了一种两阶段多模式资源受限项目反应性调度问题。第一阶段,在新的项目执行环境下,对项目进行完全重调度,得到新的最优调度目标值。第二阶段,以新的最优调度目标值为约束,以最大化调度稳定性为目标,求得新的最优调度方案。针对问题特点,基于IBM ILOG优化编程语言OPL和CPLEX V12.8.0,设计出该问题的求解程序。最后,基于标准算例,对本文提出的反应性调度方法、既有的反应性调度方法、完全重调度方法进行了充分的比较测试,结果表明本文提出的反应性调度方法在缩短项目工期、保护基准方案的稳定性方面具有明显优势。     

基于关键链改进搜索的遗传算法求解分布式多项目调度

针对基于多代理系统求解分布式多项目调度问题的不足, 开发了一种适应性的遗传算法ccm_GA。ccm_GA的独特性体现为两点:第一, 修正的串行调度过程分两个阶段分别消除全局资源和本地资源冲突; 第二, 在满足两类资源约束的调度方案中, 识别出关键链并改变关键活动在活动序列编码中的位置以增加解的多样性从而提高搜索效率。设计并实施大规模数值实验测试算法性能, 与现有文献中的六种算法作对比, 结果表明:ccm_GA在50%的算例集上获得的测试指标都好于六种算法, 且对于资源约束越紧的算例集, ccm_GA的求解效果越好。     

带有资源柔性约束的max-NPV分布式多项目调度问题

现有的分布式资源约束多项目调度问题研究中,假定全局资源限量在多项目工期内不可突破且多以工期为优化目标。针对此问题,考虑全局资源可从外部获取,以净现值为目标,构建带有全局资源柔性约束的分布式多项目调度问题的整数规划模型并设计有效的求解算法。首先,界定问题并确定项目现金流的计算方法;然后,针对求解问题的NP-hard属性,设计了遗传-模拟退火混合算法(GA_SA)求解此模型。最后,通过多组数值实验,设计不同算法与GA_SA算法进行比较,并分析了关键参数对多项目净现值的影响。结果表明,GA_SA算法具有较好的求解效果;与传统的全局资源刚性约束条件相比,全局资源柔性使用状态可以显著改善分布式多项目的收益绩效。     

基于MAS的多模式分布式资源约束多项目调度

针对实践中分布式多项目的活动往往具有多种执行模式,提出多模式分布式资源约束多项目调度问题。在项目动态到达环境下,考虑活动不同的执行模式,以工期最短和多项目延期成本最小为目标分别构建局部单项目调度模型和全局多项目决策模型,采用改进变邻域搜索算法求解初始局部调度计划,并设计基于模式调整的全局协商调度算法求解全局决策模型,通过双层算法实现分布式多项目调度中局部单项目调度与全局多项目调度系统性协调,减少项目中断和多项目延期成本。基于构建的多模式测试集进行的多项目数值实验表明：本文设计的双层算法可有效求解多模式分布式多项目调度问题,并且对不同规模问题求解具有良好的适应性。     

基于多Agent的宏观经济智能预测决策支持系统研究

在分析智能决策支持系统的发展基础上，将人工智能思想，特别是Agent应用于构建智能宏观经济预测决策支持系统。提出面向任务的Agent设计思想，以任务为核心设计多种类型Agent共同完成预测决策任务，给出基于多Agent的系统组成结构，并给出系统中不同类型Agent的具体实现结构，同时探讨了整个系统的运行机制以及系统中多Agent之间的合作。整个系统的构建过程也是面向Agent的程序设计的过程。     

求解资源约束项目调度问题的启发式算法综述

本文综述了求解RCPSP的启发式算法.首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式算法的研究成果.此外,简要介绍除上述两大类启发式算法之外的其他几种启发式算法;最后,对全文进行总结,并指出该领域几个有希望的研究方向.     

基于多Agent的Supply-Hub库存策略建模与仿真研究

Supply-Hub是一种能较好地解决装配式供应链协同运作问题的供应链运作模式,其库存参数设置对于平衡上游供应商与下游制造商之间的利益,吸弓l供应商加入Supply-Hub非常关键.建立了由两个供应不同零部件的供应商向制造商补货时的供应商多周期成本模型,采用多Agent仿真方法,研究了三种情形下(s,S)库存策略参数的变动对供应商及制造商的影响,以期为Supply-Hub运营商合理确定库存策略参数提供一定参考.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

基于资源随机中断的反应性多模式项目调度优化

资源中断是项目实施过程中一种常见现象,它会导致项目进度计划的变更并引起额外的成本。本文研究资源随机中断下的项目调度问题,目标是对基准进度计划进行合理的调整,以最小化由此所造成的额外成本。作者首先对研究问题进行界定,随后构建问题的优化模型。针对模型的NP-hard属性,设计禁忌搜索启发式算法。最后以基准列表算法和随机生成算法为参照,在随机生成的标准算例集合上对算法进行测试,得到如下结论:在可接受的计算时间范围内,禁忌搜索获得的满意解质量明显高于其他两种启发式算法;算法的平均计算时间随着项目活动数的增加而增加,随着网络复杂度、资源强度或资源中断次数的增加而减小;满意解的平均目标函数值,随着项目活动数或网络复杂度的增加而增加,随着资源中断次数的增加而减小,与资源强度无明显关系。     

A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.     

活动执行时间可提前的多模式反应性项目调度优化

研究不确定活动工期下活动执行时间可提前的多模式反应性项目调度问题。首先对反应性研究现状进行综述;其次建立以最小化反应性总成本为目标的优化模型;随后基于问题特点设计禁忌搜索算法;最后通过具体案例分析关键参数对反应性成本的影响,并得出结论:执行时间提前得到的反应性成本及完工时间明显低于执行时间不可提前的结果;随着项目推进,总成本及影响的活动数量总体上呈减小趋势,但项目完工时间在某些时刻维持不变;对于工期增加较大的活动,将其本身或紧前活动提前启动,或将其转换至活动工期较短的模式可降低反应性成本。研究可为不确定环境下反应性计划制定提供决策支持。     

一阶多智能体系统的一致性分析

研究一阶连续多智能体系统的一致性问题,其中每个智能体只能在一系列离散时刻上获得其相对邻居的状态信息,并且每个智能体的保持器的周期和采样器的周期是不同的.通过分析多智能体系统的稳定性,获得了一致性成立的充要条件,该条件揭示了交流拓扑、控制器增益、采样器的周期和保持器的周期的关系.最后,提供一个仿真例子以说明理论结果的有效性.     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。     

Four Payment Models for the Multi-Mode Resource Constrained Project Scheduling Problem with Discounted Cash Flows

In this paper, the multi-mode resource constrained project scheduling problem with discounted cash flows is considered. The objective is the maximization of the net present value of all cash flows. Time value of money is taken into consideration, and cash in- and out-flows are associated with activities and/or events. The resources can be of renewable, nonrenewable, and doubly constrained resource types. Four payment models are considered: lump sum payment at the terminal event, payments at prespecified event nodes, payments at prespecified time points and progress payments. For finding solutions to problems proposed, a genetic algorithm (GA) approach is employed, which uses a special crossover operator that can exploit the multi-component nature of the problem. The models are investigated at the hand of an example problem. Sensitivity analyses are performed over the mark up and the discount rate. A set of 93 problems from literature are solved under the four different payment models and resource type combinations with the GA approach employed resulting in satisfactory computation times. The GA approach is compared with a domain specific heuristic for the lump sum payment case with renewable resources and is shown to outperform it.     

基于时间窗延迟的资源约束项目调度双层优化研究

本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。