资源约束项目调度研究综述

资源约束项目调度问题(RCPSP)研究资源的合理利用和项目活动的合理调度,实现既定目标的最优化,具有很强的工程背景,近年来得到了学术界和工业界的广泛关注.为此,介绍了RCPSP的数学模型以及多种问题的扩充,总结了相关理论,重点综述了RCPSP的算法,并归纳了若干应用进展.最后指出了有待进一步研究的方向和内容.     

差分进化混合粒子群算法求解项目调度问题*

针对求解资源受限项目调度问题（RCPSP）,提出了基于差分进化（DE）的混合粒子群算法（PSODE）。通过在PSO种群和DE种群之间建立一种信息交流机制,使信息能够在两个种群中传递,以避免个体因错误的信息判断而陷入局部最优点。采用标准测试函数和具体算例进行检验,结果表明PSODE算法可以较好地解决RCPS问题。     

分区交叉差分进化算法及其约束优化

差分进化算法处理复杂高维优化问题时存在收敛速度慢和精度不高的缺陷,为此提出了分区交叉差分进化算法。利用柯西分布随机数设计两个动态算子,分别生成缩放因子和交叉因子用于进化中,并对进化进行合理的分区,不同区段根据不同的配置利用算子生成相应的交叉因子。同时为了加快收敛速度,采用了新的变异策略,对寻优的方向加以引导。对经典Benchmark函数进行了仿真测试,结果显示,本算法的收敛速度与优化准确率均有显著提高。同时提供了算法处理约束问题的解决方案,并检验了方案的可行性。     

改进差分进化算法在动态经济调度中的应用

针对动态经济调度(DED)存在的不可微、非凸性、非线性以及不连续性等特点,提出多策略异维变异差分进化(MDMDE)算法.一方面,从变异维数入手,提出了一种异维变异策略;另一方面,在算法的整个迭代周期内采用了多策略变异.此外,还提出了一种修改的交叉率以及动态变异因子来跳出局部最优.最后,将MDMDE应用于6种动态经济调度...     

差分进化算法参数控制与适应策略综述

差分进化算法逐渐成为进化计算领域最流行的随机搜索算法之一,已被成功用于求解各类应用问题.差分进化算法参数设置与其性能密切相关,因此算法参数控制与适应策略设计是目前该领域的研究热点之一,目前已涌现出大量参数控制方案,但尚缺乏系统性的综述与分析.首先简要介绍差分进化算法的基本原理与操作,然后将目前参数控制与适应策略分成基于经验的参数控制、参数随机化适应策略、基于统计学习的参数随机化适应策略和参数自适应策略4类进行系统性综述,重点介绍其中的参数适应与自适应策略.此外,为分析各种参数控制与适应策略的功效,以实值函数优化为问题背景设计了相关实验,进一步分析各种策略的效率与实用性,实验结果表明,参数自适应控制策略是目前该领域最有效的方法之一.     

基于改进约束差分进化算法的动态航迹规划

为解决三维复杂环境下无人机动态航迹规划问题,提出一种基于改进约束差分进化算法的动态航迹规划方法,以满足对实时性及动态搜索精度的要求.首先,根据无人机航迹规划特点将其描述为包括飞行约束及威胁约束在内的约束优化问题,并构造目标代价函数和约束限制函数;其次,将广义反向学习和自适应排序变异操作引入到约束差分进化算法中,以提高算法的多样性、收敛速度和寻优精度;最后,利用自适应权衡模型对各状态下的约束限制进行处理,充分利用\"精英\"个体信息,实现对目标适应值的合理转换.通过仿真实验以及与3种先进约束差分进化算法比较表明:所提方法能够有效实现静态及动态威胁回避,规划出安全适航的飞行路径,实现地形跟随;相较于其他3种算法,所提方法具有寻优性能好、鲁棒性强、收敛速度快和可靠性高等优势.     

具有参数自适应机制的改进离散差分进化算法

在研究和分析离散差分进化算法的基础上,提出了一种具有参数自适应机制的改进离散差分进化算法(PADDE)。该算法首先对连续域进化过程中的参数进行自适应调整,以平衡全局搜索与局部搜索,协调种群多样性和收敛速度间的矛盾,其次根据对应离散域上成功进化的个体的离散编码反馈信息引导算法协同进化。通过对背包问题进行的实验表明,该算法具有良好的收敛效率和稳定性。     

差分进化粒子群算法求解发电资源调度问题

