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

外文翻译：

基于两级帝国竞争算法求解考虑目标相对重要性的节能混合流车间调度问题

李明，雷德铭，蔡景操

武汉理工大学自动化学院

摘要：

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

关键词：混合流车间调度问题 两级帝国竞争算法 节能 目标的相对重要性

引言

混合流车间调度问题(Hybrid flow shop scheduling problems, HFSP)在电子、造纸、纺织、石化、飞机发动机和半导体等许多现实生活中的制造业中并不少见[1,2]。与流水车间相比，混合流车间在一个阶段至少存在多个并行机器，机器的冗余可以带来灵活性，也可以增加容量，避免了工序瓶颈等问题[3]。在过去的几十年中，混合流车间的调度问题，如多目标HFSP和节能混合流车间调度问题(EHFSP)都得到了解决。

对于多目标HFSP, Jungwattanakit等人[4]提出了一些启发式算法和一个遗传算法(GA)来解决机器不相关、设置时间和双重标准的问题。Rashidi等人提出了一种改进的混合并行遗传算法。Cho等人报道了一种并行遗传算法，该算法为可重入HFSP提供了四种不同版本的局部搜索策略。Karimi等人针对双目标混合柔性流水车间群调度问题，提出了一种多阶段遗传算法。Naderi等人使用改进的模拟退火解决了HFSP与顺序相关的设置时间、运输时间和两个目标的问题。Tran和Ng[9]将混合水流算法应用于带有有限缓冲区的HFSP。Mousavi等人提出了一种分三个阶段的双目标局部搜索算法。之前的著作考虑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来实现被视为关键目标的总误工和总能耗的最小化。孟等人提出了一种改进的遗传算法，该算法采用一种新的能量感知译码方法。Li等人提出了一种能量感知的HFSP多目标优化算法。Zeng等人提出了基于混合非优势排序遗传算法-II (NSGA-II)考虑总能耗和材料损耗的柔性流水车间调度问题。

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

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

帝国竞争算法(ICA)[30]是受社会政治行为启发而产生的一种元启发式算法，其主要步骤包括初始帝国的形成、同化、革命和帝国竞争。与其他优化算法如遗传算法和粒子群优化算法不同，ICA具有良好的邻域搜索能力、有效的全局搜索性能和良好的收敛速度[31]等显著特点。它也有微小的机会陷入局部最优和灵活的结构。近年来，ICA已被应用于解决各种生产调度问题，并在收敛速度和全局搜索性能方面显示出良好的特性。Molla-Alizadeh-Zavardehi等人提出了一种改进ICA用于模糊单批处理机器调度。Shokrollahpour等人提出了一种新的ICA用于双标准装配线车间调度。Seidgar等人提出了一个两阶段流水车间调度问题的独立分量分析方法。Goldansaz等人使用混合ICA和GA来解决多处理器开放车间调度问题。Karimi等人开发了一个混合ICA与模拟退火的考虑运输时间的柔性作业车间调度问题(FJSP)。Zandieh等人[37]提出了一种具有维护功能的FJSP混合ICA。Lei等人提出了一种基于ICA和VNS的两阶段能耗阈值FJSP算法。Pan等人提出了一种多目标低碳并行机调度的有效帝国竞争算法。

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

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

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

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

问题描述

本节使用以下符号(参见表1)。

表 1 符号及其描述

EHFSP由n个工件J₁，J₂，...，J_n和 m个阶段1,2，...，m组成。S_k表示在k阶段一组不相关的并行机器，一个阶段的S_k必须大于一。包含了对于每台机器有d个不同处理速度的集合V ，V={v₁,v₂,...,v_d}。每个工件J_i都是按照相同的生产流程处理的:第一阶段、第二阶段、...、m阶段。当某工件在某一个阶段处理时，它的处理必须以选定的速度在指定的机器上执行。在执行作业期间，机器的速度不能改变。当工件J_i在机器M_kj(M_kj属于S_k)上以速度v_l处理。处理时间p_ikjl定义为eta;_ikj/v_l。作业的处理可以跳过一些阶段；但是，它必须至少在一个阶段进行处理。在所有作业的处理完成之前，机器不会完全关闭。

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

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

EHFSP由三个子问题组成:机器分配在每个阶段为每个作业选择一台机器，速度选择取决于每个作业在阶段1，2，...，m分配的机器的对应处理速度以及调度。EHFSP的目标是在满足约束条件并解决子问题的情况下，同时最小化以下三个目标。

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

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

(1)帕累托最优。xgt;y,如果对于任意i有 f_i(x)le;f_i(y)并且存在i使得f_i(x)gt;f_i(y)。

(2)非支配因素。对于集合Phi;，解x属于集合Phi;，如果x在Phi;里不是由任何其他解支配，那么x是一个非支配因素。

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

(4)非劣最优目标域。它由所有帕累托最优解的客观向量组成。

其中xgt;y表示x可以支配y。

对于EHFSP，f₃的重要性比f₁，f₂低，为了反映制造商的偏好，一个新的ε-帕累托最优如下定义，对于解x和y：

ε是大于0的实数，其中xgt;_εy表示x可以支配y。gt;和gt;_ε的不同是在于目标f₃的不同，在ε-支配中，εle;f₃(x)le;f₃(y),f_i(x)le;f_i(y)(i=1,2),在以上定义中，f₃的条件是比f₁，f₂的条件更难被满足的，ε-支配主要取决于f₁，f₂。显然，当ε等于0时gt;支配与gt;_ε支配是一样的，此外，ε的值越大，f₃的条件就越难被满足，因此f₃的重要性就被减弱了，f₁，f_{2 剩余内容已隐藏，支付完成后下载完整资料}

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