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

作者：孙鑫伟; 钱斌^*; 胡蓉; 张森; 于乃康

来源：控制与决策, 2023, 1-9.

DOI：10.13195/j.kzyjc.2022.1615

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

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

• 单位
  自动化学院; 昆明理工大学