考虑路径冲突的AGV配置与调度优化

合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。     

基于混沌量子算法和MAGTD的多目标FJSP求解策略

针对多目标环境下柔性作业车间的调度问题,以最小化最大完工时间和惩罚值为目标,建立调度问题的数学模型,提出了基于混沌理论的量子粒子群算法。针对实际生产交货期不确定的特点,在量子粒子群算法基础上,提出引入混沌机制建立初始群的方法;利用混沌机制的遍历性,提出混沌局部优化策略;为获取最优调度方案提出了引入多指标加权灰靶选择策略。通过典型基准算例和对比测试,验证了所提出的算法获得最满意调度方案的可行性和求解多目标柔性作业车间调度问题的有效性。     

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

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

带有活动重叠的项目调度问题新算法:分支定界法

在复杂产品研发项目中,通常采用活动重叠的方式来缩短工期,带有活动重叠的资源受限项目调度问题的求解多以启发式算法为主,该方法虽然具有收敛速度快、计算规模大等优点,但无法得到最优解,而精确算法是求解上述问题最优解的有效方法。基于此,本文在深入分析活动重叠对项目调度影响的基础上,设计了分支定界法以获得最优解。首先,从理论上证明了算法的最优性,一是对仅考虑最小延迟替代集即可得到最优解进行了证明;二是对割集支配规则与左移支配规则在剪枝操作中的应用进行了证明。其次,在算法设计上采用数据结构——栈对搜索树上的节点信息进行存储,并针对活动重叠约束,定义了新的决策时刻点和新的搜索树节点的表示方法。最后,通过大量的算例实验分析验证了算法的可行性和有效性。综上,本文提出的算法具备成熟的理论意义与精准的计算结果,具有较高的研究价值。     

随机环境下基于成本经济的项目调度权衡优化研究

针对随机环境下项目前摄性调度与反应性调度在应对不确定因素过程中起到的不同作用,从成本经济角度出发,研究了如何通过两种调度方法的权衡实现项目计划与执行的最优配合。在此基础上构建了基于成本的前摄反应调度权衡模型,通过对鲁棒性成本与调整成本进行量化分析,实现两种调度方案的最佳权衡。考虑到问题的NP难属性,设计了基于混合变邻域禁忌搜索的随机两点启发式算法,并通过大规模算例测试验证了算法的有效性。结果表明,根据承包商对成本的敏感度,前摄性调度与反应性调度在应对不确定性因素干扰中承担的工作量会随着成本权衡比的变化而发生改变,逐渐从前摄性方法为主过渡到以反应性方法为主。最后,从项目管理角度给出了有价值的管理启示。     

人力资源约束下的项目群调度问题建模与求解

基于人员胜任力是影响工作绩效的关键因素,将资源受限项目调度问题中的可更新资源通过一系列科学合理的方法或者手段转变为存在胜任力差异的人力资源,由此构建起一个强调胜任力差异的人力资源约束项目调度问题模型,此模型最突出的优势在于选取了能够客观合理评估人员胜任力的指标,提供了严谨科学的关系式,将复杂的多项目总工期与总成本的双目标最小化问题转换为综合指标单目标最大化问题,建立数学优化模型,采用遗传算法求解。通过算例研究证实,相较于传统多模式模型,基于人员胜任力水平差异的模型明显更胜一筹,其优势集中表现为最优工期更短、最优成本更低。考虑了胜任力差异的数学优化模型更符合研发项目群管理实践,同时遗传算法在求解方面不仅效率高,并且更容易获得客观准确的结果。     

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

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

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

考虑返修的建设项目时间-成本-质量问题

当施工过程中质量不达标需要返修以改进项目质量,但相应地会影响项目工期和成本。本文基于经典多模式资源受限项目调度问题构建一种新的非线性规划模型,目标为项目成本最小和工期最短,其中项目成本考虑返修成本以提高项目质量。首先,使用二元非独立正态分布函数描述活动质量,根据活动间的串联或并联关系定义隐蔽工程质量为活动质量的函数。其次,本文提出一种基于NSGA的混合蛙跳算法,采用串行进度产生方案和调整的活动列表编码,其中蛙跳过程结合了遗传算法中的交叉操作和基于置换的局域搜索。最后,整个模型算法应用于框架铁路立交桥施工项目,验证本文算法性能在支配解数量和质量上都优于标准NSGA。     

