王付宇 汤涛

摘要：针对万有引力搜索算法在处理一些优化问题时比较容易出现早熟和搜索精度不高的缺点，通过引入变异思想和模拟退火思想，提出一种改进的万有引力搜索算法，并用此算法对以加权总误工最小为目标的流水作业排序优化问题进行分析，结果表明：改进后的万有引力算法明显优于传统万有引力算法。

关键词：流水作业;排序;加权总误SE;万有引力算法

中图分类号：TP301.6DOI：10.16375/j.cnki，cn45-1395/t，2020.02.011

0引言

流水作业排序被称为一种经典的组合优化问题，假设用m台机器加工n种零件，设加工每一种零件所需机器的次序是固定的，给出每台机器加工各个工件所需要消耗的时间，以便于确定各个工件的最优加工顺序，从而使适应度函数值达到最优，在排序中，机器数量很多的排序问题为NP完全问题，在制定生产计划时，需思考用什么方法可以使产品进行有序的生产，从而降低时间和成本，为企业带来效益，因此，流水作业排序问题的研究对于企业在市场竞争中占据有利地位具有重要的作用。

目前，许多学者将粒子群等智能算法以及其他创新方法应用于流水作业排序问题的求解。张壵等于2018年提出了一种基于遗传邻域的万有引力算法对车间产品生产问题进行求解。

万有引力搜索算法（GSA）是一种新型的群智能优化算法，与遗传算法和粒子群算法一样，都是通过粒子更新位置，从局部寻优逐渐寻得全局最优的方法，该算法拥有收敛速度快的特点，己用于解决生活、生产以及其他问题，但是在求解离散复杂组合优化问题时，依然有很多不足，因此，本文对万有引力搜索算法进行了改进，在加权总误工的模型基础上，采用新型的群智能优化算法——离散的改进引力搜索算法对流水作业排序问题进行求解。

1流水作业排序问题

1.1问题描述

流水作业排序可以分为静态排序和动态排序两种，当所有工件都在排序生产之前就已经到达车间，可以一次性对它们进行加工排序安排，这种情况被称为静态排序问题;当所有工件是在生产过程中间断到达车间，需要即兴安排它们的加工顺序，这种情况被称为动态排序问题，本文研究的便是流水作业的静态排序问题情况下，确定总加权误工最小时流水作业中零件的加工顺序。

1.2流水作业排序优化模型

假设条件：

1）排序之前，所有工件都已经到达，此时工件完工时间与流程时间相等，

2）同一个工件不可以同时在不同机器上进行加工。

3）工件在排序加工过程中，上一个工序完成后，立刻被送到下个工序加工。

4）不允许间断，一个工件一旦开始加工，不能中途停止，一直到完工结束。

5）每个工序只在一台机器上完成。

6）每台机器同时只能加工一个工件。

根据以上所述可得模型为：

2改进万有引力算法

万有引力搜索算法（Gravitational SearchAlgorithm，GSA）是由伊朗克曼大學教授Esmat Rashedi等在2009年提出的群智能优化算法，GSA算法的产生是受到牛顿万有引力定律的启发，使种群粒子具有引力质量，其引力质量根据粒子的适应度计算出，基于牛顿万有引力定律，粒子产生相互之间的吸引力，粒子间作用力和它们的质量成正比关系，和它们之间距离的平方成反比，粒子惯性质量越大，粒子间距离越小，则粒子间的相互作用力越大，粒子在吸引力的驱使下作相对运动，适应度值较大的粒子则其引力质量较大，适应度值较小的粒子则其引力质量较小，在相同力量下，质量大的粒子运动较慢，质量小的粒子运动较快，粒子逐渐收敛到最优位置，依此来达到寻优的目的，传统的引力搜索算法只能解决连续型编码问题，即便利用连续实数与离散实数之间的映射关系去编码求解离散组合优化问题，寻优效果不佳;因此，本文对万有引力算法做出了改进，从而使求解流水排序问题寻优效果更佳，

该算法借鉴了遗传算法的变异，提出了一种以引力质量为概率的父代基因片段传给子代的变异策略，将引力质量大的父代的优秀基因传给子代，不仅如此，在粒子速度更新的时候，引入了粒子群算法的优点，使粒子有着向自身历史最佳位置逼近的趋势和有向群体或领域历史最佳位置逼近的趋势，将模拟退火算法与万有引力算法相结合，以增强算法的局部搜索能力，避免陷入局部最优，通过改进的万有引力算法有效地求解了流水作业排序问题，结果表明改进的万有引力算法是可行的。

2.1编码问题

传统的万有引力搜索算法只能解决连续型编码问题的解，流水作业排序是离散型组合优化问题，所以本文借鉴了陈育兴等求解TsP问题时的实数编码规则，基于连续型数据，通过对随机生成的连续型数据进行倒序排列，取倒序排列数据的行数作为离散型问题的初始解，万有引力算法中一个位置即为一个解，表示为：

2.5改进引力算法求解问题步骤

Step1算法初始化，设定各个参数，初始温度To=1000.种群规模size_pop=300.count=0.Go=100.a=20.降温系数q=0.96.终止温度T_end=0.001.

Step 2产生初始粒子群，计算适度值，并更新全局最佳Zbest与个体最佳gbest。

Step 3开始迭代，初始粒子速度为0.将群体里较差的三分之一个体去掉，以较优的三分之一粒子代替，计算群体里各个粒子引力质量m：（t）和惯性质量M（t）。

Step 4计算各个粒子的引力Fid（t）及加速度aid（t）。

Step 5根据速度更新公式更新速度，根据位置更新公式更新位置。

Step6根据父代惯性质量决定是否变异，超出边界范围的粒子位置，采用公式控制其在边界范围内波动。

Step7根据模拟退火Metropolis原则来接受新解，

Step8更新全局最佳Zbcst与个体最佳gbest，count=count+1.To=g×To。，

Step9判断是否结束循环，若不结束，返回Step 3.若结束，输出最优解及其加工序列，

3案例分析

以10个工件，5台机器的流水作业生产作为案例来进行改进万有引力算法的求解，Pij表示工件Ji在机器Mi上的加工时间如表1所示。

工件参数如表2所示，

设定粒子群规模为300.初始温度为1000.终止温度为0.001.降温系数q为0.96.速度范围为[-1.1]，粒子边界为[-2.2]，初始速度为0.Go=100.a=20.使用matlabR2014b来进行编程，计算机处理器参数Intel（R）Core（TM）i7-1065G7@2.52GHz双核处理器，RAM为8GB，Window8操作系统64位，

运行改进后的万有引力算法GSGSA，得到的最优加工序列为2.1.10.6.4.5.3.9.7.8.目标函数最小值为66.75。

传统的万有引力算法GSA运行得到的加工序列为2.1.9.6.4.5.3.7.10.8.目标函数最小值为72.171.结果对比如表3所示。

4结论

基于最大完工时间，构造了以加权总误工为目标函数的优化模型，传统的万有引力算法无法对离散型编码问题求解，将模拟退火与引力算法相结合，增强其寻优效果，速度更新时，借鉴粒子群，使粒子有向最佳位置逼近的趋势，在相同的配置下，通过改进后的引力算法对流水作业排序问题进行了求解，寻优效果优于原来的GSA算法。