利用基于逻辑的弯曲分解方法优化具有序列依赖型准备时间的并行机器选址与调度问题
《European Journal of Operational Research》:Optimizing parallel machine location and scheduling with sequence-dependent setup times via logic-based benders decomposition
【字体:
大
中
小
】
时间:2026年07月09日
来源:European Journal of Operational Research 7.0
编辑推荐:
王云|吴鹏|袁哲|龚业明|阿贾伊·库马尔•我们提出了一种新的并行机器选址与调度问题模型,该模型考虑了与任务顺序相关的准备时间。•我们构建了一个简洁的MILP形式化模型,并设计了针对性的有效不等式。•我们提出了一种有效的下界,以及一种针对该问题的启发式算法,用以获得高质量的上界。•
王云|吴鹏|袁哲|龚业明|阿贾伊·库马尔•我们提出了一种新的并行机器选址与调度问题模型,该模型考虑了与任务顺序相关的准备时间。•我们构建了一个简洁的MILP形式化模型,并设计了针对性的有效不等式。•我们提出了一种有效的下界,以及一种针对该问题的启发式算法,用以获得高质量的上界。•我们还开发了一种定制化的、功能完备的基于逻辑的Benders分解算法。实验结果证明了所提算法、其核心组件以及有效不等式的优越性。
引言具有准备时间的并行机器调度问题因其广泛的实际应用而受到了学者和从业者的极大关注(Gedik等人,2016年;Tran等人,2016年;Yan?ko?lu和Yavuz,2022年)。然而,大多数研究忽视了机器选址这一因素,未能充分考虑机器位置对任务分配和排序的显著影响。在实际情况中,任务通常存储在地理位置分散的地方,生产过程中需要将它们运输到机器所在地点。这一运输过程会引入延迟,而这些延迟的大小取决于任务存储地点与机器地点之间的距离。这些延迟会直接影响任务处理的开始时间,因为机器只有在任务到达后才能开始处理。此外,由于任务的多样性,机器在处理下一个任务之前通常需要一定的准备时间来调整参数、更换工具或准备材料。因此,任务分配和排序成为决定机器完成时间的关键因素。例如,在半导体制造中,光刻工序是极为关键的环节,制造商会 strategically确定光刻设备的摆放位置,从不同的存储地点安排晶圆,并根据两个关键因素来排序:晶圆运输到光刻设备所需的时间,以及为处理不同类型的晶圆而调整和准备光刻设备所需的时间。在采矿、海运、饮料生产和印刷等行业中也存在类似的挑战(He?ler和Deghdak,2017年;Kramer和Kramer,2021年;Liu等人,2019年;Wang等人,2020年;Zhang等人,2022年)。
鉴于该问题属于NP难问题,大多数研究人员设计了启发式算法来解决具有准备时间的并行机器调度问题(Bektur和Sara?,2019年;Mu?oz-Díaz等人,2024年;Soares和Carvalho,2022年)。据我们所知,只有少数研究提出了精确算法来解决这一问题(Fanjul-Peyro等人,2019年;Gedik等人,2016年;Tran等人,2016年)。然而,这些精确算法并不适合解决同时涉及机器选址且准备时间与任务顺序相关的集成并行机器调度与选址问题(ScheLoc-ST),因为机器位置会显著影响任务分配和排序。例如,Tran等人(2016年)提出了一种基于逻辑的Benders分解方法(LBBD)来解决具有准备时间的并行机器调度问题。他们将原问题分解为一个主问题和一个子问题,然后将子问题转化为m个独立的旅行商问题(TSP)。最后,他们使用Concord求解器分别求解这些TSP问题,并将基于TSP解生成的解析割加入主问题中。该算法通过迭代不断收敛,直到满足停止条件。然而,这种方法无法直接解决ScheLoc-ST问题,因为ScheLoc-ST的子问题无法转化为传统的TSP问题,从而导致Concord无法发挥作用。
在本研究中,受上述情况的启发,我们专注于改进集成型ScheLoc-ST问题在实际情况中的适用性,尽管这会增加问题的复杂性。我们的目标是最小化总处理时间。据我们所知,现有文献尚未涉及这一问题。鉴于这一空白,我们总结本研究的主要贡献如下:(i)我们考虑了实际应用中常见的与任务顺序相关的准备时间,提出了一种新的并行机器选址与调度问题模型。(ii)我们构建了一个简洁的MILP形式化模型,并给出了更强的线性松弛下界。随后,我们进一步探讨了针对该问题的有效不等式,以强化线性松弛效果。(iii)我们提出了一种新的有效下界,相比He?ler和Deghdak(2017年)提出的现有最优下界更为严格。我们还开发了一种针对该问题的启发式算法,用以高效地获得高质量的上界。随后,我们利用这些上下界作为初始值,缩小FLBBD的搜索空间,从而进一步加快FLBBD的求解速度。(iv)我们开发了一种定制化的FLBBD算法,能够高效且有效地解决实际规模下的ScheLoc-ST问题。该算法采用分支定界法仅求解一次主问题;设计了一种定制的约束编程方法,以快速处理NP难级别的子问题;同时还嵌入了针对该问题的Benders割,以提高FLBBD的收敛速度。大量的实验结果证明了所提FLBBD算法、其核心组件以及有效不等式的有效性和高效性。
本文的其余结构如下:第2节概述相关文献。第3节正式描述所研究的ScheLoc-ST问题,并将其形式化为MILP模型。接着,我们根据ScheLoc-ST的结构特性,提出了有效的不等式,进一步强化MILP模型。第4节给出了一种新的、更为严格的下界。第5节详细介绍了所提出的FLBBD算法。第6节我们进行了大量的数值实验,以评估所提算法、FLBBD的核心组件以及有效不等式的性能。最后,第7节总结全文并探讨未来的研究方向。
文献综述在本节中,我们首先回顾与并行机器调度与选址问题(P-ScheLoc)最为相关的研究。接着,我们梳理了关于具有顺序依赖准备时间的并行机器调度问题的相关文献。最后,所有相关文献都在表1中进行了总结。
问题描述与建模在本节中,我们首先正式描述本文所研究的ScheLoc-ST问题,并将其形式化为MILP模型。
ScheLoc-ST问题的更严格下界在本节中,为了评估不同方法所得解的质量,并加快后续开发的精确算法的求解速度,我们首先介绍了He?ler和Deghdak(2017年)提出的几种现有的最优下界,以确保分析的完整性。然后,鉴于这些下界是为并行调度与选址问题设计的,并未考虑顺序依赖准备时间的特性,我们提出了一种更为严格的下界(针对ScheLoc-ST的LFLBBD)。LBBD算法最初由Hooker和Ottosson(2003年)提出,它是传统Benders分解方法(Benders,1962年)的扩展,提供了一种能够处理具有任意结构子问题的更复杂组合优化问题的分解框架。LBBD算法将原始优化问题分解为一个包含复杂变量的主问题以及一个或多个旅行商问题,然后通过基于逻辑的Benders割将它们联系起来。在每次迭代中,主问题都会确定这些复杂变量的取值。
数值实验在本节中,我们首先详细描述了实例生成的方法。接着,我们进行初步实验,以评估所提下界的严格程度,以及FLBBD算法及其各个组件(包括最优下界、通过启发式算法得到的上界、针对子问题设计的约束编程模型,以及所提出的组合切割和解析切割)的效率。最后,我们展示了小型、中型和大型实例的详细计算结果,并对其进行了总结。
结论与未来展望在本文中,我们研究了一种具有顺序依赖准备时间的新型并行机器调度与选址问题。我们的目标是通过优化选择机器位置、将任务分配到这些位置的机器上,以及确定任务处理顺序,同时考虑实际应用中普遍存在的顺序依赖准备时间,从而最小化总处理时间。我们首先将该问题形式化为MILP模型,然后引入针对该问题的有效不等式,进一步强化模型。
作者贡献声明王云:撰写——初稿、可视化、软件应用、方法论、概念构思。吴鹏:撰写——审阅与编辑、监督、方法论、资金获取、概念构思。袁哲:撰写——审阅与编辑、监督。龚业明:撰写——审阅与编辑、监督。阿贾伊·库马尔:撰写——审阅与编辑、监督。
利益冲突声明作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。
致谢本研究得到了中国国家自然科学基金的支持,项目编号为72571068。作者感谢所有审稿人和编辑提出的宝贵意见和建议。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号