求解车间作业调度问题的混合遗传算法_刘胜辉

融合路径重连的混合算法求解作业车间调度问题孟悦; 赵诗奎【期刊名称】《《机械工程师》》【年(卷),期】2019(000)012【总页数】6页(P32-36,39)【关键词】作业车间调度问题; 遗传算法; 邻域结构; 路径重连【作者】孟悦; 赵诗奎【作者单位】济南大学机械工程学院济南250022【正文语种】中文【中图分类】TP3910 引言随着“中国制造2025”高科技战略计划的提出，我国制造业正向高速度、高质量方向发展，因此高效的生产调度优化技术是必不可少的，不仅可以提高产品生产率、设备利用率和缩短产品生产周期，同时对提高企业的生产力和竞争力具有重大意义。

作业车间调度问题（Job shop scheduling problem，JSP）作为生产调度的核心内容和关键技术，直接影响着企业的生产和管理效率，合理有效的调度方案能够为企业带来巨大的收益。

JSP问题作为典型的“NP-hard”问题，具有动态性、离散性、耦合性等多种特性，采用智能算法对其求解已成为重要的研究内容。

目前针对JSP问题求解的智能算法层出不穷，纵观目前文献中，大量学者融合路径重连与智能算法优化求解JSP问题，2003年，Aiex等[1]将路径重连与贪婪随机自适应搜索算法融合，在一定的约束条件下，重新进行路径组合，探索连接高质量解的轨迹；Nasiri等[2]在N1邻域结构的基础上，融合路径重连与禁忌搜索算法高效求解JSP问题；Spanos等[3]融合遗传算法与具有路径重连思想的交叉变异算子对JSP问题进行求解；Peng等[4]在基于N7邻域结构基础上，融合路径重连与禁忌搜索算法求解JSP问题，改进了JSP问题基础实例的当前最好解；González等[5]融合路径重连与分散搜索算法，大大缩短了求解JSP问题的时间；Bierwirth等[6]融合路径重连方法与贪婪随机自适应搜索算法求解JSP问题，实现寻求更优解的过程。

Bakhtar等[7]、González等[8]分别将路径重连方法与贪婪随机自适应搜索算法和禁忌搜索算法相融合求解柔性作业车间调度问题，并通过基准实例测试，改进了基准实例的当前最优解。

分布式装配阻塞流水车间调度问题求解算法研究分布式装配阻塞流水车间调度问题是指通过合理的算法，对分布式装配车间中的多个工作站进行调度，以优化整个工作流程，提高生产效率和产品质量。

随着制造业的发展，车间生产过程中可能出现许多问题，如工作站的阻塞、任务延迟等，这些问题对生产效率造成了很大的影响。

因此，如何解决分布式装配阻塞流水车间调度问题成为了制造业中的重要问题。

在分布式装配车间中，通常包含多个工作站，每个工作站负责不同的任务。

这些任务可能需要按照一定的先后顺序进行，而且不同的工作站之间也存在一定的依赖关系。

如果没有合理调度，工作站之间的阻塞和延迟将会导致整个生产流程的延误。

目前，已经有很多不同的算法被提出来用于解决分布式装配阻塞流水车间调度问题。

其中，常用的算法包括遗传算法、模拟退火算法、蚁群算法等。

这些算法通过优化工作站之间的任务分配和调度顺序，来达到最优的生产效果。

在遗传算法中，通过模拟生物进化过程，将问题转化为一个求解最优解的优化问题。

该算法通过对种群的基因序列进行交叉和变异操作，生成新的个体，并根据适应度函数评估每个个体的适应度，从而选择出最优的个体作为当前种群的父代，进而形成新的种群。

通过迭代的过程，逐渐逼近最优解。

模拟退火算法则模拟了材料退火的过程，通过随机搜索的方式，以接受不太好的解，并在温度逐渐降低的过程中，逐渐收敛到最优解。

在求解分布式装配阻塞流水车间调度问题中，通过模拟退火算法可以在局部最优解中跳出来，以期望找到更优的全局最优解。

