柔性作业车间动态调度问题研究

机械设计与制造68Machinery Design&Manufacture第5期2021年5月大规模柔性作业车间调度问题分解建模和求解方法刘海涛1,邓停铭2,唐健均1,尹慢2（1.航空工业成都飞机工业（集团）有限责任公司，四川成都610000；2.西南交通大学机械工程学院，四川成都610000）摘要:研究在满足既定工序顺序约束的情况下，按序组合工序来分解柔性作业车间大规模调度问题，建立分解调度问题的数学模型，并探索高效求解的方法。

首先基于工序组合与遗传算法，将大规模调度问题进行分解降低问题空间复杂度，形成调度子问题，并建立分解后的调度数学模型；其次将利用组合规则生成高质量的初始解，采用遗传算法与蛙跳算法相结合的混合算法，采用双线程进行并行计算求解，提高全局搜索能力和效率，重组后形成原问题的可行解;最后利用实例证实了模型和算法的可行性。

关键词：柔性作业车间调度问题;数学模型;混合算法;并行运算中图分类号:TH16；TH165文献标识码:A文章编号：1001-3997(2021)05-0068-04Decomposition Modeling and Solving Method for LargeScale Flexible Job Shop Scheduling ProblemLIU Hai-tao1,DENG Ting-ming2,TANGJian-jun1,YIN Man2(1.Avic Chengdu Aircraft Inductrial(Group)Co.,Ltd.,Sichuang Chengdu610000;2.School of Mechanical Engineering,Southwest Jiaotong University,Sichaun Chendu61000,China)Abstract：It studies the decomposition of large-scale flexible job shop scheduling problem by sequential combination of processesunder the condition of satisfyingthe constraints of the specified process sequence,e stablishes a mathematical model of decomposition scheduling problem,and explores an efficient solution method.Firstly,based on the combination of processand the genetic algorithm,the large-scale scheduling problem is decomposed to reduce the space complexity of the problem and to formschedulingsub-problem,fter establishingthe decomposed scheduling mathematical model.Secondly,the high-quality initial solution is generated by using the combination rules.Moreover,t o improve the global search ability and efficiency,a hybrid algorithm combining genetic algorithm with leapfrog algorithm and parallel computing method with two threads are adopted.After recombination,the feasible solution ofthe original problem is formed.Finally,t he feasibility ofthe model and algorithm is verified by an example.Key Words：Flexible Job Shop Scheduling Problem；Mathematical Model；Hybrid Algorithm；Parallel Computation1引言作业车间调度属于NP难题，半个多世纪以来一直是学术界的焦点。

求解柔性作业车间调度问题的遗传-蚁群算法陈成;邢立宁【期刊名称】《计算机集成制造系统》【年(卷),期】2011(017)003【摘要】为更有效地求解柔性作业车间调度问题,提出了一种遗传一蚁群算法,该算法采用遗传算法解决机器分配问题,采用蚁群算法解决工序排序问题.存算法的求解过程中,不断从前期优化中挖掘、学习知识,并采用已获得的知识指导后续优化过程.通过标准实例测试,验证了所提算法的有效性.%To solve flexible job shop scheduling problem effectively, a hybrid approach which combined Genetic Algorithm(GA)with Ant Colony Optimization(ACO)was proposed. GA was applied to tackle machine assignment problem, while AC() was employed to deal with operation sequencing problem. In the solution process, knowledge was continuously learned from previous optimization process and then adopted to guide subsequent optimization. Effectiveness of the proposed algorithm was validated through an experiment.【总页数】7页(P615-621)【作者】陈成;邢立宁【作者单位】国防科学技术大学,信息系统与管理学院,湖南,长沙,410073;国防科学技术大学,信息系统与管理学院,湖南,长沙,410073【正文语种】中文【中图分类】TP312;TPL8【相关文献】1.求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法 [J], 赵博选;高建民;陈琨2.求解柔性作业车间调度问题的两阶段参数自适应蚁群算法 [J], 凌海峰;王西山3.一种异步蚁群算法求解柔性作业车间调度问题 [J], 田松龄;陈东祥;王太勇;刘晓敏4.改进遗传蜂群算法求解分布式柔性作业车间调度问题 [J], 李佳路;王雷;王静云5.应用改进蚁群算法求解柔性作业车间调度问题 [J], 刘志勇;吕文阁;谢庆华;何明玉;杨杰;刘雄辉因版权原因，仅展示原文概要，查看原文内容请购买。

