A classification of predictive-reactive project scheduling procedures

The vast majority of the project scheduling research efforts over the past several years have concentrated on the development of workable predictive baseline schedules, assuming complete information and a static and deterministic environment. During execution, however, a project may be subject to numerous schedule disruptions. Proactive-reactive project scheduling procedures try to cope with these disruptions through the combination of a proactive scheduling procedure for generating predictive baseline schedules that are hopefully robust in that they incorporate safety time to absorb anticipated disruptions with a reactive procedure that is invoked when a schedule breakage occurs during project execution. In this paper we discuss the results obtained by a large experimental design set up to evaluate several predictive-reactive resource-constrained project scheduling procedures under the composite objective of maximizing both the schedule stability and the timely project completion probability.     

考虑资源置信度的跨企业项目鲁棒性调度算法

资源不确定性高和调度鲁棒性要求高是跨企业项目调度问题的重要特征,本文采用资源置信度度量资源的不确定性,建立了考虑资源置信度约束的跨企业项目鲁棒性优化调度模型,设计了路径重连求解算法.算法以路径重连机制搜索解空间,以嵌入 的启发式时间缓冲插入算法快速生成鲁棒性调度,并可通过局部增强搜索算法进一步优化调度的鲁棒性.本文应用项目调度标准问题 库PSPLIB中大量问题实例进行了仿真实验,同两个当前具有代表性的鲁棒性项目调度算法进行了比较,实验结果表明了文中算法的有 效性与优势.     

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.     

Reactive scheduling in the multi-mode RCPSP

The multi-mode resource-constrained project scheduling problem (MRCPSP) involves the determination of a baseline schedule of the project activities, which can be executed in multiple modes, satisfying the precedence relations and resource constraints while minimizing the project duration. During the execution of the project, the baseline schedule may become infeasible due to activity duration and resource disruptions. We propose and evaluate a number of dedicated exact reactive scheduling procedures as well as a tabu search heuristic for repairing a disrupted schedule, under the assumption that no activity can be started before its baseline starting time. We report on promising computational results obtained on a set of benchmark problems.     

Heuristic procedures for reactive project scheduling

This paper describes new heuristic reactive project scheduling procedures that may be used to repair resource-constrained project baseline schedules that suffer from multiple activity duration disruptions during project execution. The objective is to minimize the deviations between the baseline schedule and the schedule that is actually realized.We discuss computational results obtained with priority-rule based schedule generation schemes, a sampling approach and a weighted-earliness tardiness heuristic on a set of randomly generated project instances.     

(DP)SM: A dynamic approach to resouce constraint project scheduling

The purpose of this paper is twofold, first to introduce and evaluate a dynamic priority scheduling model developed in this research for solving the resource constraint project scheduling problem, second to introduce an improvement made upon the first model by cross breeding Dynamic Programming with the Dynamic Priority Scheduling Method (DPSM). The second model called Dynamic Priority Dynamic Programming Scheduling Method [(DP)²SM] aims at optimising the staged resource allocation decisions in DPSM. DPSM divides a project into phases (cycles) the length of which depend on the duration of the project and the period of clock cycle selected. The scheduling process starts by allocating resources to the first phase/cycle using a variety of policies, then the best schedule is selected based on an objective function. The process continues till all the activities are scheduled. In DPSM the interaction between phases is ignored while the decisions of each phase or cycle will affect all the remaining phases. Using (DP)² SM it may be possible to improve the quality of a schedule and reduce the duration of a project by optimising the overall project schedule.     

柔性工时约束下项目调度及其蚁群算法

针对软件工程项目调度问题,在考虑加班工时的情况下,提出了柔性工时约束下项目调度问题的数学模型,并设计了相应的蚁群算法。模型对项目人力资源的特殊性进行了分析,指出项目人力资源是一种特殊的可更新资源,在允许加班的情况下,人力资源构成特殊的柔性工时约束。针对所设计的数学模型,在并行项目进度生成机制基础上设计了蚁群算法,并通过算例进行验证与分析。     

The development of a university sports complex: A project management application

The development of a university sports complex requires an integrated planning, scheduling and management approach, a requirement which is underscored by the desired to overlap design and construction activities in order to complete the facility on an accelerated schedule. The analysis of the project utilizes project management techniques: development of network models, identification of critical paths, and scheduling, cost control and resource allocation considerations. The use of computerized project planning and control tools provides flexibility and enables easy modification of the plans.     

MRCPSP的一种精确算法

着眼于多模式资源受限项目调度方法,其特色在于,针对项目中每个任务的工期不仅取决于自身的执行模式,而且决于该工工时间的一般情形,同时考虑每个任务对可更新（再生）资源需求呈任意分布、可更新（再生）资源的最大供给量随时间而变化的一般情况,作为对前人研究成果的进一步推广,本文在经典单模式DH分枝定界算法的基础上,利用事件驱动的时间增量方式,成功地获得了这种最一般的项目调度问题的最优解。     

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.     

时间管理在软件项目中的应用

