不确定资源约束条件下的结构项目排序问题

本文主要建立了具有不确定资源约束条件下的结构项目排序问题的一个数学模型。不确定资源约束主要由固定项目工期、随机项目工期和模糊项目工期组成,其目标函数为项目的整个完工时间(极小)。利用机会约束的置信度(包括某些活动的重要度)和某些有效方法将原不确定问题转化为等价的确定性规划问题。最后我们给出了一个简单的二阶段算法及其数值结果。     

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 scheduling model 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.     

Buffer sizing approach with dependence assumption between activities in critical chain scheduling

The critical chain/buffer management (CC/BM) methodology, proposed by E.M. Goldratt [1997. Critical chain. New York: The North River Press], introduced the concept of buffers to protect the critical chain against the disruptions. The buffer sizes reflect the uncertainty in the estimation of project duration and affect the project scheduling performance. However, the most current buffer sizing approaches make the assumption that project activity durations are independent. In this paper, the effects of the dependence between activities on project duration performances are analysed, a method for determining buffer sizes with dependence assumption between activities is introduced. Specifically, two definitions reflecting dependence, which are the dependence degree and the dependence factor, are integrated into the formulation of buffer sizing approach. The suggested method is tested and compared with the methods with independence assumption, the root square error method, the adaptive procedure with resource tightness and the adaptive procedure with density. The results indicate that the methods with independence assumption may underestimate the buffer size when at least one of the two definitions is at a high level, while the suggested method can provide better protection in such circumstances.     

Stability and resource allocation in project planning

The majority of resource-constrained project scheduling efforts assume perfect information about the scheduling problem to be solved and a static deterministic environment within which the precomputed baseline schedule is executed. In reality, project activities are subject to considerable uncertainty, which generally leads to numerous schedule disruptions. In this paper, we present a resource allocation model that protects a given baseline schedule against activity duration variability. A branch-and-bound algorithm is developed that solves the proposed resource allocation problem. We report on computational results obtained on a set of benchmark problems.     

A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a mixed integer linear programming (MILP) formulation that solve a sample average approximation of the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. The computational results suggest that the proposed B&B procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.     

Hybridization of genetic algorithm and fully informed particle swarm for solving the multi-mode resource-constrained project scheduling problem

In this article, the genetic algorithm (GA) and fully informed particle swarm (FIPS) are hybridized for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. In the proposed hybrid genetic algorithm–fully informed particle swarm algorithm (HGFA), FIPS is a popular variant of the particle swarm optimization algorithm. A random key and the related mode list representation schemes are used as encoding schemes, and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. Furthermore, the existing mode improvement procedure in the literature is modified. The results show that the proposed mode improvement procedure remarkably improves the project makespan. Comparing the results of the proposed HGFA with other approaches using the well-known PSPLIB benchmark sets validates the effectiveness of the proposed algorithm to solve the MRCPSP.     

属性相关的关键链计划缓冲设置方法

考虑链中包含的工序数大小、工序执行时间不确定程度和开工柔性程度三个与具体项目相关的属性,研究关键链项目计划缓冲设置.以项目计划周期和完工保证率为评价目标,通过仿真实验方法评价属性对项目计划的影响.根据仿真实验结果分析.提出缓冲设置的改进方法.算例表明与切粘法和根方差法相比改进方法可显著改善项目计划性能.     

基于混沌差分进化粒子群算法的模糊资源受限项目调度问题

本文研究了工期模糊情况下的资源受限项目调度问题,采用一种基于区间数距离的模糊取最大运算比较模糊工期的大小,解决了以往研究中忽略的工期模糊情况下,项目关键路径可能会发生改变,相应地各活动的模糊调度时间以及项目的模糊最短工期也可能随之发生改变的问题。引入一种基于混沌和差分进化的混合粒子群优化算法,并对算法的惯性权重进行改进来求解上述问题。通过一个算例验证了所建立模型及提出方法的有效性。     

