基于启发式优化算法的钢化玻璃加工车间调度优化

王 璐 张小宁 杨学男 吴 辉

（1.上海民航职业技术学院，上海 200232；2.同济大学经济与管理学院，上海 200092）

基于启发式优化算法的钢化玻璃加工车间调度优化

王 璐1张小宁2杨学男2吴 辉1

（1.上海民航职业技术学院，上海 200232；2.同济大学经济与管理学院，上海 200092）

在对钢化玻璃加工车间调度问题分析研究基础上，将钢化玻璃加工车间调度问题归结为混合流水车间调度问题。建立了以总完工时间最短为目标，并考虑了在钢化炉中存在加工批量约束的整数规划模型，同时设计了基于ECT（完工时间最早先加工）规则和FCFS（先到先服务）规则的启发式算法求解该模型。通过将所设计算法的求解结果与Cplex求解结果进行比较，验证了模型和算法的高效性。同时测试结果表明，在求解大规模调度问题时，本文所设计的算法的求解速度远远优于精确算法。

钢化玻璃加工；混合流水车间；启发式优化算法

1 问题描述

钢化玻璃的生成主要包括3个阶段：切割、印刷、钢化，典型的钢化玻璃加工的基本流程如图1所示。在切割车间将普通的玻璃按照最终产品尺寸进行切割后，进入印刷车间进行印刷，由于不同颜色的印刷效果不同，因而不同颜色所需的印刷次数存在差异，所有印刷完成的玻璃最后都要进入钢化炉进行钢化。

图1 钢化玻璃加工的基本流程

在实际钢化玻璃生产过程中，虽然切割车间、印刷车间有多条生产线，但是产线之间还是存在一定的差异，因而各条产线上所能加工的产品的个产线上的makespan；

Step4将印刷完成的工件从list2中移除，转至step2，若list2中没有待印刷工件，停止；

Stage2计算的时间复杂度为O(n log n)；

Stage3（钢化炉）主要遵循先凑成整批的先加工，也即先到先服务规则（FCFS）：

Step1根据N个工件在印刷车间完工时刻的先后顺序生成一个序列（list3）；

Step2选择list3里面第一个能凑成整批的工件进行加工，若list3中无待加工的工件，转至Step6，若list3仍有工件且不能凑成整批，转至Step4；

Step3更新makespan，将已加工的工件从list3中移除，并转至step2；

Step4若list3还有未凑成整批的工件，则将使makespan增加最少的工件先加工，若list3中无待加工的工件，转至Step6；

Step5更新makespan，将已加工的工件从list3中移除，并转至step4；

Step6输出makespan并停止；

Stage3计算的时间复杂度为O(n)。

图2 启发式算法流程图

4 数值实例测试

为了验证本文设计算法的有效性，本文将从计算结果和计算时间两个方面与相同参数设置下用Cplex计算出的结果进行比较。

4.1 实验设置

以Matlab为开发环境，采用的InterCore i52.5GHz，4GBRAMPC机，验证本文所提出的启发式算法的性能，问题规模从5～11个工件逐步扩大到25～31和45～51个工件，在各个问题规模下均随机产生5个测试数据，并计算出5次运行结果中makespan的最大、最小值和平均值，以及求解时间的最大、最小值和平均值。由于Cplex求解问题的规模有限制，因此在求解小规模问题设定让Cplex求出精确解，在求解中、大规模问题时，设定Cplex运行的时间（设定为600s），超过设定时间没有计算出精确结果即结束运行并输出当前的求解结果。

定义为Cplex运行结果与本算法计算结果中makespan之间的差距，即

表2 两种算法的测试结果（小规模）

表3 两种算法的测试结果（中规模）

4.2 运行结果分析

表2～表4分别列出了在不同规模下Cplex计算结果和本文提出的启发式算法计算结果的对比。

从表2～表4两种算法的运行结果的对比可以得出以下结论：

