[1]裴小兵,孙志卫.改进区块遗传算法解决分布式车间调度问题[J].智能系统学报,2021,16(2):303-312.[doi:10.11992/tis.201906035]
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]
点击复制
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]
改进区块遗传算法解决分布式车间调度问题
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
16
期数:
2021年第2期
页码:
303-312
栏目:
学术论文—智能系统
出版日期:
2021-03-05
- Title:
- Solving distributed-shop scheduling problems based on modified genetic algorithm
- Keywords:
- block; synergistic effect; artificial chromosomes; distributed job shop scheduling problem; genetic algorithm; gene recombination; probability matrix; combinatorial optimization
- 分类号:
- TP18
- 摘要:
- 针对分布式车间调度问题，提出了改进区块遗传算法(modified block-genetic algorithm，MBGA)。用NEH和随机性两种方式得到高质量的初始解，然后进行统计分析，选出精英染色体，建立工件?车间分配矩阵和工件?机器排序矩阵，挖掘联系紧密的基因链组成区块。构建基于区块的人工染色体，并进行基因重组，提高解的质量和多样性。通过算例与其他知名算法进行比较，结果表明该算法优于其他算法，并具有较好的稳定性和准确性。
- 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.
备注/Memo
收稿日期:2019-06-19。
基金项目:国家创新方法工作专项（2017M010800）
作者简介:裴小兵，教授，博士，天津工业工程学会理事，主要研究方向为生产调度、精益生产。发表学术论文40余篇;孙志卫，硕士研究生，主要研究方向为生产调度、智能算法
通讯作者:孙志卫.E-mail:2838569310@qq.com
更新日期/Last Update:
2021-04-25