一种基于Q学习的元启发式算法,通过种群多样性控制实现考虑有限等待时间和多订单的分布式流水车间调度优化
《Expert Systems with Applications》:A Q-learning-based metaheuristic with population diversity balance for distributed flow shop scheduling considering limited waiting time and multiple orders
【字体:
大
中
小
】
时间:2026年07月23日
来源:Expert Systems with Applications 9.4
编辑推荐:
摘要
在现代多工厂生产系统中,存在一种具有等待时间限制且每项任务包含多个相同订单的分布式流水车间调度问题,这类问题计算难度较高。本研究旨在最小化总完工时间来解决这一问题。首先,构建了一种基于位置的混合整数线性规划模型,并使用CPLEX求解器为小规模实例获得精确解。随后,提出了
摘要
在现代多工厂生产系统中,存在一种具有等待时间限制且每项任务包含多个相同订单的分布式流水车间调度问题,这类问题计算难度较高。本研究旨在最小化总完工时间来解决这一问题。首先,构建了一种基于位置的混合整数线性规划模型,并使用CPLEX求解器为小规模实例获得精确解。随后,提出了一种结合种群多样性平衡的Q学习元启发式算法——QLM-PDB。该算法的创新点包括:(1)引入Q学习机制,可自适应选择破坏比例(临界工厂序列长度的25%、50%或75%),从而实现扰动强度的自主调整;(2)提出一种名为总体种群差异度的新指标,用于量化搜索空间中解的分布情况;(3)设计基于总体种群差异度的扰动与种群重启策略,有效避免过早收敛;(4)整合路径重联与变量邻域搜索方法,进一步提升解的质量。该算法在150个不同规模(最多100项任务和20台机器)及工厂配置(2、4、6家工厂)的基准实例上进行了验证,实验结果表明,QLM-PDB在中小规模实例上表现优异,显著优于其他对比算法;在足够运行时间内,其在大规模实例上也具备竞争力。
引言
分布式流水车间调度问题是在分布式制造环境中对传统流水车间调度问题的扩展。这类问题通常涉及多个地理位置分散、结构相似或相同的工厂。每项任务需分配到其中一个工厂,并按照相同的操作步骤在多台机器上依次加工。与传统流水车间调度问题相比,分布式流水车间调度问题不仅需要确定每家工厂内任务的加工顺序,还需同时决策任务在不同工厂之间的分配方案(Becker等人,2025)。随着全球化生产、云制造以及多工厂协作生产模式的发展,这类问题在制造业、物流业和服务业等领域的实际生产系统中愈发重要。其目标是在确保资源高效利用的同时,优化整体生产性能指标,如总完工时间、总完成时间或总延迟时间。然而,由于任务分配与调度顺序之间存在复杂的相互依赖关系,该问题的规模和组合复杂性大幅增加,属于典型的NP难优化问题(Lu等人,2024)。
在分布式流水车间调度问题中,等待时间限制是调度优化中的关键约束之一。等待时间指的是任务在不同机器之间处于空闲状态的持续时间。当等待时间受到严格限制时,任务必须在完成当前操作后的预定最大等待时间内进入下一道工序(Zhang、Han等人,2025)。流水车间调度中的等待时间限制主要分为三类:时间滞后约束、有限等待时间约束和无等待约束。在具有时间滞后约束的流水车间中,从完成当前操作到开始下一道操作的等待时间既有上限也有下限。有限等待时间约束和无等待约束则是时间滞后约束的特殊形式——前者下限为零,后者上下限均为零。本研究聚焦于有限等待时间约束(Han & Lee,2023)。这类约束旨在避免任务加工过程中出现过长的空闲时间,从而保障生产过程的连续性与稳定性。尤其在电子制造和精密加工等对工艺时间要求严格的行业中,这些约束对于维持产品质量和交货进度至关重要。与无等待约束相比,有限等待时间约束在满足高时效性要求的同时,仍为调度提供一定的灵活性,因此是分布式流水车间调度中常见且具有重要实用价值的约束条件。
在现代电子产品制造中,智能手机等高科技产品的生产通常涉及多个地理位置分散的工厂,这些工厂都配备了类似的生产线。生产过程包括元件放置、焊接、测试和包装等多个高度依赖时间的工序。为确保整体生产效率和按时交付,不同机器之间的等待时间被严格限制,以避免因过度空闲而导致的生产瓶颈和延误。在这样的生产环境中,需要合理分配任务到各个工厂,并优化每家工厂内的生产顺序,以便在有限等待时间约束下实现高效调度。此外,高科技产品的生产还面临大量重复订单的挑战——根据市场需求,必须批量生产同一型号的多个任务,以确保持续满足订单需求并保持供应链稳定。这类重复订单往往具有较高的生产频率和规模,对制造系统的产能和调度效率提出了巨大要求。因此,高效管理和调度来自不同任务的大量订单,对于维持生产连续性和缩短生产周期具有重要意义。鉴于此,研究考虑有限等待时间和多重订单的分布式流水车间调度问题(DFSP-LWTMO)具有重要的实际意义和应用价值。
由于调度问题的复杂性,传统的数学方法,如整数规划、分支定界法和动态规划,仅适用于解决某些小规模的调度问题。而对于涉及多台机器、众多任务和批量作业的大规模分布式调度问题,这些方法的性能存在局限。启发式和元启发式方法则为在合理计算时间内找到具有最优或接近最优解的调度方案提供了更好的替代方案(Zhao等人,2022)。近年来,将强化学习与启发式方法结合来解决此类调度问题,已成为国内外研究的热点方向。
强化学习是一类通过与环境交互自主学习最优策略的方法。其核心思想是,智能体根据环境反馈(以奖励或惩罚的形式)不断调整自身行为,以实现长期收益的最大化。随着人工智能的快速发展,与强化学习相关的方法日益成熟。与传统方法相比,它们具有强大的适应性、广泛的适用性以及更出色的长期优化能力,因此受到了众多研究人员的关注(Zhang等人,2024)。例如,Zhou等人(2025)针对人工蜂鸟算法存在的收敛速度慢且无法处理离散优化问题等缺陷,提出了一种改进的基于Q学习的离散人工蜂鸟算法(QIDAHA)。该算法通过整合强化学习技术,能够根据环境状态和反馈自适应地选择蜂鸟的最优飞行方向。实验结果表明,该算法的调度性能更为优越。Luo等人(2026)则提出了一种由进化策略引导的深度强化学习模型,用于解决具有动态到达任务的动态流水车间调度问题,同时最小化总加权延迟成本。
在算法的进化过程中,种群会通过迭代更新逐渐向最优解靠拢。然而,在收敛过程中,种群多样性对算法性能起着至关重要的作用。多样性过低可能导致算法陷入局部最优解,而多样性过高则会降低收敛速度(Cheng等人,2021)。尽管多样性的重要性已得到广泛认可,但在实际研究中,目前缺乏直观且可量化的指标来衡量进化过程中种群多样性的变化情况。这一局限性降低了算法设计时的参考价值(Zhang等人,2019)。因此,在分布式流水车间调度问题的背景下,设计一种用于评估种群多样性的指标尤为重要。
尽管在分布式流水车间调度及有限等待时间约束领域已有大量研究成果,但仍然存在以下问题缺口。首先,现有关于分布式流水车间调度的研究(Wang & Wang,2025)主要集中在分布式排列流水车间、分布式阻塞流水车间和分布式无等待流水车间等变体上,尚未有研究在分布式多工厂环境中纳入有限等待时间约束。其次,关于有限等待时间约束的研究(Lee,2020)仅限于单工厂配置,未涉及分布式制造中固有的任务分配决策问题。第三,目前尚无研究同时考虑分布式流水车间或存在等待时间约束的流水车间场景中每项任务包含多个相同订单的情况。因此,本研究解决的问题填补了这三个研究方向之间的空白。
基于以上分析,本研究提出了一种结合种群多样性平衡的基于Q学习的元启发式算法——QLM-PDB,用于解决这一问题。在QLM-PDB中,破坏与构建策略与Q学习相结合,同时引入多样性指标来控制种群的总体质量,从而实现种群多样性的平衡。具体而言,本研究的主要贡献如下:(1)为DFSP-LWTMO问题构建了混合整数线性规划模型,并使用CPLEX求解器作为精确求解方法;(2)提出了一种解决方案差异度指标,用于衡量种群中两个个体之间的差异;(3)引入了总体种群差异度指标,直观反映搜索空间中种群的分布情况,帮助判断算法是否可能陷入局部最优解;(4)提出了结合种群多样性平衡的基于Q学习的元启发式算法QLM-PDB,该算法通过基于Q学习的破坏与构建策略优化解的质量,同时运用路径重联策略提升种群多样性,并通过基于总体种群差异度的扰动与种群重启策略帮助算法摆脱局部最优解。
本文的其余部分结构如下:第2节回顾相关研究;第3节描述DFSP-LWTMO问题的特征并建立以最小化总完工时间为目标的混合整数线性规划模型;第4节介绍解决方案差异度指标及总体种群差异度指标;第5节详细介绍QLM-PDB算法;第6节展示CPLEX在小型实例上的计算结果,验证所提算法的有效性;最后,第7节总结研究结论并指出未来工作方向。NEH启发式算法(Nawaz等人,1983年)是用于解决流程优化问题的经典且高效的方法之一。在本研究中,我们根据批量生产系统的特点,生成了150个不同规模的示例。这些示例包含了15种不同的任务数量(n)与机器数量(m)组合,具体的n×m组合为{5, 10, 25, 50, 100}×{5, 10, 20},这些实例在研究中被命名为Qd001-150。每个任务的加工时间是在[1, 99]范围内均匀生成的。
结论:本研究探讨了存在有限等待时间约束且每项任务包含多个相同订单的离散流水车间调度问题,这类配置在电子制造及多工厂协同生产中具有很高的实际应用价值。本研究的主要贡献有三点:首先,针对这种复杂的调度场景,提出了基于位置的整数线性规划模型,同时整合了分布式工厂分配、有限等待时间约束以及多订单批量处理等要素。
作者贡献说明:
乔广权:数据整理、形式化分析、软件开发、可视化处理、初稿撰写。
刘丽:问题研究、资源协调、结果验证。
邓关龙:概念设计、方法论构建、项目管理、资金筹措、监督指导、论文审阅与编辑。
资金支持:本项工作得到了山东省自然科学基金(项目编号ZR2019QF008)的支持。
利益冲突声明:作者们声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。
乔广权|刘丽|邓关龙
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号