结合禁忌搜索的混合模糊遗传算法在LED表面贴装技术调度问题中的应用

《Computers & Industrial Engineering》：Hybrid fuzzy genetic algorithm with Tabu search for the LED surface mount technology scheduling problem

智能显示需求激增推动LED制造依赖高精度SMT表面贴装技术，但高混低产特性导致调度复杂度激增，传统方法难以应对包含批次分割、机器可用性、物料供应等多约束的复杂问题。本研究创新性融合模糊逻辑控制（FLC）与禁忌搜索（TS）的混合遗传算法（HFGATS），通过动态调整交叉率和变异率实现全局探索与局部开发的协同优化，在解决批次分割这一核心约束时，有效平衡设备利用率与交期延误。实证研究表明，该算法在小规模问题中获取最优解，在复杂大规模场景下显著优于传统调度规则和通用元启发式算法，总迟延降低达23.6%，客户满意度提升18.4%，为LED智能制造提供新范式。

　　

王宏凯 | 杨祖月 | 钱晨富

台湾新竹国立清华大学AIMS研究员执行硕士项目

摘要

随着智能显示应用的迅速扩展，LED制造越来越依赖表面贴装技术（SMT）来实现高密度和高精度的元件放置。然而，LED生产的高混合度和低产量特性显著增加了SMT调度的复杂性，并阻碍了高效的生产规划。本研究提出了一种结合禁忌搜索（Tabu search，HFGATS）的混合模糊遗传算法，用于解决SMT调度问题（SMTSP），该问题被建模为一个具有多种实际约束的流水线调度问题，例如批次分割、机器可用性、材料可用性、指定机器规则以及序列依赖的设置时间约束。在这些约束中，批次分割是最关键的限制因素。在LED行业中，某些产品的订单量很大，需要提前进行批次分割以防止生产过度集中在单一机器上。然而，批次分割不可避免地增加了机器设置次数。因此，关于批次分割的决策会严重影响调度系统的整体效率。所提出的框架集成了一种模糊逻辑控制器，以自适应地调整遗传算法的参数，并结合禁忌搜索来增强局部搜索能力。为了验证所提出的HFGATS，使用从一家台湾LED制造商的SMT车间收集的实际生产数据进行了实证研究。HFGATS为小规模问题获得了最优解；对于大规模问题，它在最小化总延迟方面优于传统的调度规则和通用元启发式算法。这种改进可以提高工厂的整体准时交付率，从而提高客户满意度并提升工厂的盈利能力。

引言

随着人工智能和物联网技术的快速发展，智能显示行业的需求激增。此外，对技术可持续性的日益关注加速了紧凑型和节能型LED的采用。为了满足对高空间效率和性能的智能显示产品的需求，LED制造越来越依赖于表面贴装技术（SMT），该技术能够实现精确、高密度的元件放置。LED正被集成到越来越多样化的产品中，行业也转向了高混合度、低产量的生产方式，进一步复杂化了SMT流程。在当前竞争激烈且节奏快速的环境中，及时交付对于缩短产品生命周期至关重要。因此，特别是在SMT领域，高效且响应迅速的生产调度已成为LED行业面临的关键挑战。

SMT流程有一系列标准化的步骤，包括焊膏印刷、元件放置和回流焊接（Prasad, 2012）。这些步骤在不同产品中是一致的，并在多条生产线上执行，通过输送系统在各个阶段之间传输产品。因此，SMT流程可以被描述为一个具有固定结构的流水线调度问题（FSSP）。

已有许多研究致力于解决FSSP问题。传统上，人们使用数学编程模型来解决这些问题（Mortezaei和Zulkifli, 2013; Ramezanian等人, 2013; Sánchez-Herrera等人, 2019）。尽管这些模型可以提供最优解，但它们往往难以扩展。随着问题规模的增加，计算负担和执行时间也会增加，使得数学编程不适合处理大规模或快速变化的环境。鉴于FSSP的非确定性多项式时间（NP）难度，一些研究采用了元启发式方法，这些方法为现实世界和大规模问题提供了更实用的解决方案。例如，赵等人（2018）提出了一种离散水波优化算法，用于在机器可用性约束下解决无等待FSSP问题，目标是最小化总完成时间。郑等人（2021）开发了一种结合迭代贪婪算法和模拟退火的混合方法，用于处理涉及紧急任务、有限等待时间和机器可用性约束的FSSP问题。王等人（2023）提出了一种协作多目标进化算法，用于解决分布式FSSP问题，其中需要优化完成时间、延迟和能耗。秦等人（2019）提出了一种两阶段蚁群算法，用于处理具有批量大小、日历约束和序列依赖设置时间的混合FSSP问题。

将SMT调度问题（SMTSP）建模为FSSP引入了独特的特性和挑战，这些特性和挑战大大增加了调度的复杂性。挑战包括需要同时考虑机器可用性、材料可用性、订单优先级和生产线平衡，所有这些在SMT中都至关重要。尽管一些研究分别解决了其中一个或多个约束，但很少有研究探索它们的综合效应。根据我们对文献的回顾，没有研究将所有这些实际因素纳入统一的SMT流程调度框架中。

最近，强化学习（RL）在解决调度问题方面的应用受到了广泛关注。王等人（2021）回顾了基于RL的调度研究，并指出深度Q网络特别适合建模大规模和高度动态的调度环境。相反，LED制造线内的SMTSP具有相对较小的规模和高混合度、低产量的生产特点。由于这些特点，相应的状态和动作空间不足以让RL有效地发挥其固有优势。此外，RL要求提前构建包含状态和动作的数据库以加速收敛。这一要求不适合LED行业低产量、高混合度的生产特点。在实际生产环境中，为了平衡解决方案质量和计算时间，传统的元启发式算法比未经训练的RL更适合解决SMTSP问题。

