Memetic algorithm for multi-mode resource-constrained project scheduling problems

A memetic algorithm （MA） for a multi-mode resourceconstrained project scheduling problem （MRCPSP） is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called ＂strategic oscillation＂ to make the search process have a higher probability to visit solutions around a ＂feasible boundary＂. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.

Multi-Mode Resource Constrained Project Scheduling Models for Progress and Equal Time Interval Payments

This study utilizes a time-precedence network technique to construct two models of multi-mode resource constrained project scheduling problem with discounted cash flows （MRCPSPDCF）, individually including the progress payment （PP） and the payment at an equal time interval （ETI）. The objective of each model is to maximize the net present value （NPV） for all cash flows in the project, subject to the related operational constraints. The models are characterized as NP-hard. A heuristic algorithm, coupled with two upper bound solutions, is proposed to efficiently solve the models and evaluate the heuristic algorithm performance which was not performed in past studies. The results show that the performance of proposed models and heuristic algorithm is good.

Scheduling Multi-Mode Resource-Constrained Projects Using Heuristic Rules Under Uncertainty Environment

Project scheduling is a key objective of many models and is the proposed method for project planning and management.Project scheduling problems depend on precedence relationships and resource constraints,in addition to some other limitations for achieving a subset of goals.Project scheduling problems are dependent on many limitations,including limitations of precedence relationships,resource constraints,and some other limitations for achieving a subset of goals.Deterministic project scheduling models consider all information about the scheduling problem such as activity durations and precedence relationships information resources available and required,which are known and stable during the implementation process.The concept of deterministic project scheduling conflicts with real situations,in which in many cases,some data on the activity’s durations of the project and the degree of availability of resources change or may have different modes and strategies during the process of project implementation for dealing with multi-mode conditions surrounded by projects and their activity durations.Scheduling the multi-mode resource-constrained project problem is an optimization problem whose minimum project duration subject to the availability of resources is of particular interest to us.We use the multi-mode resource allocation and schedulingmodel that takes into account the dynamicity features of all parameters,that is,the scheduling process must be flexible to dynamic environment features.In this paper,we propose five priority heuristic rules for scheduling multi-mode resource-constrained projects under dynamicity features for more realistic situations,in which we apply the proposed heuristic rules(PHR)for scheduling multi-mode resource-constrained projects.Five projects are considered test problems for the PHR.The obtained results rendered by these priority rules for the test problems are compared by the results obtained from 10 well-known heuristics rules rendered for the same test problems.The results in many cases of the proposed priority rules are very promising,where they achieve better scheduling dates in many test case problems and the same results for the others.The proposed model is based on the dynamic features for project topography.

Scheduling Rules Based on Gene Expression Programming for Resource-Constrained Project Scheduling Problem

In order to minimize the project duration of resourceconstrained project scheduling problem( RCPSP), a gene expression programming-based scheduling rule( GEP-SR) method is proposed to automatically discover and select the effective scheduling rules( SRs) which are constructed using the project status and attributes of the activities. SRs are represented by the chromosomes of GEP, and an improved parallel schedule generation scheme( IPSGS) is used to transform the SRs into explicit schedules. The framework of GEP-SR for RCPSP is designed,and the effectiveness of the GEP-SR approach is demonstrated by comparing with other methods on the same instances.

Efficient Genetic Algorithm for Resource-Constrained Project Scheduling Problem

This paper presents a new genetic algorithm for the resource-constrained project scheduling problem(RCPSP).The algorithm employs a standardized random key(SRK) vector representation with an additional gene that determines whether the serial or parallel schedule generation scheme(SGS) is to be used as the decoding procedure.The iterative forward-backward improvement as the local search procedure is applied upon all generated solutions to schedule the project three times and obtain an SRK vector,which is rese...

An Evolutionary Algorithm with Multi-Local Search for the Resource-Constrained Project Scheduling Problem

This paper introduces a hybrid evolutionary algorithm for the resource-constrained project scheduling problem (RCPSP). Given an RCPSP instance, the algorithm identifies the problem structure and selects a suitable decoding scheme. Then a multi-pass biased sampling method followed up by a multi-local search is used to generate a diverse and good quality initial population. The population then evolves through modified order-based recombination and mutation operators to perform exploration for promising solutions within the entire region. Mutation is performed only if the current population has converged or the produced offspring by recombination operator is too similar to one of his parents. Finally the algorithm performs an intensified local search on the best solution found in the evolutionary stage. Computational experiments using standard instances indicate that the proposed algorithm works well in both computational time and solution quality.

