A hybrid evolutionary algorithm for the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) is an NP-hard optimization problem. RCPSP is one of the most important and challenging problems in the project management field. In the past few years, many researches have been proposed for solving the RCPSP. The objective of this problem is to schedule the activities under limited resources so that the project makespan is minimized. This paper proposes a new algorithm for solving RCPSP that combines the concepts of negative selection mechanism of the biologic immune system, simulated annealing algorithm (SA), tabu search algorithm (TS) and genetic algorithm (GA) together. The performance of the proposed algorithm is evaluated and compared to current state-of-the-art metaheuristic algorithms. In this study, the benchmark data sets used in testing the performance of the proposed algorithm are obtained from the project scheduling problem library. The performance is measured in terms of the average percentage deviation from the critical path lower bound. The experimental results show that the proposed algorithm outperforms the state-of-the-art metaheuristic algorithms on all standard benchmark data sets.     

Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting

In this paper, we explore the difference between preemption and activity splitting in the resource-constrained project scheduling problem (RCPSP) literature and identify a new set of RCPSPs that only allows non-preemptive activity splitting. Each activity can be processed in multiple modes and both renewable and non-renewable resources are considered. Renewable resources have time-varying resource constraints and vacations. Multi-mode RCPSP (MRCPSP) with non-preemptive activity splitting is shown to be a generalization of the RCPSP with calendarization. Activity ready times and due dates are considered to study the impact on project makespan. Computational experiments are conducted to compare optimal makespans under three different problem settings: RCPSPs without activity splitting (P1), RCPSPs with non-preemptive activity splitting (P2), and preemptive RCPSPs (P3). A precedence tree-based branch-and-bound algorithm is modified as an exact method to find optimal solutions. Resource constraints are included into the general time window rule and priority rule-based simple heuristics are proposed to search for good initial solutions to tighten bounding rules. Results indicate that there are significant makespan reductions possible when non-preemptive activity splitting or preemptions are allowed. The higher the range of time-varying renewable resource limits and the tighter the renewable resource limits are, the bigger the resulting makespan reduction can be.     

Augmenting priority rule heuristics with justification and rollout to solve the resource-constrained project scheduling problem

The key question addressed by the resource-constrained project scheduling problem (RCPSP) is to determine the start times for each activity such that precedence and resource constraints are satisfied while achieving some objective. Priority rule-based heuristics are widely used for large problems. Rollout and justification can be integrated with priority rule heuristics to solve the RCPSP. We develop several such procedures and examine the resulting solution quality and computational cost. We present empirical evidence that these procedures are competitive with the best solution procedures described in the literature.     

多次抢占项目调度问题的混合遗传算法

研究多次抢占式资源受限的项目调度问题，假设任意时间点可作为资源抢占节点且抢占次数不受限制，建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法（GA）局部搜索能力缺陷，在算法中引入禁忌搜索（TS）进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数，并以标准算例集（Project Scheduling Problem Library，PSPLIB）对算法进行可行性检验。实验结果表明，资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期，设计的算法对问题求解效果良好。     

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

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

A multi-agent system for the decentralized resource-constrained multi-project scheduling problem

A restart evolution strategy (RES) for the resource‐constrained project scheduling problem (RCPSP), as well as its integration in a multi‐agent system (MAS) for solving the decentralized resource‐constrained multi‐project scheduling problem (DRCMPSP) will be presented. To evaluate the developed approach, problem instances of the RCPSP taken from the literature with up to 300 activities are used, as well as 80 generated instances of the DRCMPSP, with up to 20 projects and with up to 120 activities each. For 73 instances of the RCPSP, the RES found better solutions than the best ones found so far. In addition, the MAS is suitable for solving large multi‐project instances decentrally. The results for the DRCMPSP instances show that the presented decentralized MAS is competitive with a central solution approach.     

SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM

In this article, a hybrid metaheuristic method for solving the open shop scheduling problem (OSSP) is proposed. The optimization criterion is the minimization of makespan and the solution method consists of four components: a randomized initial population generation, a heuristic solution included in the initial population acquired by a Nawaz-Enscore-Ham (NEH)-based heuristic for the flow shop scheduling problem, and two interconnected metaheuristic algorithms: a variable neighborhood search and a genetic algorithm. To our knowledge, this is the first hybrid application of genetic algorithm (GA) and variable neighborhood search (VNS) for the open shop scheduling problem. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches a high quality solution in short computational times. Moreover, 12 new hard, large-scale open shop benchmark instances are proposed that simulate realistic industrial cases.     

An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem

