考虑机器非加工状态的作业车间节能调度

吴正佳 华 露 白炜铖 涂晶鑫 刘秀凤 徐 峥

(三峡大学 机械与动力学院， 湖北 宜昌 443002)

考虑机器非加工状态的作业车间节能调度

吴正佳 华 露 白炜铖 涂晶鑫 刘秀凤 徐 峥

(三峡大学 机械与动力学院， 湖北 宜昌 443002)

为了减少机器在非加工状态时的能耗，采用机器关闭再开启的决策方案来实现此目的．首先建立目标为总能耗和最大完工时间最小化的车间节能调度模型，并将此决策方案抽象为约束条件，然后提出一种基于混合元胞遗传模拟退火算法的求解方法，引入插入式贪婪解码算法进行解码，基于同步机制的遗传操作更新种群，增加模拟退火操作与收敛准则实现进一步优化．最后通过案例验证了该模型与算法的有效性与实用性，结果表明运用该模型可达到很好的节能优化效果．

节能； 多目标； 作业车间调度； 混合元胞遗传模拟退火算法

机器在不同状态下会产生不同的能耗，且不同的运行状态对生产任务总能耗具有不同的影响，还会影响到机器的能量利用率．因此在研究作业车间节能调度问题时，机器非加工状态下的能耗也是需要考虑的部分，不可忽略．

车间调度问题属于NP-hard问题，许多学者对其求解算法进行了大量研究，其中遗传算法是研究最为热门的一个分支[1-2]．虽然传统遗传算法能够获得较满意的调度方案，但在解决调度问题时存在明显不足，即容易在收敛过程中得到局部最优解，形成早熟现象[3]．元胞遗传算法(cellular genetic algorithm，CGA)将元胞自动机与遗传算法有机结合，具有收敛快、多样性好的特点，在一定程度上改善了遗传算法局部搜索能力问题，但仍有可能陷入局部最优的情况[4]．模拟退火算法(simulated annealing algorithm，SA)是以随机搜索技术从概率意义上找出目标函数的全局最优点，具有强大局部搜索能力[5]．根据这两种优化算法各自的特点，取长补短进行结合，构造混合优化算法，能够发挥两种算法的优点，进而改进常规单一优化算法的性能．

本文在已有的研究基础上，详细分析机器不同状态下的能耗特征，以总能耗和最大完工时间为优化目标，将非加工状态下机器采取关闭再开启的决策方案抽象为约束条件，建立作业车间下考虑机器非加工状态下决策的多目标节能调度数学模型，然后提出混合元胞遗传模拟退火算法对其求解，并运用Pareto优化获得Pareto解集，最后通过实例验证该模型．

1 节能调度模型的建立

1.1 作业车间下机器能耗的状态变化

根据文献，可将机器的运行状态分为3种，即加工、关闭和空闲．其中，机器的加工状态能直接对工件创造价值，而关闭和空闲状态没有贡献任何形式的价值，故应尽量避免非加工状态的能耗或使其最小化．

在作业车间环境下，考虑到工件后一个工序阶段受到前一个工序阶段的时间约束，机器在加工完一个工件后，很有可能进入待机空闲状态，等待后一个工件的到达，此时，机器的空闲状态仍需要一定的能量消耗来维持机器运转，长时间待机仍然消耗大量能量．本文提出采用机器关闭再开启的决策方法解决此问题，具体步骤如下：设机器关闭再开启的能耗为Eon-off，机器空闲等待的能耗为Eidle，其中空闲能耗为机器待机功率pidle与机器待机时间tidle(刀具或工件的安装时间)的乘积[6]．

(1)当Eon-off

(2)当Eon-off>Eidle=pidletidle时，机器选择空闲等待.

其中，定义TB为决策方案的临界时间，Yildirim[7]等研究表明：

图1为采用该方法前后能耗示意图，由图1可知采取上述决策能有效减少能量消耗．

图1 采取停机在开启方案前后的能耗示意图

1.2 考虑机器非加工状态的作业车间节能调度的问题定义

JSP问题描述如下：M台机器上有N个工件加工，已知各操作的加工时间和各工件在各机器上的加工次序约束，要求确定机器上各工件加工先后顺序，使加工性能指标达到最优．本文提出以总能耗E和最大完工时间T为目标的节能调度模型，结合机器停机再开启的决策方法，最终得到性能指标较优的调度方案[4-5]．

1.3 模型建立

1.3.1 模型目标分析

本文针对作业车间节能优化问题，为了减小机器总能耗的同时保证完成时间，提出了以总能耗E和最大完工时间T为目标的节能调度模型．

1)机器总能耗E

机器总能耗包括加工能耗和非加工能耗，表达式为

