带有活动重叠的资源受限项目调度问题建模与求解

在新产品研发项目中,常常通过活动重叠缩短工期,但是重叠会带来返工风险,进而造成额外的时间和资源的消耗.将活动重叠分为自然重叠和强制重叠,采用设计结构矩阵、紧前重叠活动时间因子矩阵、紧后重叠活动时间因子矩阵和重叠返工影响矩阵量化重叠返工对时间和资源的影响.以最小化研发项目工期为目标,建立了带有活动重叠的资源受限项目调度问题优化模型,并设计了改进的遗传算法进行求解.该算法采用基于优先规则的编码机制,并将考虑活动重叠的进度生成机制作为解码方法.实例研究结果表明,提出的考虑活动重叠的模型与算法,不仅可以缩短项目工期,而且同时使项目资源的使用更加均衡.最后在随机生成的算例集合上测试了算法的有效性.     

广义优先关系约束下项目资源均衡的改进蝙蝠算法

针对带有广义优先关系的项目资源均衡问题,设计了一个改进的蝙蝠算法.改进了蝙蝠位置和种群的更新机制,提出了新的进度计划编码,解码和局部改进方法.利用正交试验设计探讨了算法参数设置.基于公开的基准数据集,通过大规模计算实验验证了所提算法的有效性.对于活动数量不超过50个的中小规模项目,所提算法可在1 s内求得接近于最优解的满意解;对于活动数量多达1 000个的大规模项目,求得满意解的时间不超过5 min;当项目截止日期较长时,所提算法优于目前最好的元启发算法.     

基于随机活动工期的资源约束项目鲁棒性调度优化

项目进度计划的鲁棒性对于不确定条件下项目的顺利实施具有重要影响. 作者研究具有随机活动工期的资源约束项目鲁棒性调度问题, 目标是在可更新资源和项目工期约束下安排活动的开始时间, 以实现项目进度计划鲁棒性的最大化. 首先对所研究问题进行界定并用一个示例对其进行说明. 随后构建问题的优化模型, 设计禁忌搜索、多重迭代和随机生成三种启发式算法. 最后在随机生成的标准算例集合上对算法进行测试, 分析项目活动数、 项目工期和资源强度等参数对算法绩效的影响, 并用一个算例对研究进行说明, 得到如下结论: 禁忌搜索的满意解质量明显高于其他两种算法; 当资源强度或项目工期增大时, 平均目标函数值上升, 禁忌搜索的求解优势增强. 研究结果可为不确定条件下项目进度计划的制定提供决策支持.     

资源转移视角下的RCPSP鲁棒资源分配方法

为使项目在工期不确定环境下既能按计划稳定执行又能维持较低的成本,以项目鲁棒性和资源转移成本为优化对象,构建了一个鲁棒资源分配优化模型.引入一种开始时间关键度指标作为项目的解鲁棒性目标,不同于已有研究均采用基于活动的资源流描述,模型定义了基于资源的二元决策变量,以表示某一资源单元在项目活动之间的转移次序.结合遗传算法和模拟退火算法的优点,提出了遗传退火混合智能算法对模型求解,模拟实验结果证明了所提算法在寻优效果和收敛速度方面的优越性.最后通过真实项目案例,进一步验证了模型和算法的实用性与有效性.     

复杂时间约束的水利工程项目调度问题研究

水利工程项目的调度属于资源受限的项目调度问题,但现实中这类项目存在着一种复杂的时间约束,即项目中的某些活动在特定时间段内不允许执行.针对这类特殊约束,本文提出了一种新的资源受限项目调度扩展模型,设计了多优先规则的启发式算法进行求解.并在此基础上提出了一种混合遗传算法,构造了新的交叉算子同时结合精英保留和双对齐技术来改善解的质量.最后,用调整后的项目调度问题库(project scheduling problem library)大量实例验证了算法的有效性.     

