李传鹏，王桂从，崔焕勇

(济南大学机械工程学院，济南 250022)

柔性作业车间调度问题研究现状及发展趋势*

李传鹏，王桂从，崔焕勇

(济南大学机械工程学院，济南 250022)

文章描述了柔性作业车间调度问题，并根据目标、约束、批量等不同的分类标准对其进行了分类，总结了柔性作业车间调度问题建模方法及优化算法的研究现状，最后通过现存问题的分析探讨了发展趋势。

柔性车间调度;建模;优化算法;发展趋势

0 引言

随着改革步伐的加快和现代工业的发展，企业的生产正朝着多品种、小批量、有着不同完工时间和产品要求的方向发展。在这种生产方式下，产品生产品种多、规模小，造成生产作业过程中信息复杂，从而使得企业的生产作业计划安排工作难度加大，难以控制。容易造成不能按期交货、产品质量不能保证、经济效益降低等问题。

柔性作业车间调度问题(Flexible Job Shop Scheduling Problem，FJSP)是传统作业车间生产调度问题(Job Shop Scheduling Problem，JSP)的扩展，是先进制造系统运筹技术、管理技术与优化技术发展的核心［1］。FJSP 是 Bruker和 Schlies［2］在 1990 年首次提出的，该问题除了要解决JSP中确定加工顺序外，还要解决各工序分配到哪台机器上加工的问题，使问题更加复杂。有关资料表明，制造过程中95%的时间消耗在非切削过程中［3］，有效的柔性作业车间调度方法的研究，对提高生产效率和实现先进制造企业的现代化具有重要意义。

1 FJSP的描述

柔性作业车间调度问题描述如下:一个加工系统有m台机器，要加工n种工件，每个工件由一道或多道工序组成，各工序有先后约束关系，且可在m台机器中的一台或多台机器上加工，每台机器可加工工件的若干工序，且在不同的机器上加工的工序集可以不同。调度的目标是将工件合理的安排到各机器上，并合理安排工件的加工次序和加工时间，使约束条件被满足，同时优化一些性能指标。

为了方便简化问题，FJSP经常作出一些条件的假设［4-5］。例如:①零时刻所有工件都能被加工;②所有机器在零时刻都可用;③每台设备一次只能加工一个工件;④工序一旦进行不能中断;⑤工件间优先级相同;⑥对每个操作均允许等待。

2 FJSP的分类

柔性车间调度问题的分类方法很多，根据不同的分类标准可将其划分为不同的类型。

根据目标划分，FJSP有单目标和多目标之分。在FJSP中常见的目标有最大完工时间最小、总加工时间最小、最大负荷机器负荷最小、提前/拖期惩罚最小、成本最低、设备利用率最高等。单目标FJSP只是针对其中一个目标进行优化，比较常见的是最大完工时间最小［6-8］。但优化单个目标很难满足实际的生产需要，通常需要同时考虑多个目标，即在不损坏其他目标性能的情况下尽量提高任何一个目标的性能。目前许多学者开始研究多目标FJSP［9-12］，比较常见的是将最大完工时间最小、最大机器负荷最小、总加工时间最小三个目标同时考虑。

根据约束划分，FJSP常见的约束条件有生产资源(能量、原料、设备等)、缓存容量、产品交货期、产品工艺流程、批量大小、成本限制等。Zribi［13］研究了FJSP中资源约束情况下机器资源的使用;Rossi［14］考虑安装时间、增加运输时间的车间实际生产情况，利用蚁群算法对FJSP进行求解;张维存［15］等人以能力约束下的FJSP，提出一种主、从递阶结构的蚁群遗传求解算法。实际生产中，往往需要同时考虑多个约束条件，随着约束条件的增多，FJSP的求解会更加复杂。

根据批量划分，FJSP有小批量和中小批量之分。分批就是将作业的加工方式由串行转换成并行，Low［16］已经验证了分批处理可以使机器利用率得到提高。分批调度的关键是如何确定最佳子批数量，子批数量过少，分批的有效性会降低，机器空闲时间增加;子批数量过多，增加了调度的复杂性，且增大了工作的准备时间所带来的时间消耗。白俊杰［17］提出可以根据机床负荷将工件分为具有柔性批量的适当子批量的粒子群的算法，同时优化了子批的工艺路钱及加工顺序。