遗传算法（GAs）是一种受自然进化过程启发的元启发式优化方法。由于其灵活性和有效性，GAs已被广泛应用于各个领域，如车辆路径问题（Abbasi等人, 2020）、机器学习中的参数调整（Hamdia等人, 2021）、特征选择（Rostami等人, 2021）和节能（He等人, 2021）。此外，GAs还广泛应用于生产调度领域，以处理复杂的多约束生产环境（Rezaeipanah和Mojarad, 2021; Chien和Lan, 2021; Hong和Chien, 2020; Huynh和Chien, 2018）。研究表明，GAs在解决资源分配、作业排序和多目标优化等挑战方面具有多样性。然而，尽管GAs很受欢迎，但很少有研究专注于LED制造中的SMT流程。

应用遗传算法（GAs）的一个主要挑战是它们对参数设置的敏感性，如变异率、交叉率和种群大小，这些参数设置会显著影响算法性能。不适当的参数设置可能导致过早收敛或优化缓慢（Katoch等人, 2021）。为了解决这个问题，开发了参数调整方法，大致分为参数调整和参数控制。参数调整涉及基于实验或历史数据预先定义固定参数值。例如，Mills等人（2015）使用实验设计和回归分析等技术来确定最优的交叉率和变异率。传统的自适应参数控制方法通常依赖于固定规则，如时间表或数学公式。然而，这些方法通常无法结合不断变化的适应度值，限制了它们适应不确定性和模糊性动态环境的能力。

模糊逻辑控制器（FLCs）提供了一种更加适应性和灵活的参数控制方法，从而解决了上述限制。与传统参数调整方法不同，FLCs根据实时反馈动态调整关键参数，如交叉率和变异率。FLCs利用模糊集合理论有效管理优化过程中常见的不确定性和不精确性。这种能力使FLCs在动态优化场景中特别有利。FLCs已成功应用于多个领域，包括自动驾驶（Chen等人, 2020）、能源管理（Zhang等人, 2020）和机器人导航（Mishra等人, 2022）。在优化算法的背景下，FLCs通过根据算法的进展动态调整参数，显著提高了性能。例如，Ochoa等人（2020）提出了一种高速区间型2模糊系统，用于实时调整差分进化算法的交叉率，从而实现更快的收敛和更好的解决方案质量。Brindha（2021）提出了一种基于模糊逻辑的差分进化算法，用于在多目标优化问题中动态调整交叉率和变异率，有效保持了种群多样性并提高了鲁棒性。Samsuria等人（2024）提出了一种模糊遗传算法（FGA），其中FLC根据适应度值动态调整GA的交叉率和变异率。这种方法已成功应用于解决动态调度问题，如移动机器人调度，并被证明在效率和适应性方面有显著改进。

为了优化SMT流程的调度效率，本研究提出了一种结合禁忌搜索（HFGATS）的混合FGA。该框架集成了FLC、GA和禁忌搜索（TS）。FLC组件用于动态校准GA的参数，如交叉率和变异率，以保持高搜索质量并适应不同的搜索阶段。同时，TS机制被纳入以增强局部探索能力，并有效防止算法过早收敛到局部最优解。这种混合架构巧妙地平衡了GA的全局探索能力和TS的局部强化强度，大大提高了识别高质量、接近最优解的可能性。通过将FLC、GA和TS结合到一个统一的调度框架中，所提出的HFGATS模型为解决LED制造行业中的复杂SMTSP问题提供了一种新颖、适应性和实用的方法。HFGATS在解决多个实际约束的同时，提高了解决方案的质量、灵活性和响应速度。

章节摘录

问题定义

本研究开发了一种HFGATS，用于解决LED制造行业的SMTSP问题。根据Chen等人（2023）和Wang等人（2025）的研究，SMT流程的关键阶段包括焊膏印刷和检查、通过拾放系统进行元件放置、芯片粘接、回流焊接、自动光学检查和预填充助焊剂清洁，如图1所示。SMT流程是一种可以视为FSSP的流水线生产类型。

实验

为了验证所提出的HFGATS的有效性，在台湾一家领先的LED制造公司进行了实证研究。该公司专门从事LED应用，如汽车照明组件、LED交通信号灯和其他节能照明产品。由于LED行业的固有特点，包括频繁的需求波动和低产量、高混合度的生产环境，SMT流程内的调度非常复杂。

结论

本研究提出了一种HFGATS，用于在考虑材料可用性、生产线平衡、机器可用性、指定机器限制和依赖设置时间等实际约束的情况下，获得SMTSP的最优解。为了克服传统GA的局限性，HFGATS结合了FLC来动态调整GA的交叉率和变异率，从而提高了解决方案质量和计算效率。此外，还采用了批次分割

CRediT作者贡献声明

王宏凯：撰写——审稿与编辑、验证、监督、项目管理、方法论、概念化。杨祖月：撰写——初稿、验证、软件开发、方法论、数据管理。钱晨富：撰写——审稿与编辑、监督、项目管理、资金获取。

利益冲突声明

作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。

致谢

本工作得到了国家科学技术委员会的支持，项目编号为NSTC 113-2221-E-006 -183 -MY3和NSTC 113-2221-E-007-114-MY3。