基于深度学习的RCPSP调度优先规则实时动态选择算法

针对资源受限项目调度问题,以最小化项目完成时间为目标,设计基于深度学习的调度优先规则实时动态选择算法,在每个调度阶段实时选择优先规则进行活动安排.通过构建深度神经网络模型,确定已调度项目在各阶段的项目状态与最佳优先规则之间的映射关系,再据此为待调度项目实时动态选择优先规则,结合串行调度机制生成最终调度计划.实验研究表明:实时动态选择优先规则算法表现优于文中所涉及的单一优先规则算法及混合优先规则算法,且具有更好的泛化性;此外,与元启发式算法相比该算法具有更高的求解效率.     

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

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

建立频繁项目集向量的极大频繁项目集挖掘

在分析和研究诸多经典关联规则挖掘算法或最大频繁项目集挖掘算法的基础上,提出了一种新的极大频繁项目集挖掘算法BOFPV_MMFIA算法.该算法引入频繁项目集向量FP-V,将极大频繁项目集的挖掘过程转化为频繁项目集向量FP-V的与运算过程.算法只需扫描数据库一次,克服了Apriori及其相关算法产生大量候选集和需多次扫描数据库的缺点.又不同于BOM算法,挖掘频繁k_项目集时,需要进行 次k个向量的与运算.因此,BOFPV_MMFIA算法的效率明显高于Apriori、DMFIA及BOM算法.     

基于粒子群算法的资源均衡

提出了将粒子群算法运用到型号研制项目资源均衡优化问题中的构想,建立了适用于资源均衡优化问题的粒子群算法模型,设计了基于非关键活动动态时差的资源均衡优化粒子群,构建了基于资源强度和活动实际开始时间的评价函数,给出了算法流程,并通过算例的计算分析,应用该算法得到的资源强度比初始方案的降低了88.38%,比P3软件及Project2002的结果分别降低了58.42%、74.48%,验证了该算法的可行性与有效性,同时还获得了若干个次优方案.     

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

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

非线性规划的混合遗传算法

遗传算法是一类模拟自然界生物进化过程与机制、求解问题的自组织和自适应的人工智能技术,是非常好的求解优化问题的算法,但是它也容易产生早熟现象,且局部搜索能力较差。因此,在分析传统的非线性规划方法的基础上,针对传统方法的局限性,为非线性规划模型设计了一种新的启发式算法,即结合遗传算法、模拟退火算法和动态惩罚函数法的混合遗传算法,以发挥各算法处理问题的优势。对算法的过程进行了分析。通过实例说明,该算法对于求解所建立的问题是有效的。     

Bayesian network learning algorithm based on unconstrained optimization and ant colony optimization

Structure learning of Bayesian networks is a wellresearched but computationally hard task.For learning Bayesian networks,this paper proposes an improved algorithm based on unconstrained optimization and ant colony optimization(U-ACO-B) to solve the drawbacks of the ant colony optimization(ACO-B).In this algorithm,firstly,an unconstrained optimization problem is solved to obtain an undirected skeleton,and then the ACO algorithm is used to orientate the edges,thus returning the final structure.In the experimental part of the paper,we compare the performance of the proposed algorithm with ACO-B algorithm.The experimental results show that our method is effective and greatly enhance convergence speed than ACO-B algorithm.     

具有引力机制的细菌觅食算法

针对细菌觅食算法中群体感应能力较弱和算法的收敛速度较慢的问题,提出一种具有引力机制的细菌觅食算法。该算法通过引入引力搜索算法中的引力机制来为每个细菌提供寻优的方向;采用细菌觅食算法原有的游动操作来实现局部寻优策略,并在游动之后增加局部维度更新,使得细菌在趋化操作中搜索范围更广;在细菌觅食算法的迁徙操作中引入双高斯函数来重新初始化细菌的位置,从而更好得避免算法陷入局部极值,提高算法的寻优能力。通过实验证明改进后的细菌觅食算法比基本细菌觅食算法拥有更好的寻优能力。     

