摘 要：针对带有阻塞限制的混合流水车间调度问题，提出一种混合粒子群优化（HPSO）算法．HPSO将粒子群优化算法与所提出的释放–回推（release-backstepping，RB）算法相结合，设计了矩阵编码方式，利用RB算法解决工件排序问题并计算问题目标值，利用粒子群优化算法进行全局搜索，不断优化问题目标．通过实例验证了所提算法的有效性．

关键词：混合流水车间调度；混合粒子群优化算法；阻塞限制；释放–回推算法

Hybrid Particle Swarm Optimization Algorithm for Hybrid Flow ShopScheduling Problem with Blocking

Abstract:A hybrid particle swarm optimization (HPSO) algorithm is proposed for hybrid flow shop scheduling problemwith blocking. HPSO algorithm combines the PSO algorithm with release-backstepping (RB) algorithm. In HPSO, the matrixbased encoding scheme is designed and RB algorithm is used to sequence jobs and obtains the objective, while PSO algorithmis employed for global optimization. Effectiveness of the proposed algorithm is validated by actual experiments.

Keywords:hybrid flow shop scheduling; hybrid particle swarm optimization algorithm; blocking; release-backsteppingalgorithm

1 引言（Introduction）

混合流水车间调度问题（hybrid flow shop sche-duling problem，HFSP）是基本流水车间调度问题的推广，其最大特点在于允许工件加工的工序中存在并行机器．HFSP最早由Salvador[1]基于石油工业背景提出．由于该类问题更加贴近于实际的工业生产，被广泛应用于石油、化工、冶金、轨道交通运输等领域．文[2] 证明了在具有2个工序的HFSP中，只有1个工序存在并行机的单目标问题属于NP（nondeterministic polynomial）完全问题，因此该类问题即属于NP完全问题．基本HFSP假设各工序机器间存在无限大的缓冲区，但实际生产过程中，机器间的缓冲区是有限的甚至是不存在的．例如，轨道交通运输系统中，对列车（工件）占用轨道区段（机器）有严格要求，一个轨道区段不允许同时有2辆列车占用，在前方相邻轨道区段被占用的情况下，列车只能阻塞在该轨道区段上，直至前方相邻轨道区段被释放为止．本文所研究的是带有阻塞（blocking）限制的HFSP（BHFSP），即各工序机器间不存在缓冲区的HFSP．目前已有文献对此问题进行研究：文[3]提出利用禁忌搜索算法和优先级规则相结合的方法解决BHFSP环境下集装箱装卸作业调度问题，其应用禁忌搜索算法对工件在第1级的排序进行优化，采用优先级规则进行其它级工件的排序，获得了较好的调度结果．文[4]将所提出的memetic算法和局部搜素算法NVNS（nested variable neighborhood search）进行了结合，有效地求解了带有阻塞限制的混合流水线调度问题．经实验证明，其提出的组合算法在求解质量上要优于传统的遗传算法．文[5]针对集装箱码头的集卡调度问题进行了研究，提出了基于属性的BHFSP，并建立了基于属性的多目标数学模型，利用遗传算法对问题进行了仿真，有效地解决了集卡优化调度问题．文[6]提出了一种EM（expectation maximization）算法，用于求解具有RCB（release when completing blocking）约束的HFSP，实验证明EM算法在解决HFSP时，在执行时间上要优于遗传算法和模拟退火算法．文[7]引入一种新的启发式算法，利用先来先服务（FCFS）规则选择加工工件，并产生多个候选解，算法最终取其完工时间最小的解，以达到求解目的．文[8]将解决NP完全问题中的一些优化处理方法与遗传算法相结合，对具有工序排序调整时间和阻塞约束的HFSP进行了求解，并证明了算法的优越性．文[9]建立了混合线性整数规划模型，提出利用分支–切割算法对有限等待混合流水车间调度问题进行求解，各种复杂的实例验证了其所提模型和算法的有效性．文[10]提出了一种2阶段混合粒子群优化算法求解车间调度问题，算法在第1阶段为每个粒子设置较大的惯性系数w，同时去掉了粒子的社会学习能力，从而保证每个微粒在局部范围内充分搜索；第2阶段的混合粒子群优化算法以第1阶段每个粒子找到的最好解作为初始解，同时以遗传算法中的变异操作保证粒子多样性，实验证明其算法具有较好的性能．文[11]提出了一种改进的遗传算法GASBC，并求解了带有阻塞限制、有限缓冲区限制以及能力约束的混合流水车间调度问题，通过与其它有效算法的比较，证明了GASBC算法在求解该类问题时具有较高的求解质量．为了更有效地求解BHFSP，本文提出了一种HPSO算法．算法设计了矩阵编码方式，每个粒子表示所有工件在每道工序上的机器分配情况；提出RB算法解决粒子中工件排序问题，并充分利用了粒子群优化算法的全局搜索能力．同时，为了避免种群陷入局部最优，算法在一定条件下对停滞粒子和全局最优粒子进行变异，增加种群多样性，提高算法的寻优质量．仿真实验证明了本文算法的有效性．

