考虑运输时间的绿色作业车间调度问题研究

戴 敏，张玉伟，曾 励

(扬州大学 机械工程学院，江苏 扬州225127)

近年来，在全球能源日益紧张和自然环境持续恶化的背景下，绿色车间调度研究受到极大关注。据统计，到2050年，全球能源需求将增长37%，未来30～40年CO2排放量将增加80%左右[1]。大量数据表明，由于加工任务安排不合理，机床大部分时间处于空转待机而非加工状态[2]。单从提高机器效率上进行节能效果一般，而车间调度是基于制造系统管理角度来优化车间生产，是实现企业低碳制造的重要途径。对于车间绿色调度问题，目前国内外学者已经做了大量研究。文献[3]建立了碳排放、能耗成本和最大完工时间的多目标绿色车间调度模型。文献[4]研究了柔性作业车间生产过程中加工时间、机器负载、运行成本的多目标调度模型。文献[5]建立了柔性流水车间节能调度模型，并采用一种改进的遗传模拟退火算法进行求解。文献[6]主要研究流水车间多目标优化问题，建立了作业时间、生产成本和生产能耗的数学模型。文献[7]研究了作业车间拖期和空闲能耗最低问题并设计了NSGA-II算法对该问题进行求解。从以上文献可以看出，目前车间绿色调度问题主要研究作业车间、流水车间加工能耗和空闲能耗，均忽略了机器间AGV运输时的能耗，且加工资源和AGV运输资源两者相互影响，分开调度很难实现系统整体节能效果。目前，对于考虑运输操作的车间调度问题也有很多研究。文献[8]研究了实际制造企业中具有顺序依赖设置和运输时间可控的置换流车间调度问题。文献[9]以完工时间最小为优化目标研究了具有运输和预期顺序依赖设置时间的群车间调度问题。文献[10]研究了AGV与机器集成的车间调度问题，并设计了新的算法进行求解，证明了AGV在车间调度中的重要性。文献[11]主要分析了车间和AGV实时联合调度问题，以完工时间为优化目标，采用文化基因算法对该问题进行求解。上述研究基本上基于生产效率指标(如生产时间)进行优化调度，未考虑节能指标。本文在以上研究基础上，以作业车间调度(job shop scheduling problem,JSP)为研究对象，考虑机器间AGV运输时间，将加工资源和运输资源集成调度，建立完工时间和总能耗的双目标优化模型，并提出一种融入模拟退火搜索策略的分布估计算法，分析不同权重系数时完工时间和能耗变化的关系及运输速度对能耗的影响。

1考虑物料运输时间的JSP问题描述及数学建模

1.1问题描述

在m台机器上加工n个工件且每个工件都有预定的工序加工顺序，所有工序按照规定的加工工艺路线在m台机器上完成操作。已知每道工序的加工时间和任意两台机器之间AGV运输时间，如图1所示。同时，约束条件如下。

1)每个工件必须在前一道工序加工完毕后方可运输到下一道工序的加工机器上进行加工；2)不同工件的工序之间没有约束；3)同一时刻每台机器至多加工一道工序，一个工件也只能在一台机器上加工；4)工序的加工过程不允许被中断；5)机器与工件开始时间都初始化为0；6)每台机器按照所安排的第一道工序的开始时间开机，最后一道工序的完成时间关机，以减少机床待机时间；7)AGV完全满足运输需求，并且在运输过程中互不影响。

图1 AGVs和机器集成下调度甘特图Figure 1 Gantt chart of the integrated scheduling with AGVs and machines

1.2 AGVs与机器集成调度下完工时间建模

以最大完工时间最短为第一个优化目标，建立考虑AGV运输时间的作业车间调度模型

式(1)为第1个优化目标，即最大完工时间最小；式(2)表示工件i在机器k上加工的开始时间，式(3)表示其完工时间；式(4)表示工艺约束，同一工件的不同工序有先后加工顺序；式(5)表示同一时刻一台机器只能加工1个工件；式(6)表示完工时间变量约束条件；式(7)和式(8)分别为指示系数和指示变量。Sik、Pik、Cik分别为工件i在机器k上的开始时间、作业时间和完成时间；Q为一个足够大的正数；thk为工件从机器h运输到机器k消耗的时间；Zk为设备k可以适用的时刻。