为了有效地解决水火电力系统资源短期优化调度问题,提出了一种基于差分进化粒子群的调度算法。设计了水火电力系统资源调度问题的数学模型,给出了差分进化粒子群优化算法的框架,通过PSO种群和DE种群之间的信息交流机制以寻求全局最优位置,从而使算法具有动态自适应性,能够较容易地跳出局部最优。实验结果表明,该算法能有效解决水火发电资源调度问题,具有较好的应用价值。     

自适应差分进化算法及对动态环境经济调度问题应用

为了应对动态环境经济调度(DEED)问题的高维性和大规模约束性,提出了一种自适应多目标差分进化算法(ADEA)。设计自适应差分交叉模块,提出改进的current to best/1交叉策略提高种群的多样性,有效地提高传统进化算法的探索与开采能力,提出一种修补策略处理功率平衡约束和爬坡率约束。为了验证该方法的有效性,数值仿真将ADEA应用于10机系统进行测试,并与同类算法展开比较,仿真结果表明ADEA具有较好的收敛能力,获得的Pareto前沿具有较好的均匀性和延展性,通过模糊决策获得的最好折中解能为电力系统调度人员提供较为合理的调度方案。     

两级差分进化算法求解多资源作业车间批量调度问题

以优化生产周期为目标,研究并建立了多资源作业车间批量调度问题模型.提出一种新的两级差分进化算法,采用两级染色体编码来解决批量划分和排序优化问题;设计了基于自适应差分进化算法(DE)的全局搜索操作,并在算法框架中嵌入了基于Interchange邻域结构的局部搜索;基于等量划分原则,为每个工件确定最优批次数及子批次的批量大小,并为各子批次确定最优排序.通过单资源算例和多资源实例仿真表明了模型和算法的可行性和有效性.     

An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.     

A note on “event-based MILP models for resource-constrained project scheduling problems”

Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Koné et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.     

Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems

Project scheduling is an inherently multi-objective problem, since managers want to finish projects as soon as possible with the minimum cost and the maximum quality. However, there are only a few papers dealing with multiobjective resource-constrained project scheduling problems (MORCPSPs). Moreover, there is no theoretical study in the literature that establishes the fundamentals for correct algorithmic developments. In this paper we try to close the gap by proving several results for MORCPSPs. With these results as a basis, both exact and heuristic procedures capable of obtaining a set of efficient solutions for several important MORCPSPs can be created.     

Event-based MILP models for resource-constrained project scheduling problems

In this paper we make a comparative study of several mixed integer linear programming (MILP) formulations for resource-constrained project scheduling problems (RCPSPs).     

A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling

Traditionally, the resource-constrained project scheduling problem (RCPSP) is modeled as a static and deterministic problem and is solved with the objective of makespan minimization. However, many uncertainties, such as unpredictable increases in processing times caused by rework or supplier delays, random transportation and/or setup, may render the proposed solution obsolete. In this paper, we present a two-stage algorithm for robust resource-constrained project scheduling. The first stage of the algorithm solves the RCPSP for minimizing the makespan only using a priority-rule-based heuristic, namely an enhanced multi-pass random-biased serial schedule generation scheme. The problem is then similarly solved for maximizing the schedule robustness while considering the makespan obtained in the first stage as an acceptance threshold. Selection of the best schedule in this phase is based on one out of 12 alternative robustness predictive indicators formulated for the maximization purpose. Extensive simulation testing of the generated schedules provides strong evidence of the benefits of considering robustness of the schedules in addition to their makespans. For illustration purposes, for 10 problems from the well-known standard set J30, both robust and non-robust schedules are executed with a 10% duration increase that is applied to the same randomly picked 20% of the project activities. Over 1000 iterations per instance problem, the robust schedules display a shorter makespan in 55% of the times while the non-robust schedules are shown to be the best performing ones in only 6% of the times.     

Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm

We study an assignment type resource-con- strained project scheduling problem with resources being multi-skilled personnel to minimize the total staffing costs. We develop a hybrid Benders decomposition (HBD) algorithm that combines the complimentary strengths of both mixed-integer linear programming (MILP) and constraint programming (CP) to solve this NP-hard optimization problem. An effective cut-generating scheme based on temporal analysis in project scheduling is devised for resolving resource conflicts. The computational study shows that our hybrid MILP/CP algorithm is both effective and efficient compared to the pure MILP or CP method alone.     

A double genetic algorithm for the MRCPSP/max

This paper presents a heuristic solution procedure for a very general resource-constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimised. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a two-phased genetic algorithm with different representation, fitness, crossover operator, etc., in each of them. One of the contributions of the paper is the optimisation in the first phase of a problem dual to the original, the searching for the best modes of the activities. Computational results show that the algorithm outperforms the state-of-the-art algorithms in medium and large instances.