根据系统的性能划分，有静态问题和动态问题之分。静态调度是指所有需要生产资源都在初始时刻到达，且加工任务的信息完备可预知。动态调度是指调度的环境和任务存在不可预测的扰动情况下的调度，不仅依赖于事前调度环境和任务，而且与当前的状态有关［18］。现在车间调度类型通常是动态的。杨红红［19］根据建立的动态数据库管理模块和遗传算法模块，引入约束解决机制，对动态环境下的调度问题进行研究。吴秀丽［20］采用事件驱动和周期驱动相结合的调度策略，提出了基于多目标免疫遗传算法的动态调度优化模型，设计了面向交货期性能最优的柔性作业车间调度算法。

3 FJSP的建模方法

FJSP具有复杂性、多约束性、多目标性、动态随机性等特点。车间调度问题都是对具体的生产环境中复杂动态、多目标、多约束调度问题的一种抽象和简化，其首要问题是对制造系统进行建模。目前建模方法有很多，主要包括以下三大类:第一类是数学规划法，第二类是图与网络方法，第三类是仿真法。

3.1 数学规划法

数学规划法是用数学关系表达式表达所研究系统变量之间的相互关系。庞哈利［21］研究了柔性作业车间计划与调度问题，建立了两层混合整数规划模型，综合运用门槛接受算法、遗传算法和启发式规则，提出了混合启发式求解算法。Parviz Fattahi［22］对柔性车间调度问题建立了一个数学线性规划模型，用模拟退火启发式和禁忌搜索启发式方法分别提出了两种遗传算法。该方法所建模型有较强的逻辑性，并能实现系统的优化，是车间调度问题中应用较多的一种建模方法。

3.2 图和网络方法

图和网络方法主要有活动循环图、关键路径法、组合网络、Petri网、GRAI网等。其中Petri网具有直观的图形表示方式和严密的数学基础，系统描述手段丰富，行为分析技术成熟，被作为柔性制造系统的建模、分析、控制与调度的重要技术手段。主要有:乐晓波［23］以带有约束条件的Petri网为动态车间调度问题建模，同时提出一种针对动态车间调度问题的编码粒子群算法，对调度序列进行优化;廖伟志［24］针对具有混杂特征的柔性制造系统调度问题，建立了柔性制造系统的一阶混杂Petri网模型，提出了用于求解柔性制造系统调度最优解的免疫算法。图和网络方法存在的不足是节点语义单一，不能携带足够的系统信息量;且重用性差，当作业需求和工艺稍作变动，模型结构就需要改动。

3.3 仿真法

仿真法就是建立描述系统行为规律的系统模型，再将其转化为计算机仿真程序。与数学规划法相比较，仿真法直观且形象化，较为常见仿真语言及软件如 Witness、SIMSCRIP、ECSL等，其中 witness软件提供了多种建模元素、优化模块、虚拟现实模块等方便于离散事件系统的仿真。陈彩丽［25］针对车间调度问题建立了基于Witness的仿真模型，对实时数据进行了分析和评价，并优化相关指标和参数，最后将结果反馈给仿真系统实施控制。陈勇［26］等人基于元胞自动机建立了大型零件生产车间动态柔性调度的仿真模型，将系统划分为工位元胞、缓存元胞、移动粒子、局部自组织演化规则4部分，最终实现了通过局域演化对宏观工件流加工过程的模拟。仿真法的缺点也很明显，成本高、建模周期长、只能给出问题的特解而不是给出问题的通解。

4 FJSP的优化方法

对车间制造系统建立数学模型后，就要构造相应的调度算法进行问题的求解。随着各种新的相关科学与优化技术的建立与发展，在车间调度领域也出现了许多新的优化方法。解决FJSP的方法主要分为两类:精确方法和近似方法。

4.1 精确方法

