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

1. 昆明理工大学 信息工程与自动化学院,昆明 650500;2. 昆明理工大学 云南省人工智能重点实验室,昆明 650500

作者简介:

通讯作者:

E-mail: bin.qian@vip.163.com.

中图分类号:

TP273

基金项目:

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


Heuristic column generation algorithm for identical parallel machine scheduling problem with deterioration effect
Author:
Affiliation:

1. Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;2. Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming 650500,China

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    An integer programming model is built to minimize the maximum completion time and a heuristic column generation algorithm(HCGA) is proposed for a class of identical parallel machine scheduling problem with deterioration effect that widely exist in practical production. In the HCGA, first, the original problem is decomposed into a master problem(MP) and multiple subproblems by using the Dantzig-Wolfe decomposition method. Secondly, a heuristic algorithm is designed to obtain initial columns, where each column represents a schedule on one machine. Based on the initial columns, a restricted MP(RMP) model is constructed. Then, a fast and effective dynamic programming algorithm is designed to solve each subproblem to obtain the column set to be added to the RMP. At the same time, considering that the convergence speed of traditional column generation algorithms is slow, a series of methods are designed to accelerate the column generation process. Finally, based on the obtained linear relaxation solution of the MP, a diving heuristic algorithm is designed to determine the integer solution of the original problem. According to the comparative experimental results of the HCGA and commercial solver GUROBI, the HCGA can obtain better solutions in a shorter time.

    参考文献
    相似文献
    引证文献
引用本文

孙鑫伟,钱斌,胡蓉,等.启发式列生成算法求解带恶化效应的同构并行机调度问题[J].控制与决策,2024,39(5):1636-1644

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2024-04-17
  • 出版日期: 2024-05-20
文章二维码