1.3 AGVs与机器集成调度下能耗建模

车间能耗主要包括机床能耗、公共能耗和运输能耗。在现有加工环境下，建立如图2所示的单机运行时输入功率简化模型[12]。该模型假设每台机器有3种功率级别：开机功率、空转功率和切削功率。

图2单机运行功率示意图Figure 2 Power diagram for single machine working

1.3.1机床能耗

开机能耗(E1)SPk(t)表示机器k的开机功率。当机器启动时，机器部件(液压部件、冷却泵)被激活从而消耗能量。消耗的能量可由式(9)计算得到。

其中，tk为机器k的开机时间。

切削能耗(E2)加工能耗E2由切削功率CPcikut乘以加工时间t

i

cku

t表示。

分别为工序Oik在机器k上的切削功率和加工时间。

空转能耗(E3)在实际加工中，由于工件未到达，机器经常处于空转状态而产生待机能耗E3。

其中， IPk为机器k的空转功率；Tk为机器k开机和关机之间的时间间隔；分别为机器k的空闲时间和加工时间，空闲时间图3为在机器k上加工4道工序的调度甘特图。

1.3.2 AGV能耗

图3机器k上的调度甘特图Figure 3 Schedule Gantt chart on machine k

运输能耗(E4)是指AGV小车在机器之间运输物料所产生的能耗，即AGV执行运输功能时消耗的能量。

式中， TP为运输设备功率。

1.3.3公共能耗

公共能耗(E5)是指车间公共设施的能源消耗，为照明，通风供暖等能耗的总和。

式中，P0为公共功率；Cmax为最大完工时间。因此，根据以上作业车间能耗分析，建立总能耗(E)优化目标为

2混合分布估计算法设计

分布估计算法(estimation of distribution algorithm，EDA)的概念最初在1996年被提出，是一种基于概率模型的种群进化算法，具有全局搜索能力强、收敛速度快的特点，但因其概率模型单一，易出现早熟现象[13]。模拟退火算法采用单点迭代搜索，具有突跳性强的特点，但学习能力较弱，其深度搜索易受降温函数的影响[14]。因此，综合两者的优缺点，本文提出了混合分布估计算法。

2.1编码与解码

选用基于工序的实数编码规则求解JSP，采用随机初始化的方法产生NIND个个体作为初始种群。个体长度为n×m，表示一个加工工序的排列，每个工件号均可出现m次。例如，3×3问题实例，个体[123311232]，对应的工序加工序列可以表示为

(O11，O21，O31，O32，O12，O13，O22，O33，O23)。其中，Oij为第i工件的第j道工序。在解码过程中，由于AGV运输操作参与车间生产，考虑到AGV在不同机器之间的运输时间，每道工序在机器上的加工开始时间确定规则为：假设机器k上前后两道工序分别为Opq和Oij，Opq在k上的完工时间为Cpqk，Oij所对应工件的前一道工序Oi(j-1)在机器w上的完工时间为Ci(j-1)w，AGV在机器k、w之间的运输时间为twk，那么工序Oij在机器k上的最早开始时间Sijk计算如下：若Cpqk≥Ci(j-1)w+twk，则Sijk=Cpqk；若Cpqk＜Ci(j-1)w+twk，则Sijk=Ci(j-1)w+twk。

2.2评价函数

由于完工时间C和总能耗E是2个相互冲突的目标，参考文献[15]，本文对2个目标进行去量纲加权求和构成单目标函数

式中，w(0≤w≤1)为权重系数，企业可以通过设置w的大小来调整目标函数倾向；Cmax和Cmin分别为目标函数完工时间的最大值和最小值；Emax和Emin分别为目标函数综合能耗的最大值和最小值。

2.3选择算子