针对当今软件项目中普遍出现的工期拖延、进度失控问题,介绍了时间管理的基本概念,接着从活动定义、活动排序、活动工期估算、进度安排、进度控制几个方面介绍了时间管理的过程。     

RCPSP中现金流优化问题的HGA方法

针对网络进度计划中财务方面对项目管理的影响 ,研究资源受限项目调度问题 (RCPSP)中网络现金流的优化问题。提出以网络净现值最大作为网络现金流优化的目标 ,建立了带有贴现率的非线性整数规划模型 ,采用遗传算法与模拟退火算法相结合的混合式遗传算法进行求解。仿真实例表明了方法的合理性和有效性。     

航空型号生产项目集成进度控制方法

针对航空型号生产项目的特点,提出了一种综合项目工期、成本及质量等多目标的集成进度控制方法。该方法中,以集成进度控制模型为理论基础,采用M-BOM作为计划制定的基本数据源,结合WBS与分级网络计划技术产生多目标集成进度计划;运用EVM思想结合监控过程构建集成进度监控的具体方法。最后,使用自主开发的软件系统,分析了某型飞机生产项目的实例,验证了方法的有效性。     

不确定资源约束下项目鲁棒性调度算法*

在跨企业项目中,由于资源可用时间具有不确定性,从而使得项目计划具有易变性。针对这一问题,首先采用模糊集对项目的不精确时间参数和资源不确定性进行了表示,并在同时考虑调度的质量鲁棒性和解的鲁棒性情况下,定义了调度的鲁棒性度量,进而开发了遗传算法来求解不确定资源约束下的项目鲁棒性调度问题。最后,给出了应用实例,并通过仿真分析说明算法的有效性。该算法已被应用到跨企业项目管理系统中,获得了良好的效果。     

A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations

The purpose of this research is to develop a new procedure for generating a proactive baseline schedule for the resource-constrained project scheduling problem. The main advantage of this new procedure is that it is completely independent of the reactive policy applied. This contrasts with the traditional methods that assume a predefined reactive policy. First, we define a new robustness measure, then we introduce a branch-and-cut method for solving a sample average approximation of our original problem. In a computational experiment, we show that our procedure outperforms two other published methods, assuming different robustness measures.     

PSO based approach for scheduling NPD projects including overlapping process

The efficient scheduling of the new product development (NPD) projects is important to reduce the required development time, and to offer the new product faster. Activity overlapping is commonly regarded as the most promising strategy to reduce product development times. However, overlapping must be well-planned by weighting the gain from the activity overlapping against the additional time for rework. The objective of this research was to develop a resource constrained scheduling methodology for NPD projects considering overlapping of activity couples. A particle swarm optimization based approach is used to schedule NPD projects that include overlapping process. The proposed PSO method is developed into a user friendly system so that the practitioners can utilize it. A real-life example of a product development project taken from the literature is used to show the efficiency of the software.     

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

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

Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach

Project scheduling under uncertainty is a challenging field of research that has attracted increasing attention. While most existing studies only consider the single-mode project scheduling problem under uncertainty, this paper aims to deal with a more realistic model called the stochastic multi-mode resource constrained project scheduling problem with discounted cash flows (S-MRCPSPDCF). In the model, activity durations and costs are given by random variables. The objective is to find an optimal baseline schedule so that the expected net present value (NPV) of cash flows is maximized. To solve the problem, an ant colony system (ACS) based approach is designed. The algorithm dispatches a group of ants to build baseline schedules iteratively using pheromones and an expected discounted cost (EDC) heuristic. Since it is impossible to evaluate the expected NPV directly due to the presence of random variables, the algorithm adopts the Monte Carlo (MC) simulation technique. As the ACS algorithm only uses the best-so-far solution to update pheromone values, it is found that a rough simulation with a small number of random scenarios is enough for evaluation. Thus the computational cost is reduced. Experimental results on 33 instances demonstrate the effectiveness of the proposed model and the ACS approach.     

Setup times and fast tracking in resource-constrained project scheduling

Resource-constrained project scheduling with activity pre-emption assumes that activities are allowed to be interrupted and restarted later in the schedule at no extra cost. In the current paper, we extend this pre-emptive scheduling problem with setup times between activity interruptions and the possibility to schedule pre-emptive sub-parts of activities in parallel.

The contribution of the paper is twofold. First, we briefly show that an efficient exact branch-and-bound procedure from the literature to solve the resource-constrained project scheduling problem can be easily adapted to cope with our problem extensions. Second, we extensively test the impact of these pre-emptive extensions to the quality of the schedule from a makespan point-of-view.     

带流水作业工程项目调度问题的遗传算法

介绍了带流水作业的工程项目调度问题，这是项目网络中带有流水作业子网络的项目调度问题。它不仅带有常规的时序和资源约束，还带有流水作业所带来的特殊约束。首先给出了带流水作业工程项目调度问题的描述；进而提出一种解决该问题的遗传算法。该算法引入了基于项目划分的编码方式，将个体划分为流水基因段和非流水基因段，并分别进行遗传操作。最后对提出的算法进行了数值计算验证，结果表明了算法的有效性。