随机活动工期下基于总不确定成本的项目前摄性调度与反应性调度集成优化

从成本经济角度研究活动工期随机中断下前摄性调度与反应性调度在应对不确定因素干扰中的集成优化问题,目标是最小化项目计划与实施过程的总成本.构建以总成本最优为目标的前摄性与反应性调度集成优化模型;针对模型特征设计混合变邻域随机禁忌搜索启发式算法,并在ProGen生成的算例上进行全因子测试.结果表明:基于随机属性的混合启发式...     

基于资金约束的项目支付进度问题研究

研究资金约束下的项目支付进度安排问题,其中活动具有多种执行模式,目标是最大化项目净现值.首先界定研究假设条件并定义文中用到的符号;随后构建问题的非线性整数规划优化模型;针对其强NP-hard属性,设计三层迭代循环嵌套的禁忌搜索启发式算法;以多重迭代改进算法为对比基准,在随机生成的3240个标准算例上对算法进行测试,结果表明:禁忌搜索获得的满意解质量远高于多重迭代改进,但其计算时间要长于后者.该研究可为承包商安排项目进度及平衡现金流提供决策支持.     

考虑鲁棒性成本的多模式双目标项目前摄性调度优化

研究多模式资源约束条件下的鲁棒性和成本双目标权衡问题,探讨如何在最低成本代价下最大程度地提升项目鲁棒性.首先界定研究问题,然后构建鲁棒值最大化、成本最小化的双目标调度优化模型,并将其转化为带有预算约束的单目标鲁棒值最大化子模型,针对模型设计迭代式遗传算法进行求解.随后,应用随机生成的标准算例集合进行大规模测试,对比结果...     

基于序贯博弈谈判机制的分布式多项目调度

设计有效的全局资源分配协调机制是解决分布式多项目调度问题的关键.基于多Agcnt系统建立以单项目完工时间为优化目标的局部调度模型,并设计基于正向逆向调度改进的遗传算法求解初始局部调度计划;综合考虑每个项目单位延期成本的差异,建立以多项目总延期成本为优化目标的全局决策模型,设计多回合序贯博弈谈判机制协调全局资源分配,并调整单项目局部进度计划;开展示例分析和不同参数下问题集的实验研究.结果表明:基于正向逆向调度改进的遗传算法求解初始局部调度具有较好的问题规模适应性和较高的求解精度;全局资源冲突越强,造成多项目延期越大且项目延期完工的风险也越大;采用序贯博弈谈判机制相比无博弈随机分配协调机制可以有效地降低多项目的总延期损失成本.     

考虑休班公平及同班次约束的呼叫中心排班优化问题

国内呼叫中心企业制定人力排班表时,越来越关注员工诉求及体现人性化管理理念.考虑坐席人员双休日休班公平性和周内工作日上班时间规律性,构建以多周为计划周期的呼叫中心排班优化问题整数规划模型.在对问题结构和优化性质分析基础上,提出构造性启发式算法.使用企业实例数据对模型和算法性能进行评估.计算结果表明规划模型只适于求解小规模问题最优解,而启发式算法能够以小计算成本获得较大规模问题优化解.最后计算分析得出了这些员工诉求因素对排班人力成本影响的量化结果.     

Client Perspective Based Multimode Project Payment Scheduling Problem and Its Heuristic Algorithm

This article involves the multimode project payment scheduling problem where activities can be performed with several discrete modes and the objective is to maximize the net present value (NPV) of the client. The assumptions are identified and the notations are defined at first. Then, the optimization model of the problem is constructed and its strong NP-hardness is proved by simplifying it to the subproblem of the discrete time/cost tradeoff problem. On the basis of the characteristic of the problem, a special heuristic algorithm composed of two modules is developed. Through the iteration between the two modules, the heuristic can find the desirable solution for the problem. The heuristic is tested on a data set consisting of 40 instances generated randomly. On the basis of the results obtained, the following conclusions can be drawn: All the instances can be solved within 24.63 seconds; the relative deviation of the objective function value from its upper bound is not greater than 8.24%; the NPV of the client decreases with the increase of the payment number, the interest rate per period, the profit margin of the contractor, or the payment proportion.     

一种新的求解Flow Shop问题的启发式算法

同顺序 Flow Shop问题是一个著名的 NP难题 ,至今尚未找到有效算法 .总体来讲 ,求解该问题的启发式算法主要可分为规则式算法和迭代式算法两种 .对该问题有很多求解目标 ,如最小加工周期 ( min makespan) ,工件的最小平均在系统的停留时间 ( min mean flow tim e)等 .本文以求解最小加工周期为目标 ,基于目前已知的性能最好的算法 NEH算法的基本思想 ,提出了一种新的启发式算法 -组合指标算法 .大量的数据实验表明 ,新的算法具有很好的计算结果 ,而且这种算法可以说是给出了求解 Flow shop问题的一种新的思路和方向.     

