Multimode time-cost-robustness trade-off project scheduling problem under uncertainty

The time/cost trade-off problem is a well-known project scheduling problem that has been extensively studied. In recent years, many researchers have begun to focus on project scheduling problems under uncertainty to cope with uncertain factors, such as resource idleness, high inventory, and missing deadlines. To reduce the disturbance from uncertain factors, the aim of robust scheduling is to generate schedules with time buffers or resource buffers, which are capped by project makespan and project cost. This paper addresses a time-cost-robustness trade-off project scheduling problem with multiple activity execution modes under uncertainty. A multiobjective optimization model with three objectives (makespan minimization, cost minimization, and robustness maximization) is constructed and three propositions are proposed. An epsilon-constraint method-based genetic algorithm along with three improvement measures is designed to solve this NP-hard problem and to develop Pareto schedule sets, and a large-scale computational experiment on a randomly generated dataset is performed to validate the effectiveness of the proposed algorithm and the improvement measures. The final sensitivity analysis of three key parameters shows their distinctive influences on the three objectives, according to which several suggestions are given to project managers on the effective measures to improve the three objectives.

     

Integrated project operations and personnel scheduling with multiple labour classes

The main theme of this paper is improving project schedules by integrating the scheduling of project jobs and labour resources. An ILP model is presented of the integrated project operations and personnel scheduling problem with multiple labour categories. Traditionally, this problem is solved in two steps: first, operations are scheduled by solving the resource-constrained project scheduling problem; then, labour categories are scheduled by solving the personnel days-off scheduling problem. The proposed model combines the two stages into an integrated problem, which is solved in one step. Using 48 test problems, the two methods were compared in terms of total cost, labour cost and scheduling efficiency. The results clearly indicate that the integrated model outperforms the traditional two-step method.     

随机抽样算法在多项目调度中的应用

针对资源约束下的多项目调度问题,扩展了单项目进度生产机制,并在此基础上设计了多项目调度的随机抽样算法。通过对比分析,说明不同的任务优先规则对随机抽样算法具有不同的影响,其中采用MINSLK等优先规则的随机抽样算法能够有效地缩短项目平均工期。与其他多项目调度启发式算法的比较和统计检验,说明随机抽样算法显著优于这些常用的启发式算法。     

随机多模式资源受限项目调度

项目调度是实现项目资源优化配置的重要手段。项目执行时往往面临大量不确定因素,并呈现出典型的多模式特性,给项目调度带来了很大挑战。鉴于此,本文研究活动工期不确定条件下的多模式资源受限项目调度问题,建立了该问题的马尔科夫决策过程模型。为了高效求解上述模型,设计了基于Rollout的近似动态规划算法。该算法可以在项目执行过程中根据最新的项目状态动态给出调度方案,从而有效优化项目期望工期。在所提算法中,利用“活动—模式”列表与并行调度机制相结合的启发式算法构建基准策略,并设计了基于离散时间马尔科夫链的动态仿真,以进一步提升算法性能。基于公开的项目调度问题库PSPLIB,通过大规模计算实验分析了本文算法的性能,探讨了多种因素对调度效果的影响。     

Effects of Erroneous Estimation of Activity Durations on Scheduling and Dispatching a Single Project*

This research examines the effects of erroneous estimation of activity durations on two different approaches for executing a resource-constrained project. The two approaches are scheduling and dispatching. This research is conducted in two phases. Phase one examines the performance of scheduling and dispatching rules in a variety of project environments. These project environments are categorized by three different factors, namely, the order strength of the precedence relationship, the level of resource availability and the size of errors in estimating the activity durations. The results show that scheduling generally produces a shorter project completion time than the heuristic dispatching rules. The results also indicate that project environment affects only the relative performance differences of the scheduling and dispatching rules but not their ranking. Phase two examines the effect of rescheduling. The results show that frequent rescheduling improves the project completion time, while the timing of rescheduling has little impact on the improvement in the project completion time. The results also identify the project environments where rescheduling is beneficial.     

资源受限下平行工序顺序对优化的0-1规划模型

