引用本文:方子丞,李新宇,高亮.带负载均衡的混合算法求解分布式异构作业车间调度问题[J].控制理论与应用,2024,41(6):977~989.[点击复制]
FANG Zi-cheng,LI Xin-yu,GAO Liang.Hybrid algorithm considering workload balance for solving the distributed heterogeneous job shop scheduling problem[J].Control Theory and Technology,2024,41(6):977~989.[点击复制]
带负载均衡的混合算法求解分布式异构作业车间调度问题
Hybrid algorithm considering workload balance for solving the distributed heterogeneous job shop scheduling problem
摘要点击 748  全文点击 213  投稿时间：2022-07-19  修订日期：2022-12-20
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  DOI: 10.7641/CTA.2023.20644
  2024,41(6):977-989
中文关键词  作业车间调度  分布式异构工厂  负载均衡  混合算法  最大完工时间
英文关键词  job shop scheduling  distributed heterogeneous factory  load balance  hybrid algorithm  makespan
基金项目  国家自然科学基金项目(51825502), 湖北省科技重大专项(2021AAB001)资助.
作者单位E-mail
方子丞 华中科技大学 数字制造装备与技术国家重点实验室 809359761@qq.com 
李新宇 华中科技大学 数字制造装备与技术国家重点实验室  
高亮* 华中科技大学 数字制造装备与技术国家重点实验室 gaoliang@hust.edu.cn 
中文摘要
      针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(DHJSP), 本文提出了一种新的混合遗传禁忌搜索算法. 首先, 综合考虑工厂的工件总负载与最大机器负载, 提出了一种新的工厂负载表达方式. 其次, 针对DHJSP总工序数不定的特性, 提出以最小化最大工厂负载为目标快速确定初始工件分配方案, 并验证了方法的高效性. 然后, 新设计了两种考虑负载均衡的单工件转移邻域结构, 根据工序调度的结果对工件分配方案进行局部搜索. 最后, 因DHJSP缺少标准算例和相关算法, 在分布式同构作业车间调度问题(DJSP)上与现有算法进行对比, 所提算法在TA算例的480个问题上更新了420个问题的最优解, 其余60个问题取得了同等最优解. 在随机生成的3个不同规模的异构算例中, 所提算法也均取得了较好解, 验证了所提方法的优越性.
英文摘要
      Aiming at the distributed heterogeneous job shop scheduling problem (DHJSP) with minimizing makespan, this paper proposes a new hybrid method considering workload balance which hybridizes the genetic algorithm and tabu search. Firstly, considering the total job load and the maximum machine load, a new expression of factory load is proposed. Secondly, for the uncertainty of total operation quantity of DHJSP, a rapid method is proposed with the goal of minimizing the maximum factory load to obtain initial job allocation, and the efficiency of the method is verified. Then, two new job transfer neighborhood structures considering load balance are designed and perform local search of job allocation according to the results of operation schedule. Finally, due to the lack of benchmark and algorithm for heterogeneous problem, comparison is made with the existing state-of-the-art algorithms for homogeneous problem. The proposed algorithm got better results of 420 problems and obtained the same optimal solution for the other 60 problems in 480 homogeneous problems of TA benchmark. As for 3 generated heterogeneous instances of different scales, good solutions are also obtained. The superiority of the proposed method is verified.