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

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

导引式局部搜索在一类过度约束VRP中的应用

针对一类带时间窗口和容量约束的车辆路线问题(VRP),给出了在过度约束即不存在满足所有约束的可行解的情况下,能够最小化约束违反成本的一种新颖的导引式局部搜索(GLS)算法。该算法通过不断动态修改原问题的目标函数,既保留了局部搜索算法的高效率,又有效克服了局部极小解的局限性,因而能够较快地返回一个满意解。求解示例表明,该算法在求解此类问题时,性能要优于常用的禁忌搜索算法。     

局部邻域搜索在对地观测卫星任务规划中的应用与扩展

任务规划作为一项重要技术,已经广泛应用于卫星的星载与地面控制系统中,以提高卫星任务执行的鲁棒性、可预测性和高效性。描述了对地观测卫星任务规划问题及特点,给出了对地观测卫星任务规划的一般处理过程。针对约束规划中的局部邻域搜索算法不能有效反应对地观测卫星成像的时效性和分辨率等需求的问题,提出了基于动态优先级的局部邻域搜索算法。算法在经典约束满足问题求解算法的基础上,主要扩展了任务优先级的定义及在搜索过程中的启发式。通过典型的仿真算例,验证了算法的可行性和有效性。     

基于CSP的Job shop调度算法研究

针对一类典型的约束满足问题——Job shop调度问题，提出一种CSP调度算法框架，详细讨论CSP调度算法中的工序开始时间窗、一致性预处理、搜索空间概率模型、工序排序启发、开工时间排序启发的求解方法。仿真结果表明CSP调度算法在较小的计算时间代价下，获得了FT10标准调度问题的近优解。     

一类人员调配问题的导引式局部搜索算法

描述一类生活实践中常见的可能存在过度约束的人员调配问题．这类问题用传统的分支定界等精确搜索算法求解时比较困难。本文则探讨了一种较新的超启发式搜索方法导引式局部搜索在求解这类过度约束人员调配问题中的应用。与其他常用的超启发式搜索算法如禁忌搜索和模拟退火的比较表明，GLS在此类问题的求解质量、求解速度和算法鲁棒性方面具有较好的综合性能。     

一类新的模糊约束满足问题的建模与求解

从模糊理论的角度讨论了软约束满足问题,即把约束中带有不确定性的参数刻画为模糊变量,定义了一类新的模糊约束满足问题(FCSP).然后,利用可信性测度度量该类问题中约束成立的可能性,并以所有约束的联合可信性作为目标函数,从而将FCSP问题转化为无约束优化问题.利用模糊模拟技术来估计目标函数中模糊事件的可信性,在此基础上设计了基于模糊模拟的猴群算法用来对无约束优化问题进行求解,以便获得原FCSP问题的约束一致解.最后,给出了数值例子来说明上述方法的可行性和有效性.     

中继卫星动态调度问题研究

针对任务时间要求改变、增加新任务和资源故障三类扰动因素分别建立了中继卫星动态调度问题的动态约束满足模型;设计了动态扩展/删除树搜索算法对模型求解,算法利用动态扰动测度中删除任务权重和调整任务权重两个参数的比指导搜索过程,合理协调扩展搜索和删除搜索,从而将对动态调度方案的需求反映到搜索过程之中,提高了算法的可用性和效率;仿真结果验证了该方法的有效性。     

基于约束满足的多卫星调度模型研究

卫星调度是空间资源管理的一项重要内容,其本身也是一类复杂的资源分配问题。约束满足技术是求解复杂资源分配问题(constraintsatisfactionproblem,CSP)的有效方法。在约束满足问题的理论基础上,首先分析了多卫星调度问题的约束条件(包括任务约束、关联约束和互斥约束);建立了多卫星调度问题的模型;最后,以地球资源观测卫星为对象,给出了示例。     

面向应急成像观测任务的多星协同调度方法

针对应急条件下的成像观测任务,设计了多星协同调度框架,将多星协同调度问题分解为任务排序主问题和资源匹配子问题。分析了多星协同调度中的主要约束条件,以任务收益为优化目标构建问题的约束满足模型,并应用改进粒子群优化算法进行求解。详细介绍了算法中的编码、解码、移动、变异等操作,给出算法时间复杂度的计算公式。通过仿真实验,对算法的有效性进行了验证。     

求解约束优化问题的改进算法及其收敛性分析

针对约束优化问题,提出一种改进差分进化算法。为了利用种群中不可行解的信息,新算法设计了一种改进DEB准则;为了进一步提升算法在受限空间的寻优能力,新算法设计了一种交叉概率CR和缩放因子F的生成方法。13个标准的测试函数的实验结果证明,与目前求解约束优化问题最优秀的算法相比,新的改进差分进化算法仍然非常有竞争力。     

