摘要： 从钢铁行业的炼钢—连铸—热轧过程提炼出中间阶段有多台批处理机，其它阶段为离散机的多阶段柔性流水车间调度问题.首先，结合工件动态到达、各阶段间的运输时间以及机器的调整时间等生产特征，对问题进行描述，建立以最小化总加权完成时间为目标的数学模型.然后，针对该问题提出了改进的自适应遗传算法,使遗传参数随其迭代及适应函数值调节.对150个工件的大量随机数据进行测试，结果表明，与常规遗传算法相比，所提出的自适应遗传算法能在较短的计算时间内得到更好的解；与拉格朗日松弛算法相比，求解大规模问题时，所提算法在解的质量方面优势较为明显.
关键词： 柔性流水车间调度；批处理机；总加权完成时间；自适应遗传算法；自适应调节
在钢铁行业，炼钢、连铸、热轧作为炼钢的主要工序，在整个流程中起着重要作用.在炼钢—连铸—热轧过程中，转炉生产出来的钢水经过精炼炉精炼后，要铸造成不同类型、不同规格的板坯；将装有钢水的钢包运至回转台，回转台转动到浇铸位置后，钢水被注入中间包，钢水分配到各个结晶器中结晶成各种铸件，之后铸件经过切割机的连续切割成为板坯[1].使用同一中间包的多个炉次(称为一个浇次)要按一定顺序连续生产.进而，板坯由保温车运送到加热炉进行加热，直至达到热轧加工的温度要求，然后，先由高压水枪祛除板坯表面的氧化鳞片，再经定宽压力机对板坯进行侧压以调整其宽度，并依次通过粗轧机进行多道次可逆轧制[2-3].
上述生产过程中，各阶段由多台同构并行机组成，并且在连铸阶段一个浇次内的所有炉次都要在同一台连铸机上进行无间断的加工，因此该结构可看作是中间阶段具有串行批处理机的柔性流水车间.考虑到钢铁生产中各个加工阶段的运输时间、机器的调整时间以及工件的释放时间，提出笔者所研究的多阶段柔性流水车间问题(flexible flowshop scheduling problem, FFSP).
对于两机流水车间批调度，文献[4]提出了一种分解启发式算法用来求解工件的总加权拖期费用；文献[5]提出以最小化加工时间跨度为目标的蚁群优化算法；文献[6]以最小化完工期makespan为目标，考虑工件动态到达，构建了一种最优化算法以求解各批次加工时间为定值的流水车间批调度问题；文献[7]针对差异工件批处理机调度，设计了一种基于LPT规则和批调度近似规则的算法用以最小化制造跨度和总完工时间.
就FFSP的串行批问题，文献[8]研究了任意一个阶段有串行批处理机且其它阶段为离散机的多阶段FFSP，提出了改进的拉格朗日松弛(Lagrangian relaxation, LR)算法，目标为总加权完成时间最小.就FFSP的并行批问题，文献[9]提出了一个新的遗传算法(genetic algorithm, GA)最小化makespan；文献[10]利用启发式搜索GA求解一个阶段含并行批处理机的情况，目标分别为最小化makespan及最小化总加权拖期费用.
从上述研究现状可知，对于两机流水车间问题，多采用一些启发式算法或最优化算法来求解最大完工时间最小化问题；针对含串行批的FFSP，多采用LR算法最小化总加权完成时间；针对含并行批的FFSP，则多采用启发式、GA等最小化makespan.针对具有串行批处理机的FFSP，GA求解总加权完成时间问题的研究较少.
在GA中，pc和pm等遗传参数常固定不变，因此，Srinivas等[11]首先提出了用AGA来求解多目标函数优化问题.后来也有一些学者[12-15]对AGA在车间调度中的应用进行了研究，文献[12]对流水车间问题进行建模，采用AGA仿真求解出最优调度方案；文献[13]为了解决置换流水车间调度问题，提出了基于模拟退火算法的多种群和自适应遗传算法；文献[14-15]均利用AGA求解了FFSP，目标为最小化makespan.
综上可知，针对参数自适应的研究多集中在流水车间和FFSP上，目标多为最小化makespan.由于笔者所研究的多阶段FFSP考虑了批生产方式和批生产阶段机器的调整时间、工件动态到达以及阶段间运输时间，是一个较为复杂的NP-hard问题，因此，需要合理地设计GA以提高其求解能力.故而，笔者提出遗传参数自适应调节策略改进遗传算法(improved adaptive genetic algorithm, IAGA)，旨在扩展GA对该类问题的求解能力.
中间阶段为批处理机的多阶段FFSP可描述为：n个工件依次经过s个加工阶段进行加工，当经过某阶段k(1<k<s)时，同一批内的工件按照已知的优先级顺序在一台机器上进行不间断的加工.至少一个阶段有两台或两台以上的同构并行机.第l批内包含的工件数Bl已知，工件只有结束前一阶段的加工才能进入下一阶段.假设工件动态到达第一阶段，阶段间的运输时间和批生产阶段机器的调整时间不可忽略，目标是使整个流程的总加权完成时间最小化.
定义一些基本符号及决策变量，如表1所示.定义参数如表2所示.
根据以上描述及符号定义，将所研究的多阶段FFSP建立为整数线性规划模型.由于实际生产中需要节省整个流程的时间，提高加工效率，所以将目标设为：
(1)
满足以下约束：
表1 基本符号及决策变量
Tab.1 The basic notation and decision variables
i工件,i∈I={1,2,…,n}k阶段,k∈K={1,2,…,s}j时间单位,j∈J={1,2,…,T},T为完成时间的上界b批,b∈l={1,2,…,B},B为总批数f批内工件,f∈Ib(第b批内的工件集)Xki工件i在阶段k的完成时间Ukij0～1变量,表示在时刻j工件i是否在阶段k上进行加工
表2 参数
Tab.2 The parameters
wi工件i的权重Pki工件i在阶段k的加工时间ri工件i的释放时间Lb第b批工件的数量Nbf第b批的第f个工件Mk阶段k可用于加工的机器数Tk,k+1工件由阶段k到k+1的运输时间x有批生产要求的阶段,1
Xki+Tk,k+1+Pk+1,i≤Xk+1,i， ∀i,k;
(2)
X1i-P1i+1≥ri， ∀i;
(3)
Xx,Nbf+Px,Nb,f+1=Xx,Nb,f+1, ∀b,f;
(4)
∀k,j;
(5)
∀i,k.
(6)
约束(2)表示工件只有在完成前一阶段的加工且被运送到下一阶段，才能开始它的加工；约束(3)定义了工件动态到达第一阶段；约束(4)表示在批生产阶段同一批内的工件在一台机器上连续地进行加工；约束(5)确保在同一时刻进行加工的工件数不能超过该时刻可用的机器数；约束(6)表示工件占用机器的时间区间.
步骤1种群初始化.对种群进行初始化，设置种群规模Popsize=100，遗传代数G=200.采用实数编码方式，用随机产生的正整数对工件依次进行编号，初始阶段每个工件都有一个释放时间，先到达先加工，同时到达按照编号顺序加工.
步骤2选择.采用轮盘赌选择方式，首先对种群内个体的适应度函数值进行评价,令适应值函数f(i)为总加权完成时间的倒数.f(i)越大，说明经函数优化后的个体对应的解越好，从而保留此个体.
步骤3交叉.采用两点交叉方式.因种群的更新效率是由交叉算子pc决定的，若pc过大，则优秀个体被破坏的可能性会增加；反之，则会使算法搜索能力变差.所以动态设置pc，即可以持续优化种群，又能保留优秀个体.在Srinivas等[11]的研究基础上，令
(7)
式中：g为当前迭代数；G为总迭代数.设置pc如下：
(8)
式中：pcmin、pcmax分别为进行交叉操作的最小和最大概率，令pcmin=0.5；f max为当前种群内所有个体最大的适应值；fi为个体的适应值；
为当前种群内所有个体的平均适应值.
步骤4变异.采用单点变异方式.虽然GA具有全局搜索能力，但也可能陷入局部收敛.有效设计遗传算子pm，可以增加算法搜索的广度和深度.将个体进行变异操作的实际概率pm设置如下[11]：
(9)
(10)
式中：pmmin和pmmax分别为进行变异操作的最小和最大概率，令pmmax=0.05.
本节分别对GA和IAGA进行相应设计，并与LR算法进行对比，在Matlab上测试其性能，这3种算法均在Celeron(R)Dual-Core CPU 2.10 GHz微机上运行.公平起见，将IAGA进行200次迭代所需时间作为停止条件，设置最大运行时间为1 000 s.当工件规模n={30, 60, 90}时，对3种算法的目标值(min Z)和迭代次数(ItN)进行比较；而当n={120, 150}时，由于LR运行一次迭代所需的计算时间较长致使在较短的计算时间内运行的迭代次数较少，解的质量也较差，随着问题规模增大这种情况也更明显，因此未再测试LR求解这2种工件规模的情况，仅对IAGA和GA的结果进行了比较.
令GA的交叉概率为0.8，变异概率为0.05.针对每种工件规模的{n, s, Mk}组合随机产生10个实例，因此本次试验共测试了300组实例，测试数据随机产生.
(1)工件数n∈{30, 60, 90, 120, 150}；阶段数s∈{3, 4, 5}；机器数Mk∈{3, 4}；
(2)x=2，Lb=5；
(3)工件的权重以及加工时间是满足[1, 10]之间均匀分布的随机数；
(4)工件动态到达第一阶段的时间、各阶段间的运输时间以及批生产阶段所需要的调整时间都是[3, 5]之间均匀分布的随机数.
表3、表4为测试结果.
(1)当工件规模和阶段数不变时，随着可用机器数的增加，3种算法的目标函数值都会相应降低，求解时间也会有所减少.
(2)当n=30时，LR得到的解的质量最好，目标值比IAGA和GA分别改进了10.7%和13.8%.当n=60时，IAGA的优势逐渐显现，目标值相对LR改进了8.3%.当n=90时，IAGA求得的目标值比LR改进了24.0%.由此可得，LR求解小规模问题的效果最好，而IAGA更适合求解贴近实际生产的中大规模问题.
(3)当n={30, 60, 90, 120, 150}时，IAGA所求的目标值相比GA分别改进了2.8%、3.3%、10.4%、12.5%、13.1%.即对于不同规模问题，IAGA求解该问题的能力一致强于GA，且在大规模问题时这种优势更加明显.
(4)在相同的时间内，IAGA的迭代次数多于GA.当n={30, 60, 90, 120, 150}时，IAGA的迭代次数比GA分别多了5、6、8、10、15.因此，随着问题规模增大，两者迭代数的差额也越大，IAGA的效率更高.
表3 规模n={30,60,90}的测试结果对比
Tab.3 Testing results of n={30, 60, 90}
nMisminZItNIAGAGALRIAGAGALRCPU/s3034345345平均6034345345平均9034345345平均98861024483512001961089521011262114871002020019499832301228312471115292001949985264883392967291200196107652079859103738918200193976822410343103501030320019498322601041110703940220019510204232235362443827771200196903902725527814336242001927745830937318033398020019374543230562396422828200195893852649627401271962001937845529753309072899220019373534268382772129065200194804605410863072739642001924590689207537180734200193371275781799158617720019238414112850774590752001934589534435849561023200191370758364608147523420019338395862464740727012001923713
表4 规模n={120,150}的测试结果比对
Tab.4 Testing results of n={120, 150}
nMisminZItNIAGAGAIAGAGACPU/s12034345345平均15034345345平均6986279045200189806800148913620018898589543101897185175100066108757142001907857821483357200188979821769506518617710007765287369195185925109798116102196182100012641114046216014110001453571600471351201000997261105961971821000114261136408164150100013027115706113912210001209701367791651501000
针对钢铁行业的炼钢—连铸—热轧工艺流程，考虑工件的释放时间、运输时间以及机器的调整时间，建立了中间阶段有批处理特征的整数线性规划模型，目标为所有工件的总加权完成时间最小.针对该多阶段FFSP，设计了遗传参数随迭代次数和适应值的改变而进行调节的自适应遗传算法.对各种规模的问题进行仿真试验结果显示，相同时间内，无论何种工件规模，IAGA解的质量均明显优于GA，且IAGA的迭代次数多于GA；与LR算法相比，在求解较大规模工件时，IAGA的性能更好，更符合实际生产对时间的要求.
参考文献：
[1] 汪恭书, 唐立新. 连铸—轧制生产中带有批决策的排序问题的建模与优化方法[J]. 自动化学报, 2012, 38(10): 1713-1720.
[2] 洪悦, 唐立新, 张颜颜. 基于数据子空间PLS建模技术的热轧轧制力优化设定[J]. 控制与决策, 2014, 29(7): 1199-1204.
[3] YU Y S, JIE J C, ZHANG S. Three-layer Al/Al-B4C composite material prepared by casting and hot rolling[J]. Powder metallurgy and metal ceramics, 2015, 54(7/8): 390-396.
[4] TAN Y, MONCH L, FOWLER J W. Proceedings of winter simulation conference[C]. 2015.
[5] 陈成栋, 陈华平, 朱颀,等. 两阶段流水车间批调度问题的蚁群优化算法[J]. 计算机工程, 2012, 38(19): 137-141.
[6] 黄锦钿, 刘建军, 陈庆新,等. 两机flow-shop类型模具热处理车间批调度算法[J]. 计算机集成制造系统, 2014, 20(7): 1665-1674.
[7] 程八一, 胡笑旋. 差异作业批调度的流水车间问题及近似算法[J]. 系统工程学报, 2011, 26(3): 393-399.
[8] XUAN H, LI B. Scheduling dynamic hybrid flowshop with serial batching machines[J].Journal of the operational research society, 2013(64): 825-832.
[9] COSTA A, CAPPADONNA F A, FICHERA S. A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints[J]. International journal of advanced manufacturing technology, 2014, 75(5/8): 833-847.
[10] LI D, MENG X, LIANG Q. A heuristic-search genetic algorithm for multi-stage hybrid flowshop scheduling with single processing machines and batch processing machines[J]. Journal of intelligent manufacturing, 2015(26): 873-890.
[11] SRINIVAS M, PATNAIL K L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE transactions on system, man and cybernetics, 1994, 24(4): 656-667.
[12] XU Y C, TAN W N. The modeling and simulation of flow shop scheduling problem based on adaptive genetic algorithm[J]. RISTI-Revista iberica de sistemas e tecnologias de informacao, 2016(17): 25-40.
[13] SUN H M, YU J W, WANG H L. Proceedings of Chinese intelligent automation conference-intelligent technology and systems[C], 2015.
[14] ZHU H M, ZHAO J F, WANG M L. Adaptive genetic algorithm for Hybrid Flow-Shop scheduling[C]. 3rd international conference on advanced engineering materials and technology, 2013.
[15] ZHAO J F, ZHU X C, WANG B S. Hybrid flow-shop scheduling method and simulation based on adaptive genetic algorithm[C]. Applied mechanics and materials, 2014.
Abstract: Based on steel making-continuous casting - hot rolling production process in iron and steel industry, the problem of scheduling n jobs in a multi-stage flexible flowshop with batching machines at some middle stage was studied. The batching production stage consisted of multiple serial batching machines in parallel, and the other stages contained discrete machines. Firstly, a mathematical model was formulated to minimize the total weighted completion time with the consideration of job dynamic arrival, transportation time between the adjacent stages and machine setup time. Then, an improved adaptive genetic algorithm was developed for this NP-hard problem where the genetic parameters were associated with the iteration number and the fitness function values. Computational experiments tested a large number of random data for up to 150 jobs. The results show that the proposed algorithm could find the better solutions within a shorter period of time, as compared with the general genetic algorithm. The comparison with Lagrangian relaxation showed that the improved genetic algorithm performed better on solution quality for medium and large sized problems.
Key words: flexible flowshop scheduling;batch machines;total weighted completion time;self-adaptive genetic algorithm;self-adaptive adjustment
中图分类号： TB49
文献标志码：A
doi：10.13705/j.issn.1671-6833.2017.05.012
收稿日期:2017-01-16；
修订日期：2017-04-30
基金项目：国家自然科学基金资助项目(U1604150)；教育部人文社会科学研究基金项目(15YJC630148)；郑州大学优秀青年教师发展基金项目(1421326092)
文章编号:1671-6833(2017)05-0086-05