Hybrid algorithm considering workload balance for solving the distributed heterogeneous job shop scheduling problem
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,com-parison 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.
国家科技期刊平台
