带批处理机的多阶段柔性流水车间调度优化

王君妍, 王薛苑, 轩 华

(郑州大学 管理工程学院，河南 郑州 450001)

带批处理机的多阶段柔性流水车间调度优化

王君妍, 王薛苑, 轩 华

(郑州大学 管理工程学院，河南 郑州 450001)

从钢铁行业的炼钢—连铸—热轧过程提炼出中间阶段有多台批处理机，其它阶段为离散机的多阶段柔性流水车间调度问题.首先，结合工件动态到达、各阶段间的运输时间以及机器的调整时间等生产特征，对问题进行描述，建立以最小化总加权完成时间为目标的数学模型.然后，针对该问题提出了改进的自适应遗传算法,使遗传参数随其迭代及适应函数值调节.对150个工件的大量随机数据进行测试，结果表明，与常规遗传算法相比，所提出的自适应遗传算法能在较短的计算时间内得到更好的解；与拉格朗日松弛算法相比，求解大规模问题时，所提算法在解的质量方面优势较为明显.

柔性流水车间调度；批处理机；总加权完成时间；自适应遗传算法；自适应调节

0 引言

在钢铁行业，炼钢、连铸、热轧作为炼钢的主要工序，在整个流程中起着重要作用.在炼钢—连铸—热轧过程中，转炉生产出来的钢水经过精炼炉精炼后，要铸造成不同类型、不同规格的板坯；将装有钢水的钢包运至回转台，回转台转动到浇铸位置后，钢水被注入中间包，钢水分配到各个结晶器中结晶成各种铸件，之后铸件经过切割机的连续切割成为板坯[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对该类问题的求解能力.

1 问题描述与建模

1.1 问题描述

中间阶段为批处理机的多阶段FFSP可描述为：n个工件依次经过s个加工阶段进行加工，当经过某阶段k(1

1.2 符号

定义一些基本符号及决策变量，如表1所示.定义参数如表2所示.

1.3 数学模型

根据以上描述及符号定义，将所研究的多阶段FFSP建立为整数线性规划模型.由于实际生产中需要节省整个流程的时间，提高加工效率，所以将目标设为：

(1)

满足以下约束：

表1 基本符号及决策变量

表2 参数

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)

(5)

(6)

约束(2)表示工件只有在完成前一阶段的加工且被运送到下一阶段，才能开始它的加工；约束(3)定义了工件动态到达第一阶段；约束(4)表示在批生产阶段同一批内的工件在一台机器上连续地进行加工；约束(5)确保在同一时刻进行加工的工件数不能超过该时刻可用的机器数；约束(6)表示工件占用机器的时间区间.

2 IAGA求解算法设计

步骤1种群初始化.对种群进行初始化，设置种群规模Popsize=100，遗传代数G=200.采用实数编码方式，用随机产生的正整数对工件依次进行编号，初始阶段每个工件都有一个释放时间，先到达先加工，同时到达按照编号顺序加工.

步骤2选择.采用轮盘赌选择方式，首先对种群内个体的适应度函数值进行评价,令适应值函数f(i)为总加权完成时间的倒数.f(i)越大，说明经函数优化后的个体对应的解越好，从而保留此个体.

步骤3交叉.采用两点交叉方式.因种群的更新效率是由交叉算子pc决定的，若pc过大，则优秀个体被破坏的可能性会增加；反之，则会使算法搜索能力变差.所以动态设置pc，即可以持续优化种群，又能保留优秀个体.在Srinivas等[11]的研究基础上，令

(7)

(8)

步骤4变异.采用单点变异方式.虽然GA具有全局搜索能力，但也可能陷入局部收敛.有效设计遗传算子pm，可以增加算法搜索的广度和深度.将个体进行变异操作的实际概率pm设置如下[11]：

(10)

式中：pmmin和pmmax分别为进行变异操作的最小和最大概率，令pmmax=0.05.

3 试验测试

3.1 试验参数设置

本节分别对GA和IAGA进行相应设计，并与LR算法进行对比，在Matlab上测试其性能，这3种算法均在Celeron(R)Dual-Core CPU 2.10 GHz微机上运行.公平起见，将IAGA进行200次迭代所需时间作为停止条件，设置最大运行时间为1 000 s.当工件规模n={30, 60, 90}时，对3种算法的目标值(minZ)和迭代次数(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.2 结果分析

表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}的测试结果对比

表4 规模n={120,150}的测试结果比对

4 结论

针对钢铁行业的炼钢—连铸—热轧工艺流程，考虑工件的释放时间、运输时间以及机器的调整时间，建立了中间阶段有批处理特征的整数线性规划模型，目标为所有工件的总加权完成时间最小.针对该多阶段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 schedulingnjobs 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.

Keywords: flexible flowshop scheduling;batch machines;total weighted completion time;self-adaptive genetic algorithm;self-adaptive adjustment

Multi-stageFlexibleFlowshopSchedulingwithBatchingMachines

WANG Junyan, WANG Xueyuan, XUAN Hua

(School of Management Engineering, Zhengzhou University, Zhengzhou 450001, China)

王薛苑(1985— )，男，河南郑州人，郑州大学讲师，博士，主要从事生产调度等方面的研究，E-mail：wangxueyuan@zzu.edu.cn.

TB49

A

10.13705/j.issn.1671-6833.2017.05.012

2017-01-16；

2017-04-30

国家自然科学基金资助项目(U1604150)；教育部人文社会科学研究基金项目(15YJC630148)；郑州大学优秀青年教师发展基金项目(1421326092)

1671-6833(2017)05-0086-05