无等待流水调度问题迭代启发式算法

针对以总完工时间最小化为目标的无等待流水调度问题(缩写为NWFSP),提出了两个迭代启发式算法(缩写为IHA1、IHA2).一个是以FL(described by Framinan and Leisten,OMEGA,2003)启发式算法产生的解作为初始解,另一个是以WY(described by Hoon-shik Woo and Dong-soon Yim,Computers&Ops Res,1998)启发式算法产生的解作为初始解,然后两者均应用RZ(developed by Rajendran and Ziegler,European Journal of Operational Research,1997)和FL插入以及成对交换技术进行多次迭代来改善解的质量.为了评估,我们使用了Taillard’s基准程序随机产生了大量实例,实验结果显示,IHA1和IHA2在解的性能上优于经典的RC1、RC2、PH1(p)算法,随着问题规模的增大,对解的质量改善得更好.

基于一种启发式迭代算法的产品组合优化

本文研究了一个单个时期的产品组合优化问题。文章假定商品的需求符合MNL model。笔者通过设计一种迭代算法从零售商所有能够经营的产品种类集合中挑选出在零售商库存约束范围内单位期望收益最大的产品集合作为其最优产品组合。数据实验表明该算法可有效提高零售商的期望收益,并为如何改进零售商经营的产品组合提供科学指导。

海岛无人机多模式应急配送模型与算法研究

灾害情况下物资海岛配送是应急物流的一种特殊应用场景.无人机配送作为解决应急物流问题的一种新型配送方式受到广泛关注,并涌现出了一系列配送模式.通过考虑无人机成本、无人机飞行距离、无人机起降平台和地面配送成本,构建无人机直接配送、点对点双阶段配送、回路双阶段配送和双层物流配送网络4种配送模式.针对回路双阶段配送的多指标耦合特征,提出一种迭代启发式算法进行优化.围绕普陀山海岛场景,构建20~100个需求点和2~4个无人机起降平台的算例进行数值实验,分析并验证模型正确性和算法性能.实验结果表明,4种配送模式模型具有有效性;算法一般经过2~5次迭代,能够有效减少回路双阶段配送约19.08%的无人机飞行距离,减少双层物流配送网络约28.63%的地面配送距离.

二值分解压缩和Consensus算法

奇异值分解(SVD)是一种流行的用于高维数据压缩的方法,二值分解是奇异值分解的一种简化形式。实现二值分解的主要算法有两种:迭代启发式算法和贪婪算法。但这两种算法都不是很理想的算法:迭代启发式算法在很多情况下不能保证收敛性,贪婪算法不满足大型数值矩阵分解的需要。采用了一种新的算法来实现二值分解:Consensus的算法。Consensus算法可在渐进多项式时间内找到一般图中的极大二分团。对于某些二分图,该算法的复杂度是多项式时间的。实验结果表明,当迭代启发式算法不起作用时,Consensus算法是一种很好的求解二值分解的方法。该算法远比贪婪算法的效率高,且具有稳定收敛性。

成本约束的网格工作流时间优化方法

针对成本约束有向无环图DAG(directed acyclic graph)表示的网格工作流完工时间最小化问题,提出两个基于优先级规则的迭代启发算法.算法利用并行活动特征定义正向分层和逆向分层两个概念,将其分别引入最大收益规则MP(maximum profit),得到正分层最大收益规则MPTL(maximum profit with top level)和逆分层最大收益规则MPBL(maximum profit with bottom level).两规则每次迭代尽量以完工时间的最小增加换取总费用的最大降低,逐步将分层初始解构造为满足成本约束的可行解.模拟结果表明,两规则在获得较少迭代次数和运行时间的同时,能显著改进MP规则的平均性能,且MPBL优于MPTL.

电力系统多时段无功优化研究

针对电力系统的多时段无功优化问题,在基于统计学原理分时段方法的基础上,提出了一种基于无功调节设备一天内最大调节次数的启发式迭代分时段算法,从而可以根据负荷变化的趋势得到无功控制设备动作的时间点.时间点确定之后,即可应用单一负荷下的静态无功优化研究成果,计算得到无功控制设备的调节状态.该方法可以自适应地修正划分时段的门槛值,从而保证了分段的结果具有可操作性.IEEE-39节点算例的分时段无功优化计算从网损、设备动作次数、计算量3个方面说明了本文所提出的分时段策略的有效性,表明了本方法不仅可明显降低网损,而且可以简化无功优化控制操作.

基于网络拓扑的子网络OD需求估计

为了对局部交通路网进行设计和评价,运用拓扑结构分析方法对子网络OD需求进行估计.根据子网络拓扑结构,分别对子网络边界点和内部点的OD量进行分析,每个与外界网络相连的边界点都为子网络的交通发生吸引点,内部点OD需求量与原来网络保持一致.进而建立了基于网络拓扑的子网络OD需求估计模型,其中目标函数同时考虑了交通需求的熵最大化及弹性化,约束条件为子网络OD量约束.将原问题分为求解交通需求和道路阻抗两部分,设计了启发式迭代算法反复求解,并运用凸组合算法计算交通需求.运用Sioux Falls网络对算法和模型进行了测试,结果表明考虑弹性需求的子网络OD估计模型在可靠性和计算精度上均优于考虑固定需求的子网络OD估计模型,算法能够快速收敛到所需精度,建立的模型可以用来对实际路网进行简化.

基于多例学习的Web图像聚类

在图像分类和自动标注系统中,多例学习(MIL)是研究的热点.目前MIL中的算法多为监督学习方法.针对非监督学习,在基于EM算法和启发式迭代优化算法的框架下,提出了6种多例聚类算法,并通过它们对来自于真实Web环境下的图像进行聚类以分析用户的搜索兴趣.由于一幅图像含有若干个区域,每个区域可被看为一个样例,属于同一个图像的区域则组成一个包.因此如何理解图像语义内容的问题即转化为多例学习.在多例学习的经典数据集MUSK数据和来自于Web图像集上的比较实验表明,提出的多例聚类算法具有优良的聚类性能.

装备维修器材生产路径双目标问题优化决策方法研究

在装备维修器材供应保障中,针对精确保障背景下部队用户对器材保障精度的要求,构建了最小化总成本和最大化订单精准执行率的双目标优化决策模型。在ε-约束法框架内,开发可生成近似Pareto前沿的两阶迭代启发式算法,并采用模糊逻辑决策法选择符合决策者偏好的折中最优解。随机实例测试结果表明所提出的模型和算法可以很好地应用在双目标优化问题的研究中,并在求解不同规模实例时表现出优异的性能。

考虑不确定性的多阶段装备维修器材供应优化方法

装备维修器材供应是作战部队持续保持战斗力的关键。考虑多阶段作战行动中,战场形势、部队位置及需求量等不确定性,将野战仓库选址、需求分配、供应路径规划融合为一类选址-路径组合优化问题,构建基于情境的多阶段混合整数规划模型。设计一种两阶段迭代启发式算法对问题进行求解。基于20个算例的数值实验,证明了所提出的模型及算法在具有高度不确定性的多阶段装备维修器材供应保障中的有效性。