第17卷第4期计算机集成制造系统
Vol.17No.42011年4月
Computer Integrated Manufacturing Systems
Apr.2011
文章编号:1006-5911(2011)04-0826-06
收稿日期:2010-03-16；修订日期:2010-08-24。Received 16Mar.2010;accepted 24Aug.2010.
基金项目：国家自然科学基金资助项目(50705076,50705077)；国家863计划资助项目(2007AA04Z187)；陕西省自然科学基础研究计划资助项
目(2009JQ9002)。Fo undatio n items:Project supported by th e Nation al Natural Science Foun dation,China (No.50705076,50705077),the Nation al H igh -Tech.R&D Program,Ch ina(No.2007AA04Z187),and the Natu ral Science Basic Research Program in Sh aanxi Province,Chin a(No.2009JQ9002).
翟颖妮，孙树栋，王军强，郭世慧
(西北工业大学系统集成与工程管理研究所现代设计与集成制造技术教育部重点实验室，陕西 西安 710072)摘 要：针对大规模作业车间生产调度问题，提出一种基于瓶颈工序分解的调度算法。该算法采用正交试验进行瓶颈设备的识别，在设备层分解的基础上进一步进行工序级的分解，将大规模调度问题分解为瓶颈工序集调度、上游非瓶颈工序集调度和下游非瓶颈工序集调度三个子问题，通过子问题的求解和协调获得原问题的解。该算法遵循约束理论中/瓶颈机主导非瓶颈机0的原则，抓住调度问题的关键因素，采用分而治之的调度策略，不仅较大程度地降低了原问题的计算规模和复杂度，还兼顾了求解的质量。仿真结果表明了该算法的优越性和可推广性。 关键词：大规模作业车间；调度；瓶颈工序；正交试验中图分类号:T H 166;T P 391 文献标志码:A
Scheduling algorithm based on bottleneck operations decomposition for
large -scale Job Shop scheduling problems
ZH A I Ying -ni,S UN Shu -dong,WA N G Jun -qiang,G UO Shi -hui
(Institute of Sy stem Integ rat ion &Engineer ing M anagement,M inistry of Educatio n K ey L ab of Contemporar y Desig n and Integ r ated M anufactur ing T echno lo gy ,N or thwestern P olytechnical
搪瓷缸
U niver sity,Xi p an,China,710072)Abstract:A iming at larg e -scale Job Sho p scheduling pro blems,a scheduling algo rit hm based o n the bot tleneck opera -tions decomposition was pro po sed.In this alg or ithm,by the bott leneck w as r eco gnized by o rthog onal experiment.T hen,the o per atio ns deco mpo sitio n w as ca rried out,ther efore the lar ge -scale Job Shop scheduling pro blem w as de -composed into thr ee scheduling sub -pro blems:bottleneck -operations set,preceding -bo ttleneck -o per atio ns set,and follow ing -bo ttleneck -o per ations set.T he solut ion to the o rig inal pro blem was o bt ained by so lv ing the sub -pr oblems and coor dinating the so lutio ns o f the sub -pr oblems.Acco rding to t he pr inciple of /Bottleneck machines leads non -bo ttleneck machines 0in T heor y o f Co nstr aints (T O C),this alg or ithm impr oved the comput ation efficiency and the qualit y o f t he so lutio n by the decom position st rateg y and the co ordinatio n techniques for the so lution of the sub -prob -lems.Simulation results sho wed the adv antag e and ext ensibility of pro po sed alg or ithm.Key words:larg e -sca le jo b shop;scheduling ;bott leneck operat ions;o rthog onal ex per iment
0 引言
作业车间调度问题(Job Shop Scheduling Pro blem,JSP)是典型的NP -hard 问题[1]
。半个世纪以来，针对该问题的建模和求解取得了很大进步,
尤其在中小规模调度领域，已有不少有效的调度方法，如数学规划法[2]
、启发式搜索法[3]
、人工智能及
仿真
[4]
等。然而，随着市场竞争的加剧，制造业的生
产规模日益增大，如何有效解决大规模生产调度问题，已经成为近年来生产调度领域研究的热点[5-6]。
第4期翟颖妮等：大规模作业车间的瓶颈分解调度算法
电梯运行检测平台
文献[7]提出一种基于操作分解的迭代求解方法，沿
时域将原调度问题的所有操作分解为多个子集进行
仿形切割机
求解。滚动时域(rolling hor izon)分解法[8]将整个
调度时域分解为若干个决策子窗口，通过依次求解
各子窗口的调度问题获得原问题的解。文献[9]采
用拉格朗日松弛法，通过松弛原问题的设备加工能
力约束或工件的工艺顺序约束，降低原调度问题求
解的复杂度。转移瓶颈(shifting bottleneck)法[10]
采用基于设备分解的方法，将原问题分解为一系列
的单机调度问题来进行求解。文献[11]和文献[12]
提出了一种基于瓶颈设备分解的调度方法，将原问
题分解为瓶颈机和非瓶颈机两个调度子问题来
求解。
然而，现有的分解调度方法往往存在子问题分
解数目多、子问题协调频繁、调度性能不理想等问
题。本文提出基于瓶颈工序分解的调度方法，采用
正交试验进行瓶颈设备的识别，将大规模JSP分解
为上游非瓶颈工序集调度、瓶颈工序集调度和下游
非瓶颈工序集调度三个子问题，以降低原问题的求
解复杂度；利用约束理论(Theory of Co nstr aints,
TOC)中瓶颈机主导非瓶颈机的思想，通过子问题
的求解和协调，最终实现大规模JSP的求解。
1问题描述
设n个工件在m台设备上加工，每个工件J i(i
=1,,,n)包含m道工序，各工序之间有工艺的先
后顺序约束，且在每台设备M k(k=1,,,m)上仅加
工一次。O i,j表示工件i在设备j上的加工工序,
p i,j表示工件i在设备j上的加工时间,t i,j表示工件
i在设备j上的开工时间。调度任务是在m台设备
上安排n个工件的加工，确定各设备上各工序的加
工顺序及相应的开工时间，以最优化既定的作业目
标，并满足以下条件:
(1)所有工件的工艺路线、工序加工时间既定
不变。
(2)工序一旦开始加工不允许中断。
(3)同一时刻每台设备最多只能加工一个工件。
(4)同一时刻每个工件只能在一台设备上加工。
以Makespan为作业目标，建立相应的调度数
学规划模型(P)如下:
m in max
1[i[n {t i,g
i
(m)+p i,g i(m)}。(1)
< i,g
i
(k+1)-t i,g i(k)\p i,g i(k),
i=1,,,n,k=1,,,m-1;(2)
t j,k-t i,k+a(1-x ij k)\p i,k,i=1,,,n,
j=1,,,n,i X j,k=1,,,m,x ijk I{0,1};(3) t i,k-t j,k+ax ijk\p j,k,i=1,,,n,
j=1,,,n,i X j,k=1,,,m,x ijk I{0,1};(4)
t i,g
i
(1)\0,i=1,,,n。(5)其中:g i(k)表示工件i第k道工序的加工设备号;a 为非常大的正数;x ijk为二进制变量，表示设备k上工件i和工件j的加工顺序，当设备k上工件i在工件j之前加工时,x ij k=1，否则x ijk=0。式(1)为调度目标函数M akespan；式(2)表示相同工件各工序之间的先后顺序约束，保证同一时刻每个工件只能在一台设备上加工；式(3)和式(4)表示同一设备上不同工件之间的加工顺序约束，保证同一时刻每台设备最多只能加工一个工件；式(5)表示各工件到达后可以开始加工。
2基于瓶颈工序分解的调度策略及算法实现自上世纪80年代TOC[13]提出以来,/瓶颈0引起了大批研究者的重视，其核心思想是/瓶颈设备主导着整个生产系统的性能0，因此通过识别生产线的瓶颈设备，抓住生产链条中最关键的环节，将瓶颈机与非瓶颈机进行分解调度，并且瓶颈机主导非瓶颈机调度，不仅可以降低大规模JSP的复杂度，还可以取得比较满意的解。
211基于瓶颈工序分解的调度策略
本文提出基于瓶颈工序分解的调度策略，即对作业车间的设备分解为瓶颈机和非瓶颈机后，进一步将调度问题中的所有工序划分为瓶颈工序集(Bottleneck Oper ations,BN-OS)、上游非瓶颈工序集(Preceding Bottleneck Operations,PBN-OS)以及下游非瓶颈工序集(Fo llow ing Bottleneck Opera-tions,FBN-OS)。其中:¹BN-OS指瓶颈设备上各工件的待加工工序的集合;ºPBN-OS指各瓶颈工序的所有前序工序的集合;»FBN-OS指各瓶颈工序的所有后继工序的集合。
相应地，原调度问题分解为三个子问题，即BN-OS调度、PBN-OS调度和FBN-OS调度，对应模型为(P b),(P p),(P f)。
(1)(P b)BN-OS调度模型(1|r i,b,p i,b|C max)。
min m ax
1[i[n
{t i,b+p i,b}。(6) s.t.t i,b\r i,b,i=1,,,n;(7) t j,b-t i,b+a(1-x ij k)\p i,b,
i=1,,,n,j=1,,,n,i X j,x ij k I{0,1};(8)
827
计算机集成制造系统第17卷
t i,b-t j,b+ax ijk\p j,b,
i=1,,,n,j=1,,,n,i X j,x ijk I{0,1}。(9)
其中:r i,b表示工件i到达瓶颈设备b的时间；式(6)
表示BN-OS调度目标，即所有工件的最大完工时间
最小；式(7)表示各瓶颈工序的开工时间必须大于对
应工件到达瓶颈机的时间；式(8)和式(9)表示瓶颈
设备上各工件的加工顺序约束。
(2)(P p)PBN-OS调度模型(J m-1|d i,p i,j
|E n i=1T i)。
min{E n i=1max{C i-d i,0}}。(10)
i
(b)-1+p i,s i(b)-1,i=1,,,n;(11)
d i=t i,b,i=1,,,n;(12)
t i,g
i
(k+1)-t i,g i(k)\p i,g i(k),i=1,,,n,
k=1,,,s i(b)-1,g i(k+1)X b,g i(k)X b;(13)
t j,k-t i,k+a(1-x ijk)\p i,k,i=1,,,n,
j=1,,,n,i X j,k=1,,,m,
玩具滑翔机制作
k X b,x ijk I{0,1};(14)
t i,k-t j,k+ax ij k\p j,k,i=1,,,n,
j=1,,,n,i X j,k=1,,,m,
k X b;x ijk I{0,1};(15)
t i,g
i
(1)\0,i=1,,,n。(16)
其中:s i(b)表示工件i在瓶颈设备b上的加工工序
号；式(10)表示PBN-OS调度目标函数)))各工件
拖期时间之和最小，从而最大程度地保证BN-OS的
调度方案；式(11)表示PBN-OS中各工件的完工时
间；式(12)表示PBN-OS中各工件的交货期，即瓶
颈设备上各工件的开工时间；式(13)表示同一工件
的上游非瓶颈工序的工艺顺序约束；式(14)和式
(15)表示各非瓶颈设备上工件之间的加工顺序约
束；式(16)表示各工件必须到达后才能开始加工。
(3)(P f)FBN-OS调度模型(J m-1|r i,p i,j|
C max)。
m in max
1[i[n {t i,g
i
(m)+p i,g i(m)}。(17)
< i,g
i
(k+1)-t i,g i(k)\p i,g i(k),i=1,,,n,
k=s i(b)+1,,,m,g i(k+1)X b,g i(k)X b;
(18)
t j,k-t i,k+a(1-x ijk)\p i,k,i=1,,,n,
太阳能炉灶j=1,,,n,i X j,k=1,,,m,
k X b,x ijk I{0,1};(19) t i,k-t j,k+ax ijk\p j,k,i=1,,,n,j=1,,,n,
i X j,k=1,,,m,k X b,x ijk I{0,1};(20)
t i,s
i
(b)+1\r i=t i,b+p i,b,i=1,,,n;(21)
r i=t i,b+p i,b,i=1,,,n;(22)其中：式(17)表示FBN-OS调度目标函数，即所有工件最大完工时间最小；式(18)表示同一工件的下游非瓶颈工序的工艺顺序约束；式(19)和式(20)表示各非瓶颈设备上工件之间的加工顺序约束；式(21)表示各工件必须到达后才能开始加工；式(22)表示各工件的到达时间为其对应瓶颈工序的完工时间。
由各子问题对应模型可以看出，原调度问题基于瓶颈工序分解后，转化为一个简单的单机调度问题和两个小规模的调度子问题。各子问题的待调度机器数小于原问题，同时各子问题的待调度工序数远小于原问题的待调度工序数，因此得到了原问题的调度规模。
212基于瓶颈工序分解调度方法的复杂度分析由调度模型(P)可知，原调度问题(J m+C max)在未分解之前，其决策变量和约束个数都为m#n2。经过瓶颈工序分解后，原问题被分解为一个瓶颈机器单机调度问题(1+C max)和两个非瓶颈工序集调度问题(J m-1+C max)。其中，瓶颈机调度问题是简单的单机调度问题，其决策变量和约束个数仅为n2，可以通过精确算法或启发式算法快速得到最优解；上游非瓶颈工序调度问题的决策变量及约束个数为(m-1)#x2,1[x[n-1,x为上游非瓶颈工序的个数；下游非瓶颈工序调度问题的决策变量及约束的个数为(m-1)#(n-1-x)2。由于(m-1) #(n-1-x)2+(m-1)#x2+n2<m#n2,1[x[n -1，原调度问题经瓶颈工序分解后，调度复杂度明显降低。与此同时，一些在
小规模JSP中应用较好的算法便可以应用到两个非瓶颈机调度子问题中，从而可以在最优化瓶颈机的基础上，进一步深入优化非瓶颈机的调度方案，得到具有更佳调度性能的调度方案。
213基于瓶颈工序分解的调度框架
根据TOC，瓶颈设备主导着生产线的性能，因此本文提出的基于瓶颈工序分解算法，也遵循瓶颈机主导非瓶颈机的原则进行调度，非瓶颈机调度最大程度地满足瓶颈机调度方案。也就是说在调度方案生成过程中,BN-OS优先调度;PBN-OS以BN-OS各工序开工时间为交货期，最大程度地满足BN-OS的调度方案，如果无法满足BN-OS调度方案，则进行冲突协调直至调度方案可行;FBN-OS紧密衔接BN-OS调度方案，以BN-OS各工序完工时间
828
第4期翟颖妮等：大规模作业车间的瓶颈分解调度算法
为到达时间进行调度;FBN -OS 调度完成后，由PBN -OS 调度方案、BN -OS 调度方案、FBN -OS 调度方案组合成原调度问题的最终调度方案。图1所
示为基于瓶颈工序分解的调度框架。
214 基于瓶颈工序分解的调度算法
(1)瓶颈识别方法的选择
在瓶颈工序分解调度框架中，正确识别瓶颈是首要任务。瓶颈识别的正确性直接决定了后续工序集分解的正确性，进而影响最终调度方案的有效性。
木材旋切机
传统的瓶颈分解算法简单地以负荷最大的设备作为瓶颈机，而负荷最大的设备未必就是对调度性能影响最大的设备，因此以负荷最大的设备主导其他设备进行调度，不能保证整个调度性能的优化性。文献[14]针对作业车间提出一种基于正交试验的瓶颈识别方法，该方法以生产系统的作业目标为立足点，从调度的角度识别其中的关键设备。因此本文采用该方法进行瓶颈设备的识别和瓶颈工序的分解，能够从生产调度本身出发，抓住最影响调度性能的关键设备，从而在/瓶颈机主导非瓶颈机调度0的原则下获得比较理想的解。
(2)冲突消解策略的实现
因为瓶颈机上各工序并非各工件的首道工序，所以优先调度瓶颈机，必然会产生后续PBN -OS 调度方案与BN -OS 调度方案之间的冲突，并产生时间轴上的迭代。为解决该问题，本文提出如下冲突消解策略:
1)瓶颈机首次调度时，合理计算其上各工件的到达时间：松弛瓶颈机的能力约束以及FBN -OS 的资源竞争，采用多种分派规则对PBN -OS 进行调度，以各工件完工时间的均值作为瓶颈工序的到达时间。如此生成的瓶颈机上各工件的到达时间相对合理，在PBN -OS 调度过程中，各工件的交货期较为紧凑又不过分紧张，从而减少了PBN -OS 调度方案与BN -OS 调度方案在时间轴上迭代的程度和冲
突协调次数。
2)瓶颈机二次调度。PBN -OS 调度完成后，如果BN -OS 调度方案与PBN -OS 调度方案之间产生了冲突，则调整各瓶颈工序的到达时间为PBN -OS 调度方案中各工件的完工时间，重新进行瓶颈机调度，从而消解冲突。
(3)非瓶颈机调度算法的选择
本文选择在小规模JSP 中应用效果较好的遗传算法来进行非瓶颈机调度问题的求解，保证瓶颈工序分解调度算法在最优化瓶颈机的同时，对非瓶颈机也进行深入调度优化，从而让非瓶颈机最大程度地满足瓶颈机调度方案，减少两者的冲突程度和
协调次数，提高最终解的求解质量。
(4)基于瓶颈工序分解调度算法的具体步骤步骤1 识别作业车间生产线的瓶颈设备，按
照211节的瓶颈分解策略，将原调度问题的所有工序分解为BN -OS,PBN -OS,FBN -OS 。
步骤2 优先进行BN -OS 调度。由于BN -OS 调度仅涉及瓶颈设备，对应模型(P b )为单机调度模型，根据文献[1]，最短加工时间优先(Shortest Processing Time first,SPT)对于1+C max 调度问题是最优的，因此本文采用SPT 规则进行瓶颈机调度。
步骤3 建立PBN -OS 调度模型(P p )并求解。瓶颈机调度完成后，由于上游非瓶颈工序必须满足瓶颈工序的调度方案,PBN -OS 调度就转化为以瓶颈工序的开工时间为交货期、延迟最小的J m -1|d i ,p i,j |
E n
i=1T
i
调度问题，对应模型为(P p )。对于(P p )，本文
采用基于工序编码的自适应遗传算法进行求解。
步骤4 按照本文提出的冲突消解策略，协调BN -OS 与PBN -OS 的调度结果，直至冲突完全消解。
步骤5 建立FBN -OS 调度模型(P f )并求解。根据瓶颈设备主导非瓶颈设备调度的原则,BN -OS 各瓶颈工序的完工时间决定了FBN -OS 各工件的到达时间,FBN -OS 调度转化为有到达时间约束的J m -1|r i ,p i,j |C max 调度问题，对应模型为(P f )。对于调度模型(P f )，本文亦采用基于工序编码的自适应遗传算法进行求解。由于FBN -OS 处于BN -OS 的下游,FBN -OS 的调度结果不会对PBN -OS,BN -OS 的调度结果产生影响。
步骤6 由PBN -OS,BN -OS,FBN -OS 组合生成原调度问题的解。
829
计算机集成制造系统第17卷3仿真算例
311测试问题及算法参数
为测试基于瓶颈工序分解调度算法(Genetic
Algo rithm based on Bottleneck-operations Decom-
position,BD-GA)的性能，本文采用文献[12]的方
式随机生成大量的大规模JSP测试数据。其中，各
工件的工艺路线为m台设备的随机排列；各工序的
加工时间服从U[1,99]的均匀分布，且为正整数；所
有工件都在0时刻到达车间。本文将BD-GA与文
献[12]提出的基于混合编码机制的遗传算法(Ge-
netic A lgor ithm based on m ix ed encoding schem e
of scheduling rules plus Operatio n Sequences,OS-
GA)、文献[11]提出的单瓶颈启发式算法(Mo dified
Bottleneck-based heur istic,M B)进行对比，以分析
BD-GA的求解质量及计算效率。
BD-GA,OS-GA根据文献[15]设置遗传算法
参数，其中交叉概率p c=019、变异概率p m=011、种
规模p op siz e=50、进化代数GN=200、迭代终止
条件GN_ex it=20(若最优解在20代内不发生变
化，则算法停止，输出最优解)。同时考虑遗传算法
的随机性，各算法对各算例分别进行了20次运算,
取各次最优解及运行时间的均值作为相应算法的最
终解和平均运行时间。
312计算结果比较与分析
在不同规模算例下,M B,OS-GA,BD-GA的计
算结果如表1所示。图2给出了三种算法求解质量
的性能分析图。
表1大规模JSP不同调度算法的性能
序号
规模
(n@m)
M B OS-GA BD-GA
最终解最终解时间最终解时间
130@10243620261652121012031110126154 230@15265022601252111602241105167130 330@20295225021102761622398180280164 450@10352431831653391633218130293191 550@15380732891004811763296150149193 650@20457537401124071273583180247197 780@10518845711458551824575165266127 880@15580149991159631944907140506156 980@206419515616014181354969105644152 10100@10644157051107721105684180334185 11100@1568396030100131514516363155564158 12100@207241622513516701355987125792169
由表1和图2可以看出，对于所有算例,BD-GA和OS-GA的求解质量均优于M B，原因可能有两个方面:¹M B在瓶颈机调度时完全松弛了非瓶颈机的能力约束，造成非瓶颈机调度方案与瓶颈机调度方案之间的激烈冲突；同时MB采用迭代循环的冲突协调方法，每步迭代都要推后瓶颈机相应工件的开工时间，造成最终解的逐步退化。ºMB仅对瓶颈机进行最优化调度，对非瓶颈机采用简单的分派规则进行调度，而基于规则的调度仅能快速给出调度问题的可行解，并不能保证解的优化性，因此M B算法的求解质量不如另外两种算法。由此可知，生产系统整体的调度性能不仅取决于瓶颈机调度的最优性，而且非瓶颈机调度的优化性同样会影响整个调度方案的性能。
对于各算例的计算效率，由于M B的计算时间很短，大大优于其他两种算法，本文仅比较BD-GA 和OS-GA的计算效率。图3给出了两种算法对各算例的计算效率的比较。
由表1和图3可以看出，对于各算例,BD-GA 的计算效率优于OS-GA，并且算例规模增大越多，两者的差异越大。这是因为BD-GA是基于瓶颈设
830
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议