其中切削能耗Ecutting表达式[8]为

式中，f为切削比能(W.s/mm3)，与工件硬度和机器属性相关，v表示材料去除率(cm3/s)，tcutting表示切削时间．

min{Eon-off，Eidle}表示机器非加工状态时选择能耗最小的方案，即

2)最大完工时间T

1.3.2 数学模型

在上述数学模型中，式(9)表示总能耗最小和最大完工时间最小两个目标函数；式(10)表示工件各操作的先后顺序；式(11)表示各机器加工各工件的先后顺序；式(12)表示机器在非加工状态的决策约束；式(13)表示各工序在各台机器上的加工时间与加工结束时间的范围约束；式(14)表示工件和机器的数量约束．

2 模型求解

2.1 求解方法概述

如前所述的多目标问题中两个目标函数优化时存在冲突，且两个目标的量纲不同，因此本文利用Pareto优化思想进行求解来获得各目标相对折中的解(即本文所提出的Pareto最优解)．为解决本文提出的考虑机器非加工状态的作业车间节能调度模型，提出了一种混合元胞遗传模拟退火算法(cellular genetic algorithm-simulated annealing algorithm，CGA-SA)，即先利用CGA的搜索能力对整个解空间进行全局搜索，确定最有可能搜索出的最优解的区域，再利用SA的局部搜索能力对各个区域进行优化，从而发挥两种算法的优点．

在算法操作细节上，本文在CGA中引入一种插入式贪婪解码算法进行解码，以确保染色体经解码后能产生主动调度，然后采用同步机制进行遗传操作，进而增加记忆功能的模拟退火操作与收敛准则，这样既防止算法求解时陷入局部最优解，又提高了算法的优化效率以及鲁棒性．

1)插入式贪婪解码

将染色体作为工序的有序序列，根据工序在该序列上的顺序进行解码，序列上第1道工序安排加工，取序列的第2道工序插入到对应机器上最佳可行的加工时刻安排加工，以此方式直到所有序列上所有工序都安排在其最佳可行位置[9]．

2)评价函数

由于本文数学模型为多约束多目标优化问题，且总能耗最小的目标函数E与最大完工时间最小的目标函数T是相互冲突的两个目标，因此本文采用加权求和方法将两个目标构成一个单目标函数，由此用来评价每组优化解集并确定最优解[10]，即

其中，Emax(t)和Emin(t)为第t次迭代中的总能耗的最大值和最小值，Tmax(t)和Tmin(t)为第t次迭代中的最大完工时间的最大值和最小值．

2.2 CGA-SA算法步骤

在借鉴前人的研究成果基础上，本文提出的CGA-SA混合算法具体步骤如下：

Step 1：初始化群体Q，规模为N，将其分布在m×n元胞空间中，N=m×n，则群体个体以矩阵表示；

Step 2：基于插入式贪婪解码算法，评价群体个体的适应度F(Qij)；

Step 3：采用同步机制对分布于元胞空间的所有个体进行相关遗传操作[4]：

选择：以确定的元胞空间位置的个体为中心元胞Qcenter=Qij，从此中心元胞领域内个体集QNij中选择一个个体QNij=max(F(QNij))，若中心元胞个体处于元胞空间边缘情况，且其邻居个体不在元胞空间内，则以另一边缘个体作为邻居个体；

交叉：以中心元胞个体Qcenter和领域内QNij中选一个个体进行交叉操作，本文选择两点交叉方法生成新个体Onew；

Step 4：选择优秀个体作为SA的初始解，并对其种群中的各个个体均进行定步长抽样的模拟退火操作，定义在温度tk下，为新产生的种群个体S*与当前种群个体S的增量，若ΔF(Qij<0)，则接收S*并判断F(S*)0，则以概率min(1，exp(-ΔF(Qij)/tk))接收S*为当前种群个体，且及时更新最优调度；

Step 5：判断是否达到算法终止条件，如果没有达到，迭代次数加1，并利用tk=αtk-1，α∈(0，1)进行降温操作，返回步骤(2)；如果达到终止条件，则把当前最优解输出，算法结束．

CGA-SA算法流程图如图2所示．

图2 CGA-SA算法流程图

3 实例分析

3.1 CGA-SA性能分析

为验证CGA-SA算法的可行性和有效性，采用标准测试案例FT06、FT10、FT20、LA06、LA11、LA21和LA31为测试基准，将CGA-SA算法与CGA算法进行比较，结果见表1．其中C**为算例的基准最优解，C*为算法最优解，Dmax为仿真20次得到的最大值与该算例已知最优值的相对偏差，Dmin为仿真20次得到的最小值与该算例已知最优值的相对偏差，Dave为仿真20次的平均值与该算例已知最优值的相对偏差．算法参数设置如下：种群规模200，最大遗传代数100，交叉概率0.5，变异概率0.9，降温速率0.9．