货运列车的编组调度问题的研究

对于货运列车的编组调度问题,建立了以压缩中时和增加运量为双目标、多约束的0-1规划模型,采用逐步紧缩中时约束的方法得到了问题一的调度方案.在此基础上对装载特别物资的车辆施加更强的中时约束得到了问题二的调度方案.提出了列车匹配系数的概念并建立了列车最优配对原则,根据该原则对列车进行优化编组得到了问题三的调度方案.基于问题二的数据转换处理得到了问题四的调度方案.     

基于时间窗延迟的资源约束项目调度双层优化研究

本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。     

Solving the discrete-continuous project scheduling problem via its discretization

In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multi-mode version is presented. A simulated annealing (SA) approach to solving this problem is described and tested computationally in two versions: with and without finding an optimal continuous resource allocation for the final schedule. In the former case a nonlinear solver is used for solving a corresponding convex programming problem. The results are compared with the results obtained using SA for the discrete-continuous project scheduling problem where the nonlinear solver is used for exact solving the continuous part in each iteration. The results of a computational experiment are analyzed and some conclusions are included.     

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

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

Scheduling non-professional table-tennis leagues

In this paper we consider a sports league scheduling problem which occurs in planning non-professional table-tennis leagues. The problem consists in finding a schedule for a time-relaxed double round robin tournament where different hard and soft constraints have to be taken into account. We model the problem as an integer linear program and a multi-mode resource-constrained project scheduling problem, respectively. Based on the second model a heuristic solution algorithm is proposed, which proceeds in two stages using local search and genetic algorithms. Computational results show the efficiency of the approaches.     

广义优先关系约束下Max-npv项目调度问题及其遗传算法

以往Max-npv项目调度问题的研究都假定活动之间的关系为单一结束-开始类型,现实中活动之间关系复杂多变,因此,将广义优先关系引入Max-npv项目调度问题中,构建了广义优先关系约束下的Max-npv项目调度模型。针对该优化模型设计了一种双层遗传算法,外层遗传算法负责任务执行模式的优化,内层遗传算法负责任务调度的优化。在内层遗传算法中,采用任务开始时间之差作为新的编码方式,大大简化了交叉变异算子,针对网络图中的环状结构设计了修复算子,确保了编码的有效性。通过一个算例对算法进行了测试,实验结果验证了算法的有效性。     

基于资源随机中断的反应性多模式项目调度优化

资源中断是项目实施过程中一种常见现象,它会导致项目进度计划的变更并引起额外的成本。本文研究资源随机中断下的项目调度问题,目标是对基准进度计划进行合理的调整,以最小化由此所造成的额外成本。作者首先对研究问题进行界定,随后构建问题的优化模型。针对模型的NP-hard属性,设计禁忌搜索启发式算法。最后以基准列表算法和随机生成算法为参照,在随机生成的标准算例集合上对算法进行测试,得到如下结论:在可接受的计算时间范围内,禁忌搜索获得的满意解质量明显高于其他两种启发式算法;算法的平均计算时间随着项目活动数的增加而增加,随着网络复杂度、资源强度或资源中断次数的增加而减小;满意解的平均目标函数值,随着项目活动数或网络复杂度的增加而增加,随着资源中断次数的增加而减小,与资源强度无明显关系。     

不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化

项目调度中的时间和费用是两个重要的指标,而在不确定环境下进度计划的鲁棒性则是保证项目平稳实施的关键。本文研究不确定环境下的多目标项目调度优化问题,以优化项目的工期、鲁棒值和成本为目标安排各活动的开始时间。基于此,作者构建多目标项目调度优化模型,将模型分解为三个子模型分析目标间的权衡关系,然后设计非劣排序遗传算法进行求解,应用精英保留策略和基于子模型权衡关系的优化策略优化算法,进行算法测试和算例参数敏感性分析。最后,应用上述方法研究一个项目实例,计算得到非劣解集,实例的敏感性分析结果进一步验证了三个目标间的权衡关系,据此提出资源的有效利用策略。本文的研究可以为多目标项目调度制定进度计划提供定量化决策支持。     

Proactive heuristic procedures for robust project scheduling: An experimental analysis

Solution-robust project scheduling is a growing research field aiming at constructing proactive schedules to cope with multiple disruptions during project execution. When stochastic activity durations are considered, including time buffers between activities is a proven method to improve the stability of a baseline schedule.     

Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.