关于"Flow Shop排序问题F2|prmu|∑wj(1-e-rCj)的一个启发式算法"一文的注记

本文指出了文献[1]中2个主要命题是错误的,最后提出了待解决的问题. 文献[1]讨论了如下的排序问题:设有2台机器M1、M2,作业(job)集记为:Jj={J1,J2,…,Jn},n个作业均依同一顺序M1、M2在2台机器上加工,每个作业的两道工序Tij、T2j的加工时间分别为Aj、Bj(j=1,2,…,n),作业Jj的权因子为wj,完工时间为Cj,目标函数为折扣加权总完工时间∑wj(1-e-rCj)[2],其中,r是区间(0,1)中的一个确定数(如取0.1,0.05),也称为折扣因子.     

混合Flow Shop的调度仿真系统及其算法分析

研究了混合Flow Shop的调度问题，调度目标为最小化工件的最大完成时间。文中给出了调度仿真系统的设计，系统由数据库、算法和控制中心用户接口三个模块组成；在算法模块中，排序算法包括了由Flow Shop扩展到混合Flow Shop的多数算法，设备分配采用最先可用机器优先规则。另外，基于CDS虚拟机和Palmer斜度指标的启发式算法，提出了一种改进的CDS算法用于工件排序。在正在开发的混合Flow Shop调度仿真系统中实现了上述所有算法，仿真分析表明改进的CDS算法优于其他启发式算法。     

折扣加权总完工时间的调整时间可分离无等待Flow Shop排序问题

研究3台机器调整时间可分离的无等待F1ow Shop排序问题，目标函数为极小化折扣加权总完工时间。对某些特殊情况，给出问题存在多项式最优算法的充分条件。在此条件下得到求解调整时间可分离的无等待F1ow Shop排序问题的分派规则。     

单机排序1|sp-graPh|∑wj(1-e-rCj)的最优算法

研究约束条件为串并有向图的单机加权总折扣花费问题,通过证明在考虑折扣因子的条件下,模块M的ρ因子最大初始集合I中的任务优先于模块M中的其他任务加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上.     

基于提前/滞后Flow Shop调度问题的混合微粒群算法

提出了一种混合微粒群算法,通过引入禁忌搜索算法和动态设置惯性权重等方法,提高了算法搜索全局最优解的能力并且能够有效避免早熟收敛问题。并将这种算法应用于求解实际的提前/滞后F lowShop调度问题,仿真实验结果表明了混合微粒群算法的可靠性与实用性。     

排序问题Pm，ai|on-line|Cmax的LPT算法

讨论了任务实时到达的平行机在线排序问题。Chen和Vestjens证明了LPT算法的界为3／2。将这一结论推广到了处理机具有准备时间的情况。     

单抓钩动态排序的启发式算法

计算机控制的抓钩被广泛地用于先进制造系统中的材料搬运.由于抓钩排序问题直接影响这些系统的生产率和安全性,因此,有必要对此进行研究.研究了单抓钩动态排序的问题,提出一个启发式算法,该算法是通过解一系列静态问题来解动态问题的.静态问题的解是使用顺序搜索和线性规划结合的方法,而线性规划模型对给定的顺序求最优解.量化的示例表明所使用的方法是有效的.     

一种新的求解Flow Shop问题的启发式算法

同顺序 Flow Shop问题是一个著名的 NP难题 ,至今尚未找到有效算法 .总体来讲 ,求解该问题的启发式算法主要可分为规则式算法和迭代式算法两种 .对该问题有很多求解目标 ,如最小加工周期 ( min makespan) ,工件的最小平均在系统的停留时间 ( min mean flow tim e)等 .本文以求解最小加工周期为目标 ,基于目前已知的性能最好的算法 NEH算法的基本思想 ,提出了一种新的启发式算法 -组合指标算法 .大量的数据实验表明 ,新的算法具有很好的计算结果 ,而且这种算法可以说是给出了求解 Flow shop问题的一种新的思路和方向.     

多目标Flow Shop调度问题的改进TA求解算法

提出一种根据搜索进展自适应设定门槛值和邻域搜索次数的改进TA算法．对无优先级双目标FlowShop问题进行求解,并与现有启发式算法进行了比较．计算比较结果表明：所提算法可以求得稳定、高质量的解．     

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

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

A Heuristic Algorithm for QoS Multicast Routing

In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algorithm deals with delay and bandwidth constraints and has low cost. The HAQMR attempts to significantly reduce the overhead for constructing a multicast tree, the proof for correctness of the HAQMR is given, and the performance of the HAQMR is evaluated by simulations. The study shows that HAQMR provides an available approach to QoS multicast routing.     

PDES信息管理的一种启发式算法

分析了并行离散事件仿真中同步信息的相关性,并提出了对这些信息进行管理的一种启发式算法,该算法包括对信息的排序和分配．最后用一个例子说明这种启发式算法．     

A Heuristic Method for Some NP|hard Robust Combinatorial Optimization Problems

