采用改良粒子群算法的弹性流水作业节能动态调度研究

摘要

基于日益增长的能源需求和相关环境因素，如今制造行业面临着可持续生产需求的严峻挑战。现存大多数关于减少生产调度损耗问题的能源消耗研究都聚焦于静态的调度模型。然而，现实中生产调度存在许多无法预测的干扰，例如新增工作、机器停机等。本文提出阐释动态调度问题的方法为弹性流水作业减少能源和完工时间的消耗。由于这是个典型的非确定性多项问题，因此采用基于改良粒子群算法的新型算法，来求出弹性流水作业的动态调度问题中帕累托最佳解。最后用大量实验来评价所提出的方法的执行情况和效率。

1、引言

由于能源需求的增加和相关环境影响，如今制造行业面临着巨大的环境挑战和经济重压。制造公司一个重要的目标就是减少能源消耗以节约成本，并且达到制造的可持续发展，实现环境友好模式。制造过程中的节能研究主要集中在基于机器和产品层面的能源消耗优化。另外，从制造系统角度来讲，优化生产调度的因素是更可行有效的方法，制造企业在减少能源消耗的同时，又不需要对任何机器或产品的重新设计。近期，许多学者把对产品调度问题的考虑纳入能源利用效率中，由此开展了许多有意义的调查研究。大多数这类研究成果主要在于开发一套解决静态调度问题的数学模型。仅少数研究着重于可持续运行调度动态方法。然而，调度问题本身处于动态发展之中，也会因现实中存在的不确定事件而变得复杂。显然，先前的静态决策模型在现实生产环境中受到严重的限制。一些降低最大工时和能耗的通用多因素调度模型被证明在弹性流水作业中有效，但并未考虑新增工作和机器停机等不确定因素。本文将在考虑动态因素的条件下分析弹性流水作业的能源消耗和最大工时，采用基于可预测性反应调度方法的动态调度策略代表多因素优化问题。此外，由于动态调度问题也是著名的非确定性多项问题，需采取多种解决方法，因此弹性流水作业问题将采用两项优化（即NS-PSO和NIW-PSO）。

本文其他部分内容归纳如下。第二章介绍相关研究。第三章阐述研究内容。第四章展示解决弹性流水作业动态调度问题的方法。第五章列示大量实验和案例研究。第六章为结论。

2、相关文献

近年来，生产调度的节能问题已经引起越来越多的关注。May等人提出作业车间系统的能量消耗和最大工时多元调度模型，并得到绿色遗传算法下一系列不同的帕累托前端解。Escamilla等人发现了减小车间作业调度拓展问题中关于能源消耗和最大工时的遗传算法，该问题中每台机器以不同的速率工作。Jiang等人建立了一个多因素优化模型，解决弹性流水作业动态调度下最大工时、运行成本、生产质量和能源损耗问题，并设计了一个修正显性分类遗传算法作为解决方案。Liu等人运用非显性分类遗传算法，建立了能减少总非生产电力消耗和总可计量延迟的调度模型。Bruzzone等人针对给定初始情况需要工作分配和排序修订的弹性流水作业，提出一个能量感知的基于混合整数程序公式的调度算法以证明能量损耗。Fang等人提出新型混合整数线性程序模型，考虑了耗能峰值、碳足迹和最大工时。同时，这些作者们也探索了能源效率调度问题的两个主体——弹性流水作业的最大工时和能源消耗。综上所述，从大多数最新论文研究中可以看出，它们都将重点放在能源效率调度在多种车间环境（车间作业、流水车间、弹性流水作业车间等）的应用中。然而从静态调度的视角来看，由于现实生产环境中无法预测的动态因素（例如新增工作和机器停机等）不可避免，导致先前可行的调度方案无法执行。

在动态调度问题的文献资料中，可预测性反应调度方法广泛用于制造系统中，这些系统修订调度方案以适应动态因素。多数系统仅考虑最大工时等调度效率。然而，生产调度考虑动态因素会限制节能。Pach等人提出基于流水制造系统中位势场的反应调度模型，其中包含三个指标：最大工时、能耗和动态环境下的资源转换器数量。Zhang等人提出一个新的目标程序算法模型，着力于将能耗和调度效率作为多对象优化功能，从而解决流水制造系统的重新调度动态问题。Zeng等人根据拥有多重任务和减节能目标的混合流水车间中每台机器在动态调度下的忙闲状态，引入空闲时间窗口的概念。

