带负载均衡的混合算法求解分布式异构作业车间调度问题

Hybrid algorithm considering workload balance for solving the distributed heterogeneous job shop scheduling problem

针对以最小化最大完工时间为目标的分布式异构作业车间调度问题(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.