In this paper, we propose an effective heuristic based on the framework of the shuffled frog-leaping algorithm (SFLA) for solving the resource-constrained project scheduling problem (RCPSP). We encode the virtual frog as the extended activity list (EAL) and decode it by the SFLA-specific serial schedule generation scheme (SSSGS). The initial population is generated by the regret-based sampling method and the priority rule. Then, virtual frogs are partitioned into several memeplexes, and each memeplex evolves by adopting the effective resource-based crossover (RBCO). To enhance the exploitation ability, a combined local search including permutation-based local search (PBLS) and forward-backward improvement (FBI) is performed in each memeplex. To maintain the diversity of each memeplex, virtual frogs are periodically shuffled and reorganized into new memeplexes. Basing on some theoretical analysis, speed-up evaluation methods are proposed to improve the efficiency of the SFLA, which are also suitable for other heuristics designed for RCPSP. In addition, we make use of a design-of-experiment method to determine the set of suitable parameters for the SFLA. Computational results and comparisons with some typical existing algorithms demonstrate the effectiveness of the proposed SFLA.     

求解任务可拆分多项目协同调度问题的启发式算法

生产项目计划与调度过程中任务可以被拆分为更小粒度的子任务分批次执行,实现缩短项目总工期的优化目标.针对抢占式任务可拆分多项目调度问题,从协同优化角度探讨任务拆分与重组方式,提出一个长工期任务优先拆分、长工期项目优先拆分和高资源利用率项目优先拆分3种任务拆分优先级判断规则,设计一种求解任务可拆分多项目协同调度问题的启发式算法.最后通过数值实例和仿真分析验证了所提出方法在多项目调度总工期的优化效果和求解效率.     

Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities

Research concerning project planning under uncertainty has primarily focused on the stochastic resource-constrained project scheduling problem (stochastic RCPSP), an extension of the basic RCPSP, in which the assumption of deterministic activity durations is dropped. In this paper, we introduce a new variant of the RCPSP, for which the uncertainty is modeled by means of resource availabilities that are subject to unforeseen breakdowns. Our objective is to build a robust schedule that meets the project deadline and minimizes the schedule instability cost, defined as the expected weighted sum of the absolute deviations between the planned and the actually realized activity starting times during project execution. We describe how stochastic resource breakdowns can be modeled, which reaction is recommended, when a resource infeasibility occurs due to a breakdown, and how one can protect the initial schedule from the adverse effects of potential breakdowns. An extensive computational experiment is used to show the relative performance of the proposed proactive and reactive strategies. It is shown that protection of the baseline schedule, coupled with intelligent schedule recovery, yields significant performance gains over the use of deterministic scheduling approaches in a stochastic setting. This research has been supported by project OT/03/14 of the Research Fund of K.U.Leuven, project G.0109.04 of the Research Programme of the Fund for Scientific Research, Flanders (Belgium) (F.W.O.-Vlaanderen) and project NB/06/06 of the National Bank of Belgium.     

A basis for the design of a multiattribute heuristic for single resource project scheduling

Two important characteristics of a project network are the network's topology and the amount of resources available. Most published project scheduling procedures take one or both of these two characteristics into account. Project scheduling procedures that are robust over variations of network characteristics are desirable. The degree of robustness is generally gauged by one or more measures of performance.

The objective of this paper is to compare a set of priority rules that are useful for a single resource project scheduling problem. The set of networks suggested by Patterson (1973) is used along with the set of performance measures proposed by Khattab and Choobineh 1991. The result of this comparison allows one to design a multiattribute heuristic for a single resource project scheduling problem.     

Optimization and heuristic models to integrate project task and manpower scheduling

The objective of project scheduling is to determine start dates and the labor resources assigned to each activity in order to complete a project on time. By moving start dates within available slack times and altering labor levels, the daily labor-demand profile can be changed. The objective of personnel scheduling is to determine how many of each feasible workday tour are required to satisfy a given labor-demand profile while minimizing the cost of labor plus overhead. Integrating these two problems permits the simultaneous determination of start dates, labor levels and tours for a minimum-cost and on-time schedule. In this paper, single and multiple resource optimization models and heuristic solution procedures to solve the integrated problem are presented. The heuristic procedure outperformed the non-integrated two-step scheduling procedure by reducing the cost of labor and overhead and performed nearly as well as the optimization procedure.     

基于广义资源日历约束的项目资源调配优化问题

