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

被引：0

作者：

Fang Z.-C. ^{[1
]}

Li X.-Y. ^{[1
]}

Gao L. ^{[1
]}

机构：

[1] State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Hubei, Wuhan

来源：

Kongzhi Lilun Yu Yingyong/Control Theory and Applications | 2024年 / 41卷 / 06期

基金：

中国国家自然科学基金;

关键词：

distributed heterogeneous factory; hybrid algorithm; job shop scheduling; load balance; makespan;

D O I：

10.7641/CTA.2023.20644

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. © 2024 South China University of Technology. All rights reserved.

引用

页码：977 / 989

页数：12

共 22 条

[1]

OKWUDIRE C E, MADHYASTHA H V., Distributed manufacturing for and by the masses, Science, 372, 6540, pp. 341-342, (2021)

[2]

WANG Ling, DENG Jin, WANG Shengyao, Survey on optimization algorithm for distributed shop scheduling, Control and Decision, 31, 1, pp. 1-11, (2016)

[3]

WANG Sihan, LI Xinyu, GAO Liang, Et al., A review of distributed shop scheduling problems, Journal of Huazhong University of Science and Technology (Natural Science Edition), 50, 6, pp. 1-10, (2022)

[4]

WANG J J, WANG L., A bi-population cooperative memetic algorithm for distributed hybrid flow-shop scheduling, IEEE Transactions on Emerging Topics in Computational Intelligence, 5, 6, pp. 947-961, (2021)

[5]

ZHANG Z Q, HU R, QIAN B, Et al., A matrix cube-based estimation of distribution algorithm for the energy-efficient distributed assembly permutation flow-shop scheduling problem, Expert Systems with Applications, 194, (2022)

[6]

ZHAO F Q, MA R, WANG L., A self-learning discrete Jaya algorithm for multiobjective energy-efficient distributed no-idle flow-shop scheduling problem in heterogeneous factory system, IEEE Transactions on Cybernetics, 52, 12, pp. 12675-12686, (2022)

[7]

JIANG E D, WANG L, WANG J J., Decomposition-based multiobjective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, 26, 5, pp. 646-663, (2021)

[8]

SAHMAN M A., A discrete spotted hyena optimizer for solving distributed job shop scheduling problems, Applied Soft Computing, 26, 5, pp. 646-663, (2021)

[9]

CHAOUCH I, DRISS O B, GHEDIRA K., A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm, Applied Intelligence, 49, 5, pp. 1903-1924, (2019)

[10]

XIE J, GAO L, PAN Q K, Et al., An effective multi-objective artificial bee colony algorithm for energy efficient distributed job shop scheduling, Procedia Manufacturing, 39, pp. 1194-1203, (2019)

← 1 2 3 →