基于混沌粒子群算法的多目标多执行模式项目调度问题研究

在工程项目调度中保持工期、成本、质量以及资源的均衡控制是构成项目建设总目标的关键因素,关系到整个工程的成败。同时,鉴于基本粒子群算法容易陷入局部最优,提出一种将混沌算法嵌入基本粒子群的新算法,并将其用于求解多目标项目调度问题,通过建立工期、费用、资源和质量多目标综合优化模型,再运用基于优先规则的混沌粒子群算法解决该模型问题。最终通过实例计算表明:相对于基本的粒子群算法,混沌粒子群算法可以更为准确快速地解决该模型下的项目多目标多执行模式优化调度问题。     

蚁群系统算法求解多模式资源约束项目调度问题

针对以工期最短为优化目标的多模式资源约束项目调度问题进行研究,在建立数学模型的基础上,通过设计合适的编码方式和调度生成策略,生成问题的构建图,定义新的信息素表示和启发式信息,提出一种改进的蚁群系统算法优化求解该问题。将模型和算法在工程项目调度实例中加以应用,验证了所提出的优化调度方法的正确性和有效性。     

一种求解多执行模式资源水平问题的遗传算法

针对资源受限情况下多执行模式工程调度中资源水平问题的特点,设计了一种遗传算法。解的编码采用满足紧前关系的工作链表与工作执行模式链表结合的双链表结构,交叉算子采用修正的一点交叉算法。为保证收敛解的可行性,在适值函数计算时对不可行解进行惩罚。对标准问题库PSPLIB中大量问题的求解实验结果表明,遗传算法是求解该问题的一种有效算法。     

蚁群-粒子群算法求解多模式资源受限项目调度问题

通过分析多模式项目调度问题的特点,提出一种主、从递阶结构的蚁群粒子群求解算法。算法中,主级为蚁群算法,完成任务模式选择;从级为粒子群算法,完成主级约束下的任务调度。然后,以工期最小和资源均衡分配为目标设计蚂蚁转移概率、模式优选概率和任务优选概率。最后,针对PSPLIB中的测试集对算法主要参数进行优化,并通过与其他算法比较验证了算法的有效性。     

支持虚拟企业建立的项目优化调度算法

研究敏捷制造模式下,动态企业联盟的形成过程中出现的多模式资源受限项目调度问题.与前人研究的问题有所不同,文中考虑了项目中每个任务对可更新(再生)资源需求的任意分布、可更新(再生)资源的最大供给量随时间而变化的情形.     

运用遗传算法实现项目调度中的现金流优化

多模式的资源受限项目调度问题(MRCPSP)是生产实践中的一类常见的重要问题,它具有NP-完全性质,难以在多项式时间内准确求解.现金流是项目财务管理及风险评估的重要指标,实现现金流优化对项目管理具有重要的意义.考虑了现金流优化与项目调度相结合的带折现流的多模式资源受限项目调度模型(MRCPSPDCF),首先对该模型建模,然后给出运用遗传算法求解的具体方案,考虑了里程碑事件和相等时间间隔两种支付方式,在仿真实验中比较了这两种支付方式的实验结果,并证明了遗传算法的有效性.     

基于遗传算法的多模式资源约束项目调度问题研究

为解决多模式资源约束项目调度问题,提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解,基因的值表示任务的优先权和执行模式,每条染色体对应一个满足逻辑关系约束的可行任务排序,根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作,能够使搜索范围遍及整个问题解空间。实际应用表明,该算法能快速求得问题的最优解或近似最优解。     

基于模拟谐振子算法的多项目调度

针对资源受限多项目调度问题(RCMPSP),介绍了一种模拟谐振子算法。算法通过模拟简谐振动系统中势能状态的变化,从经典简谐振动阶段过渡到量子振动阶段,从而实现全局搜索到局部搜索的变化过程;同时,两阶段的搜索形式使算法的收敛精度和搜索效率得到了保证。采用基于排列的方法和串行项目进度生成机制,结合多项目的任务列表,可以保证所得调度方案满足项目优先关系约束。运用标准测试函数对算法进行了测试,结果表明算法具有高质量的搜索效率和精度。最后给出了三组多项目调度算例。     

一种求解多目标资源受限项目调度的遗传算法

采用基于非支配性排序的多目标遗传算法—NSGA－Ⅱ,设计了一种求解多模式、多种类资源约束的多目标资源受限项目调度问题的遗传算法,该算法所设计的编码包含两部分,一部分为一个任务链表,另一部分为任务链表中各任务所对应的执行模式组成的模式向量。将所设计的算法用于求解文献中的以项目总工期和资源均衡为目标的农业项目调度问题,结果表明此算法对于求解多目标资源受限项目调度问题是有效的。     