资源受限项目调度问题(RCPSP)是最具代表性的项目调度问题之一,针对实际情况中考虑资源投入的必要性,建立一种以资源投入为变量的基于广义资源日历约束的项目调度优化模型.首先,引入组合优先关系的概念对广义资源日历的概念和具体内容进行整合和完善,为了避免传统网络图在表示组合优先关系时出现的网络循环等弊端,使用节点表示活动开始和结束的瞬时状态改进节点网络图;其次,考虑活动优先关系、活动持续时间、不可更新资源总量和资源日历约束,以项目工期最短和项目成本最小为优化目标,运用CP优化器求解所建立的多目标优化模型;最后,通过设计仿真算例并进行数值实验验证模型的准确性和高效性.     

An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly

Scheduling of aircraft assembling activities is proven as a non-deterministic polynomial-time hard problem; which is also known as a typical resource-constrained project scheduling problem (RCPSP). Not saying the scheduling of the complex assemblies of an aircraft, even for a simple product requiring a limited number of assembling operations, it is difficult or even infeasible to obtain the best solution for its RCPSP. To obtain a high quality solution in a short time frame, resource constraints are treated as the objective function of an RCPSP, and an adaptive genetic algorithm (GA) is proposed to solve demand-driven scheduling problems of aircraft assembly. In contrast to other GA-based heuristic algorithms, the proposed algorithm is innovative in sense that: (1) it executes a procedure with two crossovers and three mutations; (2) its fitness function is demand-driven. In the formulation of RCPSP for aircraft assembly, the optimizing criteria are the utilizations of working time, space, and operators. To validate the effectiveness of the proposed algorithm, two encoding approaches have been tested with the real data of demand.     

粒子群算法求解任务可拆分项目调度问题

首先针对任务可拆分的项目调度问题,提出一种带有局部搜索的粒子群算法LSPSO;然后采用基于任务排列的粒子表示方法,将遗传算法中的定位交叉引入粒子的更新过程中,并采用局部搜索技术对更新后的粒子进行改进;最后对Patterson测试集中110个问题实例进行了测试,实验结果表明,算法LSPSO具有较快的速度,所给出的调度方案较优.     

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

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

基于改进NSGA-II算法求解多目标资源受限项目调度问题

资源受限项目调度问题(resource constrained project scheduling problem, RCPSP)要求在满足相关约束的条件下安排各活动开始时间,从而达到某一目标的最优,具有很强的应用背景,并受到众多学者的广泛关注.经典的RCPSP模型以最小化项目工期为单一目标,忽略了资源使用率等因素对项目整体的影响,使其与实际应用仍有较大差距.基于经典的RCPSP模型,引入最优资源均衡为另一目标,将模型扩展为多目标模型,丰富了RCPSP模型的应用场景.同时,考虑到新模型中各活动间存在大量的控制关系,使用传统的启发式多目标算法需要耗费大量的时间对不可行解进行判断,求解性能较低,提出一种新的算法框架NSGA-IIs.该算法框架基于活动间控制关系将各活动分成若干子集,并在初始化和交叉变异等阶段以子集为基本单位产生新的个体,能够较好地避免不可行解的产生,提高算法的效率.使用解集覆盖度作为评价指标,通过实例数据集的实验表明,与已有的求解RCPSP的经典算法相比,所提出的算法具有明显的优越性.     

Priority-based heuristics for the multi-skill resource constrained project scheduling problem

In this paper we investigate one of the most recent extensions of the Resource Constrained Project Scheduling Problem (RCPSP): the Multi-Skill Resource Constrained Project Scheduling Problem (MSRCPSP). For this complex problem we propose the use of a parallel scheduling scheme. Such scheme has been successfully applied to the RCPSP. Nevertheless, in order to apply it to the MSRCPSP two new concepts are developed: resource weight and activity grouping. We discuss such concepts and use them for the new heuristic framework proposed. A series of computational tests performed using a large number of instances and reported in this paper shows that the new heuristic is very effective in finding high quality solutions within very small CPU times.     

Minimizing weighted earliness–tardiness on parallel machines using hybrid metaheuristics

We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem.The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies.The results show that our algorithms consistently outperform the best reported results for this problem.     

基于动态资源权重的多技能项目调度启发式算法

多技能资源受限项目调度问题中,一个资源可同时具备多项技能,相较于传统的单技能项目调度,其资源分配对调度计划的工期影响程度更大,因此在对多技能项目进行排程时更加重视资源的分配.基于此,从资源视角提出一种启发式算法求解工期最短的调度计划.算法以并行调度为主体,并设计一种动态资源权重计算方法,在每一决策点,首先采用二分图最大匹配法确定当前可排活动集,而后将动态资源权重值作为调度过程中资源分配的依据,其核心思想是将资源灵活度高、对后续活动影响大的资源留置,以待下一决策点调用.最后,为验证算法有效性,对不同参数设置下的算例进行实验,结果表明,相较于随机资源分配算法和静态资源权重算法,新算法具有明显优势.