基于运筹学的方法，是将调度问题简化为数学模型，规定一个目标函数来解决调度最优化或次优化问题。主要有整数规划、分枝定界法等。Torabi等人［27］建立了一个混合0-1规划模型，并用枚举的方法进行求解FJSP中的批量调度问题。宋晔［28］为解决对精度和实时性要求较高的调度问题，提出了基于分枝定界和神经网络的实时调度策略。基于运筹学方法能够保证任务分配和排序的全局性，但对于复杂问题，存在求解空间大和计算困难等问题限制了它的使用。

4.2 近似方法

近似方法可以很快地得到问题的解，虽不能保证得到的解是最优的，但可以较好的满足实际问题的需求，适用于大规模问题。近似方法主要有分派规则法、基于人工智能的方法、邻域搜索法等。

分派规则法是最早的近似方法。Panwalkar和Iskander［29］总结了113条规则，并将它们分为三类:简单规则、复合规则、启发式规则，比较常用的规则有SPT、LPT、EDD、FCFS等。分派规则法一般适用于求解数学规划法的建模，但采用该方法求解多目标FJSP的研究较少，因为使用单一的优先规则得到的解不能满足要求，如何把多个规则进行融合，得到一个合理的满意度值是该方法研究的方向。主要有:Ho和Tay［30］利用进化算法对分派规则进行组合并应用于FJSP。

人工智能是指模拟人类智能活动进行优化的方法。主要包括:约束满足、专家系统及神经网络等。约束满足是通过运用限制选择变量的次序和变量值排序的约束来减少搜索空间的有效规模。专家系统是将传统的调度方法与基于知识的调度评价相结合，根据给定的优化目标和系统当前状态，对知识库进行有效的启发式搜索和并行模糊推理，避开繁琐的计算，选择最优的调度方案。神经网络优化法主要是利用其并行计算能力和学习能力进行优化，最终实现可行的调度策略。目前仅见到神经网络求解FJSP的少量研究，Xu［31］设计一种离散神经网络结合瞬时混沌方法进行求解FJSP。把神经网络和其他启发式算法结合将是该方法的研究热点。

邻域搜索法包括遗传算法、蚁群算法、禁忌搜索算法、粒子群算法等，用其求解数学规划法、图和网络方法建模的FJSP问题都有大量研究。它的思想是对调度问题的解进行编码，编码与问题的调度方案一一对应，从任意有效的编码开始对其邻域的不断搜索，并对当前序列进行替换来实现优化，通常用于规模较大、传统方法难以求解的问题。其中遗传算法在求解很多组合优化问题时，不需要有很多技巧和对问题深入了解;且与其他启发式算法有较好的兼容性，能发挥各自优势来提高求解能力。孙艳丰［32］提出将遗传算法与禁忌搜索混合策略，加快了收敛速度，提高了遗传算法的局部搜索能力;高杰等人［33］设计了一种结合遗传算法和变邻域下降算法的综合算法。蚁群算法最初是用于解决TSP问题的，具有通用性和鲁莽性的随机试探法，近年来已渗透到车间调度领域。Silva［34］通过研究得出蚁群算法更适合动态调度问题;Yu等［35］提出使用经过突变处理的蚁群优化算法，使其不容易陷入局部最优，通过这种蚁群算法解决动态车间调度的紧急订单插入重调度问题。禁忌搜索算法对求解的问题、目标函数及搜索空间没有特殊的要求，且计算速度较快，受到了许多学者的重视。李俊青［36］提出了带有Pareto档案集的混合禁忌搜索算法，保证了解的多样性，并引入基于关键块结构的插入邻域和交换邻域操作，缩小了搜索空间。贾兆红［37］在粒子群算法应用上做了大量工作，利用混沌对算法的参数进行自适应优化，提出了一种混合的粒子群算法，提高搜索能力。Ghasem Moslehi等［38］设计了粒子群优化算法和邻域搜索算法相结合的Pareto算法来求解多目标FJSP问题。

除此之外，还有很多种方法对FJSP进行求解，如模糊数学理论、多代理方法等。各种调度算法都不同程度地存在着优缺点，除传统组合的启发式规则外，近年来，人们把各种近似算法的组合应用研究作为热点，以弥补各自的缺点，发挥各自优势，达到高度次优化的目标。

