基于改进差分算法解决流水车间问题

李超，张晓霞

（辽宁科技大学计算机与软件工程学院，鞍山114051）

1 课题研究的背景和意义

随着时代的进步，科技的创新，行业间不断的竞争，要想在市场上占得先机，就必须提高竞争力，那么就需要从源头出发，所以他们将注意力放到生产上的调度问题，以至于算法不停优化，效率不断的提高，逐渐趋近于理想水平。本文的主要研讨的内容是流水车间问题。最早是Miller、Maxwell和Eonway等人进行实际研究，他们的研究也为后来的发展打好根基。随着时间的迭代，直到约瑟夫哈林顿提出计算机集成概念CIMS，它是逐步分解的生产过程合并在一起，进行总体的优化运算，进而使生产效率提高，所以企业的有用功增大，无用功逐渐减少。也正因为如此，流水车间调度被许多生产行业所关注，所以现在大多数车间都在不同程度地应用这门技术。而本文以时代为背景，顺应时代的要求，通过研究改进的差分算法来解决流水车间问题[1]。

2 研究现状

流水车间调度是车间调度中的基本问题。在企业的生产流程上，每一个小小的产品都必经过所有步骤才能成功。对于车间产品的每一步都需要仔细设计，不容一点误差，尤其是这些制件需要在流水线上遵循相同的加工路线，也就是说按次序加工，不能有一点颠倒，否则就会生产失败，所以对于每个产品的加工顺序的选择就显得尤为重要。而每个产品的加工顺序就构成流水车间，他们之间的调度就是流水车间调度[2]。

它的描述为：n个产品{j1,j2,…,jn}，在m台机器{1,2,3,…,m}上加工，每一个产品的完成都需要执行每道程序，即一个产品需要流经m个机器，而且，每个产品又不能同时需要一个机器，并且一台机器不能同时生产两个或多个产品，否则会出现程序执行错误，并且各个产品在不同机器上的所需时间都不同，其目的是获得最优的调度方案，满足对问题的多重面考虑。

3 差分算法的基本原理

由StomnR和PriceK在1995年推出一种随机并行搜索的差分算法，它具有优化不连续函数的能力。1996年差分进化算法在速度位于季军，却广泛被应用。差分算法是基于群体智能理论的算法，具有全局搜索策略，通过实数编码、变异操作和竞争生存策略，来降低了操作的复杂性[3]。

它是由父代产生子代，二者中较好的作为新的父代进入下一代执行之后的循环迭代。而又不同于传统的EA，DE首先执行变异，然后任意抽取三个，运用数学中向量的加减得到新的变异个体，按照流程顺序将变异个体与目标个体交叉得到对应的子代个体，并将它与目标个体进行适应值比较，优胜劣汰，直到算法的结果结束[4]。

4 差分算法的进化流程

差分算法的概述如下：

（1）设定差分算法控制参数，顺应函数采用实数编码。

（2）随机产生初始种群。

（3）预估（2），通过实验得到它们的适应度值。

（4）判断是不是到达迭代数的峰值。如果是，则直接输出它的排列顺序；如果不是，继续执行操作。

（5）实行变异和交叉操作，将变异向量V i,G与父向量X i,G杂交，通过二项式杂交算子得到第j维个体，公式为：

CR是交叉概率因子，jrand是维数[1 ,D]之间的均匀分布，进而得到中间种群

（6）在（2）和（5）中进行选择，得到新种群，利用一对一贪婪选择，父子代的个体向量比较，优良个体遗传给下一代，计算公式表示为：

（7）进化代数k=k+1，转步骤（4）[3]。

5 蚁群算法的进化流程

蚁群算法顾名思义是基于蚂蚁研究出来的，它与蚂蚁的生理功能相类似，在寻食的途径中，需要通过生理反应留下的信息素来选择那条道路，研究总结蚂蚁寻路的规律来建立算法模型，并通过不时更新信息素浓度来更新算法的循环操作，最终使求得的最符合理想结果，所以这个过程被称为蚁群算法[5]。概述如图1。

图1 蚁群算法流程图

6 差分算法与蚁群算法的比较

设有5个工价、4台机器的生产车间调度，每个工件需要的时间如下：

j i：是第i个工件j：是第j道工序

通过设置NP=20，来研究实验结果，运用图1，得到4-3-1-2-5的解，需要72分钟。通过数据的分析，差分算法的迭代规律如图2，蚁群算法的迭代规律如图3。

图2 差分算法的迭代值

通过图2数据可得，水平坐标表示的迭代次数在70就趋近于水平，图3数据可得，蚁群算法的迭代次数在80~90之间，处于波动状态，所以，差分算法更适合解决流水车间问题，需要迭代超过70次，或者更多次才合适。而数据得出的结果就更是验证了这一结论。

图3 蚁群算法的迭代值

把数据代入蚁群算法，得到4-2-5-1-3的解，需要93分钟，比差分算法的运算结果长，差分算法与之对比，因其算法的优质解得概率达到80%以上，所以差分算法比蚁群算法更符合车间。

表1 两种算法结果对比

从两次实验结果中分析可以得出：

（1）差分算法比蚁群算法的运行结果要好，运行速度要快，结果更清晰明白，所以差分算法在优化类问题中具有典型的优势的。

（2）差分算法的能力要强于蚁群算法，主要是因为它的最优解具有普遍性，会根据情况做出改变，但是蚁群算法相对而言就相对绝对了，不具有普遍性。

（3）通过实验结果表明，提出的差分算法相对于蚁群算法在解决流水车间问题时，求解质量非常有效。所以在流水车间问题上，改进的差分算法更有优势。

7 结语

从现有的研讨结果以及本文的计算过程可以清楚地知道，流水车间问题的算法研究与实际运用相互磨合，具有一定的成果，但是如果使流水车间问题的研讨能够更广泛地被企业应用，依然存在待改良的方面，主要有一下几点：

（1）目前研讨的流水车间问题主要应用在小规模的企业，如何使它更适应大规模的范围，还需要考虑的问题很多，而对应的难度会成倍增加，所以这将是日后研究的重点[6]。

（2）好的算法需要有好的平台载体去呈现它，为了使人们更容易操纵它，需要将成熟的算法结合软件应用到实际生产问题，才是最终想达到的目的。

（3）对于流水车间调度问题本身的研究方法，本文只是研究一点，还需要进行创新思考，研究出更高效的算法步骤，为我们所用。现如今随着智能优化算法的进步，不断弃其糟粕，用之精华，不断吸收优秀的科学理论，与现代工业相结合，将会促进社会的进步。