采用轮盘赌的方式从初始种群中选择N(N＜NIND)个个体作为模拟退火算法(simulated annealing algorithm，SAA)的初始种群。初始温度定义为

式中，fmax、fmin分别为群体适应度最大值和最小值， Pr为最优个体接受概率。

对于每代优势种群中的每个个体随机交换染色体中2个位置上的元素，产生一个新个体Popnew运用Metropolis抽样策略，以一定的概率接受新解，接受概率为

党中央历来高度重视党和国家机构建设和改革。新中国成立后，在我们党领导下，我国确立了社会主义基本制度，逐步建立起具有我国特点的党和国家机构职能体系，为我们党治国理政、推进社会主义建设发挥了重要作用。尤其是改革开放以来，我们党积极推进党和国家机构改革，各方面机构职能不断优化、逐步规范，实现了从计划经济条件下的机构职能体系向社会主义市场经济条件下的机构职能体系的重大转变，推动了改革开放和社会主义现代化建设。回望改革开放40年来，为适应党和国家工作中心转移、社会主义市场经济发展和各方面工作不断深入的需要，党和国家机构改革与时俱进，不断深化，构成40年改革开放伟大实践的重要内容。

其中，ue为第e代的温度，然后随机产生一个[0,1]之间的数Re，如果ρ＞Re，接受新解，否则不接受。模拟退火算法一般采用ue+1=γue的降温方式。为在运行过程中对温度空间有充分的搜索以避免错过全局最优解，本文提出新的降温函数

在算法迭代过程中，当多次迭代却不更新最优解时，引入回火机制，人为地增加温度u，从而提高算法突变概率。设置回火代数为10，回火温度更新函数为

式中，g为退火次数，u为回火最终解。

2.4构建概率模型

概率模型的合理性对算法性能起关键作用，参照文献[14,16]构建概率模型的思想，结合自身研究问题的特点设计了一种n行l列的矩阵P来表示解空间分布的概率模型。式(21)为第e代概率模型P(e)。

其中，P(e)中元素∈[0,1],(1≤i≤n,1≤j≤l,l=n×m)为 第e代中工件i位 于第 j个位置的概率。

2.5概率模型的更新及新种群的生成

为了使概率模型矩阵P更准确地表示解空间的分布情况以及进化趋势，采用机器学习中的Hebb规则更新概率矩阵中的所有元素。

基于随机矩阵P，采用轮盘赌的方式随机产生新种群。为了保证分布估计算法迭代过程中最优解不退化，在群体采样时可以使用精英保留策略，即只产生NIND-1个新个体，并与当前最优个体一起构成新一代种群。

2.6 算法流程图

首先，设定算法的各种参数，并随机初始化种群。其次，根据式(15)目标函数计算适应度，以一定方式选择一定数量的优势群体作为SAA的初始种群。然后，基于模拟退火函数式(18)产生更多优秀个体，并用优势群体来更新概率模型。最后，采用新的概率矩阵P产生新种群。具体流程如图4所示。

图4混合分布估计算法流程图Figure 4 Flow chart of hybrid distribution estimation algorithm

3数值实验

为了验证混合分布估计算法的有效性，选择Taillard[17]提出的作业车间调度问题的基准案例FT06、FT10和FT20，采用本文提出算法进行求解20次并与EDA[18]、SAA[19]算法进行对比，调度目标为最优化完工时间(w=0)。实验设计环境和配置为Intel Core i5-3230M、2.6 GHZ CPU、4.00 G RAM、Windows 7 64位操作系统。程序编译和运行环境为Matlab R2014a。

参数设置为：学习速率α=0.38[18]；算法迭代次数 1 500作为终止条件；种群大小为60；初始接受概率Pr=0.8。优化结果如表1所示。

表1的仿真结果表明，本文提出的混合分布估计算法3个算例求解结果均明显优于EDA、SAA算法，证明了该算法的有效性。

表1不同算法优化结果Table 1 Optimization results based on different algorithms