关键链项目群进度管理的定量分析

论文从定量的角度,分析了项目群中一种资源以及多种资源的"多任务"情形,对关键链进度计划问题建立了数学模型,并引入遗传算法,使"多任务"现象转化成具有相应优先权的排序基因或染色体,对最优化进度和延迟成本构建了相应的算法.最后,通过算例证实此方法可以得出最优排序,同时能提供较多的替代方案,为关键路径法演变成关键链技术提供了定量支撑.     

考虑全局资源闲置成本的分布式RCMPSPTT

在考虑资源转移时间的分布式多项目调度问题中,增加考虑资源闲置成本,对于多项目共享资源的协调决策具有重要影响.基于多Agent系统建立以单项目完工时间为优化目标的局部调度模型,并采用遗传算法求解初始局部调度计划;同时考虑项目延期成本、全局资源转移成本和闲置成本,以多项目总成本为优化目标建立全局协调决策模型,设计基于贪婪转移策略的序贯博弈谈判机制协调全局资源的分配和转移,并根据协调结果调整单项目局部进度计划;以MPSPLIB问题集开展实验研究.研究结果表明:协调时考虑全局资源闲置成本能更好的协调全局资源的分配和转移;与无博弈随机分配和转移的协调机制相比,基于贪婪转移策略的序贯博弈谈判机制可以有效地降低多项目总成本.     

基于合作博弈协商机制的分布式资源受限多项目调度

分布式资源受限多项目调度问题涉及多个项目的独立调度以及项目之间共享资源的协调分配,因此,解决该问题的关键是设计有效的机制获取协调全局资源所需的调度信息并据此配置全局资源.考虑每个单项目延期的影响程度不同,以最小化多项目总拖期成本为全局目标建立分层决策模型:考虑分布式多项目调度问题的信息不对称性和各单项目决策者的自利性,设计基于合作博弈协商机制的分阶段进化算法对问题求解.以MPSPLIB问题集开展实验研究,结果表明:采用合作博弈协商机制可以有效降低多项目的总延期成本,并且该求解机制对问题规模和资源冲突强度的变化有很好的适应性;自主Agent参与合作博弈并选择诚信策略可获得更高的单项目收益,同时多项目获得高质量的调度方案.     

Improved differential evolution algorithm for resource-constrained project scheduling problem

An improved differential evolution (IDE) algorithm that adopts a novel mutation strategy to speed up the convergence rate is introduced to solve the resource-constrained project scheduling problem (RCPSP) with the objective of minimizing project duration. Activities priorities for scheduling are represented by individual vectors and a serial scheme is utilized to transform the individual-represented priorities to a feasible schedule according to the precedence and resource constraints so as to be evaluated. To investigate the performance of the IDE-based approach for the RCPSP, it is compared against the meta-heuristic methods of hybrid genetic algorithm (HGA), particle swarm optimization (PSO) and several well selected heuristics. The results show that the proposed scheduling method is better than general heuristic rules and is able to obtain the same optimal result as the HGA and PSO approaches but more efficient than the two algorithms.       

基于DSM的研发项目流程多目标仿真优化

分析了复杂产品研发项目中流程结构的不确定性,采用设计结构矩阵对其进行仿真建模,并将设计结构矩阵调度策略嵌入仿真模型,建立了同时最小化项目工期和成本的多目标优化模型.提出了一种基于设计结构矩阵仿真与非支配排序遗传算法的混合优化算法,获取研发项目流程多目标优化的Pareto最优解.以某飞机初步研制项目流程为研究算例,验证了混合优化算法的可靠性和有效性,并对获得的最优流程结构进行了深入的仿真评价与分析。     

可更新资源受限的工期-费用权衡问题及粒子群算法

传统离散时间-费用权衡项目调度问题(DTCTP)中,可更新资源约束被忽略,将可更新资源约束引入DTCTP模型,形成可更新资源受限的工期-费用权衡项目调度问题(RRCDCTP)。在活动执行模式中增加可更新资源需求量,并考虑项目执行中的单位工期的可更新资源限量约束,基于可更新和不可更新两类资源的使用量计算活动费用。根据模型特点,提出一种求解该模型的粒子群优化算法。实例验证结果表明,当存在可更新资源约束时,在相同总费用预算约束下,RRCDCTP获得的最优项目工期比DTCTP获得最优工期长;同时,可更新资源限量越小,最优调度计划中具有浮动时差的活动数越少。     

混合Flow Shop的调度仿真系统及其算法分析