用于异常检测的小参数集树突状细胞算法

树突状细胞算法（dendritic cell algorithm, DCA）是受自然免疫系统中树突状细胞的功能启发的免疫算法。当应用于实时异常检测时该算法具有优越的性能,但由于参数和随机元素相当多,算法难于分析。提出了一种用于异常检测的小参数集树突状细胞算法,在保证算法实现正确功能的前提下,减少了DCA中的参数,使算法参数数量得到了控制。此外,新算法还定义了更为简洁的信号处理过程以及对应的异常度量和异常阈值。最后,利用端口扫描数据集对算法进行了测试,实验结果表明,新算法是DCA的一种有效形式,新的异常度量更加敏感且它体现出的正确分类时间延长了30.3%~56.7%。     

基于遗传优化的采样模糊C均值聚类算法

在数据挖掘领域,模糊C均值聚类法(FCM)在处理小量低维的数据挖掘时是有效的,但是面向数据库的数据挖掘经常要处理大量、高维的数据.在这种情况下,FCM算法在时间性能上难以令人满意.本文基于采样技术对FCM算法进行改进,以提高算法的时间性能,并利用遗传算法对聚类结果进行优化以保证聚类的质量,给出了一种新的基于遗传优化的采样模糊C均值聚类算法SFGO(SamplingFCMwithGeneticOptimization).仿真实验证明SFGO算法在大规模数据库的聚类挖掘中,在时间性能和聚类质量上都能获得较满意的结果.     

基于FFT与MUSIC的改进DOA估计算法

针对MUSIC算法在进行信号波达方向(DOA)估计时谱峰搜索运算量大的问题,提出了一种基于FFT多波束算法与MUSIC算法的联合DOA估计方法。该方法采用FFT多波束算法形成多个波束,近似估计信号DOA,获得对应波束指向,再利用MUSIC算法实现对信号DOA的精确估计。这样就只需在该波束指向对应的空域范围内搜索,减小了DOA估计的运算量。     

基于遗传禁忌混合搜索算法的设备布局研究

针对设备布局影响制造系统的总体功效的问题,但同时遗传算法在实际应用中,出现早熟现象,爬山能力弱,等一系列缺点提出遗传禁忌混合搜索算法,该算法将遗传算法和禁忌搜索相结合,遗传算法的交叉算子中增加记忆功能,避免迂回搜索,以禁忌搜索作为遗传算法的变异算子。通过实例计算,证明遗传禁忌混合搜索算法是一种行之有效的算法,对解决设备布局这类组合优化问题具有实用价值。     

最短路树的计数、产生和优化问题

首先给出了在非负网络中构造最短路网络的算法，然后将树形图的计数算法到最短路网络中，设计出了最短路树计数问题的算法，将Gabow算法应用到最短路网络中，设计出了产生全部最短路树的算法，最后研究了最短路树的优化问题。     

频繁项目集二次挖掘方法研究

针对关联规则数据挖掘中频繁项目集的二次挖掘问题,提出了一种能够解决当最小支持度发生变化而交易数据库不变情况下进行二次挖掘的改进算法(UMSA)。该算法充分利用频繁项目集的特性,通过新的拼接方法来减少候选项目集的生成,在扫描交易数据库确定k维频繁项目集时,采用在交易数据库中剔除无用的交易,达到不断减小交易数据库规模的目的,克服了一些算法中存在的漏采现象,并在一定程度上解决了非确定性问题。通过举例说明该算法的执行过程及其算法的正确性和有效性,并对其性能进行了分析。     

基于树型结构的在线逆向组合拍卖模型

在分析逆向组合拍卖和树型结构基本特征的基础上,提出了基于树型结构的在线逆向组合拍卖的模型。针对中标者确定问题提出一种算法:标号法,并分析了标号法的一些性质。