多目标无等待流水线调度的离散果蝇算法
Discrete Fruit Fly Algorithm for Multi-Objective No-Wait Flow Shop Scheduling Problem

摘要: 本文提出了一种离散多目标果蝇优化算法，求解以最大完工时间和机床空闲时间最小化为目标的无等待流水线调度问题。与传统的果蝇算法不同，首先，该算法采用基于工序的编码方式，其次，利用GLOVE发生器进行初始化，提高初始解的分散度；最后，利用简单但有效的插入方法在邻域内进化精细搜索，增强算法的全局开发能力。仿真试验表明了所提果蝇算法的有效性和高效性。

Abstract: This paper presents a Fruit Fly Optimization Algorithm (FOA) for solving the multi-objective no- wait flow shop scheduling problem (MNFSP) with makespan and idle time criteria. Firstly, unlike the traditional FOA, the proposed algorithm applies the job-permutation-based representation. Secondly, initialization method based on the Glove generator has a uniform distribution of the so-lutions. Finally, a simple but effective insert search algorithm is made to improve global exploration. Computational results show that the FOA presented in this paper is very effective and efficient for the MNFSP.

参考文献

[1]	胡旺, Gary YEN, 张鑫. 基于Pareto熵的多目标粒子群优化算法[J]. 软件学报, 2014, 24(5): 1025-1050.
[2]	毕孝儒, 张黎黎, 贺拴, 等. 面向无等待多目标柔性车间调度问题的遗传蜂群优化算法[J]. 研究与开发, 2015(8): 11-16.
[3]	刘志雄, 王雅芬, 张煜. 多种群果蝇优化算法求解自动化仓库拣选作业调度问题[J]. 武汉理工大学学报, 2014, 36(3): 71-77.
[4]	王海军, 涂凯, 闫晓荣. 基于果蝇优化算法的GRNN模型在边坡稳定预测中的应用[J]. 水电能源科学, 2015, 33(1): 124-126.
[5]	王雪刚, 邹早建. 基于果蝇优化算法的船舶操纵响应模型的辨识[J]. 大连海事大学学报, 2012, 38(3): 1-4.
[6]	公茂果, 焦李成, 杨咚咚, 等. 进化多目标优化算法研究[J]. 软件学报, 2009, 20(2): 271-289.
[7]	Glover, F. (1998) A Template for Scatter Search and Path Reclinking. Artificial Evolution. Lecture Notes in Computer Science, 1363, 1-51.
[8]	郑晓龙, 王凌, 王圣尧. 求解置换流水线调度问题的混合离散果蝇算法[J]. 控制理论与应用, 2014, 31(2): 159- 164.
[9]	潘玉霞, 潘全科, 李俊青. 蛙跳优化算法求解多目标无等待流水线调度[J]. 控制理论与应用, 2011, 28(10): 1363- 1370.