启发式列生成算法求解带恶化效应的同构并行机调度问题

作     者：孙鑫伟 钱斌 胡蓉 张森 于乃康 SUN Xin-wei;QIAN Bin;HU Rong;ZHANG Sen;YU Nai-kang

作者机构：昆明理工大学信息工程与自动化学院昆明650500 昆明理工大学云南省人工智能重点实验室昆明650500 

基　　金：国家自然科学基金项目(62173169,61963022) 云南省基础研究重点项目(202201AS070030) 

出 版 物：《控制与决策》 (Control and Decision)

年 卷 期：2024年第39卷第5期

页      码：1636-1644页

摘      要：针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解. HCGA与商用求解器GUROBI的对比实验结果表明, HCGA可在较短时间内获得更优的解.

主 题 词：并行机 恶化效应 最大完工时间 列生成 动态规划 深潜启发式 

学科分类：08[工学] 0802[工学-机械学] 0835[0835] 080201[080201] 

核心收录：

D　O　I：10.13195/j.kzyjc.2022.1615

馆 藏 号：203127504...