考虑并行机的流水车间调度问题研究-文献综述

1、考虑并行机的流水车间调度问题研究文献综述1 前言20 世纪末期，我国制造业取得了突飞猛进的发展，生产力极大提高，企业的生产规模越来越大。同时，随着人民生活水平的提高，对于产品的需要更加的多元化，多样化和个性化，使得多品种、小批量生产方式成为占市场主要份额的重要生产方式。这种生产方式使得企业生产过程更加的复杂，生产要素急剧增加，企业生产管理变得更加的困难。随着经济全球化，市场竞争日趋激烈，制造企业要想取得长足的发展，获得最大的效益，必须提高制造企业响应速度和生产效率、提高产品质量并且减少生产成本。有关资料表明，制造过程 95的时间消耗在非切削过程中1。因此科学的调度技术和优化方法能够合理地分配并

2、使用企业的生产资源，对于降低企业的固定成本，提高的流转效率，提高设备的利用效率，缩短生产周期，减少生产成本具有非常重要的理论和现实意义。生产车间调度问题是制造系统的，车间调度是对生产过程中涉及到的生产批量、工件在加工机器上的次序等作业进行合理设计。生产调度问题一般可以描述为针对某项可以分解的工作，在一定的约束条件下，如何安排其组成部分操作所占用的资源、加工时间及先后顺序，以获得产品制造时间或者成本等性能指标最优2。车间调度的性能指标主要包括：设备利用率高、生产周期短、成本最低、库存费用最小等。在流水车间调度问题（Flow-shop Scheduling Problem，FSP）中，车间生产系统

3、中的待加工工件需要经过多道工序加工，每道工序都有一台机器进行加工，各个工序的机器功能不同，全部的零件都必须经过相同的加工流程3。在柔性流水车间调度问题（Flexible Flow-shop Scheduling Problem，FFSP）中，同一道工序工件可以选择多台机器进行加工，且每台机器所需的加工时间是不同的。柔性流水车间调度问题更接近实际的车间调度情况并普遍地应用在现代制造业中3。2 流水车间调度国内外研究现状及趋势2.1 流水车间调度在国内外的研究现状1954 年，Johnson 对两个依次加工型机台的流水车间调度问题进行研究，揭开了生1产调度问题研究的序幕4。Rock 已经证明，3

4、台机器以上的流水车间调度问题属于NP 完全问题。所以，并行流水车间调度问题必是 NP 完全问题，对于这类寻优问题是不存在精确算法的5。早期的流水车间调度主要是利用线性规划、整数规划、目标规划、动态规划及分支定界等方法来解决单机生产或小规模生产，研究范围较窄，约束条件较少，比较简单而常规的调度问题。同时，也有少数的学者将启发式算法应用于流水车间调度。七十年代开始，由于科学技术的进步，大规模生产模式开始广泛的出现，这些无疑增加了车间调度的难度，大量的学者开始了算法复杂性的研究，流水车间调度 NP-Hard 问题的理论研究取得了很多的成果，但是由于难以找到多项式算法，因此很多开始关注启发式算法。一些

5、学者总结和归纳出了 112 条调度规则，并对其进行了分类。九十年代及以后，随着最优化设计方法的成熟及多品种小批量生产模式的出现，智能优化方法与车间调度工程的结 为该领域研究的热点6。近年来，流水车间调度的新理论也层出不穷，如国外学者 Rajkumar 等提出用贪心随机自适应搜索过程来解决柔性作业车间有限资源约束问题7。Zribi 等采用分步法求解柔性作业车间调度问题（Flexible Job-shop Scheduling Problem，FJSP），先基于启发式与局部搜索方法解决机台选择问题，再对加工工序进行排序处理8。 国内学者等提出了一种合理、全面的编码方法，并运用最优子种群遗传算法来求

6、解柔性流水车间调度问题，提高了精度、加快了较优的产生并避免陷入局部最优解9。强等提出了一种基于多种群协同进化的改进量子粒子群算法来求解并行流水车间调度问题。发现在求解并行流水车间调度问题时，基于多种群协同的量子粒子群算法，在收敛速度、寻优性能等方面，都要优于传统遗传算法10。等针对遗传算法(Genetic Algorithm，GA)在求解流水车间调度问题中易出现早熟收敛的局限性，提出了自适应变异的遗传算法11。梁等将邻域搜索与遗传算法相结合用来求解流水车间调度问题，设计了一种基于扩展采样空间的混合式遗传算法12。如今，各种方法在生产调度问题的研究中得到了充分的发挥，同时新的研究层出不穷。虚拟制

7、造、柔性制造、精益制造、敏捷制造等多种现代化先进制造生产模式从传统的生产模式中得到创新与深化13。纵观目前国内外的研究成果，从总体趋势上来讲，经典调度理论依然是调度理论不可动摇的基石，但智能调度理论己崭露头角，逐渐趋于成熟，且二者的融合也将会成为一种趋势14。2.2 流水车间调度研究热点2当前国内外在该领域的研究热点主要包括以下几个方面：（1）柔性调度。目前多数柔性生产车间调度问题的解决方法首先对机台选择和工序排序分步处理，再结合智能算法进行求解。（2）动态调度。流水车间调度可分为静态调度和动态调度两类问题，目前大量研究工作是对生产加工环境、生产任务己知求解，但在生产制造过程中，往往会出现订单