蚁群算法则是通过模拟蚂蚁找到食物的行为，在分布式装配车间调度问题中，可以将每个工作站看作是食物，通过模拟蚂蚁在搜索过程中释放信息素的过程，来寻找最优解。

除了以上三种算法，还有其他一些算法，如禁忌搜索算法、粒子群算法等，这些算法各有优劣，可以根据具体问题的特点选择最适合的算法。

在实际应用中，如何选择合适的算法以及算法参数的设置，会对分布式装配阻塞流水车间调度问题的求解产生重要影响。

NSGA—Ⅱ算法求解混合流水车间多目标调度问题
刘胜军;李霞
【期刊名称】《工业经济论坛》
【年(卷),期】2015(000)006
【摘要】针对混合流水生产车间调度问题，以生产周期最短、机器加工成本最少和生产次品率最低为目标，建立了多目标优化模型，将NSGA-Ⅱ算法应用于求解混合流水生产车间调度问题。

通过MATLAB对算例仿真，得到一组Pareto解，将数据标准化处理。

然后，利用层次分析法确定各目标的权重，对标准化后的数据加权求和来选择出满意的调度方案。

表明了该算法在解决混合流水车间多目标调度问题的有效性和可行性，同时为企业的生产调度排序提供方法借鉴。

【总页数】9页(P91-99)
【作者】刘胜军;李霞
【作者单位】山东理工大学商学院,山东淄博255012
【正文语种】中文
【中图分类】TP18
【相关文献】
1.基于NSGA2算法的混合流水车间多目标调度问题研究 [J], 刘烽;游海;丁一钧;杨涛;聂电开
2.NSGA-I I算法求解混合流水车间多目标调度问题 [J], 刘胜军;李霞
3.混合NSGA-Ⅱ算法求解多目标柔性作业车间调度问题 [J], 景志强;王兆辉;高琦
4.改进的自适应NSGA-II求解多目标流水车间调度问题 [J], 张伟
5.基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法 [J], 牟健慧;郭前建;高亮;张伟;牟建彩
因版权原因，仅展示原文概要，查看原文内容请购买。

第10卷第8期计算机集成制造系统Vol.10No.82004年8月Computer Integrated Manufacturing Systems Aug.2004文章编号:1006-5911(2004)08-0966-05求解作业车间调度问题的一种改进遗传算法张超勇,饶运清,李培根,刘向军收稿日期:2003-07-15;修订日期:2003-12-08。

基金项目:国家自然科学基金资助项目(50105006;50305008)。

作者简介:张超勇(1972-),男,江苏海门人,华中科技大学博士研究生,主要从事智能调度算法、网络化制造、敏捷供应链等研究。

E -mail :superbrave-2002@ 。

(华中科技大学机械科学与工程学院,湖北　武汉　430074) 摘　要:为克服传统遗传算法解决车间作业调度问题的局限性,综合遗传算法和局部搜索的优点,提出一种改进的遗传算法。

为基于工序的编码提出了一种新的POX 交叉算子。

同时,为克服传统遗传算法在求解车间作业调度问题时的早熟收敛,设计了一种子代交替模式的交叉方式,并运用局部搜索改善交叉和变异后得到的调度解,将提出的改进遗传算法应用于Muth and Thompson 基准问题的实验运行,显示了该算法的有效性。

关键词:车间作业调度;遗传算法;交叉算子;局部搜索中图分类号:TP278 文献标识码:A0　引言为适应用户多样化和个性化的要求,现代生产方式也由大批量向中小批量和多品种生产转变,调度在这种生产方式中的作用显得更加重要。

一般典型的Job -Shop 调度问题可描述为:假设n 个工件在m 台机器上加工,由于工件加工工艺的要求,每个工件使用机器的顺序及每道工序所花的时间给定,且①不同工件的工序之间没有顺序约束;②某一工序一旦开始加工就不能中断,每个机器在同一时刻只能加工一个工序;③机器不发生故障。

调度的目标就是确定每个机器上工序的加工顺序和每个工序的开工时间,使完成所有工序所需的时间(makespan )最小。

