[1]PEI Xiaobing,SUN Zhiwei.Solving distributed-shop scheduling problems based on modified genetic algorithm[J].CAAI Transactions on Intelligent Systems,2021,16(2):303-312.[doi:10.11992/tis.201906035]
Copy

Solving distributed-shop scheduling problems based on modified genetic algorithm

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 16 Number of periods: 2021 2 Page number: 303-312 Column: 学术论文—智能系统 Public date: 2021-03-05
Title:
Solving distributed-shop scheduling problems based on modified genetic algorithm
Author(s):
PEI Xiaobing;  SUN Zhiwei
School of Management, Tianjin University of Technology, Tianjin 300384, China
Keywords:
block; synergistic effect; artificial chromosomes; distributed job shop scheduling problem; genetic algorithm; gene recombination; probability matrix; combinatorial optimization
CLC:
TP18
DOI:
10.11992/tis.201906035
Abstract:
To solve distributed-job-shop scheduling problems, in this paper, we propose a modified block-genetic algorithm (MBGA). First, we initialize the solutions by combining NEH and random assignments. Then, by statistical analysis, we select an elite chromosome to establish a job-factory distribution matrix and job-machine sorting matrix to mine the block’s closely linked gene chain. Block-based artificial chromosomes are constructed and recombined to improve the quality and diversity of the solutions. The experimental results show that the performance of the proposed MBGA algorithm is superior to that of other well-known algorithms with respect to its stability and accuracy.
References:
[1] JIA H Z, FUH J Y H, NEE A Y C, et al. Web-based multi-functional scheduling system for a distributed manufacturing environment[J]. Concurrent engineering, 2002, 10(1):27-39.
[2] 谢志强, 周含笑, 桂忠艳, 等. 基于拟关键路径的二车间综合调度算法[J]. 计算机科学, 2013, 40(4):193-198
XIE Zhiqiang, ZHOU Hanxiao, GUI Zhongyan, et al. Integrated scheduling algorithm of two workshops based on ACPM[J]. Computer science, 2013, 40(4):193-198
[3] BARGAOUI H, DRISS O B, GHéDIRA K. Minimizing makespan in multi-factory flow shop problem using a chemical reaction metaheuristic[C]//Proceedings of 2016 IEEE Congress on Evolutionary Computation. Vancouver, Canada, 2016.
[4] 谢志强, 郭禾, 苏文秀, 等. 存在多工序同时结束的多车间逆序综合调度算法[J]. 吉林大学学报(工学版), 2018, 48(2):578-587
XIE Zhiqiang, GUO He, SU Wenxiu, et al. Reversal sequence integrated scheduling algorithm of multiple workshop with multi-procedures ended together[J]. Journal of Jilin University (Engineering and Technology Edition), 2018, 48(2):578-587
[5] 王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策, 2016, 31(1):1-11
WANG Ling, DENG Jin, WANG Shengyao. Survey on optimization algorithms for distributed shop scheduling[J]. Control and decision, 2016, 31(1):1-11
[6] AZAB A, NADERI B. Greedy heuristics for distributed job shop problems[J]. Procedia CIRP, 2014, 20:7-12.
[7] ZHANG Rui, SONG Shiji, WU Cheng. A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem[J]. The international journal of advanced manufacturing technology, 2013, 67(1/2/3/4):5-17.
[8] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of operations research, 1976, 1(2):117-129.
[9] WAGNER H M. An integer linear-programming model for machine scheduling[J]. Naval research logistics quarterly, 1959, 6(2):131-140.
[10] JIA H Z, NEE A Y C, FUH J Y H, et al. A modified genetic algorithm for distributed scheduling problems[J]. Journal of intelligent manufacturing, 2003, 14(3/4):351-362.
[11] 王和敏, 谷淼, 魏志谦, 等. 基于混合遗传算法的Job Shop问题研究与实现[J]. 新技术新工艺, 2017(8):69-73
WANG Hemin, GU Miao, WEI Zhiqian, et al. The Research and implement of Job Shop problem based on hybrid genetic algorithm[J]. New technology & new process, 2017(8):69-73
[12] NADERI B, AZAB A. Modeling and heuristics for scheduling of distributed job shops[J]. Expert systems with applications, 2014, 41(17):7754-7763.
[13] CHAOUCH I, DRISS O B, GHEDIRA K. A modified ant colony optimization algorithm for the distributed job shop scheduling problem[J]. Procedia computer science, 2017, 112:296-305.
[14] NADERI B, AZAB A. An improved model and novel simulated annealing for distributed job shop problems[J]. The international journal of advanced manufacturing technology, 2015, 81(1/2/3/4):693-703.
[15] 杨敬松, 夏秀峰, 崔广才. 混合遗传算法在分布式车间作业调度中的应用[J]. 计算机工程与应用, 2005, 41(19):213-215, 225
YANG Jingsong, XIA Xiufeng, CUI Guangcai. The Distribution method of planning and scheduling based on a hybrid genetic algorithm[J]. Computer engineering and applications, 2005, 41(19):213-215, 225
[16] 高雪瑶, 谭涛, 张春祥. 遗传退火算法的模型相似性计算方法[J]. 哈尔滨工程大学学报, 2020, 41(7):1073-1079
GAO Xueyao, TAN Tao, ZHANG Chunxiang. Method of calculating model similarity based on genetic annealing algorithm[J]. Journal of Harbin Engineering University, 2020, 41(7):1073-1079
[17] CHANG P C, HUANG W H, WU J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International journal of production economics, 2013, 141(1):45-55.
[18] CHANG P C, CHEN Menghui. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft computing, 2014, 18(6):1177-1188.
[19] 裴小兵, 于秀燕. 改进猫群算法求解置换流水车间调度问题[J]. 智能系统学报, 2019, 14(4):769-778
PEI Xiaobing, YU Xiuyan. Improved cat swarm optimization for permutation flow shop scheduling problem[J]. CAAI transactions on intelligent systems, 2019, 14(4):769-778
[20] 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流水车间问题[J]. 计算机集成制造系统, 2018, 24(5):1207-1216
ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop scheduling problem[J]. Computer integrated manufacturing system, 2018, 24(5):1207-1216
[21] 裴小兵, 张春花. 应用改进区块遗传算法求解置换流水车间调度问题[J]. 智能系统学报, 2019, 14(3):541-550
PEI Xiaobing, ZHANG Chunhua. An improved puzzle-based genetic algorithm for solving permutation flow-shop scheduling problems[J]. CAAI transactions on intelligent systems, 2019, 14(3):541-550
[22] CHAOUCH I, DRISS O B, GHEDIRA K. A survey of optimization techniques for distributed job shop scheduling problems in multi-factories[C]//Proceedings of the 6th Computer Science On-line Conference. Cham, Germany, 2017.
Similar References:

Memo

-

Last Update: 2021-04-25

Copyright © CAAI Transactions on Intelligent Systems