8、更新、交货期变化、设备故障、物料短缺等多种不可预知事件15。这些不确定事件的发生导致静态调度方案不适用，决策者很难在较短的时间内做出适用于动态事件的最新调度方案。针对生产过程中出现的机台故障动态事件，Hasan 等提出一种局部搜索方法将其与遗传算法结合，能有效的降低工件的移位间隙，并分析得出机台故障在生产过程中越早发生，调度方案修复的可能性相对越大16。（3）模糊调度。模糊调度问题是指工件的交货期、加工时间、加工工艺等生产没有明确的数据信息，问题具有模糊性。（4）多目标调度。多目标优化问题的难点在于对不可通约和相互的目标进行决策优化，而生产调度问题本身就是 NP-Hard 题，将二者结合的多目

9、标生产车间调度问题是一种全新的具有性的研究方向，近十年来在国内外得到大量的研究。国内采集保存最优解，并将最优解参与跟随蜂的交叉操作，设计了多种基于 pareto 排序用的 ABC 算法求解FFSP 和FJSP 问题17。（5）调度系统。随着工业 4.0 概念的提出，越来越多的制造企业将智能制造的概念引入生产车间。目前制造业所是如何利用，将上层的规划管理系统与底层的工业系统进行关联，从而优化工艺流程、改善产品质量、实现精益生产，给管理者提供一个能快速、精准应对市场变化的决策支持。等针对多型号混线生产车间产品齐套性难以保证的调度问题，制定了一套适用于具有动态随机性及双柔性的车间调度系统18。期模糊

10、2.3 流水车间调度存在由于流水车间调度问题属于 NP-Hard 问题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。各种近似启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得的调度解的次优性不能进行评估。在这方面有必要探索更好的近似最优调度算法，可以考虑增加合理的计算时间为代价，提高解的次优性。各种基于统计优化的方法、诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但同别的优化算法类似，其也存在着一定程度的枚举、一般来说收敛到最优解较慢，并且对于判断解的最优性也很。3在调度问题的理论研究中，大多数还是集中在针

11、对经典的调度问题设计优化算法，而经典调度问题与实际相差较大，如没有考虑并行机的情况，尤其在目前柔性制造环境下，柔性流水车间调度问题将是一个研究的重点和进一步研究的方向，而目前对于这方面研究的文献相对来说较少。目前FFSP 问题还处于研究初期，针对FFSP 问题，大量学者只针对工件无等待、批量加工、单目标调度等问题，进行智能算法的适用性改进研究。在实际车间调度中，车间计划与车间调度往往是分层进行的，但这可能造成计划在实际调度中的不可行问题，如何将计划与调度结合考虑，需要进一步研究19。3 流水车间调度问题优化算法3.1 流水车间调度优化算法概述生产调度问题的研究最初集中在整数规划、仿真和简单的规

12、划等方法上，这些方法20。近年来，在生产调度领域出现了许不是调度结果不理想，就是难以解决复杂多新的优化方法，比如神经网络法、模拟退火法、遗传算法等，使得生产调度问题的研究方法了多元化21。调度算法可大致分为三类，具体分类如图 3-1 所示。图 3-1 调度算法（1）精确算法。数学规划法主要是通过对车间调度问题建立一个整数规划模型，采用枚举方法寻求调度问题的最优解。数学规划方法往往采用基于枚举或动态规划算法进行求解。的分枝定界法4（2）近似算法。近似算法基本上是在一些信息和规则的启发下进行推理和计算，从而获得调度问题的近似最优解。启发式搜索方法的优点是利用了面向特定问题的知识和经验，因而可以产生

13、好的解决方案，求解时间也可以接受。而对于如何提高搜索效率并减少内存使用以解决规模较大，还需要进一步探索。（3）智能搜索算法。遗传算法是一种并行优化搜索方法，它是模仿生物群体进化过程的一种优化算法，给定一组初始解作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。搜索算法的基本要素是初始解、移动、邻域和表。搜索算法没有自然性的终止条件，对求解，目标函数和搜索空间没有任何特殊的要求，计算速度较快。“人工神经网络”是一种模拟人脑神经系统的结构和功能，运用大量的处理经广泛互连而组成的网络系统22。3.2遗传算法理论遗传算法是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法。它

14、是模仿自然界生物进化过程中“物竞天择，适者生存”的原理而进行的一种多参数、多群体同时优化方法。经过多年的发展，遗传算法已经在数据挖掘、生产调度、函数优化、机器学习、图象处理等领域得到成功的应用，并显示出其良好的性能19。遗传算法是给定一组初始解作为一个群体，通过选择、交叉和变异等遗传操作来搜索最优解。遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性进行选择，使适应性好的比适应性差的有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛。遗传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题。遗传算法已经成为一种比较通用的优化算法，主要原因是编码