基于混合遗传算法的车间生产计划调度崔雪丽【期刊名称】《计算机工程与设计》【年(卷),期】2011(32)7【摘要】针对车间环境的动态随机性、多工序问题,研究了调度问题和算法的特征,提出了一种基于混合遗传算法的车间调度方案.在传统遗传算法的基础上,采用交叉算子、变异算子与启发式算子结合,实现了混合遗传算法,避免了传统遗传算法解的不可行性.再把紧急工序作为一个时域段,结合可变时域滚动机制,实现了可插入紧急工序的调度算法,使一道工序不需重新调度也可排入作业计划,避免了不可插入性,节省了时间,提高了效率.结合实例进行仿真分析,结果表明了调度的可行性、正确性、满意度.%The job shop schedule scheme based on the hybrid genetic algorithm is developed for the random of work shop environment and problem of procedures by studying job shop schedule problem and algorithm character. First, the hybrid genetic algorithm is implemented using heuristic crossover and mutation operators based genetic algorithm, avoiding tradition genetic algorithm inaccuracy. Second, taking emergency procedures as a rolling window combined the rolling window being time-based, the schedule algorithm of inserted emergency procedures is implemented, in which emergency procedures may be arranged work shop plan while not be scheduled over again, reducing time and improving efficiency. It ensures the correctness of schedule and the degree of being pleased with schedule.【总页数】6页(P2467-2471,2475)【作者】崔雪丽【作者单位】西北工业大学软件与微电子学院,陕西西安710072【正文语种】中文【中图分类】TP319【相关文献】1.中小型企业车间生产计划调度问题及优化 [J], 郝冠男2.基于Web的复合材料车间生产计划调度信息系统构建 [J], 李锡华;范玉青;梅中义3.基于混合遗传算法的车间生产调度问题研究 [J], 黄巍;张美凤4.一种基于混合遗传算法的车间生产调度的研究 [J], 刘红军;赵帅5.基于混合遗传算法的车间作业计划调度方法 [J], 崔广才;陶丽华;杨敬松因版权原因，仅展示原文概要，查看原文内容请购买。

生产运作实践大作业目录目录 (1)问题一：基于遗传算法求解作业车间调度问题 (2)1．问题介绍 (2)1.1 作业车间调度问题表述 (2)1.2 作业车间调度问题研究的假设条件 (2)1.3 车间作业调度问题的数学模型 (3)2 .基本遗传算法 (5)2.1 遗传算法的基本思路 (5)2.2 基本遗传算法参数说明 (5)3 .用遗传算法对具体问题的解决 (6)3.1 参数编码 (6)3.2 初始种群的生成 (7)3.3 个体的适应度函数 (8)3.4 遗传算子的设计 (8)3.5 遗传算法终止条件 (10)4．模型的求解 (10)5．结论总结 (12)6 . 附录 (13)问题二：邮政运输网络中的邮路规划和邮车调度 (20)1.问题描述 (20)2.模型建立 (21)2.1模型的基本假设 (21)2.2符号说明 (22)2.3模型分析 (23)2.4模型的建立 (23)3.模型的求解 (25)3.1求解思路 (25)3.2求解算法 (26)问题一：基于遗传算法求解作业车间调度问题1．问题介绍1.1 作业车间调度问题表述作业车间是指利用车间资源完成的某项任务，在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工，为了研究方便，我们将这项任务限定为加工一批工件。

在此基础上，可对作业车间调度问题进行一般性的描述:假定有N个工件，要经过M台机器加工,一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”,用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程,用“加工顺序”表示各台机器上各个工件加工的先后顺序。

在车间作业调度问题中，每个工件都有独特的加工路线，我们要解决的问题就是如何分配N个零件在M个机器上的加工顺序以使得总的加工时间最短。

1.2 作业车间调度问题研究的假设条件在研究一般的作业车间调度问题中往往需要明确两类重要假设条件:1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;2.资源独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。

混合流水车间调度的自适应遗传算法求解作者：轩辕佳慧来源：《智富时代》2019年第11期【摘要】针对以最小化总流程时间为目标的混合流水车间调度问题，考虑到工业生产中并行机的异构或新旧程度等使得同一工序在不同工位的加工时间的不同，假设每个生产阶段的并行机为不相关并行机，结合遗传参数自适应动态调整机制，提出了一种自适应遗传算法。

