近日，由大连理工大学经济管理学院于洋教授担任第一作者，李晓龙博士后担任通讯作者，与哈马德·本·哈利法大学Roberto Baldacci教授、东北财经大学唐加福教授、吴志樵教授、朱晗教授、孙薇教授合作论文“An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem”（一种求解非相关并行机调度问题的分支定价割平面算法）在国际顶级期刊《INFORMS Journal on Computing》在线发表。
《INFORMS Journal on Computing》是美国运筹与管理科学学（INFORMS）主办的旗舰期刊，创办于1989年，是 UTD 24 顶级期刊之一，在管理科学、运筹学和计算优化领域具有极高的学术影响力，是运筹学与工业工程领域的风向标。
研究概况
非相关并行机调度问题是组合优化领域的经典难题。然而，受限于该问题的NP难特性，现有精确算法的求解规模极小，只能求解20机器、100作业且加工时间为整数的实例，严重制约了算法在实际问题中的适用性。
为了突破现有算法的计算瓶颈，研究团队提出了一种改进的分支定价割平面算法。该算法融合了多种前沿技术，包括基于桶图的标签算法、有限内存子集行割、对偶平滑、缩减成本固定以及多阶段强分支等。对于文献基准算例，该算法能够求解300个实例中的298个，并首次将精确算法的适用规模拓展至20台机器、200个作业的大规模实例；对于来自京东履约中心的真实数据场景，传统算法受有理数加工时间带来的计算复杂性影响，未能求解任何实例；相比之下，本文算法成功求解60个真实实例中的49个，显示出较强的工业适用性。
鉴于以上卓越的算法性能，团队为该问题建立标准实例库，推动资源开放共享，以便同行学者进行对比验证与深入探究。标准实例库位于：https://faculty.dlut.edu.cn/yuyang13/zh_CN/article/1175662/content/6239.htm#article
实际应用与前景
该研究为大规模非相关并行机调度问题提供了高效求解工具，可广泛应用于生产调度、手术安排、云计算任务分配、技术员调度、反无人机防守作战、快递订单拣选等实际场景，为复杂调度决策提供理论支撑和技术手段。
作者简介
于洋，大连理工大学经济管理学院教授、博士生导师。长期致力于研究经典优化问题的大规模精确算法与人工智能技术研究，聚焦生产调度及物流配送优化等方向。发表SCI论文60余篇，其中第一/通讯作者论文30余篇，包括INFORMS Journal on Computing（UTD 24）2篇、Transportation Science 1篇、Transportation Research Part B 4篇、European Journal of Operational Research 3篇。出版学术专著2部。2022年美国大学生数学建模竞赛（MCM/ICM）Finalist奖指导教师。
李晓龙，大连理工大学经济管理学院博士后。长期致力于研究生产与调度领域的组合优化问题，涵盖非相关并行机调度及赛汝生产系统运作优化。主要研究兴趣包括大规模精确算法以及深度学习在组合优化与精确算法中的应用。研究成果发表于INFORMS Journal on Computing、European Journal of Operational Research、Computers & Operations Research、International Journal of Production Research、系统工程理论与实践等国内外权威期刊。
上一条：大连理工大学经济管理学院成功举办第三届商业人工智能夏季学术会议（SWAIB 2026）
下一条：经济管理学院党委召开2024-2026年度党内“两优一先”表彰大会
【关闭】