5 FJSP的发展趋势

虽然我们对FJSP已有大量的研究，但要形成一套系统的理论和方法还有很长的路要走，理论研究与实际应用存在的差距还是很大的。主要存在以下几个方面的问题:

(1)用数学规划的方法描述调度问题能够使用各种优化算法进行优化求解，由于描述方法的限制，忽略了很多实际因素;用Petri网的建模方法能够较好的考虑系统的实际因素，但它们对调度多用启发式规则而没有寻求一些全局最优的方法，都有待发展。

(2)多目标柔性作业车间调度问题的讨论仅仅局限在所有工件的目标均相同的情况下，关于各种工件目标不同的调度问题研究不够成熟，对工件生产批量不同的问题研究更少。

(3)单一的优化算法存在局限性，比如:遗传算法、禁忌搜索、模拟退火等。多种方法混合使用可以平衡算法搜索的广泛性和集中性，避免早熟，避免陷入局部最优。

(4)对于动态调度的研究相对较少，一般都采用基于事件的重调度或者周期调度，而对于重调度后的效果如何的研究较少，需要进一步研究。

［1］朱星辉，朱金福，姜涛.作业车间调度问题的几种模型之比较［J］. 统计与决策，2007，23:174-176.

［2］BRUKER P，SCHLIC R.Job Shop Scheduling with MultipurposeMachines［J］.Computing，1990，4(2):369-375.

［3］何霆，刘飞，马玉林，等.车间生产调度问题研究［J］.机械工程学报，2000，36(5):97-103.

［4］吴秀丽，孙树栋，杨展，等.多目标柔性Job Shop调度问题的技术现状和发展趋势［J］.计算机应用研究，2007，24(3):1-5.

［5］王锐.应用多种群遗传算法求解动态车间调度问题［D］.大连:大连理工大学，2009.

［6］KACEM I.Genetic Algorithm for the Flexible Job-Shop Scheduling Problem［J］.IEEE International Conference on Systems，Man and Cybernetics，2003，4:3464-3469.

［7］YAZDANI M，AMIRI M，ZANDIEH M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm［J］.Expert Systems with Applications，2010，37:678-687.

［8］ZHANG G H，GAO L，SHI Y.An effective genetic algorithm for the flexible job-shop scheduling problem［J］.Expert Systems with Applications，2011，38:3563-3573.

［9］潘全科，朱剑英.多工艺路线多资源多目标的作业调度优化［J］. 中国机械工程，2005，16(20):1821-1825.

［10］ADIBI M A，ZANDIEH M，AMIRI M.Multi-objective scheduling of dynamic job shop using variable neighborhood search［J］.Expert Systems with Applications，2010，37:282-287.

［11］XIA W，WU Z.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems［J］.Computers and Industrial Engineering，2005，48(2):409-425.

［12］VILCOT G，BILLAUT J C，ESSWEIN C.A genetic algorithm for a bicriteria flexible job shop scheduling problems［J］.Internation Conference on Service Systems and Service Management，2006，2:1240-1244.

［13］ZRIBI N，BORNE P.Hybrid genetic algorithm for the flexible job-shop problem under maintenance constraints［J］.LNCS，2005，3612:259-268.

［14］ROSSI A，DINI G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method［J］.Robotics and Computer-Integrated Manufacturing，2007，23:503-516.

［15］张维存，郑丕谔，吴晓丹.蚁群遗传算法求解能力约束的柔性作业车间调度问题［J］.计算机集成制造系统，2007，13(2):333-347.

［16］LOW C Y，HSU C M，HUANG K I.Benefits of lot splitting in Job-Shop scheduling［J］.International Journal of Advanced Manufacturing Technology，2004，24(9/10):773-780.

［17］白俊杰，龚毅光，王宁生，等.多目标柔性作业车间分批优化调度［J］.计算机集成制造系统，2010，16(2):396-403.

［18］王万良，吴启迪.生产调度智能算法及其应用［M］.北京:科学出版社，2007.

