双目标无等待流水线调度的加权混合算法

Weighed Hybrid Heuristics for Bi-objective No-wait Flow Shops Problem

针对最小化"总完工时间"和"最大完工时间"的双目标无等待流水线作业调度问题提出了一种粒子群加权混合优化算法,通过随机加权的方式将其转换成单目标问题,并应用基于升序排列的ROV(ranked-order-value)编码规则,将粒子群优化算法应用于无等待流水线作业调度问题。为了提高算法的性能,增强算法的搜索能力,提出的混合算法应用了NEH方法构造初始种群,在一个较好的初始值上进行粒子群优化,为防止种群陷入局部最优造成早熟,在粒子群每次迭代之后对全局最优解加入扰动并进行变邻域搜索。仿真实验结果表明该混合调度算法具有良好的性能。

A weighed hybrid particle swarm optimization was introduced for bi-objective no-wait flow shops to minimize makespan and total flow-time problem, which makes the problem into single objective by random weighted and apply PSO on no-wait flow shops problem with the rule based on ranked-order-value. In order to improve the optimization of PSO and increase the algorithm＇s exploring ability, we can improve the performances through constructing the initial swarm by using NEH and executing PSO on a better initial value. After each step of PSO, we interrupted the global best value and execute the Variable Neighborhood Search for avoiding the swarm fall into the local best value. Passing through the testing experiments, this hybrid scheduling algorithms precedes other scheduling algorithms.