英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

---

群体和进化计算

两级帝国主义竞争算法求解具有相对重要性目标的节能混合流车间调度问题

李明，雷德铭，蔡景操

关键词

混合流车间调度、帝国主义竞争算法、两级、节能、目标的相对重要性

摘要

近年来，节能混合流车间调度问题得到了广泛的研究；然而，在以往的研究中很少考虑目标的相对重要性。本文研究了带有总延迟、最大完工时间和总耗能的EHFSP问题，其中第三个目标的重要性低于其他目标。定义了一个新的帕累托优势来处理相对重要性。并提出了一个两层的帝国主义竞争算法（TICA），其中两层分别由最强大的帝国和其他帝国组成。生成高质量的解决方案，执行同化和革命不同——在帝国的不探索阶段，最强大的帝国是排除在帝国主义的竞争，记忆往往是结合最强大的帝国和记忆的成员被添加到赢得帝国为了避免包含最弱弱的帝国殖民地。大量实验表明，TICA算法为所考虑的EHFSP提供了良好的结果。

1介绍

混合流程车间调度问题(HFSP)并不少见，许多现实生活中的制造业，如电子、造纸、纺织、石油化工、飞机发动机和半导体[1,2]。与流车间相比，混合流车间存在多个并行机器至少在一个阶段，会导致机器的冗余在灵活性和增加的能力，并避免瓶颈等[3]。在在过去的几十年中，混合流车间的各种调度问题如多目标HFSP和节能混合流车间调度问题(EHFSP)已经解决。

对多目标HFSP, Jungwattanakit 等人[4] 提出了一些启发式和一个遗传算法 (GA)来解决不相关的机器，安装时间和双重标准的问题。Rashidi等人[5]提出了一种改进的混合并行遗传算法。Cho等人[6]报道了一种并行遗传算法具有四种不同版本的局部搜索策略。Karimi等人[7]开发了一种多相遗传算法双目标混合柔性车间群调度问题。Naderi等人[8]使用改进的模拟退火解决了HFSP与顺序相关的设置时间、运输时间和两个目标的问题。Tran和Ng[9]应用了混合水流算法带有有限缓冲区的HFSP。穆萨维等人[10]提出了一个双目标局部搜索算法分三个阶段。之前的作品考虑考虑HFSP与其他实际约束，如预防性维护[11]，两个代理[12]，家庭设置时间[13]和装配[14]。其他的元启发式算法也被应用，包括禁忌搜索[11,15]、殖民竞争算法(colonial competitive algorithm, CCA)[16]、邻域搜索[14,17]、可变邻域搜索(variable neighborhood search, VNS)[18]、打乱蛙跳算法[12]、萤火虫算法[19]等。

EHFSP是一个重要的节能调度问题，是绿色制造的重要组成部分，由于至少有一个目标或约束与能源效率有关，因此往往有多个目标。近年来，EHFSP备受关注。Bruzzone等人提出了一种修改作业调度的方法，以考虑功率峰值。Dai等人提出了一种遗传模拟退火算法来最小化柔性流水车间调度中的最大完工时间和总能耗。Luo等人提出了一种考虑电力消耗成本的HFSP蚁群优化方法。Tang等人提出了一种改进的粒子群算法(PSO)，用于柔性流程车间的节能动态规划。Lin等人提出了基于教学的优化方法(TLBO)，将加工参数优化和HFSP与最大完工时间和碳足迹最小化相结合。Yan等人提出了降低总能耗和最大完工时间的多级优化方法。Lei等人开发了一种新的TLBO来最小化总迟到被视为关键目标和总能耗。孟[27]等人提出了一种新的能量意识的改进遗传算法解码方法。Li等人[28]提出了一种能量感知的HFSP多目标优化算法。Zeng等人[29]利用混合非优势排序遗传算法-ii（NSGA）来实现具有总耗电量和材料损耗的柔性流水车间调度。

在上述两种HFSP的文献中，通常都是假设的所有的目标都具有同等的重要性，相对的重要性目标很少被考虑[14,26]。当制造商非常重视生产系统的性能和准时交付，他们会给予总延迟和最大完工时间高于能源相关目标。在这种情况下，有必要从能源消耗中区分总迟延和最大完工时间的相对重要性。

关于上述情况的论文很少。Lei等人[26]采用词典法处理总迟到为关键目标，总能耗为非关键目标。提出了一种新的 [14] 策略，通过赋予关键目标比非关键目标更高的优先级来处理具有关键目标的优化问题。然而，调度算法只能得到一个或多个解，且难以生成非支配解在帕累托前沿上的扩散，因此

有必要找到一个新的方法来处理目标的相对重要性。