An iterated-local-search heuristic for the resource-constrained weighted earliness-tardiness project scheduling problem

This paper deals with the weighted earliness-tardiness resource-constrained project scheduling problem with minimum and maximum time lags (WET-RCPSP/max). The problem consists of scheduling the activities of a project subject to prescribed resource and temporal constraints such that the total weighted deviation of the activities' completion times from prescribed due dates is minimized. Key applications are planning of just-in-time production and reactive scheduling. For the (approximative) solution of the WET-RCPSP/max, we present a population-based iterated-local-search heuristic. We also report the results of an experimental performance analysis where this heuristic outperformed state-of-the-art methods.     

The discrete time/resource trade-off problem in project networks: a branch-and-bound approach

In many solution methods for resource-constrained project scheduling, it is assumed that both the duration of each activity and its resource requirements are known and fixed. In real-life projects, however, it often occurs that only one renewable bottleneck resource is available and that the activities have a total work content which indicates how much work (expressed in man-periods) has to be performed. The objective then is to schedule each activity in one of its possible execution modes, subject to the precedence and resource constraints, in order to minimize the project makespan. We present a branch-and-bound procedure and report computational results, obtained using a full factorial experiment on a randomly generated problem set.     

A robust scheduling for the multi-mode project scheduling problem with a given deadline under uncertainty of activity duration

The problem of this paper deals with the multi-mode project scheduling problem under uncertainty of activity duration where only the renewable resources are taken into account and a given deadline has to be met at the cost of recruiting additional resources. A heuristic algorithm is employed to solve this problem, and to maintain the robustness of the baseline schedule, the concept of critical chain project management (CCPM) is applied in which a new definition to resource buffer is considered. A simulation methodology is used to determine the size and location of resource buffers in the schedules in which three different buffer sizes and three different uncertainty levels are considered. Results and analysis of the simulation outcomes illustrate that resource buffers are useful and should be simulated by the CCPM schedules, as they help to decrease the total duration of the project during implementation and meet the deadline of the project with more assurance.     

基于资源限制的多目标网络计划优化模型

目前网络计划优化研究要么没有考虑资源限定的柔性,要么只是集中于单纯的工期优化或资源优化等单目标优化。本文针对传统网络计划建模资源限制缺少柔性、优化目标单一等问题进行了深入的研究。在柔性资源的限制下,为使得工程网络计划达到总体最优,考虑工程项目的工期、成本、项目净现值、资源的均衡等多个目标,建立其网络计划优化模型,并采用粒子群算法予以求解。根据拓扑排序算法生成满足时序约束的活动序列并计算活动的时间参数。对于产生资源冲突的活动,依照执行优先权解决冲突资源的执行顺序,更新时间参数。采用随机权重的方法,让粒子群算法种群的多个个体进行随机转化,从而保持解的多样性。采用国际上通用的Patterson问题库中benchmark算例对本文提出的方法进行验证。结果表明,与初始方案相比,优化后的方案分别在工期上缩减了20%,成本上缩减了11.17%,净现值增加了11.82%,资源均衡度减少了18.29%。由此可见,提出的基于粒子群算法的优化模型对资源限制下的网络计划中的工期、成本、净现值、资源均衡度等多个目标均实现了不同程度的优化。     

A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows

In this paper, we present a meta-heuristic algorithm for the resource-constrained project scheduling problem with discounted cash flows. We assume fixed payments associated with the execution of project activities and develop a heuristic optimisation procedure to maximise the net present value of a project subject to the precedence and renewable resource constraints. We investigate the use of a bi-directional generation scheme and a recursive forward/backward improvement method from literature and embed them in a meta-heuristic scatter search framework. We generate a large dataset of project instances under a controlled design and report detailed computational results. The solutions and project instances can be downloaded from a website in order to facilitate comparison with future research attempts.     

关键链的随机性及其在建筑工程项目进度中的应用