１　ＩｎｔｒｏｄｕｃｔｉｏｎＧｅｎｅｒａｌｌｙ,ａｎｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｃａｎｂｅｗｒｉｔｔｅｎａｓｔｈｅｆｏｌｌｏｗｉｎｇｆｏｒｍ（Ｐ）　　ｚｐ＝ｍｉｎｘ∈Ｘｆ（ｘ）,（１）ＷｈｅｒｅＸｉｓｔｈｅｓｅｔｏｆｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｓ,ａｎｄｆ（ｘ）ｉｓｔｈｅｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎ．Ｂｕｔｉｎｔｈｅｒｅａｌｗｏｒｌｄ,ｄｕｅｔｏｔｈｅｕｎｃｅｒｔａｉｎｔｙｏｆｔｈｅｆｕｔｕｒｅ,ｔｈｅｉｎｐｕｔｄａｔａｏｆｔｈｅｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎｆ（ｘ）ｄ…     

提箱作业优化问题的嵌套启发式算法

针对集装箱堆场进口集装箱的提箱作业计划问题,建立了以作业总成本最小为目标的多阶段决策优化模型,构造了内外嵌套两层结构的优化算法,内层算法实现最短路径搜索子模型,外层算法实现倒箱策略优化子模型.对内外层优化算法,设计了基于启发式A*与GA算法分别组合的4种方案.实例分析表明:各算法组合方案具有相同的有效性,当问题规模较小时,A* A*较好,但问题规模增大时,GA GA较好.     

A Heuristic Algorithm for the Two-Machine Flowshop Group Scheduling Problem

1 .ＩＮＴＲＯＤＵＣＴＩＯＮＴｈｅｇｒｏｕｐｓｃｈｅｄｕｌｉｎｇｈａｓｂｅｅｎａｎａｃｔｉｖｅａｒｅａｏｆｒｅｓｅａｒｃｈｓｉｎｃｅｇｒｏｕｐｔｅｃｈｎｏｌｏｇｙ (ＧＴ)ｗａｓｗｉｄｅｌｙａｐｐｌｉｅｄｉｎｉｎ ｄｕｓｔｒｉａｌｐｒｏｄｕｃｔｉｏｎｓｙｓｔｅｍｓ .ＩｎｔｈｅＧＴｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ ,ｊｏｂｓｔｏｂｅｐｒｏｃｅｓｓｅｄａｒｅｃｌａｓｓｉｆｉｅｄｉｎｔｏｇｒｏｕｐｓａｎｄａｌｌｊｏｂｓｉｎａｐａｒｔｉｃｕｌａｒｇｒｏｕｐｎｅｅｄｓｏｍｅｃｏｍｍｏｎｓｅｔｕｐａｔｅａｃｈｍ…     

系统冗余优化设计的启发式算法

可靠性设计是系统设计的重要环节,系统冗余设计是可靠性设计的重要方法,也是提高系统可靠性的有效手段。在Sharma算法思路的基础上,考虑了新的试探方式,试图给“最有可靠度效益的级”增加冗余,并采用级替换因子判断给系统中的哪一级增加冗余对系统最有效益。在替换因子的考虑上,提出两种算法,并举例说明算法如何在部件可靠度确定的情况下,考虑系统设计代价(费用,重量,体积等),优化配置部件的冗余数。     

一种求解TSP的生物信息启发式遗传算法

遗传算法是解决旅行商问题（traveling salesman problem,TSP）的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题,提出一种生物信息启发式遗传算法（bioinformation heuristic genetic algorithm,BHGA）。通过优化适应度函数和初始种群,引入生物信息学中的基因序列对比手法进行交叉重组排序,采用基因逆转操作进行变异,对遗传算法进行改进,使算法能够加快收敛速度,得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解,实验仿真结果表明：该算法在中小型规模的TSP中求解效果好且结果稳定。     

一种启发式并行逻辑模拟划分算法

随着并行计算机应用的日趋广泛,在大型数字系统设计验证中,并行逻辑模拟已成为提高模拟验证效率的重要技术途径。并行逻辑模拟算法性能受多种因素影响,其中电路划分算法是直接影响并行逻辑模拟性能的主要因素。提出了一种利用预模拟信息的启发式划分算法,可以明显改善多 Ｃ Ｐ Ｕ 的负载平衡效果,减少处理器间通讯量,有效提高并行逻辑模拟效率。     

二维Strip Packing问题的嵌套启发式算法

二维Strip Packing问题(2SP)是二维装箱问题中的经典NP-Complete问题。采用两层嵌套迭代算法:第一层采用遗传算法决定矩形排放次序;第二层提出水平线择优匹配算法(LSBF),算法是基于底部左齐择优匹配算法(LLABF)和快速启发式法(FH)的改进算法,决定矩形排放规则。包含特殊结构的benchmark和新的随机算例等的排样结果表明算法的有效性。     

关于带有传输时间的F2|perm|Cmax排序问题的一个新算法

考虑传输时间的同顺序排序问题是在机器人设计及柔性制造系统中有着广泛应用的一类排序问题。