研究了混合Flow Shop的调度问题，调度目标为最小化工件的最大完成时间。文中给出了调度仿真系统的设计，系统由数据库、算法和控制中心用户接口三个模块组成；在算法模块中，排序算法包括了由Flow Shop扩展到混合Flow Shop的多数算法，设备分配采用最先可用机器优先规则。另外，基于CDS虚拟机和Palmer斜度指标的启发式算法，提出了一种改进的CDS算法用于工件排序。在正在开发的混合Flow Shop调度仿真系统中实现了上述所有算法，仿真分析表明改进的CDS算法优于其他启发式算法。     

SOLVING RESOURCE—CONSTRAINED PROJECT SCHEDULING PROBLEMS WITH BI—CRITERIA HEURISTIC SEARCH TECHNIQUES

In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm forsolving multiple resource-constrained project scheduling problems. The heuristic solves problems intwo phases. In the pre-processing phase, the algorithm estimates distance between a state and the goalstate and measures complexity of problem instances. In the search phase, the algorithm uses estimatesof the pre-processing phase to further estimate distances to the goal state. The search continues in astepwise generation of a series of intermediate states through search path evaluation process withbacktracking. Developments of intermediate states are exclusively based on a bi-criteria new stateselection technique where we consider resource utilization and duration estimate to the goal state. Wealso propose a variable weighting technique based on initial problem complexity measures.Introducing this technique allows the algorithm to efficiently solve complex project schedulingproblems. A numerical example illustra     

基于资源流网络与时间缓冲集成优化的鲁棒性项目调度

针对工期不确定的资源受限项目调度问题,将鲁棒性资源分配和时间缓冲插入两种方法进行有效地结合,通过设计两阶段集成优化算法构建抗干扰能力较强的鲁棒性项目调度计划.第一阶段提出MEPC(minimizing expected penalty cost)资源流网络优化算法,通过对资源进行有效配置生成稳定的资源流网络.为进一步提升调度计划的鲁棒性,第二阶段通过固定第一阶段构建的资源流网络,设计EPC(expected penalty cost)缓冲优化算法,通过迭代方式在延期风险较大的活动前插入时间缓冲,实现项目期望惩罚成本最小化.最后通过大规模仿真实验从"解"鲁棒性"质"鲁棒性两方面来验证两阶段算法的有效性和可行性,结果表明通过将资源流网络与时间缓冲进行集成优化构建的调度计划不仅具有较好的完工性并且能更有效地应对项目执行过程中各种不确定性因素的干扰.     

活动重叠对缩短资源受限项目工期有效性研究

活动重叠是项目赶工的一种常用手段,但并非所有活动的重叠执行均能有效缩短项目工期.识别和评估项目中活动重叠对缩短项目工期的有效性,避免无效的活动重叠及资源的浪费,对于解决资源受限项目调度问题具有重要的理论和现实意义.针对现有进度生成机制在处理带有活动重叠的资源受限项目调度问题上的不足,本文建立整数线性规划模型并对小规模算例进行精确求解.在对求解结果统计分析的基础上识别影响活动重叠有效性的关键因素,为项目调度中制定重叠策略提供指导.通过一个算例验证预先识别有效的活动重叠对提升启发式算法性能和优化项目调度结果具有积极作用.     

柔性作业车间AGV与机器双资源集成调度研究

针对含有AGV(automated guided vehicle)的柔性作业车间调度问题,建立了以最小化最大完工时间为目标的双资源集成调度优化模型.在种群初始化过程中提出一种启发式初始化方法,提高种群初始解的质量,加快算法的收敛速度.针对离散粒子群算法易早熟的弊端,结合竞争学习机制和随机重启机制提出一种可有效避免早熟的...     

Study on Resource Scheduling in Project Group Management of Offshore Engineering based on ACO

To solve the problem of resource scheduling in project group management, which is a crying problem in offshore project management, the ant colony optimization (ACO) algorithm was introduced. First, the similarities between resource dynamic scheduling problem and ant's food-seeking were analyzed and the meta-information was defined. Second, the dynamic scheduling model was proposed. Then, engineering practice in offshore project group resource scheduling showed that the resources can be allocated timely, dynamically and rationally by using this algorithm. The method can also be introduced into other related spheres. This study will give rise to project group management.     

带公共交货期窗口的提前/拖期非等同多机调度问题

提出了公共交货期窗口下提前 /拖期惩罚的多台不同设备情形的零件排序模型 .在分析相应单机问题最优排序和最优交货期性质的基础上 ,证明该多机零件问题实际上蕴含着使系统 makespan达最小的多机零件排序问题 .由于使系统 makespan达最小的并行多机零件排序问题已被证明是 NP完全问题 ,因此提出了求解该零件排序问题的一个启发式算法 ,该算法计算复杂性低且对并行多机零件排序问题同样适用 .最后给出了两个数值例子 .