共查询到20条相似文献,搜索用时 31 毫秒
1.
A survey of variants and extensions of the resource-constrained project scheduling problem 总被引:3,自引:0,他引:3
The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts. 相似文献
2.
This paper reports on a new solution approach for the well-known multi-mode resource-constrained project scheduling problem (MRCPSP). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and non-renewable) resource feasible project schedule with a minimal makespan. The problem type is known to be NP-hard and has been solved using various exact as well as (meta-)heuristic procedures.The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using an efficient meta-heuristic procedure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean non-renewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the procedure can report similar or sometimes even better solutions than found by other procedures in literature, although it often requires a higher CPU time. 相似文献
3.
4.
在项目调度过程中,活动工期应根据项目截止工期以及资源供给情况进行合理设置,而在传统的资源受限项目调度问题(RCPSP)中,活动的工期往往是已知且固定的,这在一定程度上限制了项目调度的灵活性。多模式下的项目调度方式虽然弥补了这一缺点,但其提供的工期-资源组合种类固定且有限,并不一定能保证包含最优的工期-资源组合。本文将活动工期作为项目调度问题的决策变量,允许其在一定范围内取值。这种柔性工期调度方式虽然增加了项目调度难度,但提高了项目调度灵活性,同时可以起到压缩项目完工时间的作用。为验证柔性工期调度方式对项目工期和成本的影响,本文建立了工期-成本双目标权衡优化模型,设计了两阶段嵌套算法(NSGAⅡ-RS)对其求解,实验证明,柔性工期调度策略是一种鲁棒性较好的项目完工时间压缩策略。 相似文献
5.
6.
A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available. 相似文献
7.
M H Sebt Y Alipouri Y Alipouri 《The Journal of the Operational Research Society》2013,64(9):1327-1335
This paper presents an evolutionary programming (EP)-based approach to solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling, with minimization of project duration as the objective subject to precedence and resource constraints. The individual representation of EP for the problem is based on random keys. The serial generation scheme is used in the decoding scheme to generate the project plan. Experimental analyses are presented to investigate the performance of the proposed EP-based methodology, including comparison of the four variants of EP, namely, CEP, FEP, MCEP and IMCEP, with each other and GA to find the best variant of EP for the RCPSP, and comparison of this best variant of EP (MCEP) with other approaches using the J30 standard instances set in PSPLIB. The computational results validate the effectiveness of the proposed algorithm. 相似文献
8.
Mireille Palpant Christian Artigues Philippe Michelon 《Annals of Operations Research》2004,131(1-4):237-257
This paper presents the Local Search with SubProblem Exact Resolution (LSSPER) method based on large neighbourhood search for solving the resource-constrained project scheduling problem (RCPSP). At each step of the method, a subpart of the current solution is fixed while the other part defines a subproblem solved externally by a heuristic or an exact solution approach (using either constraint programming techniques or mathematical programming techniques). Hence, the method can be seen as a hybrid scheme. The key point of the method deals with the choice of the subproblem to be optimized. In this paper, we investigate the application of the method to the RCPSP. Several strategies for generating the subproblem are proposed. In order to evaluate these strategies, and, also, to compare the whole method with current state-of-the-art heuristics, extensive numerical experiments have been performed. The proposed method appears to be very efficient. 相似文献
9.
Time slack-based techniques for robust project scheduling subject to resource uncertainty 总被引:1,自引:0,他引:1
Olivier Lambrechts Erik Demeulemeester Willy Herroelen 《Annals of Operations Research》2011,186(1):443-464
The resource-constrained project scheduling problem (RCPSP) has been the subject of a great deal of research during the previous
decades. This is not surprising given the high practical relevance of this scheduling problem. Nevertheless, extensions are
needed to be able to cope with situations arising in practice such as multiple activity execution modes, activity duration
changes and resource breakdowns. In this paper we analytically determine the impact of unexpected resource breakdowns on activity
durations. Furthermore, using this information we develop an approach for inserting explicit idle time into the project schedule
in order to protect it as well as possible from disruptions caused by resource unavailabilities. This strategy will be compared
to a traditional simulation-based procedure and to a heuristic developed for the case of stochastic activity durations. 相似文献
10.
《European Journal of Operational Research》1998,111(1):152-174
We present an optimal solution procedure for the resource-constrained project scheduling problem (RCPSP) with generalized precedence relations (RCPSP-GPR) with the objective of minimizing the project makespan. The RCPSPGPR extends the RCPSP to arbitrary minimal and maximal time lags between the starting and completion times of activities. The proposed procedure is suited for solving a general class of project scheduling problems and allows for arbitrary precedence constraints, activity ready times and deadlines, multiple renewable resource constraints with time-varying resource requirements and availabilities, several types of permissible and mandatory activity overlaps and multiple projects. It can be extended to other regular and non-regular measures of performance. Essentially, the procedure is a depth-first branch-and-bound algorithm in which the nodes in the search tree represent the original project network extended with extra precedence relations to resolve a number of resource conflicts. These conflicts are resolved using the concept of minimal delaying modes, which is an extension of the notion of minimal delaying alternatives for the RCPSP. Several bounds and dominance rules are used to fathom large portions of the search tree. Extensive computational experience is reported. 相似文献
11.
本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。 相似文献
12.
《European Journal of Operational Research》2006,175(2):707-721
This study presents a hybrid metaheuristic ANGEL for the resource-constrained project scheduling problem (RCPSP). ANGEL combines ant colony optimization (ACO), genetic algorithm (GA) and local search strategy. The procedures of ANGEL are as follows. First, ACO searches the solution space and generates activity lists to provide the initial population for GA. Next, GA is executed and the pheromone set in ACO is updated when GA obtains a better solution. When GA terminates, ACO searches again by using a new pheromone set. ACO and GA search alternately and cooperatively in the solution space. This study also proposes an efficient local search procedure which is applied to yield a better solution when ACO or GA obtains a solution. A final search is applied upon the termination of ACO and GA. The experimental results of ANGEL on the standard sets of the project instances show that ANGEL is an effective method for solving the RCPSP. 相似文献
13.
《European Journal of Operational Research》2006,174(1):23-37
This paper considers heuristics for the well-known resource-constrained project scheduling problem (RCPSP). It provides an update of our survey which was published in 2000. We summarize and categorize a large number of heuristics that have recently been proposed in the literature. Most of these heuristics are then evaluated in a computational study and compared on the basis of our standardized experimental design. Based on the computational results we discuss features of good heuristics. The paper closes with some remarks on our test design and a summary of the recent developments in research on heuristics for the RCPSP. 相似文献
14.
15.
《European Journal of Operational Research》2005,165(2):375-386
The objective of this paper is to show that justification is a simple technique that can be easily incorporated in diverse algorithms for the resource-constrained project scheduling problem––improving the quality of the schedules generated without generally requiring more computing time. The results of incorporating this technique in 22 different algorithms are shown. Fifteen of the new algorithms that use double justification outperform seven of the best heuristic algorithms that do not use justification. The tests have been performed on the standard test set j120 for the RCPSP generated using ProGen. 相似文献
16.
Andrei Horbach 《Annals of Operations Research》2010,181(1):89-107
We formulate the resource-constrained project scheduling problem as a satisfiability problem and adapt a satisfiability solver
for the specific domain of the problem. Our solver is lightweight and shows good performance both in finding feasible solutions
and in proving lower bounds. Our numerical tests allowed us to close several benchmark instances of the RCPSP that have never
been closed before by proving tighter lower bounds and by finding better feasible solutions. Using our method we solve optimally
more instances of medium and large size from the benchmark library PSPLIB and do it faster compared to any other existing
solver. 相似文献
17.
《European Journal of Operational Research》1999,112(2):322-346
In this paper, two meta-strategies for computing lower bounds (for minimization problems) are described. Constructive (direct) methods directly calculate a bound value by relaxing a problem and solving this relaxation. Destructive improvement techniques restrict a problem by setting a maximal objective function value F and try to contradict (destruct) the feasibility of this reduced problem. In case of success, F or even F + 1 is a valid lower bound value. The fundamental properties and differences of both meta-strategies are explained by applying them to the well-known resource-constrained project scheduling problem (RCPSP). For this problem, only a few constructive bound arguments are available in the literature. We present a number of extensions and new methods as well as techniques for reducing problem data which can be exploited within the destructive improvement framework. Comprehensive numerical experiments show that the new constructive bound arguments clearly provide better bounds than the former ones and that further really significant improvements are obtained through an appropriate application of destructive improvement. 相似文献
18.
本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。 相似文献
19.
《European Journal of Operational Research》2006,169(2):638-653
In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics. 相似文献
20.
《European Journal of Operational Research》2003,144(2):348-365
The paper presents an exact procedure for a general resource-constrained project scheduling problem where multiple modes are available for the performance of the individual activities and minimum as well as maximum time lags between the different activities may be given. The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized. Project scheduling problems of this type occur, e.g. in process industries. The solution method is a depth-first search based branch-and-bound procedure. It makes use of a branching strategy where the branching rule is selected dynamically. The solution approach is an integration approach where the modes and start times are determined simultaneously. Within an experimental performance analysis this procedure is compared with existing solution procedures. 相似文献