2 BHFSP 问题描述（Description ofBHFSP）

BHFSP可描述为：n个工件要在m台机器上加工，加工约束为：(1)每个工件包含一道或多道工序，每道工序都要在不同的机器上加工；(2)同一台机器同一时刻只能加工一个工件；(3)同一工件的同一道工序在同一时刻只能被一台机器加工；(4) 每个工件在工序上的加工顺序相同，工序顺序是预先确定的；(5)至少有一道工序中存在多台并行机器，工序的加工时间随加工机器的不同而不同；(6)工件在一道工序上完成加工后，在下游工序机器可用之前都将被阻塞在该道工序机器上．为方便讨论起见，引入如下数学符号：定义问题涉及到的工件数为n，机器数为m，工序数为l；第k道工序的并行机器数为pk（k=0;1;¢ ¢ ¢;l¡1）；Ti; j表示工件Ji（i =0;1;¢ ¢ ¢;n¡1）在机器Mj（j =0;1;¢ ¢ ¢;m¡1）上的加工时间；Si;k 为工件Ji 在工序k的开始加工时间；Ci;k 为工件Ji 在工序k的完工时间；Cmax为最大完工时间，Cmax=max(C0;l¡1;C1;l¡1;¢ ¢ ¢;Cn¡1;l¡1)；Rj 表示机器Mj 被释放的时间．问题假定所有工件在0时刻都可以被加工．本文给出BHFSP的数学模型：minCmax(1)s:t:pk¡1åj=0xi;k; j =1;i =0;1;¢ ¢ ¢;n¡1; k=0;1;¢ ¢ ¢;l¡1 (2)xi;k; j =8<:1; Ji在第k道工序使用第j个机器加工0; 否则06n¡1åi=0yi; j;t 61; j =0;1;¢ ¢ ¢;m¡1 (3)yi; j;t =8<:1 t时刻机器Mj加工工作Ji0 否则Si;k=max(Ci;k¡1;Rj); i =0;1;¢ ¢ ¢;n¡1;k=1;2;¢ ¢ ¢;l¡1; xi;k+1; j =1 (4)Ci;k=Si;k+Ti; j;xi;k; j =1 (5)其中，式(1)为问题的目标，式(2)限制了同一工件在同一工序中只能由一台机器进行加工，式(3)确定了同一时刻同一台机器只能加工一个工件，式(4)、(5)确定了具有阻塞限制的工件在各工序进行加工时开始时间和完工时间具有的约束关系．

3 基于BHFSP的HPSO算法（HPSO algo-rithm based on BHFSP）

3.1 粒子编码方法

