基于双重视角的MPPSP及其禁忌搜索启发式算法

首先界定研究假设条件并定义文中所使用的符号;随后从业主及承包商双重视角构建MPPSP的整数规划优化模型;针对问题的强NP-hard属性,设计禁忌搜索启发式算法;在随机生成的标准算例集合上对算法进行测试;最后用一个算例对研究结果进行说明。结论如下:本文所开发的禁忌搜索启发式算法可以有效地求解MPPSP;关于给定项目的支付进度安排,承包商和业主的偏好存在显著差异;随着支付次数与支付比例的增加,承包商收益提高,业主收益下降,而双方收益均随折现率的上升而下降。     

基于决策者风险偏好的模糊鲁棒性项目调度优化

不确定条件下模糊鲁棒性项目调度计划的生成受决策者风险偏好影响。本文研究模糊活动工期下考虑决策者风险偏好的鲁棒性项目调度优化问题，目标是合理安排活动开始时间，生成特定风险偏好下鲁棒性最大的进度计划。首先界定问题，构建优化模型；随后针对问题NP-hard属性和模型特点设计交替禁忌搜索启发式算法，求解得到不同风险偏好下满意的进度计划；最后用实例验证说明，并分析关键参数影响。结论如下：决策者风险偏好由规避转乐观时，项目冲突区间总和增多；截止日期、资源可用量较紧张时，风险偏好变化对冲突区间总和变化影响更大；风险偏好乐观时，截止日期变化对冲突区间总和变化影响更大。研究成果可为不同风险偏好决策者在不具历史数据的高不确定环境中制定合理前摄性计划提供决策支持。     

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

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

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

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

基于融资能力约束的多模式Max-npv项目调度优化: 双重视角

从项目双方的视角出发,研究融资能力约束下的Max-npv项目调度问题。首先进行问题界定,构建由两个子模型构成的多模式Max-npv项目调度优化模型。随后,鉴于问题的强NP-hard属性,设计针对两个子模型迭代循环求解的禁忌搜索启发式算法,得到项目双方都满意的解。最后用一个实际案例对研究进行验证说明,并分析关键参数对合同双方收益的影响,结果表明:与实际进度安排相比,满意进度安排下合同双方的收益均有显著的提升;承包商和业主的融资能力、项目截止日期、承包商收益底线、折现率及支付比例均会对双方的收益产生重要影响。     

随机活动工期下考虑缓冲成本及效用的融资费用最小化项目调度优化研究

巨额融资所带来的高昂融资费用，推高承包商的总成本，严重挤压其利润空间。承包商迫切需要对项目现金流进行优化，提高资金配置效率，降低融资费用。此外，为了应对不确定性干扰，承包商通常花费事前成本为活动添加时间缓冲，以保证进度计划稳定性，以减少事后变更和调整费用。因此，本文研究随机活动工期下考虑缓冲成本及效用的融资费用最小化项目调度优化研究，旨在为承包商生成具有一定鲁棒性的融资费用最小化基准进度。首先，界定研究问题并构建优化模型，在此考虑为活动插入时间缓冲所带来的成本及效用。其次，设计VNTS混合算法对模型进行求解，提炼相关性质以提高算法搜索效率，并在算例集合上进行算法测试。最后，通过案例对本文研究进行说明。研究结果可以为随机活动工期下承包商控制融资费用、提高项目收益，提供定量化决策支持。     

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

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

基于资源约束的突发事件应急救援鲁棒性调度优化

突发事件应急救援的调度优化,对于救援活动的顺利实施及应急资源的有效使用具有至关重要的作用。本文研究资源约束下的突发事件应急救援鲁棒性调度优化问题,其中,鲁棒性定义为各活动的时间缓冲与其权重系数乘积的总和,目标是在资源可用量及救援期限的约束下,安排活动开始时间和执行模式以最大化应急救援计划的鲁棒性。作者构建了问题的0-1规划优化模型,针对其NP-hard属性,基于问题特征设计双环路禁忌搜索启发式算法。通过对一个算例的计算分析,得到如下结论:给定网络结构及时间参数,利用权重系数的定义可以将时间缓冲分配到重要活动上,由此提高应急救援计划的鲁棒性;随着资源可用量的增加,计划的鲁棒性呈上升趋势,而当救援期限延长时,计划的鲁棒性单调增加。本文研究可为突发事件应急救援基准计划的制定提供决策支持。     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现：项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

