一种将人机约束纳入能源意识型流水车间调度的高层启发式方法

《AUTOMATION IN CONSTRUCTION》：A hyper-heuristic approach of integrating human–machine constraints in energy-aware flow shop scheduling

　　李锡兴|连景生|吴睿|胡友西|曾彦青|唐洪涛|李一兵|雷德明•构建了一个具有多资源约束的节能调度问题模型。•提出了一种基于选举系统的改进型TLBO启发式算法。•采用自适应多类策略以实现高效的知识传递。•设计了一种动态扰动机制来激活停滞的解决方案。•通过一个实际的自动铸造应用验证了该方法的实用性。

引言在现代计算机集成制造的背景下，为应对环境恶化和全球变暖问题，绿色制造日益受到全世界的关注[1]、[2]。作为自动化制造系统中的关键组成部分，生产调度在平衡高能耗行业（如钢铁制造[3]、铸造[4]和玻璃制造[5]）的效率与能源消耗方面起着至关重要的作用。在实际制造系统中，EFHSP常见问题出现在那些需要经过多个加工阶段、配备并行机器且能耗较高的生产线上。以热铸和冷铸车间为例，工件要经过制模、制芯、合模、熔炼浇注、震砂、喷砂、机加工和磨削等工序。熔炼浇注阶段通常配备有多个并行炉子，因此会形成批量处理环境，因为只要炉子容量允许，相同材质的铸件可以同时加工。与此同时，一些手动或半自动操作需要不同技能水平的工人，这直接影响实际加工时间。因此，这类实际系统需要同时优化生产效率、能源消耗和碳排放。

在过去的十年中，并行批量处理机器的调度、异构工人的分配以及节能型混合流水线调度问题(EHFSP)都得到了广泛研究[6]、[7]、[8]、[9]、[10]、[11]、[12]、[13]、[14]、[15]。具体而言，虽然带有各种实际约束条件的EFHSP已被广泛研究[16]、[17]、[18]、[19]、[20]，但在可持续制造领域，针对BPMs的节能调度也越来越受到重视[21]、[22]、[23]、[24]、[25]、[26]。然而，在EFHSP相关研究中，很少涉及中间阶段BPMs的集成调度、异构工人分配、阶段优先级灵活性以及碳排放问题，尽管这些特征在现实制造过程中普遍存在。此外，在大多数以往的研究中，BPMs通常位于流程的初始阶段或最后阶段[27]、[28]、[29]。很少有研究考虑具有中间阶段BPMs和异构工人分配的多资源约束EFHSP问题，更不用说同时考虑碳排放以及某些阶段之间不存在优先级关系的情况了。本研究正是探讨了具有中间阶段BPMs、阶段优先级灵活性以及异构工人分配的多资源约束EFHSP问题。

此外，标准EFHSP通常假设任务必须严格按照从第1阶段到第H阶段的顺序进行处理；但实际上，在许多制造过程中，某些阶段之间往往不存在严格的优先级关系，这样就可以更好地利用资源。例如，在一个拥有8个阶段的铸造流水线中，任务在完成第2阶段后，可以在第3阶段或第4阶段交替加工。同时考虑中间阶段BPMs、异构工人分配以及阶段优先级灵活性，能够对生产效率和能源消耗产生动态影响。因此，将这些特性结合起来，会显著增加人机协作系统中的调度复杂性。

具有双层结构的超启发式算法(HHA)是一种用于组合优化的高级优化方法[30]。在HHA中，会使用一种高级策略(HLS)来管理一组低级启发式方法(LLHs)，这些LLHs包括预先设计的启发式规则或邻域操作。由于具备有效的邻域探索能力和实用的框架，HHA在动态调度领域越来越受到关注[31]、[32]、[33]。近年来，人们开始研究利用HHA来解决具有各种约束条件的实际调度问题[34]、[35]、[36]、[37]、[38]、[39]。在这些研究中，人们设计了基于选举机制的超启发式算法，以提高动态调度问题的优化性能。

作为一种有效的元启发式算法，基于教学学习的优化方法(TLBO)模拟了课堂上的教学过程[40]。在该算法中，搜索过程由两个不同的阶段驱动，即教师阶段和学习阶段，以此提升所有解的优化水平。由于具有易于实现的框架且算法特定参数较少，TLBO被广泛用于解决生产领域的各种复杂调度问题[41]、[42]、[43]、[44]、[45]。值得注意的是，TLBO在解决EFHSP问题[46]以及并行机器调度问题[47]时都展现出了良好的效果，这体现了它在处理复杂调度场景时的强大竞争力。TLBO在多个领域的出色表现表明，它具有解决EFHSP问题的巨大潜力。最近，人们开始研究将元启发式算法与HHA相结合，进一步提升调度问题的优化性能[35]。因此，针对所研究的EFHSP问题，本文提出了一种结合TLBO与基于选举系统的HHA机制的集成协作调度方法，其中TLBO充当高级策略。