基于迭代局域搜索的智能优化算法求解车辆调度问题研究

在对基本车辆调度问题(VRP)进行简单描述的基础上,提出了求解该问题的两类混合策略.这两类策略均采用两阶段的思想:第一阶段,利用节约法对顾客进行聚类;第二阶段,构造适合求解VRP的改进dynasearch算法,且将基于随机kick的迭代局域搜索算法与改进dynasearch算法相结合,提出了迭代dynasearch算法.通过实验仿真,验证了这两类策略在很大程度上能改进问题的解.     

基于改进粒子群算法的系统辨识新方法

提出了一种利用改进的粒子群优化算法对系统进行辩识的方法.该方法是将典型的数学模型的相互组合而构成系统模型的新辨识方法,即首先将系统结构辨识问题转化为组合优化问题,然后采用粒子群优化算法同时实现系统的结构辨识与参数辨识.为了进一步增强粒子群优化算法的辨识性能,提出了利用一种改进的粒子群优化算法.最后,给出了仿真示例,结果验证了所给的系统辨识方法的合理性和有效性.     

不确定处理时间批处理过程的鲁棒调度新策略

针对化工批处理调度过程中处理时间不确定的问题,建立了具有分解结构的调度模型,提出了一种新的鲁棒调度策略.策略由基本调度策略和在线调整两部分组成,分别与模型的主问题和子问题相对应.提出了基于遗传算法的分解算法求解模型,以获取具有鲁棒性和最优性的基本调度策略.通过对子问题的分析,提出了运用简单的推理进行在线调整的方法,无需复杂计算,并运用动态规划的原理说明了该方法的可行性和最优性.最后用实例说明了该鲁棒调度策略的有效性.     

一种再制造物流网络设施定位优化方法

针对包含正向和逆向的再制造物流网络,提出一种由3种设施组成的2层物流设施定位优化方法,并给出0-1整数规划模型.基于遗传算法的全局搜索能力,全面考虑了正向流和逆向流及其它们之间的相互约束处理,避免了传统拉格朗日启发式算法中求上下限的繁琐计算过程.仿真实验表明提出方法的有效性.     

基于协同进化的航天测控资源优化调度

航天测控资源调度是一个具有很强工程背景的复杂问题,针对其特点,研究了一种基于协同进化的优化调度算法。在描述问题并给出调度模型的基础上,基于协同进化的思想,设计了和问题特征结合的遗传算法编码,对算法的算子和进化策略进行了描述,给出了算法的完整流程。通过算例表明,该算法整体上优于先到先服务（first coming first serving, FCFS）算法、任务综合优先度（task synthesis priority, TSP）算法和简单遗传算法（simple genetic algorithm, SGA）。     

最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。     

电子商务中订单配送优化模型及两阶段算法

针对电子商务环境下订单配送问题的特点,建立了以最小化车辆行驶费用及订单惩罚费用为目标的数学模型.设计了两阶段启发式求解算法.第一阶段用禁忌搜索算法求解在作计划日当天已到交货期的订单的基本配送问题;第二阶段考虑了订单的未来信息,用基于评价值的贪婪插入算法将未到交货期的订单与已有的配送方案进行整合配送,该方法能够提高车辆的使用率及配送企业的配送效率.实验结果验证了模型的合理性及算法的有效性.     

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.     

Heuristic algorithm for RCPSP with the objective of minimizing activities'''' cost

1.INTRODUCTIONPartner selection is an i mportant problemin supplychain management.When we design a constructionsupply chainin which general contractor is the kernelentity,general contractor’s project scheduling will beconstrained by the capacities of the renewable re-sources supplied by the partners such as subcontrac-tor,ready-mix concrete vendor.We should considerhowto get theleast activities’cost of the project withthe constraints of due date and resource capacities ofevery partner re…     

同时送取货的随机旅行时间车辆路径问题方法

建立了同时送取货的随机旅行时间车辆路径问题(STT-VRPSPD)的机会约束规划模型,构建了分散搜索算法求解策略.分散搜索算法中,针对STT-VRPSPD问题的复杂特性,构造了解的改进策略、组合策略,并采用改进的节约算法构造分散搜索算法初始解,从而使文中设计的分散搜索算法更加适应STT-VRPSPD问题特有的负载波动性.仿真实验中,首先对分散搜索算法的参数设置进行分析,确定了最优参数组合;然后基于经典的Dethloff算例数据,构造了STT-VRPSPD的测试算例,并对分散搜索算法和遗传算法进行了对比分析,结果表明,分散搜索算法对于STT-VRPSPD的求解质量优于遗传算法.