如表1所示，比较CGA和CGA-SA所得的7个算例的最优解C*可知，对于FT06和LA06小规模算例，两种算法均能获得基准最优解，而对于其他算例，其难度较大，CGA-SA所得最优解与CGA相比更接近基准最优解，说明加入SA后，最优解质量提高很多．比较7个算例的最大偏差Dmax、最小偏差Dmin和平均偏差Dave可知，CGA-SA算法所求的偏差值均明显低于CGA的偏差值，说明CGA-SA求解结果与CGA相比更为稳定，这是因为CGA在对整个解空间进行全局搜索来确定最优解区域时，存在局部过早收敛的情况，增加SA算法后，对各个区域进行局部搜索，能有效提高收敛精度，进而提高算法的求解能力，因此CGA-SA在全局寻优和收敛精度上都有了显著提高，具有较强的搜索能力．

表1 CGA-SA算法与CGA算法对比

3.2 CGA-SA的应用

选取某机械加工车间的加工任务进行调度试验．已知车间包含6个工件、6道工序和6台设备，其具体的机床编号，工件加工时间和加工功率见表2、表3，机床待机功率、关闭再开启的能耗和时间见表4．随着加工任务的标准化，可确定工件加工的进给量与切削速度，则由文献[11]可确定工件加工的切削比能f=2.840 J/mm3，材料去除率v=7.344 cm3/s．

表2 机床编号与对应的工件加工时间(单位：h)

表3 机床在不同工件工序的加工功率(单位：kW)

表4 机床待机功率、关闭再开启的能耗和时间

为验证本文所提出模型的优势，设定3种情况进行测试．方案1：机器在非加工状态选择等待或关闭再开启，调度目标为总能耗E和完工时间T，即本文提出的调度模型；方案2：在方案1的基础上，调度目标为单目标E或T；方案3：在方案1的基础上，机器在非加工状态仅考虑等待时的能耗情况，调度目标为E和T．

3.2.1 方案1的分析

根据本文的CGA-SA算法绘出以总能耗和完工时间为优化目标的Pareto最优解集形成的Pareto前沿，如图3所示，任务加工总能耗范围为3 007.28～3 335.39 kW·h，完工时间为58～65 h，根据式(15)中的评价函数可得方案1最优解的能耗为3 037.07 kW·h，最大完工时间为63 h，调度方案的甘特图如图4所示，红色区域表示机床在非加工状态选择关闭再开启，此时对应的生产调度节能数据见表5．

图3 方案1的Pareto前沿曲线

图4 方案1的甘特图

闲置机床编号等待时间/h停机启动时间/h待机功率/kW停机启动能耗/(kw·h)节能比/%M2150．150．903．3475．26M3290．271．112．0293．72M4180．211．951．4295．95

由表5可知，闲置机床在非加工状态采取关闭再开启的措施可节能75%以上，使机床总的空闲能耗降至21.72 kW·h，占总能耗的比例降至0.72%，因此执行关闭再启动的措施能够实现有效节能．

3.2.2 方案1与方案2的对比分析

方案1与方案2的区别是调度目标不同，根据本文算法分别求出总能耗最小(方案2a)，完工时间最小(方案2b)时的最优解，与方案1的结果对比如图5所示．

图5 方案1与方案2的结果对比

由图5可知，总能耗与完工时间这两个优化目标具有矛盾性，方案1与方案2a相比，能耗增加了197.79 kW·h，但完工时间减少了12 h，与方案2b相比，虽然完工时间增加了8 h，但总能耗减少了746.47 kW·h，故方案1的最优解介于方案2a与方案2b两者之间，且与各方案的最优值相距较小，因此方案1能综合优化两个目标，使各个优化目标更加平衡，进而获得两目标都较优的调度方案．

3.2.3 方案1与方案3的对比分析

方案3与方案1的区别是在机床非加工状态是否考虑关闭再开启的情况．根据本文算法求出方案3的Pareto最优解集，将调度完工时间为63 h时的总能耗以及空闲能耗与方案1对比结果见表6．由表6可知，方案1与方案3相比，在完工时间相同的情况下，总能耗节省了9.69%，其中空闲能耗节省了80.37%，因此方案1在机床非加工状态执行关闭再开启的措施具有更显著的节能效果．

表6 方案1与方案3的结果对比