文[12]提出了一种矩阵编码方法，利用矩阵形式表示工件在各工序的机器分配情况．本文借鉴了该方法对粒子进行编码，编码形式为An£l =264P0;0 P0;1¢ ¢ ¢ P0;l¡1P1;0 P1;1¢ ¢ ¢ P1;l¡1. .....Pn¡1;0 Pn¡1;1¢ ¢ ¢ Pn¡1;l¡1375254 信 息 与 控 制 42卷其中，矩阵An£l 的行代表工件，列代表加工工序；Pi;k 为正整数，表示工件Ji 在第k道工序加工时所分配的机器；若Pi;k =Pd;k，则说明工件Ji 与Jd 在第k道工序使用同一台机器加工；Pi;k 的取值范围可由式(6)给出：8><>:[0;p0¡1]; k=0"k¡1åt=0pt;k¡1åt=0pt +pk¡1#; k=1;2;¢ ¢ ¢;l¡1(6)

3.2 群体初始化算法随机产生每个工件在各工序的加工机器，从而完成种群初始化．式(7)描述了随机产生各工序加工机器的方法：Pi;k=mod(frand;pk) +k¡1åt=0pt(7)其中，frand 为随机整数生成器．粒子位置矩阵和速度矩阵的生成方法一致．由于算法随机生成工序，因此在初始化时可能存在在某道工序中，工件被集中分配到某一台或多台机器上而有的机器未被分配的情况，这势必会影响工件并行加工程度．为了避免此现象，在初始化种群后对每一个粒子做初步调整，调整步骤为：步骤1 记录某工序中并行机器集合S，粒子在该工序中已分配出去的机器集合N．步骤2 若9x（x2S^x= 2N），则说明机器x未被分配，将x置于集合O．步骤3 若O6=f，转步骤4；否则，转步骤5．步骤4 从已分配的机器中，选择机器Ni，满足式(8)：8Ni; Ni 2N^(LNi=max(LNc)jc6=i)^LNi6=1 (8)从集合O中取出Oj 2O，从Ni 分配的工件中随机挑选一个工件，以Oj 取代Ni，同时将Oj 从O中删除，转步骤3．Lx 代表某道工序中使用同一台机器x的工件数．步骤5 调整结束，返回调整后的粒子群体．

3.3 RB算法对工件排序方法粒子的编码初步解决了BHFSP的机器分配问题，RB算法主要解决工件的排序问题．RB算法的基本思想为：逐工序对加工工件进行排序．从最早工序开始，若某道工序尚有空闲机器，则选择工件占用机器加工；若该工序中所有并行机器都被占用且该工序中存在未加工工件，则选择一个已加工工件占用下游工序机器，同时释放上游工序机器；算法进行回推处理，回推到上一工序，对释放的机器按照完工时间最早优先（completion first process first，FCFP）策略安排工件加工．算法通过实行“加工上游工件—选择工件占用下游机器—释放上游机器—回推并安排上游工件加工”的算法步骤，直至所有工件在所有工序加工完毕为止．RB算法的处理过程如下：步骤1 对第0道工序做初始处理．从S0 中取出机器x，若Lx=1，则说明机器x只分配给了一个工件Ji（Ji 满足Pi;0=x），使工件Ji 占用机器x进行加工；若Lx >1，说明机器x被分配给了多个工件，若机器目前未被占用，则将机器x分配给工件Ji，Ji满足式(9)；若该机器已被占用，则直接返回，并从S0 中取出下一个机器：8i; Pi;0=x^Ti;x=min(Tt;xjt 6=i; t =1;¢ ¢ ¢;n) (9)重复此步骤，直到S0=f．对当前处理工序G执行步骤2～4．步骤2 按照FCFP选择工序G中的工件加工．若工序G中，存在未加工工件，则转步骤2.1；否则，转步骤4．步骤2.1 加工该工序工件．若工序G中存在空闲机器，则选择工件占用机器，返回步骤2；否则，转步骤2.2．步骤2.2 处理下游工序．若下游工序中存在可用机器，则按照FCFP策略选择在该工序已完工的工件占用下游机器，同时释放其占用的该工序机器，转步骤3；否则，转步骤2.2继续往下游寻找空闲机器．工件的完工时间可由式(10)计算，工件释放机器的时间由式(11) 计算．由于问题带有阻塞限制，因此，工件开始加工的时间与机器释放时间、工件在上一个工序的完工时间有关：Ci;d =max(RPi;d;Ci;d¡1) +Ti;Pi;d(10)Rj =Si;d; Pi;d¡1=j (11)步骤3 算法执行回推处理．从第一个存在可用机器的工序起，若该工序为非G工序，且存在未加工工件，则按照FCFP策略选择工件占用机器，同时释放其占用的上游工序机器，转步骤3；否则，若该工序为G工序，则转步骤2．步骤4 所有工件在该工序加工完毕，G=G+1．若G6=l¡1，转步骤2；否则，算法结束，退出．