此外，动态调度问题远比静态调度问题复杂，而且是非多项式困难问题。许多技术如启发式/元启发式算法以及其混合技术已经在诸类问题上有所应用。特别是元启发式方法如遗传算法（GA）、模拟退火算法（SA）和粒子群算法（PSO）近年来已经被成功应用于优化结果的产生中。不过，这些研究都没有提到能源利用效率问题。Rossi和Dini针对动态车间中心调度的流水制造系统，提出一个实时遗传算法，该算法极大减少了最大工时。然而Chryssolouris 和 Subramaniam在动态车间作业中运用遗传算法，包含车间延迟、机器停机导致的车间成本和变更作业例程的性能指标。结果显示GA从普通分配方法中脱颖而出。Chou等人研究了一项改进的模拟退火方法，以解决降低半导体加权完工时间的动态调度问题。计算实验表明该方法能有效获得优化解。另一方面，Visalakshi 和Sivanandam设计了四个不同PSO算法，来解决动态任务调度问题。Wang等人针对动态车间调度问题，引入了新增工作和机器故障两个因素，研究了新混合型分散PSO算法。Pacini等人提出云环境下线上环境的科研实验动态调度PSO研究。这些实例证实PSO能较好地解决动态调度问题。

不过，我们也必须处理文献中所存在的限制。首先，需要对优化算法更进一步的改良，使其更适应多对象的实操环境。其次，针对动态调度问题的优化算法需做到更有效。由于PSO算法的优点，在简单结构下，创新的PSO算法能探索弹性流水车间中包括新增工作及机器停机在内的动态调度问题，减少能耗和最大工时，在实际调度问题中直接应用并且迅速得到优化解。

3、问题陈述

两台不相关且平行的机器间的弹性流水作业车间动态调度（DFFS）定义如下。DFFS是多阶段产品加工由两个或以上阶段连续组成。每一阶段至少有一台机器，至少有一阶段有多台机器。假设集合J={1,2, 3, ..., n}代表n个工作，集合S= {1, 2, 3, ..., s}代表s个阶段，集合M_t = {1,2, 3, ..., m_t}，m_t (tisin;S)代表在制造系统内每个阶段t(tisin;S)的机器。所有工作都要在机器上根据相同指令完成所有阶段。另外，集合V= {1, 2, 3, ..., d}，v代表一台机器在阶段t(tisin;S)时，每个工作j（jisin;J）须在机器m(misin;M_t)上运行时分配的轴速度v（visin;V）。因此在每个阶段，不同工作的任务因通信能量消耗的不同可能有不同的处理时间。由于生产调度中可能的发生意外事件，因此将考虑两个动态因素。第一，集合Jrsquo; = {1, 2, 3, ..., nrsquo;}表示nrsquo;个新工作，必须在原有调度计划开始之后紧接着开始。第二，集合M_trsquo;= {0,1, 2, 3, ..., m_trsquo;}，代表m_trsquo;台机器在生产调度中停机。停机可能发生在机器的空闲或运行时间。DFFS的需求条件如表1所示。文中所用的注释的解释如表2所示。

表1 DFFS所需条件

表2 公式符号的注释

DFFS的正式数学模型见附表。这是覆盖了重新调度的数学模型的拓展表。

文献中有各种多因素优化问题的解决方法，可以分为两类：先验法和后验法。前者将权重分配到每个因素上，即将多元问题转化为一元问题。每使用该方法一次即可获取一个唯一最佳解。后者可以通过直接求解多元问题，获得一个非显性解的集合（帕累托最优解）。本文中我们将在改良的PSO算法上采用后验法处理多元问题。多元函数包括两个以时间为变量的函数方程，一个是最大工时，另一个是能源消耗（见公式（1））：

一个要素是调度效率，由最大工时衡量。最大工时定义为所有工作的最大完成时间。另一个要素是能源利用率，由机器工作产生的能量消耗计算。根据机器工作的能源消耗因素，能源消耗被分为三部分（见图1），减少空机时间和任务匹配时间（E2和E3）可以减少整体能源消耗。

图1 能耗三分模型示例

4、DFFS解决方法的提出

为了以可预测性反应调度方法解决DFFS，必须执行三个主要组成：预测调度、重新调度点和最佳算法（DFFS的核心）。改良的粒子群算法可用于DFFS的求解。图2总结了动态求解流程。

图2 DFFS的求解流程图

