柔性作业车间调度问题简明分析
何斌;张接信;张富强
【摘 要】分析了柔性作业车间调度问题(Flexible Job Shop Scheduling
Problem,FJSP)的基本内容和组成要素,按照从简单到复杂、从特殊到一般的思路对FJSP问题的调度模型进行了分类,指出了各类问题自身的特点以及各种调度模型间的关系,对各种模型的实用性作了评价与对比.最后,结合车间调度的实际情况展望了柔性作业车间调度问题今后的研究方向. 【期刊名称】《装备制造技术》 【年(卷),期】2018(000)005 【总页数】5页(P68-71,85)
【关键词】柔性作业车间调度问题;智能算法;静态调度;动态调度 【作 者】何斌;张接信;张富强
【作者单位】长安大学工程机械学院,陕西西安 7100;长安大学工程机械学院,陕西西安 7100;长安大学工程机械学院,陕西西安 7100 【正文语种】中 文 【中图分类】TP301 0 引言
调度是通过一定的手段对有限的人力、物力、财力和时间资源进行科学合理的配置，在保证能够获得某些最优性能的前提下使生产或作业过程高效有序地运行。调度的
概念涉及生产计划排程、企业管理、交通运输工具的运行时刻与运行路径规划，网络通讯等。在调度问题中，柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，FJSP）最具代表性，FJSP问题所研究的是各个加工任务“何时何地”进行加工才能使某些性能指标达到最优，在小批量多品种的生产模式和日趋激烈的市场竞争下，如何合理调度车间生产任务，使加工时间和加工成本最小化、生产效益和客户满意度最大化，是制造企业生产过程中不可忽略的重要因素。目前，关于FJSP问题，前人已做了大量研究，但没有进行详细的归类与分析，从而难以对FJSP问题有一个深刻的认识和理解，也就难以针对具体的问题快速地建立模型并找到合适的解决办法。因此，本文在总结已有研究成果的基础上，对柔性作业车间调度问题的内容作了简要分析，并从优化目标的数量和是否考虑不确定性因素两个方面对FJSP问题进行了综合归类和对比分析，使实际的调度问题能够对应到具体的调度类型，从而为调度模型的建立和问题的求解指明方向。 1 问题描述
车间调度是指按照被加工件的工艺规程，在现有生产能力和生产资源情况下，基于一个或多个优化目标以及相关约束条件，规划出多个工件各工序间最优的加工顺序组合方案。作业车间调度问题（Job Shop Scheduling Problem，JSP）是车间调度问题的经典类型，也是典型的组合优化问题，其一般性描述为：n个工件在m台机器上加工，各工序的加工机床和加工时间已定，所要解决的问题是确定每台机床上待加工件的最优加工顺序。而柔性作业车间调度问题是JSP问题的扩展，此类问题中，工件每道工序的加工有一至多台机床可供选择，所要解决的问题一是为每道工序选择最合适的机床，二是为每台机床上的工件安排最优的加工顺序。FJSP问题约束性较JSP问题弱，故求解难度更大，是典型的NP难题。 2 FJSP问题基本内容
FJSP问题主要包含问题类型、优化目标、约束条件、数学模型和求解方法五大要
素，如图1所示： 图1 FJSP问题组成要素
FJSP问题的优化目标和约束条件如表1所示，其中的优化目标是车间调度问题中最敏感、最关心的性能指标，而约束条件则是任一类型的车间调度问题都必须满足的共同的约束条件，具体工况下的约束条件会有所增强。
表1 一般性优化目标与约束条件时间目标 成本目标 其他目标 约束条件最小化最大完工时间；最小化提前完工时间；最小化拖期完工时间；最小化工件完工到参加装配的时间间隔；最小化平均完工时间；最小化加工总成本；最小化提前惩罚成本；最小化拖期惩罚成本；最小化最大机器负荷；最小化机器总负荷；最小化机器最大负荷之差；最大化机器利用率；最小化工件移动距离（工件相邻两个工序在不同机床上加工）；最大化最小客户满意度；最大化所有工件平均交货期满意度；最小化最大完工时间的期望值（加工时间是随机变量）；每个工件的是按其工序顺次加工的，中途不可中断，也不可跳转；同一时刻一台机器只能加工一个工件的一道工序；同一时刻一个工件的一道工序只能在其候选机器集合中的一台上加工； 对于一个具体的问题，从问题提出到解决，求解思路是贯穿始终的，FJSP问题的求解思路可分为整体法和分层法，前者同时考虑机器的选择和工件的排序，通过统一编码一次性求得结果，后者将问题一分为二。首先，为每道工序选择机床，解决了FJSP问题的第一个难题；其次，为每个机床上的工件排序，解决了FJSP问题的第二个难题，分层法使FJSP问题退化为JSP问题，降低了求解难度，是目前大多数学者所采用的方法，在求解思路的指导下，采用某种数学方法即可对模型进行解算。近年来，随着智能算法的发展和不断完善，其在求解类似于车间调度一类的组合优化问题方面的优势已日渐明显，虽然属于近似算法，但可以有效解决传统算法难以解决的问题，并且求解结果在一定范围内已为大多数人所接受，因此，使用智能算法解决FJSP问题已经成为了主流。
常用的智能算法有神经网络法、遗传算法、粒子群算法、蚁群算法、模拟退火算法等等。彭建刚[1]等分析了各种智能算法求解车间调度问题的优缺点，认为人工神经网络法学习效率低、计算速度慢、精度低；遗传算法计算速度快、易于和其他算法结合，但存在搜索范围大、搜索时间长、早熟收敛等问题；差分进化算法与其他算法结合效果较好；粒子群算法收敛速度快、计算简单，但易陷入局部优化；蚁群算法起步较晚，尚不完善；混合蛙跳算法调整参数少、计算速度快、适用于多目标优化问题，但其在多目标柔性作业车间调度方面的应用还处于探索阶段；模拟退火算法能够有效解决多目标柔性作业车间调度问题，但初始温度的选择和早熟收敛等问题还有待研究。同时，人们也在不断地对基本智能算法进行改进用以解决更为复杂的车间调度问题，张于贤[2]等提出了一种基于生物记忆曲线模型的信息素更新规则对蚁群算法进行改进，克服了蚁群算法收敛速度慢、易陷入局部最优的缺陷。孙亮[3]等提出了一种自适应超启发式遗传算法求解随机型作业车间调度问题，突破了随机算法与局部搜索相结合的传统算法解决此类问题时计算时间过长的缺陷。吴秀丽[4]等提出了一种改进的细菌觅食算法。王艳红[5]等对蚁群算法进行改进，提出了一种动态平衡自适应蚁群算法。 3 FJSP问题的分类
根据优化目标的数量，可将柔性作业车间调度问题分为单目标调度问题和多目标调度问题，根据是否考虑生产过程中的不确定因素，又可将其分为静态调度问题和动态调度问题，常见的不确定因素有机器故障、机器的预防性维修、订单异动、材料短缺等，表2所示为几种常见不确定因素及对应的解决办法。通过对已有文献的分析发现优化目标的数量以及是否考虑不确定因素对FJSP问题的复杂程度和求解难度有重要影响，据此，本文将FJSP问题分为单目标静态调度、多目标静态调度、单目标动态调度、多目标动态调度四种类型，并分析比较各自的特点。
表2 常见不确定因素及应对策略不确定因素 应对策略机器故障完全未知为每台
机器安排一定的空闲时间进行等周期/非等周期的预防性维修，维修时间不得与该设备上工件的加工时间相冲突，为此，可采用左移或右移策略机器故障部分已知根据以往数据计算得到机器的故障概率分布（一般服从指数分布或威尔分布）并设定阈值，当其故障概率值大于设定的阈值（或其可靠度低于某一阈值）时即认为机器将发生故障，此时，非故障机器继续工作，可能故障机器上的未加工件转移到其他可选机器上等待加工，若无可再选机器，则采用右移策略，即等待机器修复后继续加工或启用重调度。若维修时间小于重调度时间，则在故障机器维修好之后继续执行初始调度方案，否则，启用重调度，生成新的调度方案机器故障完全已知 制定调度方案时剔除此类机器，等待维修完毕方可分配加工任务紧急订单插入正在加工的工序照常进行，将插单工件安排到空闲机器上，空闲机器上原有的未加工工序采用右移策略，即等待插单工件完工后再按原调度方案在对应机器上继续加工订单撤销若被撤销的订单工件已被加工完成，则继续执行原调度方案；若被撤销的订单工件正在加工，则立即停止，进行后续工件的加工；若被撤销的订单工件未被加工，则跳过这些工件进行后续工件的加工材料短缺 建立预测调度模型，在每个工件的加工时间中插入空闲时间来吸收材料短缺的扰动 3.1 单目标静态调度
单目标静态调度是柔性作业车间调度中最简单、最基本的调度类型，是其他调度类型的基础，其优化目标明确且单一，通常为表1所示优化目标中的一种，约束条件则为表1所示的一般性约束，将优化目标和约束条件用恰当的数学语言或数学手段详细而准确地表达出来即得到其数学模型，例如，当加工时间是随机变量时，为了方便计算，以最小化最大完工时间的期望值作为优化目标，并且常用模糊隶属度函数来描述某些不确定性因素，并用数形结合的思想来表达某些目标函数。杨建斌[6]等用三角模糊数和半梯形模糊数分别表示模糊加工时间和模糊交货期，建立了以最大化最小客户满意度为优化目标的作业车间模糊调度模型，并采用自适应遗
传算法求解了模型。黄亚平[7]等用三角模糊数表示模糊加工时间，用梯形模糊数表示模糊交货期，以交货期平均满意度最大为优化目标，建立了作业车间的模糊调度模型，并采用自适应蚁群算法对模型进行了求解。
另一方面，为了使调度模型更符合生产实际，往往需要添加新的约束条件，如考虑工序调整时间和工件在机器间的移动时间等，此时，所建立的数学模型中还应当包含新增加的约束条件所对应的数学语言。张国辉[8]等在考虑工件移动时间的情况下建立了柔性作业车间的析取图调度模型，并通过重构遗传操作方法对模型进行了求解。
由于单目标静态调度无需考虑不确定因素，且不存在优化目标之间相互冲突的问题，因此，其建模和求解均比较容易实现。 3.2 多目标静态调度
从字面上看，多目标静态调度与单目标静态调度的区别只在于前者至少要考虑两个优化目标，然而，在多目标静态调度中，各优化目标间可能相互冲突，如既要保证最小完工时间，又要避免提前完工而增加库存成本，因此，二者在建模和求解方面也有所不同。陈明[9]等建立了多目标柔性作业车间调度模型，设计了一种扩展的基于工序的编码，采用一种插入式贪婪解码算法进行解码，将染色体解码后产生主动调度，并使用粒子群算法求解模型。黄利福[10]等提出了一种基于模糊物元模型与粒子群算法的模糊粒子群算法，用以解决高维多目标柔性作业车间调度问题。 多目标静态调度模型中通常具有至少两个目标函数，为了同时兼顾各项优化指标，常用的做法是根据对各项指标的关心程度，按不同的权值通过线性变换将多个目标函数转换为一个目标函数，从而降低求解难度，并且多采用改进的算法或混合算法对模型进行求解。 3.3 单目标动态调度
对于动态柔性作业车间调度问题，有三种调度策略：周期型调度、事件驱动型调度、
周期和事件混合驱动型调度。苟海燕[11]等开发了一套事件驱动的动态作业车间实时调度系统，设计了三种重调度方案，根据不同的不确定因素来触发相应的重调度方案。宋李俊[12]等设计了一种基于滚动时域的机器故障情况下周期和事件共同驱动的动态调度策略，并采用基于双层编码的遗传算法求解了模型。李保[13]等采用事件驱动的调度策略把带有不确定因素的动态调度问题分解为多个静态调度问题，并使用自适应蚁群算法对子问题进行求解。潘颖[14]等提出了一种基于故障处理算法的柔性作业车间调度问题的动态仿真求解模型，采用事件驱动策略判断重调度时机，并利用右移启发算法实现重调度。
同单目标静态调度一样，单目标动态调度的优化目标也是表1所列优化目标中的一种，但由于考虑了不确定因素，其调度模型中优化目标的描述方法将可能发生变化，并且除了满足三个一般性约束条件之外，还要考虑不确定因素所带来的约束，例如，当考虑机器故障时，其约束条件中还应包含故障机器的维修时间与该机器上工件的加工时间之间关系的约束。在算法方面，通常先在不考虑动态因素的情况下采用传统的优化算法求解得到初始调度方案，然后，在不确定因素触发重调度后采用改进的优化算法或混合算法求得新的调度方案。 3.4 多目标动态调度
多目标动态调度是求解难度最大的一类调度问题，是多目标静态调度和单目标动态调度问题的扩展，相对于前者而言，多目标动态调度要考虑不确定因素的影响，往往要在预调度方案的基础上进行方案的调整或重调度以应对不确定因素，其调度模型中的约束条件更多、更复杂，求解过程更加繁琐，但同时也更符合实际，因此是当前的研究热点。刘胜[15]等研究了机器随机故障情况下的多目标柔性作业车间调度问题，假设机器故障服从指数分布，提出了一种兼顾调度鲁棒性与稳定性的改进的两阶段多种群遗传算法。邹攀[16]等提出了一种基于分层蚁群遗传算法的车间资源驱动的柔性作业车间调度算法，适用于不确定情境下的车间动态调度。张国辉
[17]等提出了一种多阶段人机协同调度策略，包括制定初始调度方案、判断机器故障并记录相关信息、启用重调度方案，采用自适应遗传算法求解调度方案集，并结合调度人员经验从中选择一种最合适的调度方案。刘晓冰[18]等针对交货期与完工时间的不确定性，以最小化最大完工时间、加工成本和惩罚值为目标，建立了模糊柔性作业车间调度模型，并采用混沌量子粒子群算法对模型进行了求解。 与后者相比，多目标动态调度问题中除了考虑一般性的优化目标以外，更加关注不确定因素之前的预调度方案与不确定因素之后的重调度方案在某些指标上的差值，一方面是为了保证预调度方案能具有一定的稳定性，另一方面是为了能够更好的地指导重调度。张国辉[19]等针对考虑机器故障的柔性作业车间调度方案，提出了两种鲁棒性测度指标：初始调度与实际调度的最大完工时间偏差、每台机器的空闲时间与工作负荷比，指出预测机器的故障和维修时间以及保证每台机器拥有一定的空闲时间均可减小因机器故障而导致的工期延迟。 4 总结与展望
从单目标静态调度到多目标静态调度，再到单目标动态调度，最后到多目标动态调度，是一个从特殊到一般、从理想化到现实化的过程，多目标动态调度考虑了生产过程中的不确定因素，同时兼顾了现实中客户所要求达到的多项性能指标，因而是最符合实际生产情况的调度类型。
但是，目前的研究主要集中于单因素的动态调度，很少同时考虑多个不确定因素的综合影响，也没有对车间底层数据加以很好的利用来指导形成一种不确定情况下的数据驱动的动态调度模式，从而无法及时有效地消除不确定因素带来的扰动，也就不能最大程度地降低损失，因此，探索一种数据驱动下的满足多个优化目标且能够有效应对多种不确定因素的动态作业车间调度模型是今后的一个研究方向，为此，可从以下几方面入手：
（1）充分挖掘生产过程中的有用信息，为调度方案的制定和调整提供实时的、第
一手的资料；
（2）结合现有的调度模型和相关数学知识探索建立数据驱动的动态作业车间调度模型；
（3）改进、融合现有的调度算法，充分利用各种算法各自的优势，或设计新的算法，为模型的求解提供有力的工具。 参考文献：
【相关文献】
[1]彭建刚，刘明周，张铭鑫，等.多目标柔性作业车间调度算法研究综述[J].中国机械工程，2014，25（23）：3244-3254.
[2]张于贤，丁修坤，沈 烨，等.基于记忆曲线的ACO在柔性作业车间的调度优化[J].系统科学学报，2016，24（03）：62-66.
[3]孙 亮，王晓原，张运才.自适应超启发式遗传算法求解随机型生产调度问题[J].小型微型计算机系统，2013，34（09）：2158-2163.
[4]吴秀丽，张志强，杜彦华，等.改进细菌觅食算法求解柔性作业车间调度问题[J].计算机集成制造系统，2015，21（05）：1262-1270.
[5]王艳红，王文霞，于洪霞，等.一类求解作业车间调度问题的动态平衡自适应蚁群算法[J].计算机集成制造系统，2013，19（10）：2521-2527.
[6]杨建斌，孙树栋，牛刚刚，等.自适应遗传算法求解模糊作业车间调度问题[J].机械科学与技术，2013，32（01）：16-21.
[7]黄亚平，王万良，熊 婧.基于自适应蚁群算法的作业车间模糊调度研究[J].计算机仿真，2009，26（04）：244-248.
[8]张国辉，党世杰.考虑工件移动时间的柔性作业车间调度问题研究[J].计算机应用研究，2017，34（08）：2329-2331.
[9]陈 明，胡言乐，刘晋飞.基于粒子群算法的多目标柔性作业车间调度问题研究[J].机电一体化，2017，23（01）：11-15 60.
[10]黄利福，梁工谦，董仲慧.基于模糊物元模型的高维多目标FJSP 研究[J].计算机应用研究，2017，34（05）：1337-1341.
[11]苟海燕，张敬敏.动态作业车间实时调度系统[J].中国民航飞行学院学报，2015，27（03）：70-73.
[12]宋李俊，赵 虎.基于滚动时域优化策略的柔性作业车间动态调度研究[J].现代制造工程，2015（02）：30-35，42.
[13]李 保，王长华，熊 婧.基于自适应蚁群算法的动态作业车间调度问题的求解方法[J].机电工程，2009，26（07）：93-96.
[14]潘 颖，高天一，薛冬娟，等.基于故障处理算法的动态多目标FJSP研究[J].组合机床与自动化加工技术，2014（04）：150-153.
[15]刘 胜，于海强.基于改进遗传算法的多目标FJSP问题研究[J].控制工程，2016，23（06）：816-822.
[16]邹 攀，李蓓智，杨建国，等.基于分层蚁群遗传算法的多目标柔性作业车间调度方法[J].中国机械工程，2015，26（21）：2873-2879，2884.
[17]张国辉，王永成，张海军.多阶段人机协同求解动态柔性作业车间调度问题[J].控制与决策，2016，31（01）：169-172.
[18]刘晓冰，焦 璇，黄 明，等.用混合量子算法求解模糊柔性作业车间调度问题[J].工业工程与管理，2015，20（03）：8-13.
[19]张国辉，吴立辉，聂 黎，等.考虑机器故障的柔性作业车间鲁棒调度方法[J].系统仿真学报，2016，28（04）：867-873.