帝国主义竞争算法(ICA)[30]是一种元启发式算法，受社会政治行为的启发，其主要步骤包括最初帝国的形成，同化，革命和帝国主义竞争。与其他优化算法如遗传算法和粒子群优化算法不同，ICA有一些值得注意的特点，如良好的邻居搜索能力，有效的全局搜索性能和良好的收敛速度[31]。它还具有较小的陷入局部最优和柔性结构的机会。在近年来，ICA已被应用于解决各种生产调度问题，并在收敛方面显示出优良的特性速率和全局搜索属性。Molla-Alizadeh-Zavardehi等人，[32]为模糊单批处理机提供了一种改进的独立分量分析方法调度。Shokrollahpour等人[33]提出了一个新颖的ICA。

双标准装配流程车间调度。Seidgar等人研究了[34]基于ICA的两阶段流水车间调度问题。Goldansaz[35]等人利用混合ICA和遗传算法求解多处理器开放问题车间调度。Karimi 等 人 [36] 开发了一个混合ICA (FJSP)与模拟退火的柔性工作 车间调度问题与运输时间。Zandieh等人[37]提出了一种用于具有维护功能的FJSP混合ICA与。Lei[38]等人提出了一种基于ICA和VNS的两阶段能耗阀值FJSP算法。Pan等人[39]提出了一种多目标低碳并行机调度的有效独立分量分析方法。

在现有的ICA在调度、同化等方面的应用中，所有的帝国的执行方式往往是相同的，帝国主义的竞争是在所有帝国之间进行的。事实上，根据帝国的总成本来实行同化和革命是有用的，例如，在最弱的帝国中，同化应该通过将殖民地移向其他帝国的帝国主义来加强和完成。最强大的帝国可以被排除在帝国主义竞争之外而避免不成熟的;另一方面，独立分量分析(ICA)很少用于求解EHFSP;然而，ICA的特点和应用已经显示出它的优越性在调度问题上，因此ICA可以成为处理EHFSP的有效途径。

在本研究中，EHFSP考虑了最小化总延误、制造周期和总耗能，其中第三个目标的重要性低于其他目标。利用新定义的帕累托优势来处理目标的相对重要性，提出了两级帝国主义竞争算法，其中两级帝国主义竞争算法分别由最强大的帝国和其他帝国组成。同化和革命在帝国的不同探索阶段有不同的实现，只有第二等级的帝国互相竞争，一个记忆与最强大的帝国相结合，并在获胜的帝国中加入一个记忆的成员，以避免包含最弱的中最弱的殖民地。

进行了大量的计算实验。我们首先对参数设置和TICA新策略对其整体性能的贡献进行了实验，然后我们将TICA与文献中的算法进行比较，以测试TICA在考虑EHSFP时的性能。

论文的其余部分组织如下。正在研究的问题将在第二节中描述，然后在第三节中介绍ICA，EHFSP的TICA在第四节中报告，第五节报到了TICA上的数值试验结果，最后一节总结了试验结果，并提出了今后的研究方向。

2问题描述

本节使用如下符号（参见表1）

EHFSP由 n个作业J1、J2.......Jn和m个阶段1、2.......m组成，Sk是阶段k的一组不相关的并行机器。｜Sk｜gt;1为至少一个阶段，每台机器都有一组V-d不同的处理速度,V={v1,v2,.......vid},每个作业Ji都是按照相同的方式处理的生产流程：第一阶段，第二阶段，.....第m阶段。当一个作业在一个阶段处理时，它的处理必须以选定的速度在指定的机器上执行。在执行作业期间，机器的速度不能改变，当作业Ji在机器Mkj上以速度Vl进行加工，处理时间Pikjl被定义为eta;ikj/vl. 作业的处理可以跳过一些阶段，但是，它必须至少在一个阶段进行处理，在所有的作业处理完成之前，机器不会完全关闭。

通常认为，当作业在机器上以更高的速度[40]处理时，能量消耗会增加，处理时间会减少。Lei等人[26]对EHFSP的这一假设进行了详细的描述。

EHSFP的约束条件如下：所有的机器和工作从时间零点开始可用。每个作业一次只能在一台处理器上处理。每台机器一次只能处理一项以上的工作，不允许抢占，缓冲区大小不受限制。

EHFSP由三个子问题组成：机器分配在每个阶段为每个作业选择一台机器，速度选择决定在第一阶段所分配的机器的适当处理速度，1，2.....m代表每项工作和调度。EHFSP的目标是在满足约束条件并解决子问题的情况下，同时最小化一下三个目标。