A New Algorithm for Resource Constraint Project Scheduling Problem Based on Multi-Agent Systems

The resource constrained project scheduling problem (RCPSP) and a decision-making model based on multi-agent systems (MAS) and general equilibrium marketing are proposed. An algorithm leading to the resource allocation decision involved in RCPSP has also been developed. And this algorithm can be used in the multi-project scheduling field as well.Finally, an illustration is given.

Solving resource availability cost problem in project scheduling by pseudo particle swarm optimization

This paper considers a project scheduling problem with the objective of minimizing resource availability costs appealed to finish al activities before the deadline. There are finish-start type precedence relations among the activities which require some kinds of renewable resources. We predigest the process of sol-ving the resource availability cost problem （RACP） by using start time of each activity to code the schedule. Then, a novel heuris-tic algorithm is proposed to make the process of looking for the best solution efficiently. And then pseudo particle swarm optimiza-tion （PPSO） combined with PSO and path relinking procedure is presented to solve the RACP. Final y, comparative computational experiments are designed and the computational results show that the proposed method is very effective to solve RACP.

SOLVING RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEMS WITH BI-CRITERIA HEURISTIC SEARCH TECHNIQUES

In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm for solving multiple resource-constrained project scheduling problems. The heuristic solves problems in two phases. In the pre-processing phase, the algorithm estimates distance between a state and the goal state and measures complexity of problem instances. In the search phase, the algorithm uses estimates of the pre-processing phase to further estimate distances to the goal state. The search continues in a stepwise generation of a series of intermediate states through search path evaluation process with backtracking. Developments of intermediate states are exclusively based on a bi-criteria new state selection technique where we consider resource utilization and duration estimate to the goal state. We also propose a variable weighting technique based on initial problem complexity measures. Introducing this technique allows the algorithm to efficiently solve complex project scheduling problems. A numerical example illustrates the algorithm and performance is evaluated by extensive experimentation with various problem parameters. Computational results indicate significance of the algorithm in terms of solution quality and computational performance.

Hybrid genetic algorithm for bi-objective resourceconstrained project scheduling

In this study,we considered a bi-objective,multi-project,multi-mode resource-constrained project scheduling problem.We adopted three objective pairs as combinations of the net present value(NPV)as a financial performance measure with one of the time-based performance measures,namely,makespan(Cmax),mean completion time(MCT),and mean flow time(MFT)(i.e.,minCmax/maxA^PF,minA/Cr/max7VPF,and min MFTI mdixNPV).We developed a hybrid non-dominated sorting genetic algorithm Ⅱ(hybrid-NSGA-Ⅱ)as a solution method by introducing a backward-forward pass(BFP)procedure and an injection procedure into NSGA-Ⅱ.The BFP was proposed for new population generation and post-processing.Then,an injection procedure was introduced to increase diversity.The BFP and injection procedures led to improved objective functional values.The injection procedure generated a significantly high number of non-dominated solutions,thereby resulting in great diversity.An extensive computational study was performed.Results showed that hybrid-NSGA-Ⅱ surpassed NSGA-Ⅱ in terms of the performance metrics hypervolume,maximum spread,and the number of nondominated solutions.Solutions were obtained for the objective pairs using hybrid-NSGA-Ⅱ and three different test problem sets with specific properties.Further analysis was performed by employing cash balance,which was another financial performance measure of practical importance.Several managerial insights and extensions for further research were presented.

面向资源约束的电动公交车充电调度策略

为减少公交运营成本、合理制定插入式充电模式下公交总站的电动公交车充电调度方案,本文基于帝国竞争算法提出了一种面向资源约束的公交车充电调度策略(RCO-CSS)。基于电动公交车运营的时空特点和充放电特性,应用多技能资源约束多项目调度问题(MSRC-MPSP)运筹规划思想对电动公交车充电问题进行抽象建模,以车队规模与充电桩数量为主要资源参数,以最小化充电成本和日均设备购置成本为目标,构建资源约束充电调度模型,进而设计一种二阶段演化帝国竞争算法(TSE-ICA)对模型进行求解,输出最佳的充电调度方案及匹配的行车运营计划。采用4个分别包含5、10、20和36条线路的公交运行实例对RCO-CSS进行了性能评估与有效性验证。在实例探讨中,首先运用Taguich法对资源参数进行了敏感性分析,发现资源越宽裕,模型输出的日充电费用越小,但车辆与充放电设备平摊至每日的购置成本越大;其次,将TSE-ICA与其他4种先进的元启发式算法进行实验数值对比,验证了所提算法的寻优性能;最后,通过与无序充电调度策略和常规有序充电调度策略进行比较,证明了RCO-CSS能够更好地降低用电成本、设备购置成本和电池充放电次数。基于MSRC-MPSP和TSE-ICA的RCO-CSS为公交运营商制定充电调度方案和行车运营计划提供了一种可行且敏捷高效的新思路。