柔性作业车间在线调度问题的仿真建模与分析龙田;石宇强;王俊佳【摘要】利用离散事件系统建模与仿真技术和规则调度方法,对柔性作业车间在线调度问题进行研究.将优先级调度规则和路径选择规则结合,形成针对柔性作业车间的调度规则组合.在建立仿真模型时,定义了车间结构,并对车间结构参数设定不同的水平值.针对平均流经时间最小、最大拖期时间最小、机器最大负荷最小、拖期工件比最小这4个不同的调度目标,从备选规则集中选出了每个目标下最优的调度规则组合及相应的车间结构参数.仿真结果表明,工件交货期、车间利用率、机器平均有效率、机器平均故障水平及车间柔性程度对调度规则组合的选取有很大影响.【期刊名称】《机械设计与制造》【年(卷),期】2015(000)012【总页数】4页(P27-30)【关键词】离散事件系统建模与仿真;规则调度方法;柔性作业车间;在线调度【作者】龙田;石宇强;王俊佳【作者单位】西南科技大学制造科学与工程学院,四川绵阳 621010;西南科技大学制造科学与工程学院,四川绵阳 621010;西南科技大学制造科学与工程学院,四川绵阳 621010【正文语种】中文【中图分类】TH16;TH165;TP391摘.：利用离散事件系统建模与仿真技术和规则调度方法，对柔性作业车间在线调度问题进行研究。

将优先级调度规则和路径选择规则结合，形成针对柔性作业车间的调度规则组合。

在建立仿真模型时，定义了车间结构，并对车间结构参数设定不同的水平值。

针对平均流经时间最小、最大拖期时间最小、机器最大负荷最小、拖期工件比最小这4个不同的调度目标，从备选规则集中选出了每个目标下最优的调度规则组合及相应的车间结构参数。

仿真结果表明，工件交货期、车间利用率、机器平均有效率、机器平均故障水平及车间柔性程度对调度规则组合的选取有很大影响。

柔性作业车间调度问题（FJSP）是比作业车间调度问题（JSP）更为复杂的NP难题，它包含两个子问题：确定各工件的加工机器和确定各机器上的加工顺序。

车间调度问题研究现状与发展趋势作者：罗哲朱光宇来源：《科技创新与应用》2020年第23期摘; 要：文章从车间调度问题的实际应用特性出发，综述了当前车间调度问题在国内外的研究現状，在总结分析当前研究车间调度问题的相关方法与技术的基础上，指出了当前在车间调度问题研究中存在的问题与不足，并提出了几个车间调度问题研究的发展趋势，以期为后续车间调度问题的不断深入以及更好地为生产实际服务提供可借鉴的方向。

关键词：车间调度;生产计划;调度方法中图分类号：TP278; ; ; ; 文献标志码：A; ; ; ; ;文章编号：2095-2945（2020）23-0123-02Abstract： Starting from the practical application characteristics of the workshop scheduling problem， this paper summarizes the current research status of the workshop scheduling problem at home and abroad， and on the basis of summarizing and analyzing the relevant methods and technologies of the current research on the workshop scheduling problem， this paper points out the problems and deficiencies existing in the research of workshop scheduling problem， and puts forward the development trend of several workshop scheduling problems， in order to provide a reference direction for the continuous deepening of the follow-up workshop scheduling problems and for the production of actual services.Keywords： workshop scheduling; production planning; scheduling method1 概述生产调度指的是企业在生产过程中，以生产为中心，通过对有效的资源进行合理指挥、控制和调节，进而达到提高经济效益目的的过程。