资源受限是工程项目时刻都可能面对的挑战。由于资源限制,需要将原项目计划中相互之间无优先关系的平行工序调整为顺序工序。平行工序顺序化可导致项目工期延迟,因此需考虑如何使项目工期延迟最小。该平行工序顺序优化问题是项目调度问题,也是排列组合问题,通常难度很大,包括一些NP-hard问题。本文主要研究该问题的一类典型子问题——平行工序顺序对优化,即如何将项目中某2n个平行工序调整为n个顺序工序对,并且对项目工期的影响最小。该问题的总方案数可达到（2n）!/n!。本文借助工序网络（如CPM网络）,运用简单的时间参数量化了平行工序顺序化对项目工期的影响,进而降低问题的求解难度,建立了纯0-1规划模型。实验验证了该模型的求解效率,求解100个平行工序规模的问题平均耗时0.2605秒,而求解500个平行工序规模的问题平均耗时10.66秒。     

The project coordinator's problem

A project coordinator has a set of activities with known durations and values which are available for scheduling within a given horizon. There may be both precedence and corequisite restrictions (two activities are corequisites if scheduling one implies the other must be scheduled). The project coordinator's problem is to select the activities to be scheduled, and their start times, so as to maximize the net value of the project when there is no penalty for failing to schedule an activity. An efficient solution procedure is developed and illustrated and several generalizations are discussed.     

基于资源流网络优化的Max-npv项目调度

活动拖期通过资源流网络的传递会严重影响项目的净现值收益。针对该问题，本文首先在确定性环境下采用模拟退火算法(SA)构建了Max-NPV(Maximize the Net Present Value)非鲁棒性基准调度计划，然后考虑到活动工期的不确定性，设计了MEPC(Minimize Expected Penalty Cost)资源流网络优化算法，通过鲁棒性资源分配实现净现值期望惩罚成本最小化。大规模仿真对比实验结果表明，在活动工期低、中、高三种不确定性程度下，相对于采用随机资源分配算法(SA+RRAS)构建的非鲁棒性调度计划，SA+MEPC算法构建的鲁棒性调度计划在项目净现值实际收益、调度计划的“解”鲁棒性和“质”鲁棒性三个方面都取得了更好的结果，并且应对活动拖期风险的能力也更强。     

考虑作业空间干涉的工程项目时间-成本均衡优化研究

工程现场的空间资源是制约工程活动开展的重要影响因素。本文研究考虑空间干涉的工程调度优化问题,定义作业空间干涉的度量方式和作业效率函数,建立工程调度的工期-成本双目标优化模型。针对问题特征设计相对延迟编码方式和解码机制,采用NSGA-II算法求解模型。以某工程案例为研究对象,通过与传统方法对比实验验证了模型和算法的有效性,接着分析了算法的最大延迟时间参数对算法性能的影响。实验结果表明,本文提出的模型和算法能有效提升工程进度和成本目标。     

基于拍卖机制的资源转移时间型动态分布式多项目调度

实践中,企业并行实施地域上分散的多个项目时,资源在各子项目之间的转移时间是影响多项目整体进度的关键因素,同时在动态多项目环境下,新项目不断到达且到达时间不可预知使得制定多项目调度计划遭遇更大困难。本文在动态环境下对资源转移时间型分布式多项目调度问题进行建模和求解,基于多代理系统建立分布式多项目调度问题的动态模型,并将拍卖理论引入其中,设计一种基于时间窗拍卖机制的分布式多代理系统(DMAS/ATW),在动态环境和资源转移时间约束下为多项目配置全局资源。通过一个具体的分布式多项目示例详细分析DMAS/ATW算法的动态调度过程,并基于MPSPLIB中的分布式多项目算例开展数值实验。实验结果表明：无资源转移时间约束时,DMAS/ATW算法求得的平均项目延迟同比相关文献中的DMAS/RIA算法最多减少42%,平均减少26%;有资源转移时间约束时,DMAS/ATW算法对1/3算例集的求解结果优于DMAS/RIA算法在无资源转移时间约束时的结果,验证了本文DMAS/ATW算法求解效果的优异性。对算例规模和全局资源利用系数的实验分析还表明,DMAS/ATW算法对不同规模和资源约束紧张程度的算例都具有良好的适应性。     

具有时间转换约束的离散时间-费用权衡问题研究

