一种多目标资源受限项目调度问题的教学算法

针对多目标资源受限项目调度的特性, 基于结合活动列表和资源列表的编码设计了合理的交叉操作, 提出一种多目标教学算法. 为了在个体间有效交互信息, 在教师阶段非支配个体作为教师与学生执行交叉, 而在学生阶段学生间执行交叉, 同时在每个阶段通过前向-反向改进增强局部搜索能力, 并用Pareto 档案集存储和更新非支配个体.基于标准测试集的数值仿真及与现有最好算法的比较, 验证了所提出算法的有效性.

     

An activity-list-based nested partitions algorithm for resource-constrained project scheduling

The resource-constrained project scheduling problem (RCPSP) has received wide attention. In this paper, an activity-list-based nested partitions algorithm (ALNP) is developed for solving the RCPSP and a P-ALNP is proposed to improve ALNP with local adjustment. In the algorithms, to improve the search efficiency, a partial double justification is employed as local search mechanism. The computational experiments on the PSPLIB and analysis on robustness of the algorithms show that ALNP outperforms the traditional serial scheduling scheme for solving the large-scale, complex RCPSPs, and P-ALNP can improve ALNP and obtain better results. P-ALNP is a competitive algorithm for solving the RCPSP.     

Resource-constrained scheduling with hard due windows and rejection penalties

This work studies a scheduling problem where each job must be either accepted and scheduled to complete within its specified due window, or rejected altogether. Each job has a certain processing time and contributes a certain profit if accepted or penalty cost if rejected. There is a set of renewable resources, and no resource limit can be exceeded at any time. Each job requires a certain amount of each resource when processed, and the objective is to maximize total profit. A mixed-integer programming formulation and three approximation algorithms are presented: a priority rule heuristic, an algorithm based on the metaheuristic for randomized priority search and an evolutionary algorithm. Computational experiments comparing these four solution methods were performed on a set of generated benchmark problems covering a wide range of problem characteristics. The evolutionary algorithm outperformed the other methods in most cases, often significantly, and never significantly underperformed any method.     

基于Pareto排序和混沌加权的多目标项目调度

为综合考虑资源约束型项目调度问题的多个调度目标,有效获得该问题的近似非支配解集,建立了一种综合考虑可更新资源稳定性和工期的双目标项目调度模型。提出了一种基于Pareto排序和多目标混沌加权相结合的遗传算法,其中个体编码采用双链表结构,分别代表任务的执行顺序和执行模式,初始种群的生成包括随机生成和依据任务特性确定执行模式两种方式,设计了个体交叉和自适应变异算子,研究了基于Pareto排序法和基于多目标混沌加权法的个体适应度计算方法以及不可行解的修复和惩罚策略。利用项目调度问题算例库对该算法进行测试,数值测试结果验证了算法的有效性。     

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

针对以工期最短为优化目标的多模式资源约束优化调度问题进行研究,在建立数学模型基础上,采用改进遗传算法对模型进行求解.算法设计上,对各活动的执行模式进行统一编号,使模式的内部编号包含了时序约束、资源约束、工期等信息,针对活动执行模式采用特殊的整数编码方式,染色体基因由活动执行模式序号组成.对染色体结构设计了单点交叉和单点变异操作算子,采用锦标赛选择方法.通过实例验证了改进遗传算法在求解MMRCPSP上的有效性.     

人工蜂群算法求解任务可拆分项目调度问题

针对任务可拆分的资源受限的项目调度问题,提出了一种人工蜂群算法与任务可拆分的串行调度机制相结合的优化方法．人工蜂群算法中每个食物源的位置代表一组项目任务的优先权序列,优先权序列通过调度生成机制转换为可行调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新．实算表明,基于优先权的人工蜂群算法可以有效求解任务可拆分项目调度问题,收敛速度较快且精度较高．     

不确定资源约束下项目鲁棒性调度算法*

在跨企业项目中,由于资源可用时间具有不确定性,从而使得项目计划具有易变性。针对这一问题,首先采用模糊集对项目的不精确时间参数和资源不确定性进行了表示,并在同时考虑调度的质量鲁棒性和解的鲁棒性情况下,定义了调度的鲁棒性度量,进而开发了遗传算法来求解不确定资源约束下的项目鲁棒性调度问题。最后,给出了应用实例,并通过仿真分析说明算法的有效性。该算法已被应用到跨企业项目管理系统中,获得了良好的效果。     

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

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

Looking for the best modes helps solving the MRCPSP/max

The multi-mode resource-constrained project scheduling problem with minimum and maximum time lags MRCPSP/max is a very general project scheduling problem with multiple execution modes per activity, renewable and non-renewable resources and minimum and maximum time lags between activities. In this paper, we describe SA-EVA, an algorithm for the problem. SA-EVA first searches for the best mode for each activity, without considering renewable resources. In this phase a simulated annealing is applied. Once a mode vector has been chosen, the problem reduces to the RCPSP/max, which SA-EVA solves with EVA, an algorithm designed in Ballestín et al. [2009. An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time-lags. Journal of Scheduling, 14 (4), online]. Computational results show that SA-EVA outperforms the state-of-the-art algorithms in medium and large instances.     

采用优先规则的粒子群算法求解RCPSP

优先规则是解决大规模资源受限的项目调度问题（Resource-Constrained Project Scheduling Problem,RCPSP）强有力的方法,但是单一的优先规则的往往仅在某些特定的问题上表现出良好的性能。以粒子群算法为基础,提出了基于优先规则编码的粒子群算法（Priority Rule based Particle Swarm Optimization,PRPSO）,求解资源受限的项目调度问题。该方法能够通过粒子群算法搜索优先规则和调度生成方案的组合。分别对PRPSO采用串行调度方案、并行调度方案和混合调度方案时,不同任务数和资源强度的问题实例进行了分析。通过对PSPLIB进行测试,结果表明该方法与其它基于优先规则的启发式方法相比有较低的偏差率,因而有较好的性能。