A New Local Search Algorithm for the Job Shop Scheduling Problem

0　IntroductionThejobshopschedulingproblemwithwhichwearecon cernedconsistsinschedulingasetofjobsonasetofma chinesfortheobjectiveofminimizingthemake span ,i.e .themaximumoftimeneededforfinishingalljobs,whichissubjecttotheconstrainsthateachjobhasafixedprocessingorderthroughthemachinesandeachmachinecanprocessatmostonejobatatime .ThisproblemisNP hardandevenisoneofthehardestcom binationaloptimizationproblems.Itiswellknownthatonlysmallsizeprobleminstancescanbesolvedwithinareasonablecomputa tionalti…     

几种现代优化算法的比较研究

现代优化算法主要包括遗传算法、蚁群算法、禁忌搜索算法。这些算法主要是解决优化问题中的难解问题。由于这些算法在求解时不依赖于梯度信息 ,因而特别适用于传统方法解决不了的大规模复杂问题。介绍了3种算法的基本思想 ,阐述了它们的特点并进行了比较 ,提出了今后研究的方向     

一种模糊高斯混合说话人识别模型

为了研究模糊聚类算法在高斯混合模型（GMM）参数获取方面的应用,采用模糊C均值算法（FCM）进行语音特征矢量的聚类,并结合Tabu搜索算法得到全局最优的聚类结果,进一步用EM算法得到GMM模型参数.使用TIMIT数据库中的语音进行测试,开集和闭集说话人辨认实验都表明,该方法获取的GMM参数比普通EM算法获得的GMM模型参数性能更优,能有效降低说话人辨认系统的误识率.     

Optimal Polygonal Approximation of Digital Planar Curves Using Genetic Algorithm and Tabu Search

Three heuristic algorithms for optimal polygonal approximation of digital planar curves is presented.With Genetic Algorithm (GA), improved Genetic Algorithm (IGA) based on Pareto optimal solution and Tabu Search (TS), a near optimal polygonal approximation was obtained.Compared to the famous Teh-chin algorithm, our algorithms have obtained the approximated polygons with less number of vertices and less approximation error.Compared to the dynamic programming algorithm, the processing time of our algorithms are much less expensive.     

并行工程团队的定量化组织方法

给出了并行工程产品开发团队的组织原则并建立了基于整数规则的团队组织问题数学模型。在这一数学模型的基础上，把团队组织问题分解为一系列相互独立的子问题，并提出了一个基于Tabu搜索的算法来解决此予问题。逐个解决子问题，即可获得整个团队组织问题的解。     

一种混合混沌优化方法及其应用

利用混沌运动所特有的随机性、遍历性和规律性 ,以及禁忌搜索算法的智能性 ,提出了一种基于混沌的混合优化算法 (chaosandtabusearchoptimizationalgorithm ,CTSA)。用本方法对极小值函数优化问题作了数值试验 ,并与其它优化算法进行了比较 ,其效率明显高于其它算法。     

周期性居家医疗护理问题的禁忌求解算法

针对周期性服务需求的居家医疗与护理资源管理问题，提出一种基于插入法和节约算法的禁忌算法。该算法综合考虑客户接受服务的日期、客户的服务等级和客户访问次序，在初始解基础上进行邻域搜索，每次邻域搜索选取部分客户，搜索其所有可能的服务日期、服务等级对应的调度方案，选择成本最低的方案作为邻域搜索的最新解。邻域搜索中变换过的客户将列入禁忌表，在禁忌步长内不予变换。通过多次迭代，求解结果向最优解方向收敛。对随机生成的算例及基于标准 Vehicle Routing Problem （VRP）算例构造的算例进行仿真验证，并与 Rolling Horizon Myopic Planning Approach （RHMPA）算法求解结果对比，实验结果表明，该算法在一定运行时间内适合求解客户规模低于500人的案例，且求解结果优于 RHMPA 算法，多次求解的结果相对误差仅为0．94％。该算法为家庭护理管理和计划调度问题提供了新的算法设计优化思路，对提高当前我国相关产业的管理和调度水平具有现实意义。     

BWC着色问题的一种启发式算法研究

无向图的BWC着色问题是给定两个正整数b和w,判断是否存在这样的着色方案:对b个顶点着黑色,对w个顶点着白色,其它顶点不着色,着黑色顶点集合与着白色顶点集合之间没有任何边相连。BWC的最优化问题,是找出一种最优化着色方案,使得与所有黑色顶点不相连接的着白色顶点数最大。该问题被证明是NP-完全问题。提出了一种基于禁忌表和局部搜索机制的混合启发式算法(BTLSBWC),通过对部分网络图进行测试,结果达到了现有文献计算出的最好值。     

基于GPS/GIS/GPRS技术的动态车辆调度系统设计与实现

针对车辆配送动态调度问题,在以基于并行节约法和禁忌搜索的混合禁忌搜索算法为理论进行静态调度求解的基础上,将新的客户需求设置为虚拟点并以局部调整策略实现VRPB的动态调度计算.开发基于GPS/GIS/GPRS技术的动态车辆调度系统.该系统能够实时跟踪车辆位置,检测新的客户需求,以这些参数作为输入动态地优化车辆配送方案和行驶路径,并通过GPRS将调度结果快速准确地传送给车辆.     

禁忌搜索粒子滤波算法在目标跟踪中的应用

雷达目标跟踪量测系统常受到闪烁噪声干扰,导致传统滤波算法的滤波性能急剧下降甚至发散。针对标准粒子滤波算法存在粒子退化的缺陷,重采样环节引入禁忌搜索思想,提出了禁忌搜索扩展卡尔曼粒子滤波算法,驱散局部最优的粒子集,使其向全局最优位置靠近,提高采样粒子的有效性。结合交互多模型（IMM）,将算法与IMM-PF算法进行仿真比较,结果表明该算法对机动目标具有较优的跟踪性能。