3.4 粒子更新方法记Pi 为第i 个粒子的当前最优机器分配矩阵，记Pg 为所有粒子到目前为止找到的最优机器分配2期 张其亮，等：带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法 255矩阵．由于采用特殊的编码方式，若按基本粒子群优化算法，其速度、位置难以表达．因此，修改速度、位置更新公式为式(12)、(13)，­代表交叉操作：Vi(k+1) =Vi(k)­Pi ­Pg(12)Xi(k+1) =Xi(k)­Vi(k+1) (13)利用RB算法对交叉后产生的2个后代个体进行工件排序，并计算问题适应值，更新后的速度和位置矩阵取适应值Cmax较小的后代个体．对于粒子更新公式中的交叉操作，本文提出采用列交叉的方法．图1、2显示了2个个体的交叉过程．2个个体交叉时，随机产生交叉点，图1中交叉点在第2列，个体1和个体2互换交叉点右侧所有列的内容，交叉产生后代1和后代2，如图2所示．图1 原始个体Fig.1 Original individuals图2 交叉后个体Fig.2 Individuals after crossover

3.5 极值更新方法粒子在2个“极值”的引导下，不断更新自己，从而向最优位置靠近．定义1 粒子停滞状态：在更新粒子Pi 时，若粒子个体极值在若干代内没有改进，则称粒子进入停滞状态．定义2 粒子群早熟收敛状态：在更新Pg 时，若粒子群全局极值在若干代内没有改进，则称粒子群陷入早熟收敛状态．粒子进入停滞状态或粒子群出现早熟收敛，必须进行改进，否则算法很难寻找到最优解．本文提出对停滞粒子和粒子群全局最优位置Pg 进行变异的方法来进行改进．变异方法为：依次从所有工件中随机选取一个工序，将工件在该工序的加工机器用该工序中其它并行机器进行替换．变异过程如图3所示：随机选择第2个工件的第3道工序，将其分配的机器6变异为7，变异后的机器要满足式(6)限定的范围．图3 粒子变异过程Fig.3 Mutation process of the particles3.6 HPSO算法流程综上所述，应用HPSO算法求解BHFSP的基本流程为：(1)参数设置．算法用到的主要参数包括种群大小p、最大迭代次数g．(2)种群初始化．随机产生粒子的位置矩阵和速度矩阵，矩阵大小由问题的工件数n和工序数l确定．同时，对产生的位置矩阵和速度矩阵进行初始调整，以增加机器的并行性．(3)若当前迭代次数小于g，则循环执行步骤(3)～(5)，直至算法运行到指定的代数．(4)利用RB算法对工件排序，计算粒子的适应值．结合3.5节方法更新粒子的个体极值和全局极值．(5)利用式(12)、(13)以及3.4节交叉方法更新粒子位置和速度．将当前迭代次数加1．输出Pg 对应的Cmax值，Cmax即为所求得的该问题最小化最大完工时间．

4 实验结果及分析（Experiment results andanalysis）

为验证算法的可行性和有效性，本文选取了2组具有代表性的标准数据进行测试．算法基于VC++6.0实现，在处理器为Pentium 1.6GHz，内存为1.5GB的PC机上运行．算法的关键参数p=30，g=10 000．