基于不同规模问题的仿真实验说明了所提出算法的有效性。

【关键词】混合流水车间;不相关并行机;总流程时间;自适应遗传算法1.引言混合流水车间调度问题（hybrid flow shop scheduling problem， HFSSP）在流程工业较为常见，如钢铁业、化工业等。

按并行机的特点，可将HFSSP分为同构并行机、均匀并行机、不相关并行机调度问题[1]。

由于两阶段HFSSP即使只有一个阶段有多台机器也是NP-hard 的，因此求解HFSSP的方法多为近似算法。

在相同并行机环境下，关于HFSSP的近似算法多追求最小化最大完工时间，如韩忠华等[2]提出了改进帝国竞争算法;任彩乐等[3]设计了基于两阶段解码方法的候鸟优化算法;吴秀丽和崔琪[4]考虑可再生能源提出集成低碳调度策略的快速非支配遗传算法以同时最小化最大完工时间和碳排放量。

在不相关并行机环境下，吴楚格等[5]提出了解决并行机调度的基于信息熵的自适应分布估计算法，目标是最小化最大完工时间。

针对HFSSP，为最小化最大完工时间，孟磊磊等[1]考虑了阻塞限制，提出了一种改进的回溯搜索算法;宋存利[6]提出了改进贪婪遗传算法;王芳等[7]结合自适应调整模型设计了高效分布估算算法求解大规模调度问题;杜利珍等[8]提出了果蠅优化算法。

从上述研究现状可发现，对于含不相关并行机的HFSSP的研究多为最大完工时间问题，缺乏对其它目标问题的探讨。

因此，为减少在制品库存，本文以总流程时间为目标函数，设计结合遗传参数自适应动态调整机制的遗传算法，以有效求解该问题。

企业战略混合遗传模拟退火算法解决多机调度问题 Ting Bao was revised on January 6, 20021★★★文档资源★★★摘要：将模拟退火引入遗传算法，构造混合遗传模拟退火算法。

通过对具体多机调度问题的求解，表明混合遗传模拟退火算法的效率要优于单一的遗传算法和模拟退火算法。

关键词：多机调度；遗传算法；模拟退火算法；混合遗传模拟退火算法作业调度问题是生产管理与控制的一个基本问题。

按照加工设备数量和加工作业的流动方式，一般可分为单机调度、并行机调度、Flowshop调度、可重入式调度和Jobshop调度等多种类型。

作业调度中的许多问题，不仅具有随机性、约束复杂、规模大及多目标冲突等特点，而且许多都属于NP完全问题，即使在单机情形也是如此。

因此，如何寻求有效可行的调度求解方案，一直是生产管理与控制研究的热点和难点。

一、多机调度问题的数学模型二、算法分析自Davis首次将遗传算法（Genetic Algorithms，GA）引入到调度问题的研究中以来，进化算法（包括遗传算法）在制造生产零件和生产调度研究领域获得了广泛的应用，并取得了较好的优化效果。

遗传算法用于求解某些并行多机调度问题也有不少的研究成果。

遗传算法的优点是：不受搜索空间的****性假设的约束，不必要求诸如连续性、导数存在和单峰的假设，并且具有内在的并行性，收敛速度快，能够解决非常困难的寻优问题。

当然，传统的遗传算法也有许多缺点，其中最为严重的是“过早收敛”问题。

所谓“过早收敛”是指在搜索的初期，由于优良个体急剧增加使种群失去多样性，从而造成程序陷入局部，达不到全局最优解的现象。

遗传算法的另一个缺陷是“GA欺骗”问题，即在GA的搜索过程中，有可能搜索到最优解然后又发散出去的现象。

另外，遗传算法还有参数选择未能定量和不能精确定位最优解等缺陷。

模拟退火算法（Simulated Annealing，SA）又称为模拟冷却法、统计冷却法、Monte－Carlo退火法、随机松弛法和概率爬山法等。