通过上述3种案例的对比分析可知，本文提出的考虑机床非加工状态并以总能耗E和完工时间T为目标的节能调度模型能够有效平衡优化目标，在任务加工完成时间较小的情况下，总能耗也相对较小．在机床非加工状态下采取关闭再开启措施后，进一步减少了能耗，实现了有效节能．因此本文所提出的模型能够获得较好的加工生产方案，具有较好的节能优化效果，并且提出的CGA-SA算法能获得Pareto最优解集．

4 结 论

本文基于作业车间环境，考虑到机器在非加工状态下仍存在大量能耗，提出了机器关闭再开启的决策方法来达到节能优化的效果．

1)建立了以总能耗和最大完工时间为目标的节能调度模型，定义决策方案的临界时间，并将此决策方案抽象为约束条件．这样综合了两个优化目标，在满足完工时间的同时可减少能耗，另外采取机器关闭再开启的决策方法能进一步减少能耗，实现更有效的节能．

2)提出了CGA-SA混合算法，在算法操作细节上，引入插入式贪婪解码算法进行解码，然后采用同步机制进行遗传操作，进而增加记忆功能的模拟退火操作与收敛准则．这样既防止算法求解时陷入局部最优解，又提高了算法的优化效率以及鲁棒性．

3)通过性能测试验证了CGA-SA混合算法的求解质量优于其他算法，且具有较好的优化性能与鲁棒性．结果表明，本文提出的节能调度模型能够有效平衡优化目标，具有显著的节能效果．

因此，本文提出的考虑机器非加工状态的多目标节能调度模型，通过采用CGA-SA混合算法能获得较好的加工生产方案，同时实现设备的有效节能．

[1] 王万亮，吴启迪. 生产调度智能算法及其应用[M]．北京：科学出版社，2007．

[2] 王宇平. 进化计算理论和方法[M]．北京：科学出版社，2011．

[3] 朱凤龙. 遗传算法“早熟”现象的探究及改进策略[D]．成都：西南大学, 2010．

[4] 鲁宇明. 元胞遗传算法研究及应用[D]．南京：南京航空航天大学,2013．

[5] 赵 卫. 模拟退火遗传算法在车间作业调度中的应用[J]．计算机仿真，2011，28(7)：361-364．

[6] Rajemi M F, Mativenga P T, Aramcharoen A. Sustainable machining: selection of optimumturning conditions based on minimum energy considerations[J]． Journal of Cleaner Production,2010,18(10):1059-1065．

[7] Yildirim M B, Mouzon G. Single-machine Sustainable Production Planning to Minimize Total Energy Consumption and Total Completion Time Using a Multiple Objective Genetic Algorithm[J]．IEEE Transactions on Engineering Management,2012,59(4):585-597．

[8] Gutowski T, Murphy C, Allen D, et al. Environmentally benign manufacturing: observationsfrom Japan, Europe and the United States[J]． Journal of Cleaner Production, 2005,13(1):1-17．

[9] 杨宏安，孙启峰，李锦远. 求解作业车间提前/拖期调度问题的一种新解码方法[J]．计算机集成制造系统，2011，17(12)：2652-2659．

[10] He Y, Li Y, Wu T, et al. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops[J]．Journal of Cleaner Production,2015,87(1):245-254．

[11] 张洪潮，孔露露，李 涛，等. 切削比能模型的建立及参数影响分析[J]．中国机械工程，2015，26(8)：1098-1104．

Jop-shopEnergySavingSchedulingunderMachineNon-workingCondition

Wu Zhengjia Hua Lu Bai Weicheng Tu Jingxin Liu Xiufeng Xu Zheng

(College of Mechanical & Power Engineering, China Three Gorges Univ., Yichang 443002, China)

To reduce energy consumption under machine non-working condition, the decision method of machine is closed and then opened to achieve this goal. First, a multiobjective jop-shop optimization model based on this decision method is put forward, in which the energy consumption and makespan are considered. Then, a cellular genetic algorithm-simulating annealing algorithm (CGA-SA) is designed, with using insert greedy decoding algorithm, updating population by genetic operation based on synchronization, increasing simulated annealing and convergence criterion to improve searching performance. Finally, the effectiveness and practicability of model and algorithm are verified by case study. The results show that the model can achieve a good energy saving effect.

energy saving; multiobjective; jop-shop scheduling; cellular genetic algorithm-simulated annealing algorithm

10.13393/j.cnki.issn.1672-948X.2017.05.020

2016-12-23

湖北省自然科学基金资助项目(2014CFB686)

吴正佳(1964-)，男，教授，博士，研究方向为先进制造企业信息系统分析与集成、智能算法理论、设备综合管理与检测．E-mail： zjwu@ctgu.edu.cn

TH166

A

1672-948X(2017)05-0100-06

[责任编辑张 莉]