[1]李雪花,高全力,赵 辉,等.求解柔性作业车间调度问题的混合遗传算法[J].计算机技术与发展,2022,32(08):185-190.[doi:10. 3969 / j. issn. 1673-629X. 2022. 08. 030]
　LI Xue-hua,GAO Quan-li,ZHAO Hui,et al.A Hybrid Genetic Algorithm of Solving Flexible Job-shop Scheduling Problem[J].,2022,32(08):185-190.[doi:10. 3969 / j. issn. 1673-629X. 2022. 08. 030]
点击复制

求解柔性作业车间调度问题的混合遗传算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
32
期数:
2022年08期
页码:
185-190
栏目:
应用前沿与综合
出版日期:
2022-08-10

文章信息/Info

Title:
A Hybrid Genetic Algorithm of Solving Flexible Job-shop Scheduling Problem
文章编号:
1673-629X(2022)08-0185-06
作者:
李雪花1; 高全力1; 赵 辉2; 杨 昊1; 金 帅2; 徐国梁3
1. 西安工程大学 计算机科学学院,陕西 西安 710048;
2. 山东如意毛纺服装集团股份有限公司,山东 济宁 272000;
3. 山东如意恒成产研新材料科技有限公司,山东 济宁 272000
Author(s):
LI Xue-hua1; GAO Quan-li1; ZHAO Hui2; YANG Hao1; JIN Shuai2; XU Guo-liang3
1. School of Computer Science,Xi’an Polytechnic University,Xi’an 710048,China;
2. Shandong Ruyi Woolen Garment Group Co. , Ltd. ,Jining 272000,China;
3. Shandong Ruyi Hengcheng New Material Technology Co. , Ltd. ,Jining 272000,China
关键词:
柔性作业车间调度; 遗传算法; 混合蛙跳算法; 优良种子库; 交叉变异
Keywords:
flexible job shop scheduling; genetic algorithm; shuffled frog leaping algorithm; good seed bank; crossover mutation
分类号:
TP393
DOI:
10. 3969 / j. issn. 1673-629X. 2022. 08. 030
摘要:
针对用遗传算法求解柔性作业车间调度问题过程中所表现的局部搜索能力差及易“早熟”现象,提出了一种将遗传算法与混合蛙跳算法相结合的混合算法用于求解单目标柔性车间调度问题。 首先对单目标柔性车间调度问题进行建模,然后对算法的整体流程进行阐述,在遗传算法的基础上,在初始种群生成时采用混沌理论产生分布均匀的随机数提高初始种群在解空间分布的均匀性,并针对柔性车间调度问题的特性改进遗传算法的交叉方式及变异规则;并在遗传算法每轮迭代后,将表现优异的个体加入优良种子库进行保护,并采用混合蛙跳算法对优良种子库进行局部搜索寻优,将得到的更优解与下轮个体交叉迭代,提高局部搜索能力,改善传统遗传算法“早熟”问题。 通过对 Brandimarte(mk01 ~ mk10)算例进行仿真测试及对比其他算法,该算法得到了目前的 MK08 算例的最优解,证明了该算法具有一定的有效性与可行性。
Abstract:
Aiming at the poor local search ability and easy "premature" phenomenon in the process of using genetic algorithm to solveflexible job shop scheduling problems,we propose a hybrid algorithm that combines genetic algorithm and shuffled frog leaping algorithmto solve single-object flexible job shop scheduling problem. Firstly,the single-objective flexible job shop scheduling problem is modeled,and then the overall process of the algorithm is described. On the basis of genetic algorithm,chaos theory is used to generate uniformly distributed random numbers when the initial population is generated to improve the uniformity of the initial population distributionin the solution space and improve the crossover mode and mutation rules of genetic algorithm according to the characteristics of flexiblejob shop scheduling. After each iteration of the genetic algorithm,the individuals with excellent performance are added to the excellentseed bank for protection,and the shuffled frog leaping algorithm is used to search for local optimization of the good seed bank,and thebetter solution is cross-iterated with the individuals in the next round to improve the local search ability and improve the "premature" problem of traditional genetic algorithm. Through the simulation test of the Brandimarte (mk01~ mk10) example and comparison withother algorithms,the proposed algorithm obtains the optimal solution of the current MK08 example,which proves its effectiveness andfeasibility.

相似文献/References:

[1]冯智明,苏一丹,覃华,等.基于遗传算法的聚类与协同过滤组合推荐算法[J].计算机技术与发展,2014,24(01):35.
　FENG Zhi-ming,SU Yi-dan,QIN Hua,et al.Recommendation Algorithm of Combining Clustering with Collaborative Filtering Based on Genetic Algorithm[J].,2014,24(08):35.
[2]余晓光 严洪森 殷乾坤.基于Flexsim的车间调度优化[J].计算机技术与发展,2010,(03):44.
　YU Xiao-guang,YAN Hong-sen,YIN Qian-kun.Workshops Scheduling Optimization Based on Flexsim Simulation[J].,2010,(08):44.
[3]贺计文 宋承祥 刘弘.基于遗传算法的八数码问题的设计及实现[J].计算机技术与发展,2010,(03):105.
　HE Ji-wen,SONG Cheng-xiang,LIU Hong.Design and Implementation of Eight Puzzle Problem Based on Genetic Algorithms[J].,2010,(08):105.
[4]沈珏萍 庄亚明.基于Agent的二级供应链企业自动谈判研究[J].计算机技术与发展,2010,(03):121.
　SHEN Jue-ping,ZHUANG Ya-ming.A Research for Company Automatic Negotiation in Secondary Supply Chain Based on Agent[J].,2010,(08):121.
[5]张磊 王晓军.基于遗传算法的业务流程测试[J].计算机技术与发展,2010,(03):155.
　ZHANG Lei,WANG Xiao-jun.Test of Business Process Based on Genetic Algorithm[J].,2010,(08):155.
[6]曹道友 程家兴.基于改进的选择算子和交叉算子的遗传算法[J].计算机技术与发展,2010,(02):44.
　CAO Dao-you,CHENG Jia-xing.A Genetic Algorithm Based on Modified Selection Operator and Crossover Operator[J].,2010,(08):44.
[7]范维博 周俊 许正良.应用遗传算法求解第一类装配线平衡问题[J].计算机技术与发展,2010,(02):194.
　FAN Wei-bo,ZHOU Jun,XU Zheng-liang.Appication of Genetic Algorithm to Assembly Line Balancing[J].,2010,(08):194.
[8]熊伟平 曾碧卿.几种仿生优化算法的比较研究[J].计算机技术与发展,2010,(03):9.
　XIONG Wei-ping,ZENG Bi-qing.Studies on Some Bionic Optimization Algorithms[J].,2010,(08):9.
[9]余晓光 严洪森.基于禁忌搜索遗传混合算法的装配线平衡[J].计算机技术与发展,2010,(05):5.
　YU Xiao-guang,YAN Hong-sen.Assembly Line Balancing Based on Tabu Search and Genetic Hybrid Algorithm[J].,2010,(08):5.
[10]黄永聪 张旭[] 吴义纯 吴琦 程家兴.改进的径向基函数网络的研究及应用[J].计算机技术与发展,2010,(05):158.
　HUANG Yong-cong,ZHANG Xu,WU Yi-chun,et al.Research and Application of Improved Genetic Algorithm-Based RBFANN[J].,2010,(08):158.

更新日期/Last Update: 2022-08-10