当准时交货和提高生产性能是制造商的主要目标时，总延迟和最大完工时间应高于总能耗，以反映制造商的偏好。如果我们在优化过程中平均对待三个目标，制造商往往会忽略小技术参数下得到的解决方案；相反，如果在TICA过程中降低TEC的重要性，重视对总延迟和最大完工时间的优化，则由于TICA中包含了制造商的偏好，可以很好的得倒制造商要求的结果。

对于G目标最小化的多目标优化问题，定义了以下几个概念

（1）帕累托的主导地位

如果

表一符号及其描述

符号 描述

K 阶段的第J台机器

机器Mkj上作业Ji的基本加工要求

在Mjk机器上以vl速度处理作业Ji的时间

能源消费总量

作业Ji的完成时间

作业Ji的到期时间

所有作业的最大完成时间

机器的速度

如果机器Mkj在时刻t以速度vt运行，则取1，否则取0

如果Mkj在时刻t处于待机状态，则取1，否则取0

单位时间内 在速度 下的能量消耗

单位空闲时间的耗能

（2）不占主导地位。对于Ф集和解决方案 如果x不是Ф中的任何解决方案，那么集合x是不占主导地位的。

（3）帕累托最优。如果一个解在搜索空间不受其他解的支配，那么这个解就是帕累托最优解。

（4）帕累托最前。它由所有帕累托最优解的客观向量组成。

意义着x支配y

对于EHFSP，f3的重要性低于f1,f2,为了反映这种 偏好的制造商，一个新的 ε-Pareto 优势定义如下，对于解x和y，

其中εgt;0是实数， 表示 支配y.

与 的差约为目标f(3)，在ε控制下，f3(X)必须小于或等于f3(y)至少ε，然而仅要求fi(x)小于或等于fi(y)，i=1,2,也就是说,在上面的定义中,f3表现更加难以被满足的条件比f1,f2, 的主导地位主要被f1，f2决定，显然，当ε=0时， 和 是一样的。此外ε的价值越大，f(3)的条件越难满足。由此，f(3)的重要性降低了，f(1),f(2)的偏好得到了体现。

3介绍ICA

在ICA中，国家代表问题的解决方案，人口P的解决方案分为两部分：帝国主义和殖民地，前者是P的一些最佳解决方案，后者是除帝国主义外的所有P的解决方案。

ICA的具体步骤如下。

步骤一：初始化。随机生成初始种群P，计算P中每个解的代价。

步骤二：最初的帝国。选择成本最小的Nim解作为帝国主义者，计算其归一化成本ck 和殖民地数量Nck，并为每个帝国主义者随机分配Nck殖民地。

步骤三：同化。在每个帝国中，每个殖民地都朝着自己的帝国主义前进，并尽可能用新产生的解决方案取而代之。

步骤四：革命。根据公转概率UR进行公转。

步骤五：交换。在每一个帝国中，把每一个殖民地和它的帝国主义进行比较，用比它的帝国主义的成本更小的殖民地来代替帝国主义。

步骤六：帝国主义竞争。计算各帝国的总成本TCK、归一化总成本TCK和功率，构建下列向量[POW1-r1,POW2-r2,....,POWNim-rNim],决定建立一个拥有最大战果的帝国g，并把最弱帝国中最弱的殖民地分配到帝国g。

步骤七：重复步骤三到步骤六，直到满足终止条件。

其中rk为均匀分布在[0,1]中的随机数。

在成本方面，解决方案的成本越小，解决方案就越好。

ck、NCk、TCk、TCk和POWk是由Hosseini和Khaled[32]定义的。 4目标的相对重要性

当帝国被视为亚种群时，ICA是一个多种群的元启发式，帝国主义竞争是亚种群之间进行交流的唯一方式，因此在帝国之间引入更多的交流可能是有益的;另一方面，对于所有帝国来说，同化和革命的实现方式往往是相同的，根据帝国的总成本来区分帝国是很有意义的并在不同的帝国中应用不同的同化和革命;然而，这种情况很少被ICA采用。在本研究中，我们提出了一种基于上述两种思想的新型算法TICA。

4.1初始化和初始帝国

EHFSP由调度、机器分配和速度选择三部分组成，采用三字符串表示，编码和解码如Ref.[26]所示。

随机生成一个具有N个解的初始种群P。初期帝国的建立是人口划分的过程。

最初的帝国是这样建立的。

步骤一：对P中的所有解执行非优势排序[41]。

步骤二：计算各国i的标准化成本ci

步骤三:选择正常化成本最大的Nim国家为帝国主义国家，其他国家为殖民地国家。

步骤4:计算帝国主义k的Fk和NCk的幂。

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[239430]，资料为PDF文档或Word文档，PDF文档可免费转换为Word