（1）对于小规模问题(玻璃数为5～11)，虽然本文提出的启发式算法求解结果与Cplex计算出的精确解之间的gap超过了将近15%，但是从计算时间角度来看，与Cplex计算时间相比，本文提出的启发式算法能在相当短的时间内找到一个令人满意的近优解。

（2）对于中规模问题（玻璃数为25～31），本文提出的启发式算法结果与在设定时间内Cplex计算出的结果之间的gap已经缩小了很多，且求解速度远远优于Cplex的计算时间，这在一定程度上说明所设计算法的高效性。

（3）对于大规模问题（玻璃数＞45），测试结果表明，Cplex在600s内计算出的结果已经比不上本文所设计算法在1s不到的时间内计算出的调度方案。实际上，通过测试发现，当问题规模超过30块玻璃时，用Cplex求解需要花费相当长的时间，而本文所设计的算法在超大规模（玻璃数＞10000）时，求解时间也仅需10s左右，考虑到实际钢化玻璃加工车间的玻璃数量很大，因而本文所设计的算法在解决实际钢化车间调度问题时仍然具有高效性。

表4 两种算法的测试结果（大规模）

[1]FattahiP,HosseiniSMH,JolaiF,et al.Abranch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations[J].AppliedMathematicalModelling,2014,38(1):119-134.

[2]ChengM,TadikamallaPR,ShangJ,et al.Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs[J].EuropeanJournal of operational research,2014,234(3):650-657.

[3]MarichelvamMK,PrabaharanT.Performance evaluation of an improved hybrid genetic scatter search(IHGSS)algorithm for multistage hybrid flow shop scheduling problems with missing operations[J].InternationalJournal ofIndustrial andSystemsEngineering,2014,16(1):120-141.

[4]李俊青,潘全科,王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管理,2015,1:023

[5]宋代立,张洁.蚁群算法求解混合流水车间分批调度问题[J].计算机集成制造系统,2013,19(07):1640-1647.

[6]LinQ,GaoL,LiX,et al.Ahybrid backtracking search algorithm for permutation flow-shop scheduling problem[J].Computers&IndustrialEngineering,2015,85:437-446.

[7]SoltaniSA,KarimiB.Cyclic hybrid flow shop scheduling problem with limited buffers and machine eligibility constraints[J].TheInternationalJournal ofAdvancedManufacturingTechnology,2015,76(9-12):1739-1755.

[8]张其亮，陈永生.基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论实践,2014,34(3):802-809.

Heuristic Optimization Algorithm for Tempered Glass Production shop Scheduling Problem

Wang Lu1Zhang Xiaoning2Yang Xuenan2Wu Hui1
（1. Shanghai Civil Aviation College, Shanghai 200232; 2.School of Economics & Management，Tongji University, Shanghai 200092）

Based on the analysis of tempered glass production shop scheduling problem, it is formulated as a hybrid flowshop scheduling problem. Combined with the scheduling theory, a scheduling model with processing batch of tempering furnace is presented. Based on ECT rule and FCFS rule, a heuristic optimization algorithm is developed to solve the special scheduling model. By comparing the numerical result with the result calculated by Cplex, effectiveness and efficiency of the proposed algorithm and model are verified, also the numerical result also indicated that, the proposed heuristic algorithm has great advantage in solving speed than exact algorithm when solving large scale scheduling problem.

tempered glass processing; hybrid flow-shop; heuristic optimization algorithm

F252

A

1005-9679(2017)02-0079-06

2016-12-17

国家自然科学基金重点项目（编号71531011）资助

王璐，上海民航职业技术学院，讲师，硕士学位，主要研究机场物流优化；张小宁，同济大学经济与管理学院，研究员，博士生导师，主要研究交通管理及物流优化；杨学男，同济大学经济与管理学院，研究生，主要研究优化调度问题；吴辉，上海民航职业技术学院，讲师，硕士学位，主要研究机场物流优化。