无等待流水车间调度问题的优化.docx

无等待流水车间调度问题的优化国家自然科学基金重大项目(90104010)，博士后科学基金(20070410791)潘全科，1971年生，男，教授，博士后主要研究方向：计算智能及其应用o E-mail: qkpan@赵保华，1947年生，男，教授，博士生导师主要研究方向：软件工程、协议理论与协议工程和无线传感器网络E-mail: bhzhao@屈玉贵，1945年生，女，教授，博士生导师主要研究方向：通信与信息系统、计算机体系结构和通信协议工程等□ E-mail: ygqu@潘全科1，2赵保华1屈玉贵1(1中国科学技术大学计算机科学系，合肥，2300262聊城大学计算学院，聊城，252059 )摘要：研究以生产周期为目标的无等待流水车间调度问题首先，结合问题特征，提出了一种复 杂度为O(n)的快速生产周期算法其次，研究了两种插入邻域结构：基本插入邻域和多重插入邻 域，并提出了快速基本插入邻域算法和最大多重插入移动算法在此基础上，将离散粒子群算法 与上述两种邻域搜索算法相结合，得到了离散粒子群优化调度算法第三，根据问题生产周期的 不规则性，给出了一种通过延长工序加工时间进一步改进调度方案的方法。

最后，仿真试验表明 了所得算法的可行性和有效性关键词无等待流水车间生产周期粒子群算法邻域搜索算法不规则性1引言无等待流水车间(no-wait flow shop，NWFS)调度问题是一类十分重要的调度问题技】，它广泛存在于 炼钢、食品加工、化工和制药等领域已经证明机床数量大于2的NWFS是强NP难题⑶新发展起来的 粒子群算法(particle swarm optimization，PSO)为解决该类问题提供了新思路与进化算法相比，PSO具 有结构简单、容易实现、快速聚合和鲁棒性强等优势性］但连续本质决定了它难以直接求解生产调度这类 复杂的离散问题于是，文献［5-7］结合PSO的优化机理和调度问题的特点，提出了一种离散PSO(Discrete PSO, DPSO)该DPSO采用自然数编码，在离散的解空间内执行粒子更新操作，非常适合于调度问题的求解 在此基础上，本文针对NWFS提出了一种高性能的DPSO调度算法，并结合其不规则特性，提出了通过延 长工序加工时间进一步改进调度方案的方法仿真试验表明了所得算法的可行性和优越性2调度模型2.1问题描述NWFS可描述为：给定m台机床和n个工件，所有工件在各机床上的加工顺序均相同。

同时约定，一 个工件在某一时刻只能够在一台机床上加工，一台机床在某一时刻只能够加工一个工件由于技术条件的 限制，同一工件的加工必须连续完成，即同一工件的相邻工序之间没有等待时间各工序的加工时间已知 问题是如何安排生产，在满足上述要求的条件下得到最小生产周期2.2生产周期的计算由于同一工件的工序必须连续生产的限制，计算NWFS的生产周期不同于一般流水车间调度问题文 献囱给出了 NWFS生产周期的计算公式：令?兀为工件，在机床k上的加工时间，n = {1, ...,i — 1,i,...n}为一个调度，di—1i为相邻两工件，-1和i的开工时间之差(如图1a)所示)；则七i为机床机床a) NWFS调度b)流水车间调度4321图1两工件的NWFS调度和流水车间调度-如p},E⑴i, q i—1,1q=d. . = max{ max {^p.i—1,i 2

因此，可先按照流水车间调度问题求得生产周期，再根据连续生产的要求从后向前依次求得NWFS的各工序开工时间，进而得到di—1i令s*y、;，分别为工序气，的开工、完工时间，求di—1i的算法如下:1)s = 0，c = p ；令 y 从 2 到”，分别计算 S = C ，C =S + p.i —1,1 i —1,1 i —1,1 i —1, y i —1, y—1 i —1, y i —1, y i —1, y2)s「= c ，c =s「+p「；令 y 从 2 到”，分别计算 s. = max{c “ c }，c. =s. + p .i ,1 i—1,1 i ,1 i ,1 i ,1 i, y i, y—1 i—1, y j, y j, y /, y3)令j从m-1到1，分别调整c = s ，s = c - pi, y i, y+1 i, y i, y iy4)di—1,i = Si ,1 ― Si—1,1n的生产周期为上述算法的复杂度为O(m)若将得到的d 代入式(2)，容易求得生产周期，其复杂度为O(nm)因i —1, i为dt 1t共有n(n-1)个，为了提高算法效率，可预先求出所有d^。

这样，在计算生产周期时，电土就可视为常数同样的，§ p也可看作常数于是，式(2)的复杂度就可降低为O(n) n ,kk =13 DPSO调度算法3.1 PSO算法PSO是KENNEDY和EBRHART于1995年提出的在PSO中，粒子代表候选解，具有位置和速度两 个特征从初始群体出发，粒子根据自己和同伴的飞行经验不断调整位置和速度，使整个群体逐渐接近最 佳解PSO的基本步骤为［4：1) 初始化算法参数：惯性系数、社会系数和认知系数2) 初始化粒子群：粒子、个体极值和全体极值3) 循环步骤4)—5)直到满足停止条件4) 对所有粒子执行下列操作：i. 产生新粒子ii. 更新该粒子的个体极值5) 更新全体极值6) 输出全体极值3.2 DPSO 算法PSO是针对连续函数的优化提出的，其位置矢量和速度矢量的编码以及新粒子的产生策略均具有连续 本质，而NWFS是复杂的离散问题，故需要专门设计位置矢量编码及其更新策略位置矢量编码对于NWFS问题，最直接的编码方法就是采用位置矢量的分量代表工件，而粒子本身 表示所有工件的一个排列，即一个调度如表1所示表1位置矢量及对应的工件排列粒子维数123456位置向量x312465工件序列312465位置更新公式 粒子群算法的实质在于粒子根据自己和同伴的飞行经验不断调整位置和速度，从而向最 优位置飞行。