机器人在制造业中的柔性生产线配置与调度策略机器人技术的快速发展和广泛应用，正在为制造业带来深刻的变革。

在制造业中，柔性生产线的配置与调度策略对于提高生产效率和降低成本至关重要。

本文将探讨机器人在制造业中的柔性生产线配置与调度策略，并提出相应的解决方案。

一、柔性生产线配置柔性生产线配置是指根据生产需求和工艺特点，合理安排生产线上的工作单元和设备资源，以实现生产流程的柔性调整和高效运行。

在机器人的应用中，柔性生产线配置需要考虑以下几个方面：1. 工作单元布局：在柔性生产线上，各个工作单元之间的距离和布局应该合理安排，以便机器人能够高效地处理物料的传输和加工过程。

例如，可以采用U型或S型的生产线布局，以减少物料的运输时间和成本。

2. 机器人数量与布局：根据生产需求和工艺要求，确定需要的机器人数量和其在生产线上的布局位置。

机器人应该能够覆盖所有工作单元，并且能够进行灵活的动态调度。

此外，不同类型的机器人应该能够协同工作，以实现生产线的高效运行。

3. 自动化设备选型：在柔性生产线配置中，选择适合的自动化设备对于提高生产效率和产品质量至关重要。

例如，可以选用具有自动化装卸功能的机械手臂，以减少人工干预和生产过程中的错误。

4. 传感器与控制系统：在柔性生产线中，传感器和控制系统能够为机器人提供实时的数据和反馈信息，以便对生产过程进行监控和调整。

因此，在配置柔性生产线时，应充分考虑传感器和控制系统的布局和选型。

二、柔性生产线调度策略柔性生产线调度策略是指为了实现生产线资源的最优利用和生产效率的最大化，对生产任务进行合理调度和分配。

在机器人的应用中，柔性生产线调度策略需要考虑以下几个方面：1. 任务调度算法：选择合适的任务调度算法对生产任务进行合理安排和分配。

例如，可以采用启发式算法、遗传算法或智能优化算法等，以实现任务的优化分配和调度。

2. 机器人调度策略：机器人在柔性生产线上的调度策略应该灵活多样，能够根据生产任务和工艺特点进行动态调整。

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。

本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。

对智能算法在生产调度中的应用做出总结。

关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度0.前言柔性作业车间调度问题(Flexible job-shopsche- duling problem, FJSP)是传统作业车间调度问题的扩展，是实际生产中迫切需要解决的一类问题。

在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。

而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。

柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。

作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。

1.蚁群算法在作业车间的应用[2]以3个工件2台机器的问题作为例子，如图1。

图1 三个工件两台机器的JSP问题为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。

图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。

其它则为无向弧。

每个弧与表示节点间信息素的量和启发式距离的一对值{αij, d ij}有关。

d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1−ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。

初始时刻τij(0)= c（c为常数）。

柔性制造系统中的调度算法及性能分析随着信息技术和自动化技术的发展，柔性制造系统越来越普及。

柔性制造系统是一种能够生产多种不同产品的生产线。

与传统的生产线不同，柔性制造系统需要根据需求动态地调度生产任务，以便在多种产品之间实现快速切换。

因此，调度算法是柔性制造系统中的一个关键问题。

本文将介绍柔性制造系统中的调度算法及其性能分析。

一、调度算法的分类调度算法根据任务分配的方式和优化目标的不同，可以分为以下几种类型。

1. 静态调度算法静态调度算法是指在任务产生前就将任务分配给机器，并且不进行调整的算法。

静态调度算法通常适用于任务量较小、任务类型较少的生产线。

静态调度算法的主要优点是简单易实现，不需要大量的计算资源。

2. 动态调度算法动态调度算法根据实时产生的任务信息，动态地进行任务分配和调整。

