共查询到20条相似文献,搜索用时 31 毫秒
1.
《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. 相似文献
2.
Lucio Bianco Massimiliano Caramia 《4OR: A Quarterly Journal of Operations Research》2011,9(4):371-389
In this paper we study the Resource Constrained Project Scheduling Problem (RCPSP) with “Feeding Precedence” (FP) constraints
and minimum makespan objective. This problem typically arises in production planning environment, like make-to-order manufacturing,
where the effort associated with the execution of an activity is not univocally related to its duration percentage and the
traditional finish-to-start precedence constraints or the generalized precedence relations cannot completely represent the
overlapping among activities. In this context, we need to introduce in the RCPSP the FP constraints. For this problem we propose
a new mathematical formulation and define a lower bound based on the Lagrangian relaxation of the resource constraints. A
computational experimentation on randomly generated instances of sizes of up to 100 activities shows a better performance
of this lower bound when compared to other lower bounds. Moreover, for the optimally solved instances, its value is very close
to the optimal one. Furthermore, in order to show the effectiveness of the proposed lower bound on large instances for which
the optimal solution is known, we adapted our approach to solve the benchmarks of the basic RCPSP from the PSLIB with 120
activities. 相似文献
3.
Vicente Valls Francisco Ballestín Sacramento Quintanilla 《European Journal of Operational Research》2008
In this paper we propose a Hybrid Genetic Algorithm (HGA) for the Resource-Constrained Project Scheduling Problem (RCPSP). HGA introduces several changes in the GA paradigm: a crossover operator specific for the RCPSP; a local improvement operator that is applied to all generated schedules; a new way to select the parents to be combined; and a two-phase strategy by which the second phase re-starts the evolution from a neighbour’s population of the best schedule found in the first phase. The computational results show that HGA is a fast and high quality algorithm that outperforms all state-of-the-art algorithms for the RCPSP known by the authors of this paper for the instance sets j60 and j120. And that it is competitive with other state-of-the-art heuristics for the instance set j30. 相似文献
4.
5.
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. 相似文献
6.
7.
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. 相似文献
8.
A “pure” Constraint Programming approach for the Resource-Constrained Project Scheduling Problem (RCPSP) is presented. Our
basic idea was to substitute the resource constraints by a set of “sub-constraints” generated as needed. Each of these sub-constraints
corresponds to a set of tasks that cannot be executed together without violating one of the resource constraints. A filtering
algorithm for these sub-constraints has been developed. When applied to the initial resource constraints together with known
filtering algorithms, this new filtering algorithm provides very good numerical results. 相似文献
9.
近年来 ,大型项目特别是大型工程项目存在如下的发展趋势 :1 )项目规模越来越大 ;2 )项目的复杂程度不断增加 ;3 )项目必须由多方合作才能完成 .本文针对上述特点 ,提出了基于多 Agent系统 (MAS:Multi-Agent Systems)解决资源约束条件下的项目调度问题 (RCPSP:Resource Constrained ProjectScheduling Problems)的方法 ,并通过实例项目对所提出的算法进行了验证 . 相似文献
10.
11.
《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. 相似文献
12.
本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。 相似文献
13.
Several efficient lower bounds and time-bound adjustment methods for the resource constrained project scheduling problem (RCPSP) have recently been proposed. Some of them are based on redundant resources. In this paper we define redundant functions which are very useful for computing redundant resources. We also describe an algorithm for computing all maximal redundant functions. Once all these redundant functions have been determined, we have to identify those that are useful for bounding. Surprisingly, their number is reasonable even for large resource capacities, so a representative subset of them can be tabulated to be used efficiently. Computational results on classical RCPSP instances confirm their usefulness. 相似文献
14.
This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known
resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum
start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an
acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have
been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance
rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30
and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior
performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP. 相似文献
15.
Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times 总被引:6,自引:0,他引:6
In this work a new heuristic solution technique for the Resource-Constrained Project Scheduling Problem (RCPSP) is proposed. This technique is a hybrid multi-pass method that combines random sampling procedures with a backward–forward method. The impact of each component of the algorithm is evaluated through a step-wise computational analysis which in addition permits the value of their parameters to be specified. Furthermore, the performance of the new technique is evaluated against the best currently available heuristics using a well known set of instances. The results obtained point out that the new technique greatly outperforms both the heuristics and metaheuristics currently available for the RCPSP being thus competitive with the best heuristic solution techniques for this problem. 相似文献
16.
Directional distance functions provide very flexible tools for investigating the performance of Decision Making Units (DMUs). Their flexibility relies on their ability to handle undesirable outputs and to account for non-discretionary inputs and/or outputs by fixing zero values in some elements of the directional vector. and indicate how the statistical properties of Farrell–Debreu type of radial efficiency measures can be transferred to directional distances. Moreover, robust versions of these distances are also available, for conditional and unconditional measures. B?din, Daraio, and Simar (2012) have shown how conditional radial distances are useful to investigate the effect of environmental factors on the production process. In this paper we develop the operational aspects for computing conditional and unconditional directional distances and their robust versions, in particular when some of the elements of the directional vector are fixed at zero. After that, we show how the approach of B?din et al. (2012) can be adapted in a directional distance framework, including bandwidth selection and two-stage regression of conditional efficiency scores. Finally, we suggest a procedure, based on bootstrap techniques, for testing the significance of environmental factors on directional efficiency scores. The procedure is illustrated through simulated and real data. 相似文献
17.
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. 相似文献
18.
Lucio Bianco Massimiliano Caramia 《4OR: A Quarterly Journal of Operations Research》2012,10(4):361-377
In this paper we study an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) with minimum makespan objective by introducing a special type of precedence constraints called “Feeding Precedences” (FP). To the best of our knowledge no exact algorithm exists for this problem. Exploiting the lower bound and the mathematical formulation proposed in Bianco and Caramia (4OR 9(4):371–389 2011) for the RCPSP with FP, in this paper we propose an exact algorithm based on branch and bound rules. A computational experimentation on randomly generated instances and a comparison with the results achieved by a commercial solver, show that the proposed approach is able to behave satisfactorily. 相似文献
19.
In this paper we present an application of project scheduling concepts and solution procedures for the solution of a complex problem that comes up in the daily management of many company Service Centres. The real problem has been modelled as a multi-mode resource-constrained project scheduling problem with pre-emption, time and work generalised precedence relationships with minimal and maximal time lags between the tasks and due dates. We present a complete study of work GPRs which includes proper definitions, a new notation and all possible conversions amongst them. Computational results that show the efficiency of the proposed hybrid genetic algorithm and the advantages of allowing pre-emption are also presented. 相似文献