Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations

This study addresses the resource-constrained project scheduling problem with precedence relations, and aims at minimizing two criteria: the makespan and the total weighted start time of the activities. To solve the problem, five multi-objective metaheuristic algorithms are analyzed, based on Multi-objective GRASP (MOG), Multi-objective Variable Neighborhood Search (MOVNS) and Pareto Iterated Local Search (PILS) methods. The proposed algorithms use strategies based on the concept of Pareto Dominance to search for solutions and determine the set of non-dominated solutions. The solutions obtained by the algorithms, from a set of instances adapted from the literature, are compared using four multi-objective performance measures: distance metrics, hypervolume indicator, epsilon metric and error ratio. The computational tests have indicated an algorithm based on MOVNS as the most efficient one, compared to the distance metrics; also, a combined feature of MOG and MOVNS appears to be superior compared to the hypervolume and epsilon metrics and one based on PILS compared to the error ratio. Statistical experiments have shown a significant difference between some proposed algorithms compared to the distance metrics, epsilon metric and error ratio. However, significant difference between the proposed algorithms with respect to hypervolume indicator was not observed.     

Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem

The resource-constrained project scheduling problem is one of the classical problems in the field of operations research. There are many criteria to efficiently determine the desired schedule of a project. In this paper, a well-known criterion namely project’s makespan is considered. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional methods. Therefore, an enhanced scatter search, based on a new path relinking and two prominent permutation-based and crossover operators, is devised to solve the problem. In order to validate the performance of the proposed algorithm, in terms of solution quality, the algorithm is applied to various test problems available on the literature and the reliability of it, is compared with well-reported benchmark algorithms. The computational results reveal that the proposed algorithm has appropriate results in comparison with the existing benchmark algorithms.     

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

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

Knowledge integration using problem spaces: A study in resource-constrained project scheduling

The need to develop schedules for projects with resource constraints and cash flows arises in organizational settings ranging from construction planning to research and development. Given the intractable nature of the problem, a variety of knowledge sources relevant to the project scheduling task have been identified in the Operations Management literature. These include a large number of heuristic procedures that can be used to generate feasible project schedules as well as recent neural network-based approaches that can select appropriate heuristic procedures to apply to a specific instance of the project scheduling problem. While integrated application of these knowledge sources is required to effectively support scheduling, previous work has focussed on developing and implementing them in isolation. The problem space computational model presented in this paper addresses this shortcoming by integrating these various knowledge sources, thus enabling the development of decision support systems for resource constrained project scheduling. More generally, the modeling approach used in this paper can be applied to create systems to assist knowledge intensive tasks that arise in many organizational settings.     

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).     

Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem

Finding a Pareto-optimal frontier is widely favorable among researchers to model existing conflict objectives in an optimization problem. Project scheduling is a well-known problem in which investigating a combination of goals eventuate in a more real situation. Although there are many different types of objectives based on the situation on hand, three basic objectives are the most common in the literature of the project scheduling problem. These objectives are: (i) the minimization of the makespan, (ii) the minimization of the total cost associated with the resources, and (iii) the minimization of the variability in resources usage. In this paper, three genetic-based algorithms are proposed for approximating the Pareto-optimal frontier in project scheduling problem where the above three objectives are simultaneously considered. For the above problem, three self-adaptive genetic algorithms, namely (i) A two-stage multi-population genetic algorithm (MPGA), (ii) a two-phase subpopulation genetic algorithm (TPSPGA), and (iii) a non-dominated ranked genetic algorithm (NRGA) are developed. The algorithms are tested using a set of instances built from benchmark instances existing in the literature. The performances of the algorithms are evaluated using five performance metrics proposed in the literature. Finally according to the technique for order preference by similarity to ideal solution (TOPSIS) the self-adaptive NRGA gained the highest preference rank, followed by the self-adaptive TPSPGA and MPGA, respectively.     

An efficient hybrid algorithm for resource-constrained project scheduling

We propose an efficient hybrid algorithm, known as ACOSS, for solving resource-constrained project scheduling problems (RCPSP) in real-time. The ACOSS algorithm combines a local search strategy, ant colony optimization (ACO), and a scatter search (SS) in an iterative process. In this process, ACO first searches the solution space and generates activity lists to provide the initial population for the SS algorithm. Then, the SS algorithm builds a reference set from the pheromone trails of the ACO, and improves these to obtain better solutions. Thereafter, the ACO uses the improved solutions to update the pheromone set. Finally in this iteration, the ACO searches the solution set using the new pheromone trails after the SS has terminated. In ACOSS, ACO and the SS share the solution space for efficient exchange of the solution set. The ACOSS algorithm is compared with state-of-the-art algorithms using a set of standard problems available in the literature. The experimental results validate the efficiency of the proposed algorithm.     

A new lower bound for the resource-constrained project scheduling problem with generalized precedence relations

In this paper we propose a new lower bound for the resource-constrained project scheduling problem with generalized precedence relationships. The lower bound is based on a relaxation of the resource constraints among independent activities and on a solution of the relaxed problem suitably represented by means of an AON acyclic network. Computational results are presented and confirmed a better practical performance of the proposed method with respect to those present in the literature.     

