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 solutions. 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.

Keywords:Fruit Fly Optimization Algorithm, No-Wait Flow Shop Scheduling Problem, Multi-Objective

多目标无等待流水线调度的离散果蝇算法

潘玉霞¹，贾保先²

¹三亚学院，公共计算机教学部，海南 三亚

²聊城大学计算机学院，山东 聊城

收稿日期：2016年4月20日；录用日期：2016年5月14日；发布日期：2016年5月17日

摘 要

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

关键词 :果蝇优化算法，无等待流水线调度问题，多目标

1. 引言

多目标优化问题是需要同时处理多个相互冲突和相互影响的目标，一个子目标的改善有可能会引起另一个或者另几个子目标的性能降低，需要在他们中间进行协调处理。起初，多目标优化问题往往通过加权等方式转化为单目标问题，但此方法效率较低且对权值和次序较为敏感。因此，后来发展了基于Pareto最优解集(Pareto-optimal set)或非支配解集(Nondominated Set)的群体智能算法解决多目标问题。文 [1] 根据无等待多目标优化问题和粒子群算法的特征，采用近似Pareto前端的分布熵及其变化来估计种群进化状态，并依据这些进化过程反馈信息设计具有动态平衡开发能力的进化策略。文 [2] 为了解决无等待柔性车间调度的多目标优化问题，结合灰色失联分析和熵理论，提出灰互信息适应度分配策略，以评价Pareto解的优劣。

果蝇优化算法(Fruit Fly Optimization Algorithm, FOA)是由台湾博士潘文超于2011年提出的一类全局进化优化算法。该算法源于对果蝇觅食行为的模拟，已在自动化仓库拣选作业调度问题 [3] ，边坡稳定预测问题 [4] ，船舶操纵响应模型的辨识问题 [5] 等方面得到成功的应用。进化算法通过在代与代之间维持由潜在解组成的种群来实现全局搜索，这种从种群到种群的方法对于搜索多目标优化问题的pareto最优集是很有用的 [6] 。

2. 多目标无等待流水线调度问题 (Multi-Objective No-Wait Flow Shop Scheduling Problem, MNFSP)

2.1. 无等待流水线问题描述

无等待流水线调度问题要求加工的任务从开始到结束必须连续进行，即同一工件的两个相邻工序之间没有间隔。此类调度广泛存在于食品加工、炼钢、制药等生产领域。该问题可以描述为：有个工件

在台机床上加工，工件在台机床上的加工操

作为。同时需要满足如下条件：所有工件启动和运输时间包含在工件的加工时间内，均可在零时刻进行加工，每个工件在各机床上的加工顺序相同。为了满足无等待的条件，推迟工件在第一台机床上的加工

时间，使得工件在每台机床上的完成时间必须等于其在下一台机床上的开始加工时间，即的完成时间必须等于的开始时间。目的是得到一个可行调度，求其Pareto最优解集。该问题的模型如图1所示。

图1. 无等待流水线调度问题

2.2. 调度优化目标计算

提出以最大完工时间、机床最大空闲时间为指标对无等待调度问题进行研究。其中最大完工时间是从第一个工件开始加工计时到最后一个工件完成时间，机床空闲时间为各工件加工的空隙时间和。优化最大完工时间有利于提高生产率，降低工件的生产周期，优化机床空闲时间可以提高机床的利用率。

假设工序按机床1到的顺序进行加工，其中为工件在机床上的加工时间，代表工件和在第一台机床上的开始时间差。各工序的加工时间已知，工件在机床上的完成时间的计算公式为：

(1)

(2)

其中的计算公式如下：

(3)

那么工序的最小化最大完成时间计算公式如下：

(4)

最小化最大机器空闲时间的计算公式如下：

(5)

两个目标值算法的时间复杂度分别为是O(n)，O(mn)。为了降低算法复杂度，提前定义变量代表第一个工件与第个工件在第一台机床的开工时间差

(6)

为工件在第一台机床到第台机床上的加工时间和

(7)

(8)

(9)

通过公式(8)，(9)所示算法的时间复杂度降低为O(1)，O(n)。

2.3. Pareto最优解集

不同于单目标优化问题需要求得一个最优解，而多目标问题的优化就是寻找Pareto最优解集。在有限集合上，给出两个目标的调度优化问题，，若，假定支配，则，。在中如果有一个没有被任何其他解所支配，则称它为Pareto最优解或非支配解。所有非支配解或Pareto最优解的集合成为Pareto最优解集。

3. 基于MNFSP的离散果蝇算法

果蝇优化算法的基本原理是初始化种群的中心位置，利用敏锐的嗅觉进行搜索，即根据中心位置随机产生多个邻域解。计算各可行解的味道浓度，即评价值，然后利用视觉从中选择较好的解，更新替换中心位置，然后进行迭代寻优，以更好的进靠近食物源。FOA在整个迭代寻优过程中，在连续空间中产生新个体的方法不适合解决MNFSP。故运用FOA算法的主体流程，对其优化过程进行离散化是算法成功应用于MNFSP的关键。基于以上分析，提出了离散果蝇算法(Discrete Fruit Fly Optimization Algorithm DFOA)。