离散时间-费用权衡问题(DTCTP)是项目进度中研究最多的双目标优化问题,它通常以三种形式出现:(1)P1:截止日期问题,在项目截止日期约束下使完成项目的总费用最小;(2)P2:预算问题,在费用预算约束下使项目工期最短;(3)P3:工期-费用曲线问题,找出全部有效的工期-费用模式集合。然而,考虑时间转换约束(TSC)的DTCTP却很少被关注。本文首先介绍时间转换约束的问题描述,在此基础上,建立具有活动类型时间转换约束的DTCTPTSC-P2模型;从实用角度出发,设计求解模型的遗传算法;最后,用一个真实项目实例说明模型的合理性和算法的有效性,对算例分析结果表明,该模型对承包商更准确地进行项目工期-费用权衡决策具有借鉴意义。     

USING A LATE-START RESOURCE-CONSTRAINED PROJECT SCHEDULE TO IMPROVE PROJECT NET PRESENT VALUE*

Although literature on the achievement of monetary objectives in a resource-constrained project environment is limited, the maximization of project net present value (NPV) is an important criterion of project success. This paper presents a procedure for developing a late-start resource-constrained project schedule using the critical path method-material requirements planning. Using an extensive set of problems from the literature, we show that this procedure yields a higher NPV and lower average duration than schedules derived with heuristics that schedule each activity as early as possible. In addition, while the late-start schedule on average was significantly longer than the optimal-duration resource-constrained schedule, no significant difference occurred in the average NPVs of the two scheduling methods.     

A comparison of dispatching rules for executing a resource-constrained project with estimated activity durations

This research examines the performance of 13 dispatching rules for executing a resource-constrained project whose estimated activity durations may differ from the actual activity durations. The dispatching rules are tested in environments characterized by three factors, namely, the order strength of the precedence relationship, the level of resource availability and the level of estimation errors in the activity durations. The results show that project environment affects only the performance differences but not the grouping of the better dispatching rules. The greatest number of successors, rank positional weight, greatest cumulative resource requirement and minimum activity slack dispatching rules consistently perform better than the other dispatching rules, unaffected by the accuracy of the estimated activity durations. This finding validates the results of many past studies in the deterministic project environment for choosing the right dispatching rule for both projects with and without well-estimated activity durations.     

基于鲁棒性的关键链二次资源冲突消除策略

以关键链方法中的二次资源冲突困境为切入点,从鲁棒调度优化角度提出一种解决策略.首先,采用定量化建模对问题进行数学描述和表达,剖析插入输入缓冲引起二次资源冲突的原理,进而采用场景分析法从复杂的冲突表象中分解出四种基本的冲突场景构成要素.其次,基于鲁棒调度优化理论,探究各种冲突子问题的有效对策并归类,据此开发出一种消除二次资源冲突的局部重调度启发式协调策略;根据策略设计基于两次调度进程和两类缓冲动态消耗的鲁棒性指标,采用鲁棒性关键链项目调度问题输出鲁棒性最大的调度方案.再次,设计仿真程序和三个测试指标:项目实际按期完工率、活动开始时间偏差绝对值之和及偏差绝对值的方差;基于ProGen随机地生成测试算例集合进行数值实验.结果发现,以鲁棒性调度方案为依据安排项目的实施过程,三个统计指标值都优于以传统关键链调度方案为依据时相对应的指标值.结论表明:基于鲁棒调度优化的二次资源冲突消除策略及设计的关键链鲁棒性指标在项目实施中具有较好的稳定性效果.     

Staffing and scheduling flexible call centers by two-stage robust optimization

We study the shift scheduling problem in a multi-shift, flexible call center. Differently from previous approaches, the staffing levels ensuring the desired quality of service are considered uncertain, leading to a two-stage robust integer program with right-hand-side uncertainty. We show that, in our setting, modeling the correlation of the demands in consecutive time slots is easier than in other staffing approaches. The complexity issues of a Benders type reformulation are investigated and a branch-and-cut algorithm is devised. The approach can efficiently solve real-world problems from an Italian call center and effectively support managers decisions. In fact, we show that robust shifts have very similar costs to those evaluated by the traditional (deterministic) method while ensuring a higher level of protection against uncertainty.     

基于两阶段资源分配协调机制的分布式多项目随机调度

