n／m／F／C排序问题的启发式算法

流水车间以极小化平均完工时间为目标的排序问题已被证明为ＮＰ难题，本文给出了求解该问题的两种方法；求最优解的分枝定界法和求近化解的启发式算法．大量计算机模拟结果表明，本文给出的启发式算法优度较高，而且是简单的多项式算法．     

求解作业排序问题的通用混合遗传算法研究

车间作业排序理论是生产管理与组合优化领域的重要研究方向 ,由于其固有的计算复杂性( NP-Hard) ,一般无法利用经典方法求出最优解。本文针对一般作业排序问题 ,将遗传算法与启发式方法相结合 ,建立了一种混合算法框架 ,利用遗传算法改进启发式方法的求解性能 ,同时利用启发式方法引导遗传搜索过程 ,以提高其搜索效率。通过对完工时间与平均延误时间等不同优化目标的计算分析与比较表明 ,该方法对不同类型的排序问题均具有相当满意的求解效果.     

车辆路径问题的遗传算法研究

在分析车辆路径问题的现有启发式算法的基础上,本文构造了车辆路径问题的染色体表达,并对染色体进了可行化影射,建立了此问题的遗传算法．实验结果表明,此算法可以有效求得车辆路径问题的优化解或近似优化解,是求解车辆路径问题的一个较好的方案     

能力受限批量问题的启发式算法与CPLEX仿真优化

能力受限批量问题多数都是NP-hard问题,解决方法之一就是构造启发式算法获取尽量接近最优解的可行解。目前多数文献通过大规模计算分析来评价启发式算法的性能,但是这种评价方式只能表明该算法针对特定实例的适应性。利用商业优化软件求解同一实例并与算法计算结果进行对比分析,可以体现算法的有效性。针对一种运输能力外包且费用时变的多产品动态经济批量问题,建立混合整数规划模型,通过约束松弛与模型分解,设计出一个基于拉格朗日松弛理论的启发式算法进行模型求解。大量随机实验计算结果以及CPLEX仿真优化结果对比分析表明,在某些实例情况下,启发式算法获取的最优值与CPLEX获取的相当,但是求解时间要明显优于CPLEX,因此选择启发式算法求解此类实例是较优的。     

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

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

一种基于遗传算法的最优空间布置方法

空间布置问题是工业生产中的瓶颈问题,因为存在太多的可能组合,容易陷入局部最小解。本文提出一种在空间布置问题中基于遗传算法把空间位置进行编码并通过遗传操作算子进行重定位和改变有限旋转方向策略的全局搜索方法。种群中每一个个体是一种有效的空间分配方案,在遗传算法进化过程中为减少计算时间,提高空间利用率,采用了多种启发式信息如原点策略、边策略、避免重复定位点策略和无悬挂策略等来加速收敛到全局最优解。最后,仿真例子说明了所提方法是工业应用中一种可选方案。     

行为综合功能流水线中的资源约束LB-ACO算法

针对行为综合功能流水线中带资源约束的调度问题,提出了一种新的功能流水线调度算法负载平衡蚁群调度算法(load-balanced ant colony scheduling,LB-ACO).该算法将蚁群算法和力向算法的受力公式相结合,在保证较低运行时间复杂度O(cn²)的前提下,可获得近似最优的流水线调度结果.通过确定蚁群算法的局部试探因子和全局试探因子的计算方法,描述了该算法的实现步骤.通过仿真实验证明了该算法的流水线调度性能.     

应用改进微粒群算法求解Job-shop调度问题

针对微粒群算法在求解实际问题过程中会出现早熟的现象,提出一种改进的微粒群算法。该算法利用记忆库来动态调整惯性权重值,增快了算法的收敛速度。同时结合进化、灾变机制避免了算法陷入局部极值的问题。在列出改进算法的具体步骤基础上,通过实际的车间调度仿真实例证明了算法的有效性,可以得到比启发式、遗传算法更佳的调度效果。     

模拟植物生长算法的原理及应用

为解决国外主流智能算法普遍存在的参数选择难题,模拟植物生长算法(PGSA)以植物独有的向性运动为启发式准则,将优化问题的解空间当做植物的生长环境,通过生长信息和分枝模式(L-系统)构造出依赖优化环境而不断生长的人工植物分枝生长模式,建立了跳出局部最优解并迅速求出全局最优解的遍历搜索机制和智能算法体系.模拟植物生长算法开拓了"无参数智能优化算法"研究的新领域,本文从该算法的思想源头进行阐述,对国内外学者近年来在不同研究领域应用该算法的情况进行了分析和评述,指出了植物生长原理对智能优化领域的影响以及未来的发展方向.     

采用混合单亲遗传算法求解一类资源-时间优化问题

针对资源有限最短时间的一类资源 -时间优化问题 ,提出了混合单亲遗传算法进行求解 .作为一类 NP完全问题 ,该问题求解难度相当大 ,尤其问题规模大时寻找最短时间优化解就更困难 .针对问题的特点本文引入的算法结合了启发式规则 ,给出了算法全局收敛的理论分析 ,并给出实际应用表明该算法的有效性.     

基于改进遗传算法的流水车间调度求解方法

流水车间调度问题是一类经典的NP完全问题,为此提出了一种求解极小化总完工时间的流水车间调度问题的改进遗传算法.该算法采用构造型启发式算法和随机方法共同产生初始种群,结合禁忌搜索算法的局部搜索性能和遗传算法的全局搜索性能.仿真实例的结果表明该算法对问题求解的可行性和有效性.     