基于CPM的多模式资源约束项目调度建模与复杂度分析

为有效降低多模式资源约束项目调度模型的复杂度和解空间,构建3类混合整数线性规划模型。运用紧上界TTUB缩减时间序列T的上界和关键路径法缩减各项活动结束时间的上下界,以降低模型复杂度和解空间。为验证改进模型的有效性,从MRCPSP标杆案例库中选取1106组规模不等的算例进行求解。结果表明,基于CPM的多模式资源约束项目调度模型解空间更小;决策变量同比缩小3~65倍,约束数同比缩小1~4倍;平均求解时间同比减少53%~112%,求解性能显著优于其他模型。为验证紧上界T_(TUB)的参数α性能,1106组算例结果表明,α越接近1,模型的复杂度越低,解空间越小。但随着算例规模增加,算例可行解探寻难度增加。因此,对大规模算例,α值应适当放宽。

基于改进遗传算法的船舶维修项目调度问题研究

船舶维修项目调度问题是典型的受优先关系和维修空间限制的资源受限项目调度问题。针对该问题,文章建立了一种船舶维修项目调度数学模型,并提出了改进遗传算法进行求解。基于问题的特征,改进遗传算法主要采用解码与编码策略、选择操作、交叉操作以及变异操作等方法平衡算法的探索和探寻能力。最后,采用工程实例验证了模型的合理性和算法的优越性。

基于改进多种群遗传算法的多目标资源受限项目调度问题研究

多目标资源受限项目调度问题普遍存在于生产经营活动中,具有较高的实用价值。本文提出了一种改进的多种群遗传算法以解决多目标资源受限项目调度问题,为改变现有算法计算步骤理解困难、不易推广的特点,巧妙地通过平移工作解决此类问题,算法首先对工作的优先级进行随机编码,然后根据工序约束进行解码,并根据解码结果安排工作调度,同时为防止无效迭代,融合了禁忌搜索的思想。最后,通过PSPLIB标准算例库中算例进行实验,实验结果表明该算法在具备较高精度的同时,兼顾了快捷性和简洁性。

基于改进NSGA-II算法的装配式建筑施工调度优化

针对以往装配式建筑调度研究主要基于每项活动只有确定的活动时间和一种执行模式,而实际调度过程中存在不确定的活动时间和多种执行模式,建立多目标多模式资源约束下的模糊工期调度模型,提出一种改进的非支配排序遗传算法(INSGA-II)来求解(时间−成本)双目标优化模型。该算法根据活动的优先级关系进行种群初始化和交叉操作,同时提出新的包含活动列表、模式列表和资源列表的3段编码。最后,通过装配式建筑施工现场实际案例分析和算法性能对比,证明本文构建的调度模型和算法设计能有效地解决多模式资源约束下的模糊工期调度模型,为施工调度计划的设计提供科学的思路和方法。

甲供非商品化资源约束下可中断项目群调度模型

不可更新资源的约束会导致项目群中各合同项目开工延误甚至施工中断。针对不可更新资源受限理论研究存在的局限性,开展了多种甲供非商品化资源(NCRPE)约束下可中断项目群调度问题的研究。首先,由于资源分配多样性会给项目群进度造成不确定性影响,围绕项目群工期—延误成本双目标优化模型展开研究,采用改进编码方式的多目标粒子群算法(MOPSO)进行求解,获取项目群的资源分配方案,利用串行调度生成机制(SSGS)得到项目群进度计划;其次,将MOPSO算法和NSGA-II算法进行对比,通过IGD和HV两个指标来衡量MOPSO算法求解该问题的有效性;最后,结合实际案例,对模型进行求解分析。在甲供非商品化资源约束和项目可中断情况下,构建的项目群调度模型能够有效地实现项目群工期和合同项目延误成本的双目标优化。研究成果为业主合理分配NCRPE以及进行项目群调度提供理论依据。

