《基于遗传算法的作业车间调度问题实证研究》10000字（论文）

[18]（FlexibleJobShopSchedulingProblem,FJSP）是传统的Job-Shop调度问题的扩展，作业车间的静态调度问题中工件要在确定的机器上加工；而本节所研究的柔性作业车间调度，有多台机器可以对某一个工件的某一道工序进行加工，并且他们的加工时间也不相同，如此一来就指数倍的增加了可行解的数量，大大增加了求解的难度。柔性作业车间调度问题的问题描述即为：一个作业车间中有m台机器，现需要在这m台机器上加工n个工件，这n个工件中每个工件都需要若干道的加工工序，每道工序只能在某几台特定的机器上才能加工，并且在这几台不同的机器上加工所需要的加工时间也不一样；每个工件只有完成前一道工序才可以继续进行下一道工序，要求合理的对工件的加工顺序及加工机器进行调度分配，使得加工时间能够达到最短。其约束条件如下：1.每个工件只有完成上一道工序才可以进行下一道工序；2.每个工件的每道工序在不同机器上加工的优先级都相同；3.各个工件的各道工序在同一台机器上的加工优先级都相同；4.每台机器在同一时刻只能加工一个工件的一道工序；5.每个工件在同一时刻只能被一台机器加工一道工序；6.不考虑机器损坏及加工人意愿。在此我们提出以下具体问题进行研究：表4.1FJSP例题1工件工序加工机器及时间M1M2M3M4M5M6M7M8J1114432108712806654761308075357J221483670100220744859723080546282499769600J3318009668232095778903323470908J441425688924210128795684338595427J55146561009052809657605307958760541010089648J66158524809621208895736398813120110J7717535801107208081289673010849708J8813768050128284375012083880876318480452670（二）柔性作业车间调度问题的算法实现柔性作业车间调度问题是在传统的作业车间调度问题的基础之上所提出来的，因此在求解的思路上也大同小异，尽管在编码解码以及交叉等操作方面有所改动，但总体思路不变，只需按照前面所提到的流程思想继续进行算法的编写即可。1.编码和解码在作业车间的静态调度问题中每个个体只有一条染色体，代表的是工件的加工顺序。在柔性作业车间的调度问题中，由于我们放宽了加工机器对于工件加工的约束，使得我们可行解的范围增大，因此我们在JSP基础之上为每一个个体增加了一条染色体。第一条染色体同静态调度中个体的染色体一样代表工件的加工工序，而第二条染色体表示的是每一个工件的每一个工序的加工机器，这样就能够完整的表现出工件的加工方案。例如以下一个个体：P1:131312322145233455其中第二行表示的是每一个工件的每一道工序分别在哪一台机器上加工，如工件1的三道工序分别在机器1/4/5上加工。这样表示的好处在于在接下来的交叉操作中，基于机器分配编码基因中可以只使得同一个工件的同一个工序进行交换，这样一来就能保证了所产生的子代的可行性。2.初始化种群柔性作业车间调度问题的种群初始化时要尤其注意个体的可行性，因为现在每一个个体拥有两条染色体，在基于工序的编码基础之上，再通过将给出的工件的每一道工序的可加工机器作为一种约束，进而来产生初始化的种群个体。3.适应度计算适应度的计算也同传统的作业车间调度问题一样，将个体基因解码之后将染色体转化为调度方案，计算其加工时间，仍然选取适应度函数为加工时间的倒数。4.交叉操作由于现在的每个个体拥有了两条染色体，在生物学上不同的染色体所控制的是不同的性状，个体之间的基因交换仅限于控制相同性状的染色体之间的基因交换，所以我们把基于工序编码基因的染色体和基于机器分配编码基因的染色体分别进行交叉，且由于这俩染色体所描述的信息的特性不同，所以对其进行的交叉操作采用不同的交叉方式。（1）基于工序编码基因的交叉同静态作业车间调度问题一样，仍选择IPOX交叉因子，其操作过程同3.2.4所述，在此不再赘述。（2）基于机器分配编码基因的交叉对于机器分配编码基因，在此选取了MPX交叉因子的方法。它能够对加工顺序和加工机器分别进行交叉，其交叉过程如下所述：首先产生一个由0，1组成的长度同机器分配编码基因相同的集称为Z；对于父代P1和P2，其产生的子代C1和C2，若Z在某一处为0，则P1,C1;P2,C2在该处的值一一对应，反之若Z在某一处为1，则P1,C2;P2,C1在该处的值一一相对应。例如：P1:124561235125P2：426354221135010100010110则C1:124361225135C2:426554231125由于是同一工序的加工机器交换，所以产生的子代必定会是可行解。5.变异操作在此变异操作的目的为改善算法的局部搜索能力和维持群体多样性，也能够防止算法过早收敛，对于两种基因编码在此采取不同的两种变异方式。（1）基于工序编码基因的变异同3.2.5所述。（2）基于机器分配编码基因的变异鉴于在柔性作业车间调度问题中每一道工序都可以有多台机器完成，故在此可随机选择一道工序，查阅这道工序可被加工的机器，并综合考虑加工时间最短的那台机器，实现变异操作。6.选择操作同3.2.6所述。（三）FJSP仿真结果及分析同样根据以上分析我们搭建了MATLAB模型来进行仿真，通过多次仿真得到以下结果：图4.1FJSP第一次仿真甘特图图4.2FJSP第二次仿真甘特图图4.3FJSP第三次仿真甘特图对比图4.1，图4.2，图4.3所给出的甘特图，FJSP所给出的问题模型更为的复杂，因此在求解上所具有的可能性也更多，仿真三次所得到的三个加工方案的最优解并不相同，且不同方案之间也是有着较大的差别，故在FJSP问题上还有待继续深入研究。可见相对于作业车间的静态调度问题，柔性作业车间调度问题更为复杂，可行解也更多，但已能基本实现要求，给出相应的解决问题的基本方案。五、总结与展望车间调度问题作为制造系统的核心，是企业提升竞争力的重要途径，本文简要的分析了车间调度问题，并且简述了遗传算法的基本原理。基于MATLAB仿真，研究了基于遗传算法的JSP和FJSP两个车间调度问题实例，更加深入的说明了调度问题的特点，表明了智能算法在解决传统经典问题上的可能性。本文仅仅是简单的阐述了两个经典的车间调度问题，并且简要的介绍了遗传算法，然而车间调度问题并不是仅限于此，遗传算法也可以通过与其他算法相结合，或者增添新的过程处理机制来实现更为优秀的效果，作为一种通用的算法，遗传算法有望应用在其他领域去解决一些其他问题。尽管目前为止对车间调度问题的研究已经有了几十年的历史，也提出了众多新颖新奇且实用的算法，但仍没有一套系统的理论和方法来解决有关车间调度的这一类问题，且对车间调度问题的研究仍停留在理论上，与实际应用之间还存在着较大的差距，有待专家学者们继续深入研究。参考文献肖艳伶.金融科技创新对实体经济发展的影响研究[J].河北农机,2021(04):94-95.王珏,唐青青.以培育新优势实现中国制造业转型升级[J].西北大学学报(哲学社会科学版),2021,51(03):69-79.PruetthaNanakorn,KonlakartnMeesomklin.ANovelPenaltySchemeinGeneticAlgorithmsForStructuralDesignOptimization[J].ASEANJournalonScienceandTechnologyforDevelopment,2000,17(2).金晶,苏勇.一种改进的自适应遗传算法[J].计算机工程与应用,2005(18):64-69.张海涛.基于遗传算法的车间作业调度问题研究[D].沈阳理工大学,2016.刘连成,陆淑珍,刘悦辰.整数规划法在优化模拟生产实习中的应用[J].襄阳职业技术学院学报,2014,13(01):11-14.DavidA.Plaisted.AHeuristicAlgorithmforSmallSeparatorsinArbitraryGraphs[J].SIAMJournalonComputing,2006,19(2).张煜东,吴乐南,王水花.专家系统发展综述[J].计算机工程与应用,2010,46(19):43-47.周飞燕,金林鹏,董军.卷积神经网络研究综述[J].计算机学报,2017,40(06):1229-1251.朱祥磊.加速AI分布式训练研究和实践[J].电信技术,2019(12):28-31.黎静华,韦化.求解机组组合问题的领域搜索法[J].中国电机工程学报,2008(13):33-40.刘宏磊,张佳欢,谢添.作业车间调度问题(JSP)研究综述报告[J].装备制造技术,2015(12):235-237.王明.基于改进遗传算法的作业车间调度问题研究[D].安徽工程大学,2019.韩明.遗传算法在作业车间调度问题中的应用[D].吉林大学,2015.张超勇,饶运清,刘向军,李培根.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程,2004(23):83-87.王芳,邱玉辉.一种引入轮盘赌选择算子的混合粒子群算法[J].西南师范大学学报(自然科学版),2006(03):93-96.何燕.基于遗传算法的车间调度优化及其仿真[D].武汉理工大学,2006.AsmaFekih,HatemHad