不同支付方式下的多模式项目支付进度问题研究

本文首先明确了研究的假设条件并对多模式项目支付进度问题（MPPSP）进行了界定;随后从承包商和业主两个角度构建了MPPSP的基本优化模型;鉴于支付方式的不同,将基本优化模型扩展为基于进展、基于时间和基于费用的MPPSP优化模型;最后,通过对一个算例的计算分析,讨论了支付方式对最优支付进度安排及合同双方收益的影响.     

一种求解柔性资源约束前摄性项目调度问题的启发式算法

在不确定环境中,一个具有较高鲁棒性的进度计划可以保证项目的稳定实施。考虑到现实中资源可能具有多种技能,会对制定鲁棒性较高进度计划的过程产生影响,因此本文研究了柔性资源约束下前摄性项目调度优化问题。首先界定研究问题;然后从鲁棒性最大化的视角出发,构建了研究问题的优化模型,在对模型进行分析的基础上将其分解为经典鲁棒优化和资源技能分配两个子模型;随后设计了求解问题的基于削峰算法的启发式算法;最后用一个实际案例验证了算法有效性,并分析了关键参数对进度计划鲁棒性的影响,得到如下结论:项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而增大。     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

具有线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立.     

A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

软件项目支付进度问题研究

软件项目的复杂性和特点使得其支付进度问题较具特殊性。针对软件质量的差异性,对软件项目支付进度问题进行研究。以承包商净现值最大化为优化目标,构建了具有惩罚结构的支付进度优化模型,该模型反映了不同软件质量对承包商收益的影响;针对该问题的特点设计了启发式求解算法;最后通过一个算例对模型进行了验证。可为承包商在签订外包合同及外包实施中的策略提供决策依据。     

求解资源约束项目调度问题的启发式算法综述

本文综述了求解RCPSP的启发式算法.首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式算法的研究成果.此外,简要介绍除上述两大类启发式算法之外的其他几种启发式算法;最后,对全文进行总结,并指出该领域几个有希望的研究方向.     

基于不同奖惩机制项目支付进度优化:双重视角

奖惩机制会对合同双方的收益产生重大影响,本文基于承包商和业主的双重视角,对不同奖惩机制下项目支付进度优化问题进行了研究。首先对所研究问题进行界定,并分别基于承包商和业主视角构建了不同奖惩机制下的优化模型;基于模型的属性设计了模拟退火启发式算法;最后通过一个实例对比了承包商和业主在四种不同奖惩机制下收益的优化结果,并对其中的关键参数进行了敏感性分析。结果显示:不同的奖惩机制对承包商和业主的收益有较大影响;不同的奖惩强度也会影响承包商和业主的收益。通过对奖惩机制类型及强度的分析,可以为项目中奖惩机制的设置提供定量化决策支持。     

Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included.     

资源有限的加权总完工时间单机排序问题

本讨论资源有限的加权总工时间单机排序问题，对现在仍为OPEN问题1｜pj=bj-ajuj，∑uj≤U｜∑wjCj给出了一个有关最优解中最优资源分配的重要性质，并利用该性质分别给出了三种情况bj=b,wj=w,aj=a；bj=b,wj=w,uj=u；aj=a,wj=w,uj=u的最优算法。     

基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化

承包商的现金流动态均衡对不确定条件下项目的顺利实施有重要影响。作者研究基于随机活动工期的现金流动态均衡前摄性及反应性项目调度问题,目标是在随机活动工期条件下,为承包商生成现金流均衡基准进度,并根据执行过程中的实际情况,动态地对其进行反应性调整。首先,通过建立前摄性调度优化模型生成基准进度,并提出两个反应性调度策略对其进行调整。其次,为以上诸模型的求解设计了模拟退火和禁忌搜索相结合的混合算法tabu-SA。最后,针对前摄性调度模型,在随机生成的算例集合上对算法进行测试,并进行大规模仿真实验。研究结果可以为随机活动工期下承包商保持现金流动态均衡、确保项目顺利实施,提供定量化决策支持。     

基于随机活动工期的多模式现金流均衡项目调度优化

承包商在项目执行过程中的现金流均衡是保证项目成功的关键因素。本文研究基于随机活动工期的多模式现金流均衡项目调度问题,旨是在项目工期及鲁棒性阈值约束下合理安排活动执行模式与开始时间,实现承包商现金流均衡。本文通过构建整数规划优化模型对研究问题进行刻画,随后设计模拟退火算法进行求解,最后进行案例分析。结果表明:鲁棒性阈值虽然可以保证基准进度的稳定性,但是提高鲁棒性阈值水平反而不利于承包商的现金流均衡,该值过高时甚至得不到可行解。本文研究可为随机活动工期背景下承包商的现金流控制提供定量化决策支持。     

带有资源柔性约束的max-NPV分布式多项目调度问题

现有的分布式资源约束多项目调度问题研究中,假定全局资源限量在多项目工期内不可突破且多以工期为优化目标。针对此问题,考虑全局资源可从外部获取,以净现值为目标,构建带有全局资源柔性约束的分布式多项目调度问题的整数规划模型并设计有效的求解算法。首先,界定问题并确定项目现金流的计算方法;然后,针对求解问题的NP-hard属性,设计了遗传-模拟退火混合算法(GA_SA)求解此模型。最后,通过多组数值实验,设计不同算法与GA_SA算法进行比较,并分析了关键参数对多项目净现值的影响。结果表明,GA_SA算法具有较好的求解效果;与传统的全局资源刚性约束条件相比,全局资源柔性使用状态可以显著改善分布式多项目的收益绩效。     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

一类具有资源限制的调度问题

研究了具有线性退化及学习效应作用下的单台机器调度问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下求最大完工时间最小化问题给出了最优算法.     

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1｜rj,pj=bj-ajuj,Cmax≤｜∑uj和1｜rj,prec,pj=bj-ajuj C max≤｜∑uj并给出求其最优资源分配的多项式算法.     

基于多Agent系统的项目调度研究

近年来 ,大型项目特别是大型工程项目存在如下的发展趋势 :1 )项目规模越来越大 ;2 )项目的复杂程度不断增加 ;3 )项目必须由多方合作才能完成 .本文针对上述特点 ,提出了基于多 Agent系统 (MAS:Multi-Agent Systems)解决资源约束条件下的项目调度问题 (RCPSP:Resource Constrained ProjectScheduling Problems)的方法 ,并通过实例项目对所提出的算法进行了验证 .     

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

提出了将人工鱼群算法应用于求解资源受限项目调度问题中的构想,建立了求解资源受限项目调度问题的人工鱼群算法模型,设计了一种标准随机键编码方式,构建了人工鱼的觅食行为、聚群行为、追尾行为和随机行为四种基本算子,采用了正向逆向局部改进技术和精英保留策略,并给出了算法流程。应用PSPLIB标准问题库对该算法进行了大量的测试,并与其他算法进行了比较,验证了该算法的有效性。     

A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.