已有大量研究致力于将TLBO与各种元启发式算法相结合[41]、[42]、[43]、[44]。不过，目前大多数框架只是将HHA视为一种通用的高级选择工具，或者以松散的方式依次结合这两种算法[34]、[36]。因此，为了获得高质量的解决方案，本文提出了一种基于TLBO和基于选举系统的HHA机制的集成调度方法。与传统具有静态启发式选择的混合算法不同，这里将TLBO作为高级策略，用来动态管理LLHs。具体而言，设计了一种双向量编码方案，用于同时演化调度序列和投票者序列。在得分选举系统的驱动下，LLHs被当作独立的投票者，而投票者序列则负责动态优化选举群体的构成，从而共同决定机器的分配方案。通过这种结构参数协同演化机制，有效地整合了TLBO的全局探索能力与HHA的局部优化精度。这样一来，就能避免过早收敛，提升其在处理复杂人机约束问题时的优化能力。

本研究探讨了一种具有中间阶段BPMs、阶段优先级灵活性以及异构工人分配的多资源约束EFHSP问题。为了同时最小化生产周期、总能源消耗和总碳排放，本文提出了一种基于EHTLBO算法的集成方法。本研究的主要贡献如下：(1) 设计了一种基于得分选举系统的解码策略。该方法没有采用通用规则，而是将低级启发式方法作为独立的投票者，通过共识机制共同决定机器和工人的分配方案，从而有效实现复杂约束条件下的双向量解码。(2) 设计了一种自适应多类构建及类间协作教学机制。将所有解明确划分为八个专门的子集（Class1–Class8），以便与教师的专长相匹配，同时还构建了一个精英解库（Estudent），以促进有针对性的知识传递。(3) 实现了一种包含五种邻域结构（N1–N5）的动态扰动机制。该机制能够平衡搜索的强度和多样性，避免过早收敛并摆脱局部最优解。(4) 进行了大量的计算实验，并以一家自动铸造企业为案例进行了实际应用研究。实验结果表明，与现有的元启发式算法及传统工业规则相比，所提出的方法能够在提高生产吞吐量的同时降低能源消耗和碳排放。

本文的其余部分结构如下：第2节将对相关文献进行综述。第3节将定义所研究的调度问题。第4节将介绍TLBO、选举系统以及HHA的基本概念。第5节将详细介绍EHTLBO算法的设计与实现方式。第6节将分析比较实验结果。最后一部分将总结研究结论并指出未来可能的研究方向。

文献综述下面将对与EFHSP、并行BPMs调度以及基于HHA的元启发式算法应用相关的最新研究进行综述和讨论。

问题描述所研究的这种多资源约束EFHSP具有中间阶段的BPMs（阶段σ）、相邻阶段σ?2和σ?1之间的灵活优先级关系，同时还需考虑碳排放问题以及异构工人分配问题。该生产环境包含n个任务、Nw个工人小组，以及一个H阶段的混合流水线。对于除σ之外的任何离散阶段s，任务都会在ms台相互独立的并行机器上分别加工，这些机器记为Ms,1、Ms,2……Ms,ms。而阶段σ则包含……

TLBO在TLBO框架中，搜索空间是由一群模拟学生群体的解构成的[40]。其进化机制分为两个不同的阶段，即教师阶段和学习阶段。在教师阶段，算法会将迄今为止找到的最佳解视为教师xteacher，旨在将优秀的解决方案传递给其他解。通过这种“教学”互动，每个解的位置都会向新的状态转变……

EHTLBO用于多资源约束EFHSP为了解决所研究的这种多资源约束EFHSP问题，本文基于帕累托最优原则，提出了一种改进型的基于教学学习的优化算法——EHTLBO。该算法整合了多种策略，旨在平衡收敛性与多样性，逼近帕累托前沿，从而找到高质量的非支配解。

计算实验所提出的EHTLBO算法是在MATLAB 2024b环境中实现的，运行设备为配备AMD Ryzen 7 - 9700x处理器（4.50 GHz）和32 GB内存的个人电脑。通过大量实验来测试EHTLBO在处理所研究的EFHSP问题时的性能。

结论与未来工作在本研究中，我们构建并研究了具有BPMs、阶段优先级灵活性、异构工人分配以及严格碳排放限制条件的多资源约束EFHSP问题。为同时最小化生产周期、总能源消耗和总碳排放，我们提出了EHTLBO算法。在该算法中，通过整合四种协同机制，建立了一个强大的结构参数协同演化框架。具体而言，还设计了一种解码策略……

CRediT作者贡献声明李锡兴：写作——审稿与编辑，监督工作。连景生：写作——初稿撰写，软件工具使用，方法设计，数据整理。吴睿：问题研究，资金获取。胡友西：监督工作，形式化分析。曾彦青：可视化处理，概念构建。唐洪涛：可视化处理。李一兵：形式化分析。雷德明：监督工作。

利益冲突声明作者声明自己没有已知的可能会影响本文研究结果的财务利益或个人关系。

致谢本研究得到了中国国家自然科学基金（52475528、52575595）、湖北省重点研发计划（2024BAB058、2025BAB063）的支持。