Abstract: The existing intelligent optimization algorithms for permutation flow-shop scheduling problem are all stochastic optimization methods. One problem with these approaches is that they have poor solution stability. In this paper, a method based on central force optimization algorithm which is a deterministic intelligent optimization algorithm is proposed to resolve this problem. The basic algorithm depends upon the choice of the initial solutions. To deal with this problem, low-discrepancy sequences are used to generate initial solutions to improve the quality of initial solutions. The acceleration and position equations are employed to update the solutions. A sorting method to swap two positions in a solution is used to conduct local searches, to enhance the performance of the algorithm. The benchmarks are used to perform numerical experiments. The presented algorithm is compared with basic central force optimization algorithm, NEH heuristic algorithm, particle swarm optimization algorithm, and firefly algorithm. The results demonstrate that the proposed method not only has better solution stability but also higher accuracy. The presented approach provides a feasible and effective way to solve the permutation flow-shop scheduling problem.

Key words: permutation flow-shop scheduling, makespan, central force optimization, deterministicness

摘要： 目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。

关键词: 置换流水车间调度, 最大完工时间, 中心引力优化算法, 确定性