4.1 实例

1实例1数据来源于文[13]，对应于一个复杂的列车线路，有12辆列车顺序经过，该线路中有3个轨道区段，每个轨道区段的并行轨道数分别为3、2、4．256 信 息 与 控 制 42卷采用HPSO算法对实验数据独立运算10次，在最大迭代次数g分别为100、500和10 000时统计结果如表1所示．由表1可以看出：当g=100时，计算得到的最小化完工时间为27，平均解为28，实验计算10次平均耗时4 s；当g=500时，计算得到的最小化完工时间为27，平均解为27.7，实验计算10次平均耗时19.5 s；当g=10 000时，计算得到的最小化完工时间为26，平均解为26.8，实验计算10次平均耗时170 s．随着迭代次数的增加，算法得到平均解的质量有所提高，但是计算时间明显增加．算法所得最优解Cmax=26对应的甘特图如图4所示．表1 计算结果统计Tab.1 Statistics of computing results次数 1 2 3 4 5 6 7 8 9 10Cmax（g=100） 27 29 29 28 28 27 29 27 28 28Cmax（g=500) 29 27 27 28 27 28 27 29 27 28Cmax（g=10 000） 27 27 26 28 27 26 27 27 26 27图4 实例1最优调度甘特图Fig.4 Best scheduling Gantt chart of Problem 1为进一步验证算法的有效性，将本文算法与GA[13]、SPGA[14]、分布式方法[15]、PSO[16]进行了比较，算法独立运行10次，比较结果如表2所示．表2 基于实例1的结果比较Tab.2 Result comparison of Problem 1算法 最优解 平均解GA 29 29.4SPGA 29 29.1分布式方法 27 ¡PSO 26 27.2本文 26 26.8表2实验结果比较，证明了本文算法解决BHFSP是有效的，算法较GA、SPGA、分布式方法、PSO等的求解质量更高．

4.2 实例

2实例2的规模较大，其数据来源于文[12]，有12个工件、4道工序，分别表示钢铁生产过程中的炼钢–精炼–铸造–轧制四个阶段，各阶段之间不存在缓冲区，工件的加工带有阻塞限制．每道工序中并行机器数分别为3、3、2、2．算法独立运行10次，得到的最优解为301，平均耗时190 s，最优解对应的甘特图如图5所示．图中数字(i; j)分别表示工件编号和完工时间．文[12] 使用遗传算法对相同的数据进行求解，得到的最优解为347，执行时间约为70 s；本文算法得到的最优解为301，平均执行时间约为190 s．由此可见，本文算法在求解质量上优于遗传算法，但在求解速度上还需进一步提高．

5 结语（Conclusion）

本文针对BHFSP，提出一种混合粒子群优化算法进行求解．算法利用矩阵编码方式解决并行机器分配问题，利用RB算法解决工件排序问题，利用粒子群优化算法进行全局搜索．同时，为了避免粒子群过早陷入局部收敛，对停滞粒子和已陷入局部最优的全局最优粒子进行变异，以增加种群多样性．经实验证明，本文提出的混合粒子群优化算法能够较好地解决带有阻塞限制的混合流水车间调度问题．2期 张其亮，等：带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法 257图5 实例2最优调度甘特图Fig.5 Best scheduling Gantt chart of Problem 2