［19］杨红红，吴智铭.基于自适应遗传算法的柔性动态调度研究［J］. 中国机械工程，2002，13(21):1845-1848.

［20］吴秀丽.柔性作业车间动态调度问题研究［J］.系统仿真学报，2008，20(14):3828-3832.

［21］庞哈利.柔性Job Shop集成化计划调度模型及其求解算法［J］. 控制与决策，2003，18(1):34-39.

［22］PARVIZ F，ALIREZA F.Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability［J］.CIRP Journal of Manufacturing Science and Technology，2010(2):114-123.

［23］乐晓波，秦娜，刘武.基于Petri网和PSO算法的动态分类车间调度［J］.长沙理工大学学报，2008，5(2):72-76.

［24］廖伟志，古天龙，王汝凉，等.基于混杂Petri网的柔性制造系统免疫调度算法［J］.系统仿真学报，2010，22(1):205-209.

［25］陈彩丽，王加兴.基于Witness的汽轮机叶片车间仿真优化方法研究［J］. 轻工机械，2010，28(4):116-122.

［26］陈勇，阮幸聪，鲁建厦.基于元胞自动机的大型零件生产车间动态柔性调度仿真建模［J］.中国机械工程，2010，21(21):2603-2608.

［27］Torabi S A，Karimi B，Fatemi S M T.The common cycle economic lot scheduling in flexible job shops:the finite horizon case［J］.Int J.Production Economics，2005，97(1):52-65.

［28］宋晔，杨根科.基于分支定界和神经网络的实时调度策略［J］. 计算机仿真，2008，25(12):321-324.

［29］PANWALKER S，WAFIK I.A Survey of Scheduling［J］.OPS.Res.2003，25(1):45-61.

［30］HO N B，TAY J C.Genace:an efficient cultural algorithm solving the flexible job shop problem:proceedings of Congress on Evolutionary Computation［C］.2004:1759-1766.

［31］XU X L，GUAN Q，WANG W L，et al.Transient chaotic discrete neural network for flexible job-shop scheduling［J］.LNCS，2005，3496:762-769.

［32］孙艳丰.基于遗传算法和禁忌搜索算法的混合策略及应用［J］. 北京工业大学学报，2006，32(3):258-262.

［33］GAO J，SUN L Y，GEN M.A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problem［J］.Computers＆ Operations Research，2008，35:2892-2907.

［34］SILVA C A，SOUSA J M C，RUNKLER T A.Rescheduling and optimization of logistic processes using GA and ACO［J］.Engineering Applications of Artificial Intelligence，2008，21(3):343-352.

［35］YU Y H，YAN J Q.Flow shop rescheduling problem under rush orders［J］.Journal of Zhejiang University，2005，10:1040-1046.

［36］李俊青，潘全科，王玉亭.多目标柔性车间调度的Pareto混合禁忌搜索算法［J］.计算机集成制造系统，2010，16(7):1419-1425.

［37］贾兆红，陈华平，孙耀晖.多目标粒子群优化算法在柔性车间调度中的应用［J］.小型微型计算机系统，2008，5(5):885-889.

［38］GHASEM M，MEHDI M.A pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search［J］.International Journal of Production Economics，2011，129:14-22.

Research Status and Development Trend of Flexible Job Shop Scheduling Problem

LI Chuan-peng，WANG Gui-cong，CUI Huan-yong
(School of Mechanical Engineering，University of Jinan，Jinan 250022，China)

This paper describes the flexible job shop scheduling problem，classifies according to the different classification criteria of objectives，constraints，batches and so on，and summarizes research status of flexible job shop scheduling problem’s modeling methods and optimization algorithm，finally through the analysis of the existing problems，discusses the development trend.

flexible job shop scheduling problem;modeling;optimization algorithm;development trend

TH162;TP273

A

1001-2265(2012)11-0109-04

2012-04-16

山东省优秀中青年科学家科研奖励基金(BS2009ZZ013)

李传鹏(1987—)，男，山东荣成人，济南大学机械工程学院硕士研究生，研究方向为制造系统工程及其信息集成，(E-mail)lcp87292006@126.com

(编辑 李秀敏)