企业趋向于多项目共享全局资源的分布式协同管理。但在多项目实际执行时，全局资源可用量往往由于外部环境的动态变化而存在不确定性，活动中断、资源浪费等现象频发，项目管理变得愈加复杂。本文将不确定的全局资源可用量建模为随机变量，设计两阶段资源分配协调机制，在预分配阶段，考虑项目允许的最大活动中断次数约束，建立各项目调度的马尔可夫动态决策过程模型；预分配结束后，基于活动重要度依次对剩余全局资源进行协调再分配，以提高资源利用率并减少平均项目延期。设计基于全局资源协调分配的Rollout近似动态规划算法进行求解。开展问题库算例实验研究与案例分析，验证协调机制与求解算法的性能；同时，探讨并分析不确定参数对目标结果的影响。     

An exchange heuristic for resource constrained scheduling with consideration given to opportunities for parallel processing

This paper describes a heuristic which produces efficient makespans for resource-constrained scheduling problems with parallel processing capabilities. This heuristic was initially developed for the scheduling of army battalion training exercises. The original heuristic has also been successfully applied to solve problems in project scheduling with limited resources, generalized job shop scheduling, and resource-constrained scheduling. The exchange heuristic requires an initial feasible solution upon which it improves the makespan by efficiently and systematically shuffling activities while maintaining feasibility. The method has recently been modified twice, termed the intelligent version and naive version, respectively, such that its ability to reduce the initial makespan is enhanced. In this study     

考虑不确定履约率的全局鲁棒供应组合决策研究

生产和采购的全球化为供应链企业带来了更多的复杂性与不确定性。收集全面信息和使用有效的工具是控制决策风险、减少不确定性危害的有效途径。在供应商选择与订单分配管理中,供应商履约率是影响企业供应组合决策的主要因素,如何对其进行定量刻画是迫切需要解决的问题。已有的研究通常是由期望方法或鲁棒方法来刻画履约率。然而,期望履约率法往往忽略了履约率的波动性,从而造成需求损失;而鲁棒履约率法通常存在过于保守、退化过于迅速两个缺点,使企业承担不必要的成本。本文研究供应商选择与订单分配决策问题,使用全局鲁棒优化的两个不确定集合来刻画供应商履约率,同时给出了这一问题的确定性鲁棒表达和一种多项式时间求解算法。最后,通过仿真实验证实本文的全局鲁棒优化模型可克服期望模型和一般鲁棒模型的缺点。本文提出的算法能有效求解本文全局鲁棒优化等价确定性问题,为企业的供应商选择和订单分配决策提供更为灵活精确的辅助工具。     

基于图的广度搜索的进度生成机制

启发式算法是解决资源受限的项目调度问题的经典方法之一，通常用来生成元启发算法初始解，传统的串行（SSGS）和并行（PSGS）是生成项目调度方案的经典机制，本文基于图的广度优先搜索算法，提出了一种考虑任务节点位置因素的广度生成机制（BSSGS），并验证了算法的效果。借鉴广度搜索算法定义进度生成机制中的当前任务集合C、候选任务集合D以及阶段变量g等，对各任务节点进行层次划分并定义任务调度秩序；结合优先规则选择候选任务j^*并进行资源R_k（t）调度更新，进而生成完整的调度方案；案例分析表明新机制在满足优先规则和资源约束的同时兼顾了任务节点在网络中位置因素，拥有对于局部复杂网络不回避，对关键节点及时调度等明显优势；选择PSPLIB中算例，在不同优先规则下对新机制进行了测试，测试结果表明新的进度生成机制在LPT、SPT、MTS和MIS等优先规则下，在平均最短工期、平均资源利用率及最优调度方案率等方面优于串行和并行进度生成机制，且算法时间复杂度与传统机制相比并未增加，仍为O（J²，K）。     

一种策略层项目计划的双目标优化方法

针对产品开发项目管理的实际情况,对策略层计划优化方法进行研究。以工作包的工作量估算为基础,以资源投入水平和工期最小化为目标,考虑各种约束条件,提出一种策略层项目计划问题的混合整数规划问题模型。以非支配遗传算法NSGA-II为基础框架,设计了一种改进的双目标遗传算法。该算法针对问题的特点,提出了基于资源平滑的解码算法。参考NSGA-III的关键特征,对拥挤密度计算方法进行改进。通过企业实际项目案例,验证了算法的性能和所提出的策略层项目计划方法的有效性。