机械设计与制造
68Machinery Design&Manufacture
第5期2021年5月
大规模柔性作业车间调度问题分解建模和求解方法
刘海涛1，邓停铭2，唐健均1，尹慢2
（1.航空工业成都飞机工业（集团）有限责任公司，四川成都610000；2.西南交通大学机械工程学院，四川成都610000）
摘要：研究在满足既定工序顺序约束的情况下，按序组合工序来分解柔性作业车间大规模调度问题，建立分解调度问题的数学模型，并探索高效求解的方法。首先基于工序组合与遗传算法，将大规模调度问题进行分解降低问题空间复杂度，形成调度子问题，并建立分解后的调度数学模型；其次将利用组合规则生成高质量的初始解，采用遗传算法与蛙跳算法相结合的混合算法，采用双线程进行并行计算求解，提高全局搜索能力和效率，重组后形成原问题的可行解；最后利用实例证实了模型和算法的可行性。
关键词：柔性作业车间调度问题；数学模型；混合算法；并行运算
中图分类号:TH16；TH165文献标识码:A文章编号：1001-3997(2021)05-0068-04
Decomposition Modeling and Solving Method for Large
Scale Flexible Job Shop Scheduling Problem
LIU 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 l
eapfrog 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 Computation
1引言
作业车间调度属于NP难题，半个多世纪以来一直是学术界的焦点。对于机床x工件=20x50以内的中小规模“碉度问题，目前采用启发式算法|2］可以获取较好的结果；超岀此规模，即当工件〉50，工件x机器＞1000时|3］，便成为大规模作业车间调度问题，这种问题往往过于复杂，求解的时间会急速恶化|4］。对此进行了实验，当规模达到4000时，在MATLAB环境下采用遗传算法和一台2.8GHz处理器、8GB内存的计算机上寻优,9h后才获得优化近似解。
为解决这类问题，众多学者采用了对问题进行分解的方法，按照一定的策略获取子问题并分别求解，再根据各问题之间的关系重构大规模调度问题的可行解。文献|5］将滚动时域混合瓶颈及分解策略，利用时空两个维度进行大规模调度问题的分解。文献|6］将调度问题中约束和目标函数进行叠加处理后，大规模调度数学模型即转变成若干个分解问题。文献|7将大邻域搜索融合自适应随机方法，并基于一定的
规则策略来分解大规模柔性作业车间调度问题。文献|8根据工艺相似性进行动态相似度编码，并改进编码规则提高优化求解效率。文献|9利J用模拟退火搜索总拖延期最小的工序集分解方案，并采用粒子算法求解各调度子问题，最后重组问题获取总调度问题的可行解。文献|10提岀根据交付期分解问题，并采用混合移动瓶颈、模拟退火和可变邻域搜索方法求解大规模问题，求解精度较高，但是时间较长。
来稿日期:2020-07-10
基金项目:2017年四川省智能制造新模式工程项目一飞机移动式总装智能生产线
作者简介：刘海涛,（1983-），男，陕西人，本科，高级工程师，主要研究方向：飞机总装技术
第5期刘海涛等：大规模柔性作业车间调度问题分解建模和求解方法69
基于上述研究，提岀一种简单可行的按序组合工序集以进行大规模调度问题的分解方法，针对分解后的问题进行描述的基础上建立大规模调度分解问题的数学模型，最后采用初始解生成策略、遗传算法与蛙跳算法结合、双线程等一系列改进算法和策略对问题进行求解，以高效高精度地得到最优解。
2基于工序组合分解大规模调度问题2.1工序按序随机组合分解方法
对于某柔性作业，假设工件数为3，各工件加工工序数也为3，但可在不同的机床上完成工序加工，析取
图，如图1所示。图中工件按照既定的顺序加工，工序顺序采用实线表示,0”、0；2、0；3是工件i的第1、2、3道工序。工序能够于同一机床上加工用虚线连接起来，例如在机床1上可以加工011、。21、。32工序，在机床2上可以加工013、022、。31工序，在机床3上可以加工O12.O23.O33工序。原调度问题按照图1析取图工序顺序进行组合，如将工序O11、O12、O21、O22、O31组合形成阶段1子问题，同时将工序O13、O23、O32.O33组合形成阶段2子问题。其中先完成的工序所处阶段不晚
连接弧非连接弧子问题
图 1析取图
Fig.1The Disjunctive Graph
2.2基于双段整数编码遗传算法的子问题分解
将最大完工时间作为优化目标，采用GA算法对子问题分解进行优化，如图2所示。子问题分解采用整数编码方式，图1中将原调度问题分解为2个子问题，而图2是其编码方式,2段基因代表了2个子调度问题的工序集，第一段为首个子问题包含的每个工件按序排列的工序数，第二段表示第2个子问题包含的每个工件按序排列的工序数。同基因段中，每个基因位置号表示工件类别号，数字则代表着该工件在此子问题中按序排列的工序数。
Sub I基因段Sub II基因段
图2分解整数编码示意图
Fig.2The Decompose Inter Coding Schematic
2.3大规模柔性作业车间调度分解问题描述
大规模柔性作业车间调度问题是指m台机床(M=[M k\M1,M2，…,M m,k=1,2,…,m)上加工n类工件(J={/|/,,2，…,= 1,2，…,m|)，第i类工件包含N道确定加工顺序的工序，且可选不同机床加工，包含R个工件，第i类工件的第j道工序在机床k 上加工时间为j,T表示第i类工件最后一道工序的完工时间，此调度问题基于工序按序随机组合后自然分解成为Q(Q={Q q Q1,Q2…Q q,q=1,2，…,Q)个子问题，以最大完工时间最小并采用并行计算对各子问题进行调度重组后形成原调度问题的可行解。
2.4大规模柔性作业车间调度分解问题数学模型
这里的数学模型建立在以下假设基础上：各子问题中工件工序和机床在零时刻可用；同一时刻同一机床只加工一个工件；工件的某道工序只能在同一台机床上加工；一旦工序开始加工直到完工才能被终止。
本数学模型的目标函数为最大完工时间最小：
(1)原问题目标函数为最大完工时间最小
f=min(maxT;), i=1,2，…n(1)
⑵第q个子问题目标函数为第q子问题最大完工时间最小
f q=min(maxT qi),q=1,2,.“Q,i=1,2,.“n(2)式中:T q—第q个子问题中第i类工件的最后一道工序完工时间。
同时满足以下约束条件：
(1)第i类工件的第j道工序在机床k上加工时间等于本类工件加工时间之和。
T k=移％Y jk R jk,j=1，2,…N z，k=1,2，—m(3) i=1
式中：Y j*=(0,1)—第i类工件第j工序选择k机床的决策变量，在机床j上加工为1，否则为0;
(2)第i类工件的第j道工序同一时刻只能在一台机床上加工:
移X jjk=1,i=1,2,—n,j=1,2,—N i(4)
k=1
(3)第i类工件的j工序只能分配到一个子问题中：
Q
移血=出,i=1,2,…n,j=1,2,…N：(5)
q=1
(4)各子问题包含工件i的工序之和等于第i件工件工序总数:
Q
移號=R i N i(6)
q=】
(5)第q个子问题包含的工序数：
蓘],q=1,2,…Q-1
S"=缮”Q q-1(7)移U-移H q,q=Q
式中:[]—取整数；
(6)各问题包含的工序个数总和等于所有各类工件的工序个数之和：
Q”
移S q=移R i N(8)
q=1i=1
(7)子问题中同一类工件后一道工序的开工时间ST”.不晚于前道工序的完工时间ET”"：
ETn燮S j i=1,2,…N,k=1,2,…n(9
)
No.5
May.2021 70机械设计与制造
3改进遗传算法
遗传算法具有好的全局寻优能力、鲁棒性、操作简单等特点，特别适应于典型的NP-Hard诸如车间调度问题，一直是研究热点。但是也存在受初始解集影响大、过早收敛陷入局部最优解、计算效率低等缺陷，为此，提岀一系列改进策略，以提高求解精度和求解效率。
3.1改进策略
3.1.1提高初始种个体质量和多样化的策略
对于遗传算法，初始解在空间分布越均匀，则越容易到最优解。为了提高初始种的质量，并保证其多样性，可利用不同的组合策略，产生一部分初始种|11-12]，来提高解的搜索精度。按照以下4种组合策略生成50%初始种：(1)剩余最大工序数与工序最短加工时间的策略;(2)剩余最长加工时间与工序最短加工时间的策略;(3)全局最短处理时间与剩余最大工序数的策略；
(4)全局最短时间与工件最长剩余加工时间的策略。种初始化过程中，另外50%初始种则随机生成。
3.1.2全局搜索能力的改进策略
遗传交叉在实现的时候，比起蛙跳算法参数多、结构复杂，但精度高。为了更快的实现交叉和个体更新，结合两种算法的优点,50%的个体用蛙跳局部搜索策略，以缩短遗传算法计算时间, 50%的个体仍然采用GA双点交叉策略。这种个体更新方式，在保证寻优的精度的同时，提高了遗传算法的运算效率。
混沌随机数生成策略具有非线性系统的特征，与随机乱数不同，是有界随机数的一种生成方式，对初始情况存在高敏感性|13]。将混沌策略融入到算法的交叉过程中，使种在混沌空间与稳定空间交替过程中更易于跳岀局部最优解，有效地避免算法过早收敛，提高全局搜索能力。按照强混沌映射|14]，产生
混沌随机数，第t 代混沌随机数变量，如式(10)所示。
ChaosticNum(t)=K*ChaosticNum(t-l)*
(1-ChaosticNum(t-1))(10)式中:K—系统分岔参数。
遗传算法的双点交叉方式，是在选择的两个染体上，随机选岀两段基因位置，并将交换这两个基因片段，产生的两个新个体一般会存在多余的基因以及部分缺失的基因，因此需要使基因合格化；蛙跳算法在局部更新时将50%的种个体自动分成Y个子，每个子内有y个个体，首先利用各个子的最优个体Pl更新子中的最差个体Pw，并形成新个体Pw，，如式(11)所示。
Pw'=Pw+ChaosticNum()*(Pl-Pw)(11)其次若形成的新个体Pw'劣于Pw，则利用式(12)更新Pw;
Pw'=Pw+ChaosticNum()*(Pg-Pw)(12)若形成的新个体Pw'仍然劣于Pw侧以一定概率接受差解Pw';
3.1.3双线程并行计算子问题
MATLAB针对循环次数过多、数值阵列数据过大和消息传递过多等情况提供并行处理结构，该结构能处理数据实现并行算法。采用MATLAB工具箱中Spmd并行结构进行多线程并行计算，以缩减大规模调度问题的求解时间。在计算的过程中，由于使用双核计算机，可设置2个线程进行子问题的并行运算。3.2改进遗传算法流程及步骤
采用融合了初始解集产生策略、混沌策略、蛙跳算法的改进遗传算法，其流程图，如图3所示。首先设置初始参数，包括确定种规模、子问题个数、子问题工序数、代沟、交叉率、变异率和最大迭代次数。其次采用两层整数编码方式，首层为工序排序基因层，后面一层为工序选择机床基因层，进行种初始化。然后计算种内各个个体的适应度值选岀全局最优个体，判断是否满足终止条件，是则结束，否则采用赌的方式，从种中选择适应度较高的个体；采用双点交叉和蛙跳算法结合的策略更新个体，当变异概率大于算法参数设置的变异算子时，机床基因发生变异，产生新种，重新计算适应度并选择个体。依次循环直到优化过程达到终止条件时，得到最优解。
开始
图3基于蛙跳算法的改进遗传算法流程图
Fig.3The Improved Genetic Algorithm Flow
Based on Leapfrog Algorithm
4实例验证
4.1应用实例与实验
表1基于工序组合分解调度与传统调度方法对比表
Tab.1The Comparison Table Base on Process
Combination Decomposition Scheduling
and Traditional Scheduling Method
规模工序组合传统调度(1)与(2)组批调度(1)与(3)
规模调度(1)(2)比较(3)比较
工件数最大收敛最大
x机床完工时敛完工
数x序时间时间时间
数(min)(s)(min)
460x
18x8
690x
18x8
173
53.2
255
51.0
129.7
191.6
232
22.4
343
58.2
1150x4243389613
18x810.6338.982.2
收敛
时间
(s)
目标
值优
化率
收敛最大
时间完工
建模方法占(2)时间
的(min)
收敛
时间
(s)
目标
值优
化率
收敛
时间
占⑶
的
323
2.9
518
3.2
973
9.0
25.3%4%
195
47.9
461.411.2%28.1%
25.6% 3.7%
30.9% 3.5%
294
69.2
506
11.0
680.713.3%28.1%
119
9.3
16.2%28.3%
针对某航空企业生产的不同典型管类零件进行实验，每类管子加工工艺不同，但是工序数目都为8,
工序加工时间和准备
No.5
May.2021机械设计与制造71时间也不同。实验时工件数x机床数x工序数分别为460x18x8、
690x18x8.1150x18x8等3种大规模。为了进行对比分析，这里采
用传统调度方法即不分解问题直接进行优化计算的方法、按照批
次分解子问题以及提岀的基于工序组合分解子问题的方法，分别
进行了10次计算，取其平均值作为对比依据。实验后数据表，如
表1所示。收敛精度和时间对比，如图4、图5所示。
J0000
60000 50000 40000 30000 20000 10000
・基于工序分解调度
■组批调度
比传统调度
调度规模
X
8X
O
69
x
g
x
o
專
x
g
x
o
e
z
图4各种方法收敛精度对比图
Fig.4The Comparison of Convergence Accuracy of Various Methods
(s)
国fe*
M
图5各种方法收敛时间对比图
Fig.5The Comparison Graph of Convergence Time of Various Methods 4.2实验数据对比分析
(1)收敛精度与收敛时间对比分析
根据图4、图5及表1可见，相对于传统调度，提岀的基于工序组合后再分解子问题的调度方法，在搜索到的优化目标值最大完工时间方面以及运算时间方面都得到大幅度的降低，搜索精度比传统算法提高25%以上，而收敛时间上缩短到仅为传统算法的(3~4)%，大大提高了调度效率。当调度规模不断增加，搜索时间和精度也不断改善，说明提岀的方法寻优能力在超大规模中优势更加显著。同时基于工序组合后分解子问题的调度方法比起一般的组批调度方法，在收敛精度至少提高11%以上，而在缩减计算时间上仅为组批调度的28%左右。
5结论
针对大规模调度问题进行了研究，提岀了一套基于工序再组合的大规模调度问题的分解、建模和求解方法。
(1)提岀基于工序的再组合，将大规模问题分解成复杂度低的子问题可便于求解，并采用双段整数编码遗传算法实现分解。
(2)提岀各个子问题的最大完工时间最小为目标函数，分析各个子问题空间的约束条件，建立大规模调度分解问题的数学模型;
(3)采用蛙跳与遗传算法相结合的改进算法，同时提岀了组合规则下的初始种产生方法、基于混沌数的更新策略、通过MATLAB的Spmd结构实现该算法的双线并行运算等系列改进策略，形成的改进求解算法。
通过实例显示，提岀的改进算法寻优能力比起传统调度算法提高了25%，同时在获取更佳最优解的基础上，收敛速度提高25倍以上，证明提岀方法的可行性和显著优势。
参考文献
[1]Xin-Sheng X U,Fang S L,Xin-Jian G U.Mass customization and variety
[J].Computer Integrated Manufacturing Systems,2007,13(7)：1330—1335.
[2]Zhang J,Ding G F,Zou Y S,Qin S F,&Fu J L.(2017).Review of job sh
op scheduling research and its new perspectives under Industry4.0.
Journal of Intelligent Manufacturing,1-22.
[3]金锋，吴澄.大规模生产调度问题的研究现状与展望[J].计算机集成
制造系统,2006(2)：161-168.
(Jin Feng,Wu Cheng.Research status and prospect of mass production scheduling[J].Computer Integrated Manufacturing System,2006(2)：161-168.)
[4]Garey,Michael R.,David S.Johnson,and Ravi Sethi.The complexity of fl
owshop and jobshop scheduling]J].Mathematics of Operations Research
1.2(1976)：117-129.
[5]左燕.大规模复杂生产调度问题瓶颈分解方法研究[D].上海：上海交
通大学,2007.
(Zuo Yan.Study on bottleneck decomposition method of large-scale complex production scheduling problem[D].Shanghai:Shanghai Jiaotong University，2007.)
[6]Nishi T,Hiranaka Y,Inuiguchi M.Lagrangian relaxation with cut gener
ation for hybrid flowshop schedule problems to minimize the total weighted tardinessJ].Computers&Operations Research,2010,37(1):189—198.
[7]Pacino D,Hentenryck P V.Large neighborhood search and adaptive ran
domized decompositions for flexible jobshop schedule]J].2011.
[8]梁旭，王佳，黄明.解决大规模生产调度问题的一种新编码方法[J].计
算机集成制造系统,2008(10):1974-1977+1982.
(Liang Xu,Wang Jia,Huang Ming.A new coding method to solve mass production scheduling problem[J].Computer Integrated Manufacturing System,2008(10)：19741977+1982.)
[9]Zhang R,Wu C.A divide-and-conquer strategy with particle swarm opt
imization for the job shop schedule problem[J].Engineering Optimizat-ion，2010，42(7).
[10]Sobeyko O,Monch L.Heuristic approaches for schedule jobs in large-
scale flexible job shops[J].Computers&Operations Research,2016
(68)：97-109.
[11]Pezzella F,Morganti G,Ciaschetti G.A genetic algorithm for the flexi
ble job-shop schedule problem[J].Computers&Operations Research, 2008,35(10)：3202-3212.
[12]Li J,Pan Q,Chen J.A hybrid Pareto-based local search algorithm for
multi-objective flexible job shop schedule problems[J].2012,50(4)：1063-1078.
[13]刘金梅，屈强.几类混沌序列的随机性测试J].计算机工程与应用,
2011,47(5)：46-49.
(Liu Jin-mei,Qu Qiang.Random test of several chaotic sequences[J].
Computer Engineering and Applications,2011,47(5):46-49.)
14More secure chaotic cryptographic scheme based on the dynamic lookup table J].Circuits,Systems&Signal Processing,2005,24(5)：
571-58.
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论