3.1. 算法编码和初始化

种群中每个果蝇个体对应问题中的一个解，即工件的完整加工序列，如为4个工件的调度实例解。

果蝇初始个体产生采用GLOVE [7] 发生器产生一组分布均匀的工件排列。对于一个给定排序，GLOVE发生器可得到n/2个分散均匀的排列。随机变化给定排列，即可得到足够多的初始果蝇个体，即可构成一个分散性较好的初始种群。

3.2. 嗅觉和视觉搜索

影响FOA算法性能的核心是如何生成嗅觉阶段的邻域个体 [8] 。一般全局Pareto最优解集中在局部Pareto最优解附近；因此利用Pareto最优解集中的解产生新解的质量较高。

对于MNFSP来讲，插入操作是最有效的邻域解生成方法 [8] 。因为子代可以很好的继承父代个体的优良基因，可以充分利用非支配解信息优势，引导算法向Pareto最优前沿进化。嗅觉阶段在Pareto最优解集中随机选取一个果蝇个体，对其执行插入邻域操作步骤如下：

步骤1：当前个体记为，通过对进行三次插入操作得到调度。

步骤2：从中随机选取一个工件得到调度用公式(8)(9)分别计算和。

将工件插入到所有可能的位置，得到调度，如图2所示。

指标计算公式如下：

(10)

图2. 插入邻域完工时间和空闲时间快速计算方法

(11)

步骤3：代表临时非支配解集，保存插入过程中得到的非支配解。

步骤4：若中有解没有被AS中的解支配，则更新AS。

步骤5：若中有解支配，则替换之；若互不支配，则随机选择一个替换。

确定新解是否为非支配解，若为非支配解，则更新AS，同时选择较好的解替换当前解。

4. DFOA算法流程

基于上述设计，DFOA算法的流程步骤如下所示：

步骤1：设置参数，初始化种群。

步骤2：评价果蝇个体，并判断是否为非支配解，更新AS。

步骤3：在AS中随机选择一个非支配解，利用算法的嗅觉和视觉部分产生新的个体，并更新AS。

步骤4：判断终止条件是否满足，是则转到步骤5，否则转到步骤3。

步骤5：算法终止。

5. 仿真实验

5.1. 实验设置

将本文所提算法DFOA与文献 [9] ESFLA进行比较，通过不同规模的解决6个标准问题进行有效性验证。几种算法都在处理器为Intel(R)Core i3 2.13 GHZ、内存为2G的PC机上，采用C++编码进行测试。对于每个算例，两种算法分别独立运行20次，为第个算法得到的非支配解集，从中选出非支配解集作为参考非支配解集。算法最大运行时间为微秒。采用两个性能指标来评价算法所得到的非支配解集：距Pareto边界的平均距离、非支配解的比率。

5.2. 仿真结果对比

对文献 [9] 提出的ESFLA算法进行修改，按文中规定的参数进行设置，并将其应用于求解基于最大

表1. DFOA、ESFLA算法的比较

表2. DFOA和ESFLA 算法的比较

完工时间和最大机床空闲时间的多目标无等待流水线调度问题。两种算法采用相同的终止条件。AVG、MIN和MAX分别代表20次仿真实验目标值的平均值、最小值和最大值。结果如表1，表2所示。

由于真正的非支配解很难搜索到，有必要对所得解集计算，距离越近，得到的解质量就越高。由表1可知，DFOA算法的平均，最小，以及最大的值分别是0.07，0.01，1.39，均小于ESFLA算法的0.64，0.60，2.86。因此，相对于平均距离而言，DFOA算法性能优于ESFLA。

算法DFOA优于ESFLA的另一个方面表现在非支配解的比率上。由表2可以看出，DFOA算法中平均有85%没有被中的其他解所支配，而ESFLA算法中只有76%。

6. 结论

综上所述，DFOA算法之所以优于ESFLA，因为DFOA算法在算法中执行过程中保留了所以的非支配解，并充分利用了非支配解的优势，在其基础上用插入方法产生邻域解，更好的指导了算法的进化方向，增强算法全局搜索的能力。

基金项目

海南省教育厅科研项目(Hnky2015-51, Hnky2015-55)；三亚市院地科技合作项目(2015YD57, 2015YD11)。

文章引用

潘玉霞,贾保先. 多目标无等待流水线调度的离散果蝇算法
Discrete Fruit Fly Algorithm for Multi-Objective No-Wait Flow Shop Scheduling Problem[J]. 建模与仿真, 2016, 05(02): 9-15. http://dx.doi.org/10.12677/MOS.2016.52002

参考文献 (References)