参考文献（References）[1] Salvador M S. A solution to a special class of flow shop schedul-ing problems[C]//Proceedings of the Symposium on the Theoryof Scheduling and Its Applications. New York, USA: Springer,1973: 83-91．[2] Gupta J N D. Two stage hybrid flow shop scheduling prob-lem[J]. Asia-Pacific Journal of Operational Research, 1988,39(4): 359-364.[3] 陈璐，奚立峰，蔡建国，等．一种求解带有阻塞限制的混合流水车间的禁忌搜索算法[J]．上海交通大学学报，2006，40(5)：856-859．Chen L, Xi L F, Cai J G, et al. A tabu search algorithm for hy-brid flow shop problem with blocking constraints[J]. Journal ofShanghai Jiaotong University, 2006, 40(5): 856-859.[4] Tavakkoli-Moghaddam R, Safaei N, Sassani F. A memetic al-gorithm for the flexible flow line scheduling problem with pro-cessor blocking[J]. Computers & Operations Research, 2009,36(4): 402-414.[5] Zhang Y, Wang S M. The research of trailer scheduling based onthe hybrid flow shop problem with blocking[C]//Proceedings ofthe 7th World Congress on Intelligent Control and Automation.Piscataway, NJ, USA: IEEE, 2008: 3936-3940.[6] Yuan K, Sauer N, Sauvey C. Application of EM algorithm tohybrid flow shop scheduling problems with a special block-ing[C]//Proceedings of the 14th IEEE International Conferenceon Emerging Technologies and Factory Automation. Piscat-away, NJ, USA: IEEE, 2009: 1-7.[7] Thornton H W, Hunsucker J L. A new heuristic for minimalmakespan in flow shops with multiple processors and no inter-mediate storage[J]. European Journal of Operational Research,2004, 152(3): 96-114.[8] Zandieh M, Rashidi E. An effective hybrid genetic algorithmfor hybrid flow shops with sequence dependent setup times andprocessor blocking[J]. Journal of Industrial Engineering, 2009,4(8): 51-58.[9] Gicquel C, Hege L, Minoux M. A discrete time exact solutionapproach for a complex hybrid flow-shop scheduling problemwith limited-wait constraints[J]. Computers & Operations Re-search, 2012, 39(3): 629-636.[10] 宋存利，时维国．求解车间调度问题的2阶段混合粒子群优化算法[J]．信息与控制，2012，41(2)：193-196,209．Song C L, Shi W G. A two stage hybrid particle swarm opti-mization algorithm for job-shop scheduling problem[J]. Infor-mation and Control, 2012, 41(2): 193-196,209.[11] Yaurima V, Burtseva L, Tchernykh A. Hybrid flow shop withunrelated machines, sequence-dependent setup time, availabil-ity constraints and limited buffers[J]. Computers & IndustrialEngineering, 2009, 56(4): 1452-1463.[12] 崔建双，李铁克，张文新．混合流水车间调度模型及其遗传算法[J]．北京科技大学学报，2005，27(5)：623-626．Cui J S, Li T K, Zhang W X. Hybrid flow shop scheduling modeland its genetic algorithm[J]. Journal of University of Scienceand Technology Beijing, 2005, 27(5): 623-626.[13] 王万良，姚明海，吴云高，等．基于遗传算法的混合Flow-shop调度方法[J]．系统仿真学报，2002，14(7)：863-869．Wang W L, Yao M H, Wu Y G. Hybrid flow-shop schedulingapproach based on genetic algorithm[J]. Journal of System Sim-ulation, 2002, 14(7): 863-869.[14] 王金鹏，朱洪俊，周俊．最优子种群遗传算法求解柔性流水车间调度问题[J]．计算机应用研究，2012，29(2)：442-444．Wang J P, Zhu H J, Zhou J. Optimal sub-population genetic al-gorithm for flexible flow shop scheduling problem[J]. Applica-tion Research of Computers, 2012, 29(2): 442-444.[15] Zou F X, Zeng L L, Gao Z. A distributed approach to solv-ing hybrid flow shop scheduling problem[C]//Proceedings of theControl and Decision Conference. Piscataway, NJ, USA: IEEE,2009: 2457-2461.[16] 周辉仁，唐万生，魏颖辉．基于微粒群算法的柔性流水车间调度优化[J]．中国机械工程，2010，21(9)：1053-1056．Zhou H R, Tang W S, Wei Y H. PSO-based optimization offlexible flow-shop scheduling[J]. China Mechanical Engineer-ing, 2010, 21(9): 1053-1056.