A preemptive bound for the Resource Constrained Project Scheduling Problem

The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging ${\mathcal {NP}}$ -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.     

蜂群算法求解资源受限项目调度问题及仿真

蜂群算法作为一种较为新颖的启发式算法已经在多种类型的优化问题求解过程中表现了优秀的性能.针对蜂群算法在项目调度问题中的模型求解资源受限的问题,提出对求解方法进行改进,采用人工蜂群算法和蜂群优化算法两类典型的蜂群算法,对资源受限项目调度问题进行优化设计,并在benchmark上进行仿真并与传统的调度优化算法进行比较.实验结果表明,新设计的两类蜂群算法在调度成功率和收敛速度方面均有更好表现,人工蜂群算法求解的质量方面更优,蜂群算法在收敛速度上更具有优势.     

资源受限的项目调度问题的求解算法

本文建立了不确定资源环境下的资源受限的项目调度模型,用不确定规划的方法将不确定问题转化为等价的确定性问题,并给出了一个解决该问题的二阶段算法及实例。     

多资源约束下的项目调度邻域搜索算法

为了解决项目调度过程中不同项目之间的资源冲突问题,提出了一种基于拓扑排序的邻域搜索算法．设计跳动和微动两个操作,实现编码的更新,保证解的多样性与收敛性．用项目调度问题库（Project Scheduling ProblemLibrary．PSPLIB）中不同规模的实例对算法进行检验,结果表明,这种邻域搜索算法能够找到较优的解．用这种邻域搜索算法计算其它算法的案例,结果也显示这种算法具有一定的优越性．对这种邻域搜索算法的不同参数进行实验,分析了参数设置对算法性能的影响．     

动态选择时钟的资源约束下调度算法

为拓展数据流综合可搜索解空间,使资源约束下的调度结果更加接近全局最优,提出一种动态选择时钟周期的资源约束下调度算法.在资源约束调度过程中,通过对单周期、多周期和链式操作进行组合来计算备选时钟;在调度过程中选择能够充分利用元件资源,并可减小数据通道延迟时间的时钟周期,最终完成最佳时钟下的资源约束下调度.该算法将资源约束的影响引入时钟周期的选择,可得到能够真正提高性能的最优时钟;在时钟选择过程中完成资源约束下调度,使调度和时钟选择同时完成,保证调度结果的全局最优性.实验结果表明,采用文中算法得到的时钟周期和调度结果保证了资源约束条件下的数据通道延时最小.     

优化寄存器需求的资源约束调度算法

调度和寄存器优化是两个相互关联的问题,顺序完成这两个步骤的传统方法会导致非优化的结果．提出一种优化寄存器需求的资源约束调度算法RSROP,能够有效地同时优化调度长度和寄存器需求,并通过标准高层次综合测试电路实验,说明了RSROP算法的有效性．     

基于基因表达式的克隆选择算法求解JSP问题

针对作业车间调度问题的特征,提出一种基于基因表达式的克隆选择算法。在这个方法中,采用基因表达式编程算法中的编码方式来表示调度方案,同时为了提出的方法具有更强的全局搜索能力,运用克隆选择算法作为搜索引擎。最后,验证提出的方法的有效性,对7组Benchmark实例进行测试。实验结果表明,基于基因表达式的克隆选择算法在求解作业车间调度问题中是非常有效的。     

The Multi-Mode Resource-Constrained Multi-Project Scheduling Problem

Scheduling projects is a difficult and time consuming process, and has far-reaching implications for any organization’s operations. By generalizing various aspects of project scheduling, decision makers are enabled to capture reality and act accordingly. In the context of the MISTA 2013 conference, the first MISTA challenge, organized by the authors, introduced such a general problem model: the Multi-Mode Resource-Constrained Multi-Project Scheduling Problem (MRCMPSP). The present paper reports on the competition and provides a discussion on its results. Furthermore, it provides an analysis of the submitted algorithms, and a study of their common elements. By making all benchmark datasets and results publicly available, further research on the MRCMPSP is stimulated.     

项目调度及其优化

研究了项目调度问题及其优化算法,在对调度问题作了详细分类的基础上,对各种调度问题的优化算法做出．总结,并针对目前各种调度模型存在的不足,提出了均衡优化调度和可持续发展调度等新的调度目标。