P-枢纽航线网络设计问题的一种启发式算法

针对无容量限制的多重分派枢纽中位问题(UMApHMP),提出了一种基于禁忌搜索和最短路算法的新的启发式算法。利用CAB基准数据对该算法进行了验证,计算结果表明所提算法具有较强寻优能力和较快的求解效率。     

带有资源转移时间的RCPSP资源流模型及算法

本文在传统资源受限项目调度问题(resource-constrained project scheduling problem, RCPSP)中引入资源转移时间,为有效获得问题的最优解,采用资源流编码方式表示可行解,建立了带有资源转移时间的RCPSP资源流优化模型,目标为最小化项目工期。根据问题特征设计了改进的资源流重构邻域算子,分别设计了改进的禁忌搜索算法和贪心随机自适应禁忌搜索算法求解模型。数据实验结果表明,相较于现有文献中的方法,所提两种算法均可针对更多的项目实例求得最优解,并且得到最优解的时间更短,求解效率更高。此外,分析了算法在求解具有不同特征的项目实例时的性能,所得结果为项目经理结合项目特征评价算法适用性提供了指导。     

A new heuristic for the multi-mode resource investment problem

This paper considers the problem of minimizing resource investment required to execute the tasks in a project network by a given project due date. A project consists of non-pre-emptive tasks executed in a known and required precedence order. Each task is completed in one of its feasible modes, which may differ not only in task duration but also in consumption of renewable resources. A priority rule heuristic with polynomial computational complexity is presented for this computationally intractable problem. This heuristic simultaneously considers due date constraints and resource usage to select and schedule tasks with one decision rule. This differs from prior multi-mode priority rule scheduling heuristics that apply two consecutive decision rules to schedule tasks. Extensive computational testing indicates promising results.     

Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages

In this paper we propose a heuristic for solving the problem of resource constrained preemptive scheduling in the two-stage flowshop with one machine at the first stage and parallel unrelated machines at the second stage, where renewable resources are shared among the stages, so some quantities of the same resource can be used at different stages at the same time. Availability of every resource at any moment is limited and resource requirements of jobs are arbitrary. The objective is minimization of makespan. The problem is NP-hard. The heuristic first sequences jobs on the machine at stage 1 and then solves the preemptive scheduling problem at stage 2. Priority rules which depend on processing times and resource requirements of jobs are proposed for sequencing jobs at stage 1. A column generation algorithm which involves linear programming, a tabu search algorithm and a greedy procedure is proposed to minimize the makespan at stage 2. A lower bound on the optimal makespan in which sharing of the resources between the stages is taken into account is also derived. The performance of the heuristic evaluated experimentally by comparing the solutions to the lower bound is satisfactory.     

Local search metaheuristics for discrete–continuous scheduling problems

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.     

A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm.     

基于禁忌算法的中枢辐射航线网络鲁棒优化方法

文章针对航空公司构建中枢辐射航线网络问题展开研究,采用鲁棒优化的方法建立数学模型,针对鲁棒解的特点以及问题的复杂性,将禁忌算法和最短路算法相结合并加以改进,提出了一种适应于求解大型问题的启发式算法,并通过实例进行了仿真实现.     

An Exact Procedure for the Resource-Constrained Weighted Earliness–Tardiness Project Scheduling Problem

In this paper we study the resource-constrained project scheduling problem with weighted earliness–tardinesss penalty costs. Project activities are assumed to have a known deterministic due date, a unit earliness as well as a unit tardiness penalty cost and constant renewable resource requirements. The objective is to schedule the activities in order to minimize the total weighted earliness–tardinesss penalty cost of the project subject to the finish–start precedence constraints and the constant renewable resource availability constraints. With these features the problem becomes highly attractive in just-in-time environments.We introduce a depth-first branch-and-bound algorithm which makes use of extra precedence relations to resolve resource conflicts and relies on a fast recursive search algorithm for the unconstrained weighted earliness–tardinesss problem to compute lower bounds. The procedure has been coded in Visual C++, version 4.0 under Windows NT. Both the recursive search algorithm and the branch-and-bound procedure have been validated on a randomly generated problem set.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.