考虑工作量均衡的成品油二次配送车辆路径问题

为避免工作量分配不均,研究了考虑工作量均衡的成品油二次配送车辆路径问题。以总配送成本极小化和不同车辆路径长度之差极小化为目标,建立了双目标混合整数规划模型;并设计了变邻域禁忌搜索启发式算法。利用改进的Solomon＿I1插入算法求出使总配送成本尽量小的初始解;再利用变邻域禁忌搜索算法改进初始解,得到近似最优解。模拟计算结果显示,通过变邻域禁忌搜索算法改进后的解,总配送成本仅增加6.2%,车辆路径长度差值降低了45%,验证了算法的有效性。     

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization (ACO) is a new heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems.The traveling salesman problem (TSP) is among the most important combinatorial problems.An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature convergence problem of the basic ACO algorithm on TSP.The main idea is to partition artificial ants into two groups: scout ants and common ants.The common ants work according to the search manner of basic ant colony algorithm,but scout ants have some differences from common ants,they calculate each route's mutation probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability.Simulation on TSP shows that the improved algorithm has high efficiency and robustness.     

基于遗传-模拟退火算法的空间目标地基监视调度方法

空间目标监视是航天任务得以顺利开展的重要基础。针对空间目标地基监视中的大规模复杂调度问题,建立了包含多种约束条件和优化目标的调度问题数学模型。探讨了利用遗传算法对全局解的一部分进行局部优化以提高资源利用率的算法混合策略,构建了遗传-模拟退火算法,其中对模糊需求使用了启发式方法以构造可行解的局部,并采用窗口修剪法进行冲突处理。仿真结果表明,遗传-模拟退火算法与窗口修剪法结合能够在可接受的时间内求得满意的解,验证了模型和算法的有效性。     

多车场满载货运车辆优化调度的网络流算法

探讨在一般条件下的多车场满载的VSP问题。建立了它的网络流模型，并给出了一个基于该网络流最优解的启发式算法。该算法的一个明显特征是，对每一条行车路线的确定总是基于一修改后的网络流模型的最优解，大大提高了算法结果的优化质量。同时，与其它同类算法相比，其算法设计也明显偏优。     

三站无源定位系统数据关联算法

全局最优量测数据关联算法是无源定位技术中的关键问题。针对三站无源定位系统全局最优数据关联的三维（3-D）分配问题，提出一种新的直接求解算法——启发式消元算法。该算法通过直接对代价矩阵的元素进行启发式消元，得到分配问题的最优解。给出算法相关原理的分析和证明以及算法的具体步骤。并将其应用于三部光电被动传感器多目标无源定位系统两级数据关联算法的第二级关联过程中。对启发式消元算法和求解3一D分配问题的近似最优求解算法——拉格朗日松弛算法的算法复杂性进行了分析对比。理论分析和仿真实验均表明，该算法较适合与两级关联算法联合使用。与拉格朗日松弛算法相比。该算法计算量小。便于实现。是一种新的、有效的全局最优数据关联算法。     

一种求解连续空间优化问题的改进蚁群算法

蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法,该算法采用分布式并行计算和正反馈机制,易于与其它方法结合,目前虽然已经在离散空间优化领域中得到了广泛应用,但是在求解连续空间优化问题方面的研究相对较少。在介绍基本蚁群算法机制原理和数学模型的基础上,提出了一种用于求解连续空间优化问题的改进蚁群算法。将连续空间优化问题的解向量分解成有限个网格,同时构造了一个与蚁群转移概率相关的评价函数,并借助相遇搜索策略对蚁群算法进行了改进,将各条寻优路径上可能的残留信息素数量限制在一个最大最小区间,以提高改进后蚁群算法的全局收敛性能。仿真实验表明,提出的改进蚁群算法较文献[11]所提出的自适应蚁群算法能更快地找到连续空间优化问题更优良的全局解,从而为蚁群算法求解这类问题提供了一条可行有效的新途径。     

SENSITIVITY ANALYSIS OF THE KNAPSACK PROBLEM： TIGHTER LOWER AND UPPER BOUND LIMITS

In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.     

动态加强CPT解job-shop调度约束满足优化问题

带有相同到达期与交货期的job-shop调度问题(JSSP)作为多种实际生产调度问题简化模型,是一类典型强NP-hard问题.对优化目标是最小化最大完工时间的JSSP问题,建立了约束满足优化问题模型(JSSC-SOP).利用弧一致约束传播算法和深度优先启发式构造活动调度,逐步加入新约束,实现活动调度集的部分列举与寻优.提出3种动态加强约束传播技术(CPT),嵌入搜索过程,提高求解效率.最后通过随机生成的实例,验证了各方法可行性与有效性.     

最优信号控制条件下城市交通离散网络设计问题的备用能力模型

将备用能力的概念与城市交通离散网络设计问题结合在一起,一方面通过对路口的信号进行最佳设置使交通网络可以容纳最大的交通需求量;另一方面,通过在交通网络中添加新的路段来提高整个交通网络的通行能力.给出了最优信号控制条件下城市交通离散网络设计问题备用能力的优化模型及其启发式求解算法.最后,通过一个简单的算例,说明该算法是可行并且有效的.