粒子的新位置是粒子的速度、个体极值和全体极值相互作用的结果在位置矢量编码的基础 上，定义粒子更新方法如下：Xk+1 = c2 区 g(c1 区 g(w区hab(Xk),pBk),gBk) (3)式中，Xk和pBk分别为粒子i•在第k次迭代中的位置及其个体极值；gBk为第k次迭代中的全体极值;rand()为区间［0,1］上的随机数；w为惯性系数；c1是认知系数；c2是社会系数上述位置更新公式由3部分构成：，Vk\第1部分为：Ek=w区h (Xk) = J ha,b(XQ rand () < w，表示粒子对自身飞行速度的思考其中，1 a,b 1 Xk rand() > wl ihab(Xk)表示粒子的速度它的实现方法为：先产生两个不同的随机数a和b，然后交换位置矢量的第a、 b分量k mDk\第2部分为Fk = c ® g (Ek, pBk) = F(Ei,叫)rand () q 1Yk = g(Ek,pBk)的实现方法为：先从Ek中随机抽取一段，放在pBk的前面或后面；再从pBf删除重复工件77k cRk、第3部分为Xk+1=c ® g (Fk, gBk) = Jg (Fi , gB ) rand()

i 2 i Fk rand> c 1i2对gBk的局部搜索利用粒子群的优化原理，采用上述离散位置矢量编码并在离散域内执行粒子更新操 作的算法就称为DPSO该DPSO算法虽然收敛快，但求解质量不高分析算法原理知，DPSO的信息传 递是单向的：gBk将信息传给其它粒子，带动其它粒子在较好的区域搜索因此，可通过提高gBk的局域搜 索能力改进算法性能同时，为了防止算法陷入局部最优，需要采取如下措施：1) 先对gBk执行扰动，再对扰动结果执行邻域搜索算法2) 采用概率接收准则接收所得结果，即如式下成立，则用所得结果取代gBk0Rand() < min(1,exp(-A/1)} (4)式中，A为邻域搜索算法的输出结果与gBk的目标值之差，t是温度参数DPSO的实现步骤1) 初始化算法参数：惯性系数、社会系数、认知系数，扰动长度和温度参数2) 初始化粒子群：粒子、个体极值和全体极值3) 循环步骤4)—5)直到满足停止条件4) 对所有粒子执行下列操作：i. 采用式(3)产生新粒子ii. 更新该粒子的个体极值5) 更新全体极值6) 对全体极值执行局部搜索算法7) 输出全体极值3.3邻域搜索算法研究表明，对于作业调度这类复杂问题，插入邻域搜索算法性能较高3］。

本文采用两种插入邻域算法，DPSO的每次迭代随机选择一种执行3.3.1插入邻域及其搜索算法定义1在工件排列中随机选择不同的两位置i、J，把位置i的工序插入位置J，称为插入移动，记为 Insert（i, j）由该移动得到的新排列称为原排列的邻居所有这样的邻居构成插入邻域插入邻域搜索算法如下：1） 令k=1从当前排列中取出第k个工件，将其分别插入另外n-1个位置，并计算生产周期2） k=k+1如kVn返回步骤1）3） 如果邻域内的最优排列优于当前排列，则用其置换当前排列，并返回1）；否则算法结束a）插入工件k前的机床加工任务分配们插入工件k后的机床加工任务分配图2插入工件k前后总流水时间的变化上述邻域算法的复杂度为O（n3）为了提高效率，根据邻域解的相似性可降低其复杂度设含有n-1个 工件的一个排列为｛1,...,i-1,i,...n-1｝，其生产周期为f若将工件k插入位置p后，则所得排列的生产周期 为：f + dk ,1（5）广十 + d ,i + dTk-Lf + "nW Wn』,j +'j=1 j =1采用式（5）计算生产周期，可将插入邻域搜索算法的复杂度降为O（n2）3.3.2块结构及其性质机床图3 NWFS的块结构定义2在同一机床上，四个或四个以上的连续加工的工序称为块。

除去块的第一工序和最后工序后剩 余的工序，称为块内工序定理1改变块内工序所对应工件的次序不会缩短生产周期证明：如图5所示，工序o」2k，0心，Ojk，o.+i k，和Oj+2k构成块生产周期L = li +12 +13改变块 内工序对应工件的加工顺序后，li和13不变，而12不可能减小，故L不会减小根据上述定理，可在插入邻域算法中除去不必要的移动，进一步提高算法效率3.3.3多重插入移动定义3[3]两个Insert移动(v = Insert (x,y和v = Insert (x ,y ))是相互独立的，如果x、y与x、1 '112 '22 1，12y2不相邻，即满足下列三个条件之一max(x , y )。