15、技术和遗传操作比较简单，优化不受限制性条件的约束。但遗传算法也有明显的之处，对于大规模的组合优化问题，由于搜索空间大，搜索时间较长，往往会出现早熟收敛的情况对初始种群很敏感，初始种群选择不好会影响解的质量和算法效率。为了进一步改进遗传算法，人们主要从两方面入手：一是对遗传算法本身进行改进，二是与其它算法结合，取长补短。遗传算法具有如下几个特点：（1）遗传算法从问题解集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的最大区别。传统优化算法是从单个初始值开始迭代求最优解的，容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。（2）遗传算法求解时使用特定问题的信息极少，容易

16、形成通用算法程序。在标准的遗传算法中，基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估5，并在此基础上进行遗传操作。需要着重是遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，对于输入，可计算出加以比较的正确输出。遗传算法的这一特点使它的应用范围大大扩展。（3）遗传算法有极强的容错能力。遗传算法的初始串集本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程，并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。（4）遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精

17、确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解优解的产生，变异体现了全局最优解的覆盖23。近，交叉体现了最对于遗传算法的改进，等提出了一种基于仿真技术和改进非支配排序遗传算法的分步优化方法，降低并行机作业车间等量分批多目标优化调度问题的复杂度，提高了优化效率24。等对最小化完工时间的等同和非等同并行多机调度一类问题，提出了一种递阶遗传算法。该算法根据问题的特点，采用一种递阶编码方案，此编码与调度方案一一对应。递阶遗传算法能适用于大规模等同和非等同并行多机调度问题，操作简单并且收敛速度快25。文献26把模拟退火算法（Simulated Annealing，SA）和遗传算法

18、相互结合，并利用两者的优点构建了算法框架，同时采用高效的编码方式与优化算法，成功的解决了车间调度问题，并且使 GA 和 SA 对参数的依赖性减低了26。文献27改变了遗传算法的框架，生成初始种群的方法，变异方式以及交叉方式，并将其用于求解柔性调度问题，获得了比较满意的结果27。4 结论流水车间调度问题是生产调度中的一个重要的研究部分，制造业实际生产中，为提高机器的使用效率及生产效率，增加制造系统的柔性，同一工序往往设置多台可选的机器，为提高流水车间问题的实际研究意义，提出一种考虑并行机的流水车间调度问题，该问题也称为柔性流水车间调度问题。其在离散制造工业和流程工业中具有十分广泛的应用。该问题属

19、于 NP-Hard，需要采用智能算法进行问题求解。本文将采用遗传算法，并利用编程解决考虑并行机的流水车间调度。参考文献1, 等. 车间生产调度问题研究J. 机械工程学报, 2000, 36(5): 97-102.2. 智能生产调度方法的研究与应用D. 合肥: 合肥工业大学, 2005.63. 一种基于改进遗传算法的柔性流水车间调度问题研究D. 广州:工业大学, 2014.4 S. M. John. optimal two-and three-tage production schedulings with setup time includedJ. NavalResearch Logistic

20、s, 1954, 1(1): 61-68.5. 流水车间调度问题模型与算法研究J. 科学技术与工程, 2007, 7(22): 335-345.6,. 生产调度智能算法及其应用M.: 科学, 2007.7M. Rajkumar, P. Asokan, N. Anilkumar, etal. A grasp algorithm for flexuible job-shop schedulingproblem with limited resource constras J.2409-2423.ernational Journal of Production research, 2011, 49(

21、8):8 N. Zribi, I.Kacem, A. Eloptimization J. IEEE Tranel, etal. Assignment and scheduling in flexible job-shops by hierarchicalions on system, Man, and cybernetics Part c, 2007, 37(4): 652-661.9,.最优子种群遗传算法求解柔性流水车间调度问题J. 计算机应用研究.2012, 29(2): 442-526.10强,. 用 MC-QPSO 算法求解并行流水车间调度问题J. 计算机工程与应用. 2010,46(

22、16): 229-231.11 于12-15., 陈亚军. 自适应变异的遗传算法求解 FlowShop 问题J. 电脑与, 2006. 8:12 梁,. 求解流水车间调度问题的一种混合式遗传算法. 华南理工大学学报J. 自然科学版, 2002. 11: 85-88.13,. 世界先进制造系统的演进路径及体系结构J. 兵工自动化, 2013, 32(11): 1-7.14.基于遗传算法的柔性流水车间调度方法研究D.: 电子科技大学, 2017.15, 唐立新,. 动态调度的研究方法综述J. 控制与决策, 2001, 16(2): 141-145.16S. K. Hasan, R. sarker, D. Essam. Genetic algorithm for job-shop scheduling with machineunavailability and breakdowns J.ernation Journal of producton Research, 2011, 49(16): 4999.17.基于人工蜂群算法的柔性调度问题研究D.:, 2012.18. 制造执行系统(MES)若干研究D. 大