粒子群算法（PSO）是一种随机搜寻最优解的技术。一般来说，更新速度和位置能确定每个部分的最优解。速度和位置的更新由认知部分和社会部分决定。更新速度和位置的标准方程分别见式（2）和（3）。

本文中提出的求解DFFS的PSO算法主要是新型粒子编码方案和PSO的速度更新。该算法的细节将在下一章解释。

4.1、基于绝对位置价值矩阵的粒子编码方案

根据第三章的问题描述，矩阵X（k）（粒子）有n n#39;列，s行。如式4所示。

其中

矩阵中每个元素都代表每个阶段t中工作j在k循环时的绝对位置。另外，DFFS的每个元素可定义为：

如果t阶段的工作j在重新调度时段（RS）的时间开始前就已经在机器上执行，元素x_jk（k）的值为0。这包括：

例1：一个原有作业已完成。

例2：一个原有作业已被执行。

如果t阶段的工作j在重新调度时段（RS）的时间之后在机器上执行，元素x_jk（k）的值等于一个随机数字。其小数部分作为工作分配到每台机器的序列号，整数部分代表接到工作分配的机器号。这包括：

例1：一项新工作必须被执行。

例2：一项原有工作的操作必须被执行。

在编码阶段，矩阵Q（k）通过矩阵X（k）的整数部分生成元素，命名为int（x_ji（k））（见式5）。设Q（k）为机器所得任务。具体编码过程见表3。

其中

4.2 动态弹性流水车间示例

DFFS的一个实例如表4所示。它由3个工作和3个阶段组成。1阶段有3台机器，2阶段和3阶段分别有2台机器。每台机器（Mi）对每个工作的处理时间（pi）和能耗（ei）都不相同。为了模拟神出鬼没的干扰因素，在程序执行期间加入2个新工作（工作4和工作5）。图3显示基于可预测性反应调度的DFFS调度优化。由于工作4和工作5在RS=7点到达，需要在分配新工作的同时保留原有任务的状态（粗体字表示）。

图3 DFFS最佳解甘特图

表4 一个DFFS示例

以下矩阵展示了给定示例下DFFS的编码结果。由随机生成的X（k）得到Q（k）。处理时间矩阵P（k）和能源消耗矩阵E（k）由表4获得。

这样，矩阵的一列代表一个工作，一行代表一个阶段。根据描述，示例的粒子编码由图4解释。例如，根据机器矩阵Q（k），1阶段的工作4将由机器1（甘特图的红色部分）执行，而工作5将由机器2（甘特图的蓝色部分）执行。另外，工作3在重新调度时期（RS=7）开始时（甘特图的绿色部分）被执行。第二阶段包括工作3、4和5，根据矩阵X（k），由于工作4和5在1阶段的完成时间相同（C₄₁₁=C₅₁₂，见P（k）），2阶段的工作4和5在机器5上的执行顺序将由矩阵X（k）的小数部分来决定。因为5.1560 lt; 5.8495，2阶段中工作4将在工作5之前被执行。最终到3阶段，工作1和工作4将会在机器6上执行（见Q（k））。因为C₁₂₅lt;C_425,，工作1会在工作4之前执行。同理可得，在3阶段，工作2、工作3和工作5会以这个顺序在机器7上执行。

图4 DFFS编码结果

4.3基于Hill函数的惯性变化速度更新

为了提高PSO搜索效率，设一个新的惯性权重w控制全局和局部的搜索能力的平衡。一般来说，惯性权重是线性函数或常数函数。它的一个缺点在于，由于其线性特质，容易被局部最优（早熟收敛）限制。Hill函数是非线性、非否定性的单调函数。受Hill函数的启发，在式6中提出新的惯性权重函数w（k）以调整求解范围。因此它能避免受到早熟收敛的影响。

Ho等人为独立随机权重因素在粒子的认知部分和社会部分之间建立了联系，可以用于更新速度。因此速度更新的公式可表示为：

注意在公式3和公式7中，元素x_id（k）的值可能会超过范围。如此，每个t阶段溢出值的整数部分由 随机生成。

例如，假设下列矩阵为初始速度，元素X（K）的局部最优位置和全局最优位置如下：

假设w₀=0.4，w_max=0.9，w_min=0.4，T=12，q =0.5; c₁ = c₂= 1.8; r₁ = 0.3; r₂= 0.8.代入公式7，可计算出（k 1）循环的值：

因此根据式3，可计算出元素X（k）移动到下一个位置：

由于-0.1540超出矩阵X（k 1）的范

资料编号：[3125]