A heuristic approach for resource constrained project scheduling with uncertain activity durations

In this paper, we address the resource constrained project scheduling problem with uncertain activity durations. Project activities are assumed to have known deterministic renewable resource requirements and uncertain durations, described by independent random variables with a known probability distribution function. To tackle the problem solution we propose a heuristic method which relies on a stage wise decomposition of the problem and on the use of joint probabilistic constraints.     

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.     

人工蜂群算法求解资源受限项目调度问题

针对资源受限项目调度问题,提出了一种基于人工蜂群算法的优化方法。人工蜂群算法中每个食物源的位置代表一种项目任务的优先权序列,每个食物源的位置通过扩展串行调度机制转换成可行的调度方案,迭代中由三种人工蜂执行不同的操作来实现全局最优解的更新。实验结果表明,人工蜂群算法是求解资源受限项目调度问题的有效方法,同时扩展调度机制的引入可以加速迭代收敛的进程。     

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem

We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler.     

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

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

应用遗传模拟退火算法实现资源受限项目调度

针对以最小化项目工期为目标的资源受限项目调度问题（RCPSP）,提出将模拟退火算法融合到遗传算法中,以改善遗传算法局部搜索性能,增强进化能力的遗传模拟退火算法——RCPSPGSA。在每次进化迭代过程中,下一代种群的个体需经过模拟退火算法改进,并通过在每次迭代结束前进行降温操作保证遗传算法和模拟退火算法具有相同的收敛方向和速度。算法在RCPSP标准测试问题库PSPLIB上进行数值仿真实验,并采用正交实验分析法解决参数选择问题。实验结果证明选择的参数组合具有突出的性能,RCPSPGSA是求解RCPSP的有效算法。     

A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags

This paper presents an exact model for the multi-mode resource-constrained project scheduling problem with generalized precedence relations in which the minimal or maximal time lags between a pair of activities may vary depending on the chosen modes. All resources considered are renewable. The objective is to determine a mode and a start time for each activity so that all constraints are obeyed and the project duration is minimized. Project scheduling of this type occurs in many fields, for instance, construction industries. The proposed model has been inspired by the rectangle packing problems. In spite of the fact that it needs a feasible solution to start for conventional models, the new model has no need for a feasible solution to start. Computational results with a set of 60 test problems have been reported and the efficiency of the proposed model has been analyzed.     

A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling

This paper presents an effective heuristic algorithm based on the framework of the filter-and-fan (F&F) procedure for solving the resource-constrained project scheduling problem (RCPSP). The proposed solution methodology, called the filter-and-fan approach with adaptive neighborhood switching (FFANS), operates on four different neighborhood structures and incorporates improved local search, F&F search with multiple neighborhoods and an adaptive neighborhood switching procedure. The improved local search, in which a new insert-based move strategy and new time compression measurement of schedules having the same makespan are embedded, is utilized to identify a local optimum and a basic move list. The F&F search, aimed to further improve the local optimum, applies multi-neighborhood filter and fan strategies to generate compound moves and a neighborhood-switch list in a tree search fashion. When the current neighborhood cannot further improve the local optimum, the adaptive neighborhood switching procedure picks the most potential neighborhood for the next run of the local search procedure. The entire solution procedure is autonomous and adaptive due to its variable search range depending on the project sizes and characteristics. Computational results and comparisons with some state-of-the-art algorithms indicate the effectiveness and competence of the proposed FFANS.     

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.     

Multi-start iterated local search metaheuristic for the multi-mode resource-constrained project scheduling problem

In this paper a multi-start iterated local search (MS-ILS) algorithm is presented as a new and effective approach to solve the multi-mode resource-constrained project scheduling problem (MRCPSP). The MRCPSP is a well-known project scheduling NP-Hard optimization problem, in which there is a trade-off between the duration of each project activity and the amount of resources they require to be completed. The proposed algorithm generates an initial solution, performs a local search to obtain a local optimum, subsequently, for a certain number of iterations, makes a perturbation to that local optimum and performs a new local search on the perturbed solution. This whole process then restarts with a different initial solution for a certain number of restarts. The algorithm was tested on benchmark instances of projects with 30, 50 and 100 activities from well-known libraries. The obtained results were compared to recent benchmark results from the literature. The proposed algorithm outperforms other solution methods found in related literature for the largest tested instances (100 activities), while for smaller instances it shows to be quite competitive, in terms of the average deviation against known lower bounds.     

A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem

In this paper, a hybrid estimation of distribution algorithm (HEDA) is proposed to solve the resource-constrained project scheduling problem (RCPSP). In the HEDA, the individuals are encoded based on the extended active list (EAL) and decoded by serial schedule generation scheme (SGS), and a novel probability model updating mechanism is proposed for well sampling the promising searching region. To further improve the searching quality, a Forward-Backward iteration (FBI) and a permutation based local search method (PBLS) are incorporated into the EDA based search to enhance the exploitation ability. Simulation results based on benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed HEDA.