带转移时间的资源受限项目鲁棒调度优化

为使项目在面临活动工期扰动时尽可能按照基准调度计划稳定执行,针对带转移时间的资源受限项目调度问题提出鲁棒调度与资源分配集成优化方法。分别从资源转移关系、活动时差、随机活动工期三个不同角度设计三种解鲁棒性代理指标,构建了两个混合整数规划模型(MinEA,MaxPF)和一个随机规划模型(MinTPC),并分别采用精确方法和禁忌搜索启发式算法求解;在此基础上提出MinTPC+MaxPF混合优化策略。仿真实验结果表明,MinTPC+MaxPF方法在项目解鲁棒性和质鲁棒性两方面均能获得最优绩效;MinEA方法的解鲁棒性优于MinTPC,而后者的质鲁棒性优于前者。所研究的模型和方法,可以为项目决策者在工期不确定环境下协调活动进度安排和优化资源转移提供指导,提升项目计划鲁棒性,提高企业的经济效益。

基于时间窗延迟的多次抢占型项目调度优化研究

实际项目进程中因不确定因素导致活动执行被迫中断的情况时有发生,该研究针对允许活动在任意单位时间节点被中断的抢占型资源约束项目调度问题,设计了一种启发式算法。算法首先通过网络图的转化规则将活动进行拆分,然后结合深度优先和广度优先搜索设计了一类基于时间窗延迟方案的调度生成机制。通过调用PSPLIB数据库,设置不同参数,设计多组实验进行分析,结果表明,相较于非抢占模式,该算法在求解允许抢占模式的项目调度问题时表现出更优的结果,尤其对于大规模项目,验证了算法的有效性。同时与基本精确算法对比,该算法表现出更好求解速率,该求解结果为实际项目调度提供了决策参考。

面向资源约束项目调度的二阶段帝国竞争算法

资源约束项目调度问题是一类经典的组合优化难题,有着广泛的工程应用背景。自20世纪60年代起,该问题的优化方法层出不穷,但大多数智能优化算法在该问题空间中搜索表现一般。针对这一挑战,提出了一种二阶段演化帝国竞争算法(TSE-ICA)。首先,基于由关键路径法得到的组块提取策略,提出两种分别用于种群多样性开发和高效收敛的同化算子,通过在不同阶段选择合适的同化算子实现二阶段演化框架的构建。其次,基于组块的改进革命机制包含插入和乱序两种邻域搜索策略,帝国竞争机制则通过收集不同帝国的收敛信息实现参数的自适应调整;最后,利用记忆库引导种群进化,提高算法的收敛速率。TSE-ICA的最佳参数设置由Taguchi法的实验设计方法确定。数值实验面向典型实例库PSPLIB中的3个实例集J30、J60和J120对TSE-ICA执行了性能测试,并基于两种评价标准与17种先进的元启发式算法进行性能对比。实验结果显示,TSE-ICA具有较好的优化性能和收敛效率,初步验证了所提改进机制的有效性和所提算法的问题适用性。

基于改进离散蜉蝣算法的双资源柔性车间可持续调度方法

在目前对柔性车间调度问题所进行的研究中,大多忽略了工件运输时间这一因素,并且也很少对可持续发展的经济、环境和社会3个要素进行综合优化。针对这些问题,提出了一种考虑运输时间的双资源柔性车间调度问题(DRCFJSPT)模型。首先,以完工时间、生产成本、能耗和人体工程学风险为优化目标,构建了柔性车间调度数学模型,并结合多目标模型的特点,设计了一种改进离散蜉蝣算法(IDMA),并对模型进行了求解;然后,采用熵值法评价了帕累托解集,基于三层编码并考虑了运输时间的插入式解码方式,设计了混合初始化方法,离散改进了蜉蝣更新方式;最后,为了验证IDMA求解DRCFJSPT的性能,采用MATLAB,对某机床零件加工企业生产数据进行了实验,并将其结果与采用非支配排序遗传算法(NSGA)-Ⅱ得到的结果进行了对比分析。研究结果表明:改进算法的解集质量和收敛性能均显著优于参考算法,通过改进算法求得最优解的最大完工时间为35.94 h,加工成本为6 003.95元,能耗为2 054.54 kW·h,人体工程学风险值为138.16;该结果可为实际复杂的柔性车间调度环境提供清晰准确的调度方案。