置换流水车间调度的蚁群优化算法

提出了一种求解置换流水车间调度的蚁群优化算法。该算法的要点是结合了NEH启发式算法和蚁群优化方法。理论论证和对置换流水车间调度问题的基准测试表明了该算法的有效性。     

改进的蚁群算法求解置换流水车间调度问题

针对蚂蚁算法在求解置换流水车间调度问题时易陷入局部最优以及计算时间较长的缺点,对最大最小蚂蚁系统(MMAS)进行了改进。在该算法中,采用NEH启发式算法提高初始解质量,并通过自适应的调节策略进一步提高蚁群算法的搜索能力。运用提出的混合算法求解Taillard基准测试集,并将测试结果与其他算法进行比较,验证了该调度算法的有效性。     

混合遗传NEH算法在流水车间调度中的应用

针对流水车间调度问题提出一种混合遗传NEH算法,以提高求解效率.NEH算法是一种高效的构造性算法具有很强的邻域搜索能力,而遗传算法则能有效地提供全局搜索.据此,新算法首先通过选择、交叉和变异操作,经过迭代获得一个较好解,然后在这个解所在的特定邻域内进行改进的NEH搜索,以获得更好解,经过NEH搜索后求得的最好解作为一个新个体加入下一代种群中,继续进行遗传操作.通过对流水车间调度的最小化最大完成时间问题的仿真实验结果表明,新算法有明显改进.     

置换流水车间调度问题的两阶段分布估计算法

针对置换流水车间调度问题,以最小化总流水时间为目标,提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham,NEH）启发式构造一个较优的初始个体,然后随机生成初始种群,为保留种群的多样性,提出一种择优机制来选择个体并建立概率模型,同时在当代种群中利用精英机制保留当代种群中的最优解,最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索,来提高分布估计算法的全局搜索能力,阻止其陷入局部最优解。通过对算例进行实验、对比和分析,证明该算法的可行性和有效性。     

基于新邻域结构的Memetic 算法求解流水车间调度问题

流水车间调度是一类典型的生产调度问题,属于NP-难问题.针对传统的最优化方法难以求解大规模问题,提出了一个Memetic算法,在算法的局部搜索中使用一种新型的基于NEH的邻域结构,并且其邻域规模随着搜索的进行能够动态变化,可以大大提高算法的搜索能力.通过对标准Benchmark问题的测试,所得结果表明提出的基于新邻域结构的Memetic算法具有较好的性能,并且优于已有文献中的粒子群算法.     

多构造蚁群优化求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种多构造蚁群优化求解算法。在该算法中,蚁群采用两种方式构造解,分别是基于NEH(Nawaz-Enscore-Ham,NEH)启发式算法和Rajendran启发式算法,并根据解的质量,自适应地调整两种构造方式在蚁群中所占的比例。对置换流水车间调度问题的基准问题测试表明,提出的算法是有效的。     

多目标混合遗传算法求解流水车间调度问题

为高效地求解多目标流水车间调度问题,提出了一种多目标混合遗传算法,此算法将局部搜索融入进化计算中,采用非劣解并行局部搜索策略,并依据基于Pareto支配关系的个体排序数和密度值进行适应度赋值,以加速算法的收敛,保持群体多样性.仿真结果表明,新算法能够有效地解决多目标流水车间调度问题.     

改进的萤火虫算法求解阻塞流水线调度问题

为了提高阻塞流水线调度问题的求解性能,提出了一种改进的萤火虫算法来求解阻塞流水线调度问题.首先,提出一种离散机制把个体的实数编码形式转换成离散的作业序列,从而使算法能够应用于离散问题求解;其次,设计一种双重初始化方法,并将NEH启发式方法应用到初始化中来,使算法有一个较优的初始化环境,提高初始种群的解的质量;此外,重新设计了算法中个体的移动方式来增大搜索域;最后,以一定概率对种群中的个体进行局部搜索,加强算法的局部搜索性能.通过对Taillard数据集中部分实例进行求解,实验结果验证了新算法的有效性.     

求解流水车间调度问题的混合粒子群算法

针对最小化流水车间调度总完工时间问题,提出了一种混合的粒子群优化算法(Hybrid Particle Swarm Algorithm,HPSA),采用启发式算法产生初始种群,将粒子群算法、遗传操作以及局部搜索策略有效地结合在一起。用Taillard’s基准程序随机产生大量实例,实验结果显示:HPSA通过对种群选取方法的改进和搜索范围的扩大提高了解的质量,在性能上均优于目前较有效的启发式算法和混合的禁忌搜索算法,产生最好解的平均百分比偏差和标准偏差均显著下降,最优解所占比例大幅度提高。     

A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem

This paper proposes a hybrid modified global-best harmony search (hmgHS) algorithm for solving the blocking permutation flow shop scheduling problem with the makespan criterion. First of all, the largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Second, an efficient initialization scheme based on the Nawaz-Enscore-Ham (NEH) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. Third, harmony search is employed to evolve harmony vectors in the harmony memory to perform exploration, whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Moreover, a new pitch adjustment rule is developed to well inherit good structures from the global-best harmony vector. Computational simulations and comparisons demonstrated the superiority of the proposed hybrid harmony search algorithm in terms of solution quality.     

基于改进离散和声算法的批量流水线调度研究

针对批量流水线调度问题,提出了以总流经时间为目标的改进离散和声算法。与基本的和声算法相比,该算法首先采用了基于工件序列的编码方式,使其直接应用于调度问题,同时运用NEH和SWAP方法产生初始和声库,保证了初始种群具有较高的质量和多样性。使用自适应和声微调概率参数和INSERT方法产生新解,提高了算法的优化性能。为了提高算法的局部搜索能力,结合交换扰动策略和插入邻域搜索算法给出了两种混合求解策略。仿真实验表明所提算法的有效性。     

Flow shop问题的嵌套分区优化调度方法

介绍了嵌套分区算法(NP)的基本思想, 并用于求解流水作业优化调度问题. 算法用嵌套分区树来描述流水作业调度问题, 对可行域进行系统性分区, 然后集中搜索有优良解的区域. 在每一步迭代中, 算法跟踪最有希望的分区, 并结合启发式算法和邻域搜索来实现分区转移. 仿真实验表明, 该算法比单纯的启发式算法和邻域搜索有较好的寻优能力.     

扩展job shop模型的启发式批量流水线调度算法

提出了改进的job shop模型,定义了工作中心以及关键节点的概念。将流水线与批量调度策略引入到新的模型中,并在此基础上提出了一个关于扩展job shop模型的启发式批量流水线调度算法。在关键节点进行选择时,通过回溯计算其余产品的开始时间,使用贪心算法选择优先级最高的产品进行排序。该优先级法则由三个优先级变量组合而成,分别囊括了价值高低、时间紧要程度以及剩余加工时间这三个影响因素。进行加工时,设定最小加工批量,在一个工序内实现多套设备的并行加工,同时在两个相邻工序之间实现流水线加工,从而缩短加工时间,提高了生产效率。通过仿真表明该策略能取得较好的结果。     

求解流水线调度问题的万有引力搜索算法

研究了以最大完工时间为目标的流水线调度问题,使用万有引力算法求解调度问题,提出了一种最大排序规则,利用物体间各个位置分量值存在的大小次序关系,并结合随机键编码的方法产生,将物体的连续位置转变成了一个可行的调度方案;提出了一种边界变异的策略使得越界的物体不再聚集在边界上,而是分布在边界附近的可行空间内,从而增加种群的多样性;结合交换算子和插入算子提出了一种新的局部搜索算法,有效地避免了算法陷入局部最优值,进一步提高了解的质量.最后证明了算法的收敛性,并且计算了算法的时间复杂度和空间复杂度,仿真实验说明了所得算法的有效性.     

改进细菌觅食算法解决零空闲流水线调度问题

针对零空闲流水线调度问题,建立以最大完成时间为目标的数学模型,并提出了解决问题的改进细菌觅食优化算法。在标准细菌觅食优化算法的基础上,引入了交叉优化算子、混合复制策略以及一种基于健康度和适应度共同控制的自适应迁徙概率,以加速算法的收敛过程,并有效抑制精英个体的逃逸,防止解发生退化。采用路径编码方式,通过MATLAB算例试验,表明了改进细菌觅食优化算法在求解零空闲流水线调度问题上的可行性和有效性;同时,运用两种方式产生初始解：随机方式和NEH方法,进一步验证算法的鲁棒性。     

求解零空闲流水线调度问题的改进蚁群算法*

在研究蚁群算法的基础上,解决零空闲流水线调度问题的最大完工时间。改进了蚁群算法中信息素密度的初始化方法和更新规则,结合快速邻域搜索算法,解决算法易陷入局部收敛的缺点,提出了该算法解决零空闲调度问题的最佳求解策略。仿真实验表明,该算法具有高效性和优越性。     

求解阻塞混流生产机器人制造单元调度问题的分支定界算法

针对阻塞混流生产机器人制造单元调度问题,为了同时优化机器人运行顺序和工件加工顺序,提出了分支定界算法。首先,定义机器人活动,将双排序转化为单排序;其次,构建顺序插入规则生成可行解;最后,依据顺序插入规则,设计了分支过程。通过计算随机生成算例,计算结果表明：工作站个数为3时,分支定界算法得到的目标函数值与CPLEX相同,但平均运行时间比CPLEX降低38.58%,证实了分支定界算法的有效性;工作站个数大于3时,与CPLEX相比,在同等时间内,有85.19%的算例搜索到更好解,因此,对于大规模情形,分支定界算法更有价值。