先采用CPM方法计算出项目的关键线路和工期,但是CPM方法没有考虑各种资源对施工的约束,往往与实际不符,而基于关键链方法,可以获取到工程施工过程中的资源约束下的关键链。实际上,施工过程中需要的各种资源又受到某些外界因素的影响,使得这些工序的完成呈现出一定的概率性。所以,本文将随机过程的思想和方法应用到最优关键链的获取中,最终找出最优的施工线路和施工工期。该方法对后续的工程施工具有重要的指导意义。     

Scheduling optimization of design stream line for production research and development projects

In a development project, efficient design stream line scheduling is difficult and important owing to large design imprecision and the differences in the skills and skill levels of employees. The relative skill levels of employees are denoted as fuzzy numbers. Multiple execution modes are generated by scheduling different employees for design tasks. An optimization model of a design stream line scheduling problem is proposed with the constraints of multiple executive modes, multi-skilled employees and precedence. The model considers the parallel design of multiple projects, different skills of employees, flexible multi-skilled employees and resource constraints. The objective function is to minimize the duration and tardiness of the project. Moreover, a two-dimensional particle swarm algorithm is used to find the optimal solution. To illustrate the validity of the proposed method, a case is examined in this article, and the results support the feasibility and effectiveness of the proposed model and algorithm.     

Resource–constrained project scheduling: a heuristic for the multi–mode case

This paper presents a heuristic solution procedure for a very general resource–constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi–pass priority–rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real–life size with 100 activities and up to 5 modes per activity.

---

---

Received: September 22, 2000 / Accepted: May 18, 2001     

Project scheduling with flexible resources: formulation and inequalities

In this paper, we study a variant of the resource-constrained project scheduling problem in which resources are flexible, i.e., each resource has several skills. Each activity in the project may need several resources for each required skill. We present a mixed-integer linear programming formulation for this problem. Several sets of additional inequalities are also proposed. Due to the fact that some of the above-mentioned inequalities require a valid upper bound to the problem, a heuristic procedure is proposed. Computational experience is reported based on randomly generated data, showing that for instances of reasonable size the proposed model enlarged with the additional inequalities can be solved efficiently.     

基于优先规则的模糊资源受限多项目调度

在分析国内外相关研究现状的基础上,结合资源受限多项目调度问题的特点,针对多项目中各个工序资源参数的不确定性,通过对工程项目工序资源需求量的模糊表示,建立了模糊资源受限多项目调度模型,并运用基于优先规则的启发式算法对所建立的模型进行调度计算,最后通过算例验证模型的有效性和可行性,以实现多项目资源的优化配置。     

A survey on the resource-constrained project scheduling problem

In this paper, research on the resource-constrained project scheduling problem is classified according to specified objectives and constraints. Each classified area is extensively surveyed, and special emphasis is given to trends in recent research. Specific papers involving nonrenewable resource constraints and time/cost-based objectives are discussed in detail because they present models that are close representations of real-world problems. The difficulty of solving such complex models by optimization techniques is noted. For the purposes of this survey, a set of 78 optimally solved test problems from the literature and a second set of 110 benchmark problems have been subjected to analysis with some well-known dispatching rules and a scheduling algorithm that consists of a decision-making process utilizing the problem constraints as a base of selection. The computational results are reported and discussed in the text. Constructive scheduling algorithms that are directly based on the problem constraints and whose performances are independent of problem characteristics are identified as a promising area for future research.     

Flexible job-shop scheduling problem under resource constraints

A flexible job-shop-scheduling problem is an extension of classical job-shop problems that permit an operation of each job to be processed by more than one machine. The research methodology is to assign operations to machines (assignment) and determine the processing order of jobs on machines (sequencing) such that the system objectives can be optimized. This problem can explore very well the common nature of many real manufacturing environments under resource constraints. A genetic algorithm-based approach is developed to solve the problem. Using the proposed approach, a resource-constrained operations–machines assignment problem and flexible job-shop scheduling problem can be solved iteratively. In this connection, the flexibility embedded in the flexible shop floor, which is important to today's manufacturers, can be quantified under different levels of resource availability.