混合流水车间调度问题(HFSP)广泛存在于机械加工、化工等生产中．在实际生产过程中，HFSP不同阶段机床间的缓冲区是有限的，甚至没有缓冲区[1]．针对HFSP问题，若相邻阶段机床间缓冲区有限，则称之为有限缓冲区HFSP (HFPS-LB)[2]；若相邻阶段机床间无缓冲区，则为阻塞HFSP (HFSP-B)．针对HFSP-LB，文献[2]提出了一种混合人工蜂群与禁忌搜索的算法，文献[3]提出了一种改进的帝国竞争算法，文献[4]设计了一种改进的禁忌搜索算法．针对HFSP-B最大完工时间问题，文献[5]提出了求解该问题的4个MILP模型及改进回溯搜索算法，文献[6]提出了一种离散布谷鸟搜索算法，文献[7-9]提出了一种粒子群算法，文献[10]提出了一种禁忌搜索算法．针对HFSP-LB，文献[11]提出了一种禁忌搜索算法，文献[12]提出了一种模因进化算法．在实际生产中，不同工件在同一机床上加工时，会存在使用不同夹具、刀具等情况，相邻工件间会存在一定的调整时间．文献[13]针对考虑调整时间的HFSP-LB问题，提出了求解问题的两种多目标遗传算法．针对HFSP-LB问题，文献[14]提出了一种遗传算法，文献[15]提出了一种改进的遗传算法与规则相结合的混合算法．综上，求解HFSP-B主要有元启发式算法及基于MILP模型的求解方法．元启发式算法为近似求解方法，虽然可高效求解HFSP-B问题，但HFSP-B问题复杂，在解码过程中须考虑阻塞因素，若解码方法设计不好，则求解效果不可保证，更不能保障求得最优解[16-17]．近年来，随着计算机硬件及数学模型求解软件性能大幅提升，MILP模型求解考虑复杂因素的调度问题引起广泛关注[16-18]．对于带有复杂约束的车间调度问题，MILP更具有优势，如针对分布式柔性作业车间的MILP模型[19]．针对HFSP-B最大完工时间问题，MILP模型[5]在多个实例上优于现有元启发式算法．针对考虑调整时间的HFSP问题，MILP模型[20]在多个实例上优于现有的高效人工蜂群算法．综上，针对考虑特殊约束的调度问题，MILP模型具有一定的优势．近年来，节能调度问题引起广泛关注．关机/重启策略可大幅降低机床待机能耗，对HFSP有效．针对HFSP节能调度问题，考虑关机/重启节能策略，文献[21]提出了求解该问题的5个MILP模型及改进遗传算法．与HFSP问题相比，HFSP-B由于阻塞原因，机床待机时间会更长，更能发挥关机/重启策略的节能优势．然而，目前还没有针对面向节能的HFSP-B问题的研究．本研究考虑关机/重启策略节能策略，构建HFSP-B问题MILP模型，考虑调整时间，构建考虑调整时间的HFSP-B问题(HFSP-B-SDST)的MILP模型．通过对最优解进行分析，挖掘阻塞因素对车间能耗的影响．1 车间能耗分析1.1　HFSP-B问题描述HFSP-B描述如下：车间中有n个工件须在S个加工阶段上加工，至少有一个阶段存在2台及以上并行机床，每个并行机床的加工能力有差异．相邻阶段机床间不存在缓冲区，即工件在上一阶段完成加工后，只能等下一阶段有空闲机床时方可离开上一阶段所在机床，等待过程即为阻塞过程．车间总能耗主要包括机床加工能耗、机床调整能耗、机床待机能耗及公共能耗4部分．其中，机床加工能耗是指当机床在加工工件时所消耗的能耗；调整能耗是指机床更换夹具、重新对刀等转换操作所消耗的能量；待机能耗包括阻塞能耗及空闲能耗，阻塞能耗是指由于工件被阻塞在机床上而导致机床在该时间段内消耗的能量，空闲能耗是指机床在空闲时间段能所消耗的能量；公共能耗是指车间中如照明、空调等设备的能耗．1.2　加工能耗当工件在不同机床上加工时，由于机床特性不同，加工功率及加工时间不一样，因此消耗的能量也不一样，Pi,kE=pi,kTi,k    (i∈I,k∈K),式中：Pi,kE为工件i在机床k上加工的加工能耗；pi,k为工件i在机器k上的加工功率；Ti,k为工件i在机器k上的加工时间；i为工件序号；I工件集合，I=1,2,⋯,n，n为工件总数；k为机床序号；K为机床集合，K=1,2,⋯,m，m为机床总数．总加工能耗PE，即加工完所有工件所消耗的能量可表示为PE=∑i∈I∑k∈K∑t∈Lkpi,kTi,kYi,k,t,式中：t为机床位置序号；Lk为机床k的位置集合，Lk={1,2,⋯，n}；Yi,k,t为0-1决策变量，若工件i选择在机器k的第t位置上加工，则为1，否则为0．1.3　调整能耗调整时间内机床不能关机，这部分能耗是必须的．机床k第t到t+1位置之间的调整时间可表示为Sk,tet=∑i∈I∑i'∈I∑j∈Ji∑j'∈Ji'Yi,j,k,tYi',j',k,t+1Si,i',ket(∀k∈K,t∈Lk'),式中：j为加工阶段序号；J为加工阶段集合，J={1,2,⋯,S}，S为加工阶段总数；Lk'为机床k的位置集合，Lk'={1,2,⋯,n-1}；Si,i',ket为工件i与i'在机床k连续加工时的调整时间．只有当工件i安排在机床k位置t上且工件i'安排在机床k位置t+1上时，Yi,k,tYi',k,t+1才等于1，否则等于0．调整能耗Sk,tE可表示为Sk,tE=Sk,tetPsetk=∑i∈I∑i'∈I∑j∈Ji∑j'∈Ji'Yi,j,k,tYi',j',k,t+1Si,i',ketPsetk(∀k∈K, t∈Lk'),式中Psetk为机床k的调整功率．总调整能耗为SE=∑k∈K∑t∈Lk'Sk,tE=∑i∈I∑i'∈I∑j∈Ji∑j'∈Ji'Yi,j,k,tYi',j',k,t+1Si,i',ketPsetk．1.4　机床待机能耗不考虑调整时间时，空闲阻塞时间为bidlek,t=Sk,t+1-Fk,t    (∀k∈K,t∈Lk'),式中：bidlek,t为机床k第t到t+1位置之间空闲阻塞时间；Sk,t+1为机床k第t+1位置的开始时间；Fk,t为机床k第t位置的结束时间．考虑调整时间时，bidlek,t表示为bidlek,t=Sk,t+1-Fk,t-Sk,tet    (∀k∈K,t∈Lk'),Sk,tet=∑i∈I∑i'∈IYi,k,tYi',k,t+1Si,i',ket    (∀k∈K,t∈Lk').待机能耗Wk,tE可表示为Wk,tE=pidlekbidlek,t    (∀k∈K,t∈Lk'),式中pidlek为机床k的待机功率．当机床k的bidlek,t比较长时，该机床可以实行关机/重启策略．只有当bidlek,t大于等于机床k一次关机/重启策略所需要的时间Tkoff/on，且消耗的能耗大于等于机床k一次关机/重启的能耗Ekoff/on时方可实施．空载平衡时间TkB-off/on，即机床k可实行关机/重启策略的最短等待时间可表示为TkB-off/on=max{Tkoff/on,Ekoff/on/pidlek}    (∀k∈K).引入关机/重启策略后，待机能耗为Wk,tE=(1-Zk,t)tidlek,tpidlek+Zk,tEkoff/on(∀k∈K,t∈Lk'),式中Zk,t为0-1变量，用来控制是否实行关机/重启策略，当Zk,t=1时，表示在机床k的第t到t+1之间实行关机/重启策略，否则不实行关机/重启操作，此时Zk,t=0．引入关机/重启策略后，待机能耗为Wk,tE=(1-Zk,t)bidlek,tpidlek+Zk,tEkoff/on(∀k∈K,t∈Lk').总待机能耗WE为所有机床所有空闲阻塞段能耗的总和，WE=∑k∈K∑t∈Lk'Wk,tE=∑k∈K∑t∈Lk'((1-Zk,t)bidlek,tpidlek+Zk,tEkoff/on).1.5　公共能耗车间公共能耗为CE=p0Cmax，式中：p0为公共功率；Cmax为最大完工时间．1.6　车间总能耗不考虑调整时间时，车间总能耗QEC为总加工能耗PE，总待机能耗WE及公共能耗CE之和，QEC=PE+WE+CE=∑i∈I∑k∈K∑t∈Lkpi,kTi,kYi,k,t+∑k∈K∑t∈Lk'((1-Zk,t)(Sk,t+1-Fk,t)pidlek+Zk,tEkoff/on)+p0Cmax. (1)考虑调整时间时，QEC可表示为QEC=PE+SE+WE+CE=∑i∈I∑k∈K∑t∈Lkpi,kTi,kYi,k,t+∑k∈K∑t∈Lk'∑i∈I∑i'∈IYi,k,tYi',k,t+1Si,i',ketPsetk+∑k∈K(1-Zk,t)∙(Sk,t+1-Fk,t-∑i∈I∑i'∈IYi,k,tYi',k,t+1Si,i',ket)pidlek+Zk,tEkoff/on+P0Cmax. (2)2 MILP模型建立2.1　决策变量式(1)与(2)包含非线性项Yi,k,tYi',k,t+1，Zk,tYi,k,tYi',k,t+1，Zk,tSk,t+1和Zk,tFk,t决策变量相乘的情况，导致目标函数为非线性．非线性模型的求解十分困难，通过引入待机段能量决策变量Ek,tS，表示机床k第t到t+1位置之间的待机能耗Wk,tE．其中，当不考虑调整时间时，Ek,tS表示Wk,tE；考虑调整时间时，Ek,tS表示Sk,tE+Wk,tE．Ek,tS将非线性模型转换为线性模型，线性化目标函数为QEC=∑i∈I∑k∈K∑t∈Lkpi,kTi,kYi,k,t+∑k∈K∑t∈Lk'Ek,tS+p0Cmax．(3)HFSP-B及HFSP-B-SDST决策变量相同，都包含Yi,k,t，Bi,j，Ei,j，Di,j，Sk,t，Fk,t，Ek,tS及Zk,t 8个决策变量．2.2　约束条件∑k∈Kj∑t∈LkYi,k,t=1    (∀i∈I,j∈J); (4)∑i∈IYi,k,t≥∑i∈IYi,k,t+1    (∀k∈K,t∈Lk'); (5)∑i∈IYi,k,t≤1    (∀k∈K,t∈Lk); (6)Di,j=Bi,j+1    (∀i∈I,j∈{1,2,⋯,S-1}); (7)Ei,j=Bi,j+∑k∈Kj∑t∈Lk(Ti,kYi,k,t)    (∀i∈I,j∈J); (8)Fk,t=Sk,t+∑i∈I(Ti,kYi,k,t)    (∀k∈K,t∈Lk); (9)Ei,j≤Di,j    (∀i∈I,j∈J); (10)Di,S≤Cmax    (∀i∈I); (11)Bi',j≥Di,j-M(2-Yi,k,t-Yi',k,t+1)(∀i,i'∈I,i≠i',j∈J,k∈Kj,t∈Lk'); (12)Bi',j≥Di,j+Si,i',ket-M(2-Yi,k,t-Yi',k,t+1)(∀i,i'∈I,i≠i',j∈J,k∈Kj,t∈Lk'); (13)Sk,t≤Bi,j+M(1-Yi,k,t)(∀i∈I,j∈J,k∈Kj,t∈Lk); (14)Sk,t≥Bi,j-M(1-Yi,k,t)(∀i∈I,j∈J,k∈Kj,t∈Lk); (15)TkB-off/onZk,t≤Sk,t+1-Fk,t    (∀k∈K,t∈Lk'); (16)      TkB-off/onZk,t+Si,i',ket≤Sk,t+1-Fk,t+M(2-Yi,k,t-Yi',k,t+1)    (∀i,i'∈I,i≠i',k∈K,t∈Lk'); (17)Ekoff/onkZk,t≤Ek,tS    (∀k∈K,t∈Lk'); (18)        Ekoff/onkZk,t+PsetkSi,i',ket≤Ek,tS+M(2-Yi,k,t- Yi',k,t+1)    (∀i,i'∈I,i≠i',k∈K,t∈Lk'); (19)(Sk,t+1-Fk,t)Pidlek≤Ek,tS+MZk,t    (∀k∈K,t∈Lk'); (20)      (Sk,t+1-Fk,t-Si,i',ket)Pidlek+PsetkSi,i',ket≤Ek,tS+MZk,t+M(2-Yi,k,t-Yi',k,t+1)               (∀i,i'∈I,i≠i',k∈K,t∈Lk'); (21)Fk,t≤Sk,t+1    (∀k∈K,t∈Lk'); (22)∑t∈Lk'Zk,t≤Nk    (∀k∈K); (23)0≤Ek,tS    (∀k∈K,t∈Lk')；(24)Bi,j,Sk,t≥0    (∀i∈I,k∈K,j∈Ji,t∈Lk), (25)式中：Bi,j为连续决策变量，表示工件i在加工阶段j的开始时间；Di,j为连续决策变量，表示工件i离开加工阶段j的时间；Kj为加工阶段j的并行机床集合，Kj={1,2,⋯,mj}，mj为加工阶段j的并行机床数；Ei,j为连续决策变量，表示工件i在阶段j的结束时间；M为一个极大正数．式(4)表示在任一阶段，每个工件只能选择在一台机床上加工．式(5)表示机床按照位置的先后顺序安排工件加工．式(6)表示机床的任一位置最多只能加工一个工件．式(7)表示阻塞约束，即工件在上一阶段离开所在加工机床的时间等于在下一阶段的开始时间．式(8)表示工件在任一阶段的结束时间等于开始时间与加工时间之和．式(9)表示机床位置的结束时间等于其开始时间与所加工工件加工时间之和．式(10)表示工件在任一阶段的结束时间不大于其离开所在加工机床的时间．式(11)表示最大完工时间约束．式(12)表示不考虑调整时间时，机床后一位置工件的开始时间不小于前一位置工件的离开时间．式(13)表示考虑调整时间时，机床后一位置的开始时间不小于前一位置工件的离开时间与调整时间之和．式(14)和(15)为对偶约束，表示工件开始时间与机床位置开始时间的关系．式(16)、(18)及(20)表示不考虑调整时间时的关机/重启节能策略约束，式(17)、(19)及(21)表示考虑调整时间时的关机/重启节能策略约束．式(22)表示机床相邻位置时间约束．式(23)限制每个机床的最多关机/重启次数，式(24)和(25)限定决策变量的取值范围．针对HFSP-B问题，约束条件为式(4)~(14)、(17)、(19)、(20)、(22)~(25)．针对HFSP-B-SDST问题，约束条件为式(4)~(11)、(13)~(15)、(17)、(19)、(21)~(25)．3 试验验证MILP模型由CPLEX进行求解．共设计了4组规模不同的测试实例，工件数量分别为8，10，15及20．求解时间设为1 200 s．3.1　HFSP-B为了研究阻塞因素对能耗目标求解的影响，不考虑阻塞约束条件(12)，可求不考虑阻塞约束的HFSP问题．对HFSP-B及HFSP所得最优解进行分析，挖掘阻塞因素对能耗目标的影响．表1给出了4组实例的HFSP-B及HFSP求解结果对比．表中：T为求解时间；Gap为所得解与所得下届之间的百分比偏差，Gap=0表示求得最优解．从表1可以看出：HFSP-B及HFSP在1 200 s内可以求得2个实例的最优解，且求解时间随问题规模增大急剧增加．对于15及20个工件实例，MILP模型无法在1 200 s内求解最优解．HFSP-B比HFSP多考虑了阻塞这一特殊约束，约束数量增加，求解时间大幅增加．HFSP-B的总能耗大于HFSP，这是因为考虑阻塞因素后，机床待机时间大幅增加．10.13245/j.hust.210722.T001表14组实例的HFSP-B及HFSP求解结果对比工件数量HFSP-BHFSP0-1决策变量数约束数/103连续决策变量数Gap/%T/sQEC/MJ0-1决策变量数约束数连续决策变量数Gap/%T/sQEC/MJ86395.4032800.0041.85.683 86391 8752800.002.15.575 81098110.0053520.00518.86.673 69812 7153520.006.56.529 6152 15131.90553237.521 200.015.043 82 1515 4455322.401 200.010.659 0203 77174.05571257.531 200.026.883 93 7719 07571213.681 200.013.269 3针对8工件实例，表2给出了HFSP-B及HFSP最优解的能耗．可以看出：考虑阻塞因素后，机床空闲段时间大幅增加，机床空闲能耗增加，可执行关机/重启策略次数增加．这是因为阻塞大幅增加机床的待机时间段及待机时间．10.13245/j.hust.210722.T002表28工件实例HFSP-B及HFSP最优解能耗加工环境QEC/kJPE/kJ空闲阻塞CE/kJ关机(重启)次数HFSP-B5 683.83 755.81081 8203HFSP5 575.83 755.801 82003.2　HFSP-B-SDST针对HFSP-B-SDST，将约束(13)修改为Bi',j≥Ei,j+Si,i',ket-M(2-Yi,k,t-Yi',k,t+1)(∀i,i'∈I,i≠i',j∈J,k∈Kj,t∈Lk'),则可求解不考虑阻塞因素HFSP-SDST问题．表3给出了HFSP-B-SDST及HFSP-SDST的求解结果对比．在1 200 s内，MILP模型求得最小8工件实例的最优解．这是因为考虑调整时间后约束数量大幅增加，求解难度变大．10.13245/j.hust.210722.T003表3HFSP-B-SDST及HFSP-SDST求解结果对比工件数量0-1决策变量数约束数/103连续决策变量数HFSP-B-SDSTHFSP-SDSTGap/%T/sQEC/MJGap/%T/sQEC/MJ863916.3022800.00227.15.959 60.0045.55.869 81098132.4423525.371 200.07.065 01.481 200.06.861 0152 151112.79753237.191 200.015.025 216.171 200.011.482 0203 771271.90271269.651 200.037.612 721.631 200.014.566 2针对8工件实例，表4给出了HFSP-B-SDST及不考虑阻塞约束HFSP-SDST最优解的能耗．阻塞因素增加了机床的待机时间，从而增加了机床实行关机/重启节能策略的机会．10.13245/j.hust.210722.T004表48工件实例HFSP-B-SDST及HFSP-SDST最优解能耗加工环境QEC/kJPE/kJ调整能耗空闲阻塞CE/kJ关机/重启次数HFSP-B-SDST5 959.63 755.8124.8592 0203HFSP-SDST5 869.83 755.8114.002 00004 结语研究了考虑能耗目标的HFSP-B，分析了HFSP-B车间能耗组成，建立了考虑关机/重启节能策略的MILP模型．MILP模型分为考虑调整时间及不考虑调整时间两种．针对MILP模型，从目标函数和目标函数的线性化过程、决策变量、约束方程等方面进行介绍．使用CPLEX对MILP模型进行求解，求得小规模问题的最优解，验证了所提MILP模型的有效性．通过对MILP所得最优解的分析，挖掘了阻塞因素对能耗目标的影响规律：阻塞因素大幅增加机床的待机时间及能耗．通过简单修改MILP模型，就可求解不同约束、不同目标函数的调度问题，因此本模型及构建过程可为考虑其他约束HFSP调度问题的建模过程提供支撑，如针对无等待HFSP、无等待HFSP-SDST等．虽然MILP针对考虑复杂约束调度问题有一定优势，但是求解效率较低，很难应用于实际加工中．今后将针对节能阻塞混合流水车间调度问题设计高效的元启发式算法，如遗传算法、粒子群算法及人工蜂群算法．