动态调度算法可以分手动和自动两种。

手动调度算法是指根据用户指定的规则进行任务分配和调整的算法；自动调度算法是指系统自动进行任务分配和调整的算法。

动态调度算法适合于任务量较大、任务类型较多的生产线。

3. 启发式调度算法启发式调度算法是指根据经验和规则进行任务分配和调整的算法。

启发式调度算法通常结合优先级调度算法使用，用于解决多个任务同步进行的问题。

二、优先级调度算法优先级调度算法是一种常用的调度算法，它根据任务的紧急程度和优先级对任务进行排序和分配。

优先级调度算法包括静态优先级调度和动态优先级调度两种类型。

1. 静态优先级调度静态优先级调度是指在任务产生前就根据任务的属性和优先级确定任务的调度顺序。

静态优先级调度算法的主要缺点是如果任务属性或优先级发生变化，需要重新进行优先级调度。

2. 动态优先级调度动态优先级调度是指随着任务产生和机器使用情况的变化，动态地调整任务的调度顺序。

动态优先级调度算法通常结合手动调度算法或自动调度算法使用，以便更好地进行任务调度。

三、性能分析调度算法的性能通常可用以下几个指标来衡量。

1. 完成度完成度是指已完成任务的数量占总任务数量的比例。

第5期2013年5月组合机床与自动化加工技术Modular Machine Tool ＆Automatic Manufacturing TechniqueNo．5May 2013文章编号：1001－2265（2013）05－0130－04收稿日期：2012－10－25*基金项目：甘肃省自然科学基金（1112RJZA045）作者简介：武福（1973—），男，甘肃人，兰州交通大学机电工程学院副教授，主要从事制造系统建模与优化调度的研究，（E －mail ）wufu@mail．lzjtu．cn 。

一种求解柔性作业车间调度问题的混合智能算法*武福1，2张治娟2（1．甘肃省轨道交通装备系统动力学与可靠性重点实验室，兰州730070；2．兰州交通大学机电工程学院，兰州730070）摘要：提出了一种将蚁群算法、遗传算法和粒子群算法优化融合的混合智能算法，并将其应用于解决多目标柔性作业车间调度问题。

采用蚁群算法寻径生成初始群体，利用遗传算法进行调度路径的优化，利用粒子群算法对蚁群算法中的信息素进行优化，优势互补。

最后通过仿真实例验证了该算法的可行性和有效性。

关键词：蚁群算法；多目标优化；柔性作业车间调度中图分类号：TH165；TG65文献标识码：A Research on Multi-objective Flexible Job-shop Scheduling Problem Basedon Hybrid Intelligence AlgorithmWU Fu 1，2，ZHANG Zhi-juan 2（1．Key-lab of System Dynamics and Reliability of Rail Transportation Equipment of Gansu Province ，Lanzhou 730070，China ；2．Institute of Mech-Electronic Technology ，Lanzhou Jiaotong University ，Lanzhou 730070，China ）Abstract ：This paper proposed a hybrid intelligence algorithm to solve multi-objective flexible job-shopscheduling that was based on the combination of ant colony algorithm ，genetic algorithm and particle swarm optimization．First ，it adopted ant colony algorithm to get a new population by routing．Second it made use of genetic algorithm to optimize the path ，the PSO algorithm to optimize the pheromone in ant colony algorithm．Finally ，it developed enough advantage of the three algorithms．The simulation results show that the algorithm is feasible and effective．Key words ：ant colony algorithm ；multi-objective optimization ；flexible job-shop scheduling0引言蚁群算法（Ant Colony Algorithm ）是意大利学者M．Dorigo 等人通过模拟自然界蚂蚁寻径的行为提的一种应用于组合优化问题的启发式搜索算法，它充分利用蚁群行为中所体现的正反馈机制进行求解，同时，利用分布并行计算方式在全局的多点进行解的搜索［1］。