对于FT06问题，先分配机器调度后分配AGV调度，实际加工时直接产生物料运输时间，最大完工时间为67 min，其调度甘特图如图5所示。将AGV与机器集成调度时，采用本文提出的混合分布估计算法和上述参数设置进行求解，通过实验测试10次均可得到最大完工时间为63 min，其调度甘特图如图6所示。最大完工时间数值从67降到63，生产效率提高了8.95%。这充分说明考虑物料运输与加工资源集成调度的必要性。

图5 AGVs与机器未集成下调度甘特图Figure 5 Gantt chart of the unintegrated scheduling with AGVs and machines

图6 AGVs与机器集成下调度甘特图Figure 6 Gantt chart of the integrated scheduling with AGVs and machines

为验证考虑物料运输与加工资源集成调度模型节能的有效性，本文以FT10案例为基础，参照文献[20]设定机床生产时的功率(表2)。考察实际车间布局设定机器间运输时间(表3)和运输设备功率为1.89 kW，整个车间其他辅助设备平均功耗为1 kW。

优化算法的权重系数w在[0,1]之间变化，将运输服务资源与加工资源分别独立调度和运输服务资源与加工资源集成调度2种情形在不同权重系数下运行20次，优化的完工时间和能量消耗取平均值，测试结果如表4所示。

表2机器功率信息Table 2 Information on machines power

表3 AGV在机器间的运输时间Table 3 Transportation time of AGVs between machines s

表4 AGVs与机器集成和未集成的调度实验结果Table 4 Experimental results of the integrated or unintegrated scheduling with AGVs and machines

在实际生产中，能量消耗和完工时间相互排斥，不能同时达到最优。如表4所示，当w=0时，AGV运输与加工资源集成调度，平均完工时间为980.32 min，能量消耗为975.65 kWh；当w=1时完工时间为1 202.32 min，总能耗提高约4.67%。这在企业交货期不紧张时可以适当调节权重，减少能量消耗。

AGV运输与加工资源集成调度与分开调度相比，在不同权重系数下能量消耗平均降低约1%，完工时间平均降低1.6%。这表明AGV运输与加工资源集成调度既能提高生产效率又可以降低能量消耗。

4不同AGV运输速度时的车间总能耗变化

以表3数据为基准运输时间，分别以2倍和10倍基准运输时间作为中速和低速作业模式。3种不同AGV运输速度下的能耗变化如图7～9所示。

图7 w=0时不同运输速度下能量消耗Figure 7 Energy consumption at different transport speeds with w=0

图8 w=0.5时不同运输速度下能量消耗Figure 8 Energy consumption at different transport speeds with w=0.5

图9 w=1.0时不同运输速度下能量消耗Figure 9 Energy consumption at different transport speeds with w=1

图7～9表明加工能耗不受调度的影响，始终保持不变。不同权重系数w下，当速度提高2倍时，总能耗平均降低3.2%，空转能耗平均降低16.3%，公共能耗平均降低6.71%；当速度提高10倍时，总能耗平均降低17.6%，空转能耗平均降低56.3%，公共能耗平均降低23.1%，运输能耗降低10倍。但本文没有充分考虑运输速度的变化对AGV功率的影响。一般地，速度提高，相应的功率会变大，运输能耗也会增加，后续研究工作会在运输速度变化引起的功率能耗的变化上进行深入研究，进一步提高车间能耗的节能效率。

5结论

本文分析作业车间调度的特点，结合实际生产需要，对车间加工资源和AGV运输进行集成调度，建立完工时间和能量消耗的多目标作业车间调度模型。提出一种融入模拟退火思想的分布估计算法，并设计新的退火函数，引入回火机制。实验结果表明：当不考虑能耗影响时，通过协同优化加工时间和AGV运输时间可以使完工效率提高8.95%；分析不同物料运输速度下的能量消耗，物料运输速度提高10倍，总能耗降低17.6%；当交货期不紧张时，可以调节权重系数w，节能可达4.67%。这可为企业适应当下节能、环保的大环境提供帮助，为企业可持续发展提供新思路。