论文研究-基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题.pdf

所需积分/C币:37 2019-09-20 18:21:09 1.28MB .PDF

论文研究-基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题.pdf,  针对以最小化最大完工时间为目标的无等待柔性流水车间调度问题,提出了一种混合粒子群-NEH算法.该算法 利用粒子群优化算法解决机器分配问题,并进行全局优化;利用改进的NEH算法确定工件加工顺序,并首次提出差值 平移算法计算问题目标值.在算法求解过程中,通过不断对停滞粒子实行变异操作,避免粒子群陷入早熟收敛状态.基
804 系统工程理论与实践 第34卷 矩阵Onx入的一行代表一个工件,一列代表一道工序.因此,对丁具有n个工件、入道工序的 NWFFSP 来说,编妈矩阵的大小为nxA.B,k为一止整数表示件在序k加」时分配的机器.若Pk=P,k, 则说明工件J与J在工序k加工时使用同一台机器.按照工序的先后顺序对工序中的并行机器进行升序 编号,对任一序k(0≤k≤A-1),该序中的机器范围可由公式(2)给出.例如,一个 NWFFSP中有3 道工序,第0道工序有4台并行机器,第1道工序有3台并行机器.第2道工序有2台机器,即:πo=4, π1=3,丌2=2.根据公式(2).第θ道工序中可选择的加工机器编号为0、1、2、3;第1道工序中可选择的加 ⊥机器编号为4、5、6;第2道『序屮可选择的加机器编号为7、8. 0,rk-1],k=0 y 丌,>++丌k-1,0<k≤A-1 t=0 给定一个粒子的编码矩阵:O2×2=13,该编码表示问题中有3个工件,2道工序,第0个工件 03 在第0道工序和第1道工序分別使用机器0、机器2进行加工:第1个工件在第0道工序和第1道工序分 别使用机器1、机器3进行加工;第2个工件在第0道工序和第1道工序分别使用机器0、机器3进行加工 通过矩阵形式可以很清晰地表示机器的分配方案 312种群初始化 粒」群初始化主要是随机产生粒」的位置和速度矩阵.矩阵中的机器编号必须满足公式(2)限定的范 围.种群初始化时产生的机器分配方案可由公式(3)给出 P.k=70d0%丌k,=0,1,……,m-1;k=0 Pk=7070(%xk+∑m,=0,,…,n-1;k=1,2,…,A-1 公式(3)根据公式(2)限定的机器缩号范围随机产生上件J在第k工序的加工机器.其中.rad()%丌k 随机产生0,π之间的数;∑=0π的值为0~(-1)工序中的机器总数,由丁机器编号从0开始,因此该 值亦即第k道序中最小的机器编号.由于随机产生的数据存在不确定性,可能会存在某一工序中,所有⊥ 件或绝大部分工件都被分配使用某几台机器进行加工而该工序中有的机器相对空闲的情况,如上例中产生 的编码矩阵变为O3x2=03第0道工序所有工件使川机器0进行加工,而机器1空闲此类情况的 发生会影响到解的质量,必须进行调整 定义1在某道工序中,被分配加工工件数最多的机器称为瓶颈机器 存在瓶颈机器的工序,必须对机器分配方苿进行调整,消除瓶颈.消除瓶颈的过程为: 步骤1对工序k(k=0,1,…,λ-1)中的机器按照其被分配加工工件的多少从大到小进行排列,记排 列为{M0,M1,…,Mx},对应的加工工件集合分别为{Go,G1,…,Gr} 步骤2加工工件数最小的机器M对应的加工工件数为△加工工件数最大的机器M0对应的加工 工件数为Δ.若满足Δ≤n/k-1.则转步骤3:否则k=k+1,若k=λ,转步骤4;否则转步骤1继续进 行操作 步骤3从(中随机选取一个工件J,将五在第k工序使用的机器Mo调整为Mn,Go Gnk=Gn+J,△=△+1,△′=△-1.转步骤1 步骤4操作结束 其中,η/πk表示第k个序中,每个机器加匚件数的平均值通过与该值进行比较、调整.可使每台 机器分配的工件数均衡化 31.3位置更新公式 粒子群算法的实质是每个粒子在飞行过程中.不断通过粒子本身找到的最优位置和整个种群找到的最优 位置调整自已的速度和位置.从而向最优位置靠近.本文釆川离散整数编码形式,若川标准粒子群算法的速 度、位置更新公八,难以对问题进行表述.为此,本文修改速度、位置更新公式如下: Vi(k+1)=Vi(k)s Pbest, S best 第3期 张其亮等:基于混合粒子群-NFH算法求解元等待柔性流水车间调度问题 805 Xn(k+1)=X(k)V2(k+1) V(k)、X(k)分别表示粒子在第k次迭代的速度和位置:Pest、9hest分别表示粒子x和整个种群到 日前为止找到的最优位置;⑧代表交叉操作.对于粒子更新公式中的交叉操作,本文提出采用列交叉的方法 随机产生交叉点?(0<γ<m-1),对实行交叉的两个体,互换?列分界点右侧或者左侧部分内容,得到交 叉后的两个个体图2、图3显示了两个体的交叉过程.为了加快收敛,保留交叉后适应值较小的个体继续进 行运算,丢弃其它个体 交叉点 04|7836 020104 个体1 图2原始个体 6 代1 图3列交叉后产生的个体 31.4粒子“极值”更新方法 粒子i在个体极值Pυesε和全局极值shεs的引导下,逐步向最优位置靠近.随着迭代次数的增加,种群 多样性在快速下降,使粒」难以跳出局部极值的约束而陷入早熟收敛状态,难以找到全局最优解.为此,引入 变异机制对停滞粒子进行变异,增加科群多样性. 粒子一次迭代后,更新个体最优位置 Pbest,若Pes在若代内未改进,则认为该粒子已经停滞.改变 粒子停滞状态的方汰为对粒子进行变昴,变异策略为:对编码矩阵的每一行,随机选取一列,将该列所对应的 机器用所在工序中的其它机器替换.变异后的粒子对应的解可能比原来差,本文釆用模拟退火思想概率接收 即:计算变异后粒子和变异之前粒」解的变化量△E,若△E≤0,接收新值;若exp(-△E/T)>7amd(0.1) 也接收新值;否则拒绝.其中,T表示退火温度,rand(0,1)生成0~1之间的随机数 若种群最优位置gwκst在若T代内未改进,则认为种群已陷入早熟收敛状态.增加种群多样性的方法为 1)对9est进行变异,新的‘极值”会引导种样跳出局部极值的约束;2)对种群进行变异,即对种群中目标值 最低的一定比例粒子进行变异 32NEH算法 粒子群优化算法解决了工件在各工序上的机器分配问题,但并未安排工件的加工顺序,本文提出改进的 NEH算法予以解决 321基本NEH算法 NFH算法是一种构造性启发式算法,在求解流水车间调度问题中具自较高的效率.基本NFH算法 的步骤如下 步骤1按照工件在机器上加工的总时间对工件进行降序排列 步骤2对开始的两个工件进行排列,取目标值较小的排列作为初始排列 步骤3对k=2,3,…,n-1,执行步骤4 步骤4将第k个上件插入到前面k个可能的位置,取目标值较小的排列作为新的排列,转步骤3执行, 直至所有工件加工完成 322NEH算法的改进 NWFFSP屮存在并行机器,多个工件可能并行加L,因此件的加工顺序很难用一个排列表示.本文根 据NEH算法的思想对NEH算法进行了改进 定义2对于工件J、J1:若两个工件在入道工序上加工时所分配的机器完全不一致,则称J、1互为 全并行工件.互为全并行的两个工件可以并行加工 改进的NFH算法首先选取完工时间最小的工件以及与其互为仝并行的工件进行加工,对剩余的工件, 选取的策略为:该工件被加工片所得到的完工时间最小.改进N上H負法的伪代码描述如下: 806 系统工程理论与实践 第34卷 定义变量 CONT0COUN7表示已完成加工的工件数 Complete fagIn/工件完工标志,初始为alse C marn/∥/当前完工时间 钔入:粒子編码矩阵 出:加上顺序和最小完工时句 (1)查找在所有工序加工时间总和最小的工件 min work 2)查找与 互为全并行的工件 sec work (3)使工 f-min work完成加工,记录工件加工时在各工序的川始加工时间 S、完工时间C、释放机器时间R 记录mwnk的 Complete1ag标志为rue 存在)the 使T件 sec work成加工,记录工件加T时在冬T序的开始加工时间 S、完「时间C、释放机器时间R; COUNT2 记录ewrk的 Complete /lag标志为u AUNT (5 whilc(coux7不等于n)do for i=0 to n-I do if( Complete flagii/)false)then 使工件加1,计算完后完工时间Cmax记录件加时在 各工序的开始加工时间S、完工时问C d for j=0 to n-1da begin 查找 Complete ag// false HC muxii/最小的工件,记工件为k; 计算k加时在各工厅释放机器时间R 置工件k的 Camplete flag为tmue for i=0 to n-l do if(o flag为 对C ⊥mmxD/、S 清零 end 输出加工顺序和最小完工时间 d 323问题目标的计算 当确定了L件在各工序的加」机器和加L顺序后,可以计算问题的目标值文献[12给出了最大完⊥时 间的计算公式,E()为相邻两工件J-1与J由连续生产的要求而引起的开工时间之差 F() max 1),k 1<k<A-1 (-1),0 ∑M)= 4k=C(-1,0+∑A+E(),=1,2 -1:k=0.1 入-1 该方法计算完工时间的算法复杂度为O(n22).但由于 NWFFSP的特殊性,可能存在多个工件并行加 工的情况,公式(6)、(7)在某些情况下已不再适应.为此,本文提出一种基于差值平移的快速算法计算问题 的完工时间 性质1假定初始状态时,对任意机器M2,∈0.,m-1],有R=0.在加过程中若件在任意 工序k.k∈0,A-1],满足fA=0,则该工件在各工序加工的开始时间S;,k、完工时间C,与已加工完毕 的工件不存在任何关系 性质2假定初始状态时、对任意机器M,j∈0,m-1],有成=0.在加工过程中若工件在任意 工序k,k∈0.A-1]满足R2≠0,则必定存在一个工序dd∈0,A-1])满足:S=Cd=R,,t为在 a工序与工件使用相同机器、相邻且已加工完毕的工件 提出的基于差值平移算法计算完工时间的基本思想为:1)若工件J(∈0,n-1)满足性质1的条件, 则根据性质1可直接计算出工件在各工序的廾始时间、完工时间和释放机器时间,计算公式为 第3期 张其亮等:基于混合粒子群-NFH算法求解元等待柔性流水车间调度问题 807 C0=A2 C;=C;-1+41,,j=1,2,…,A-1 1,2,……,入-1 C 0.1 入-1 (12) 2)若工件∈0,n-1)满足性质2的条件,则首先找到满足Pn1≠0的工序k,计算在工序k 的开始加工时间、完上时间,计算公式如下: S2k=Rp,k:k∈[0,-1 (13) =51,+A,k,k∈0,A-1 (14) 根据工件连续加工的特点,可推算出J在间0,k-订和+1,λ-1工序的开始加工时间、完工时间 但是,通过该步骤推算出的工件在各上序的加L时间可能与其它上件存在冲突,必须检测出冲突,进行调整 性质3若一·台机器加工的两相郐工件存在加工时间上的重叠,则认定两工件在该机器上加工时存在冲 突,重叠时间即为冲突时间 解决工件加工冲突的方沄为:计算工件J在λ道工序中与其它工件的最大冲突时间△,将该工件按照 时间轴方向平移△单位图4演示了基于差值平移算法检测冲突和消除冲突的方法 机器0 工序0 机器1 I1 工字0 机器2 机器 n 机器3 机器3 +11.2 机器 器4 i+1 工应3 1234567891011121314 1234567891011121314151 (a)冲突检测 (b)差值平移消除冲突 图4差值平移算法处理过程 图4a)屮的阴影部分为工件冲突时间,根据性质2.使S+1,1=C.1,推算出J2+1在各工序的加工时间 但在工序2和工序3加工时与存在冲突,冲突时间分别为1个时间单位和2个时间单位.取最大冲突时 间,即2个时间单位,将J+1的加工过程按时间轴方向平移2个时间单位得到图4(b)满足生产约束差 值平移算法的伪代码描述如下 33算法关键操作复杂度分析 /检测工件沖突并进行调整 在第k个工序为工件J分配机器的复杂度为 定义 chachi为工件在各工序的差值 for i=0 to / du O(xk).因此为n个工件在λ道工序分配机器的复杂 度为O(m∑k-m)=0(mn考虑种群规模POP 甙t所用机器的释放时间为 Othen i(T件在T序的开始加T时间≥0) 产生初始种群的复杂度为O( mn POP,消除瓶颈的 contiue;继续执行下·循环 复杂度为 O(mnPOp).粒子群优化算法中,变异操 else在突 作只在粒子停滞时执行,在此只计算执行·次变异操 chah=ah(工件工序的开始加工时间 /取绝对值 作的时间复杂度为O(m).改进NEH算法的时间复 else 杂度为O(m2).算法计算问题目标的复杂度为O(n入) 件在序的开始加工时间≥在/序所用机器 的释放时间)then 综合混合算法的工件排列、机器分配和计算问题目标 continue;/继续执行下一循不 等过程可见,本文所提混合粒子群NFH算法的问题 else/存在冲突 复杂性并不大 chazhili- fab(工件在工序的开始加工时间-在 工序所用机器竹释放时间) 4算法性能测试 d 突调整 算法基于VC++60实现在处理器为 Pentium 从 chazh中找到最人的差值△ 16GHz,内存为1.5GB的PC机下运行.算法设置的 ※工件按时间轺方向平移Δ单位,即:工件的开始加工时 间、亢工时间增加A 粒」群规模为30.,迭代次数为1000 4.1实例测试 由于目前对该类问题的研究较少,没有统一的数据进行测试.有些文献屮没有给出测试数据、有些文献 中的数据随机产生,很难找到统一的测试数据标准为验证算法求解该类问题的有效性,本文选取了3组文 献屮提供的具有代表性的测试数据对算法进行了测试 系统工程理论与实践 第34卷 实例1数据来源于文献[3].有12个工件、4道工序,每道工序分别有3/3/2/2台并行机器.利用本文 提出的 PSO-NEI算法对实例独立计算10次,得到问题的最优解为317.所得最优解对应的甘特图如图5 所示,图中相邻数字、j中,代表工件编号.j代表加工时间 实例2数据米源亍文献[4.,有12个工件、3道工序,每道工序中并行机器数分别为3/2/4.利用本文 提出的 PSO-NEH算法对实例独立计算10次,得到问题的最优解为26.所得最优解对应的甘特图如图6所 示,图中数字代表工件编号 机器 10,46 348 5.35 机器2 1.4 050 931 7,48 机器 机5 3,35 2,36 135 机器5 1.35 8,34 9.35 6.31 7,30 3,271,25 2,30 825 9,31 7,24 机器9 10,25 5.26 4,31 25 102030405060708090100110120130140150160170180190200210220230240250260270280290300310317 图5实例1最优解甘特图 b器10 10 9 器 2 七器 6 3 杭器7 8 b浴 5 34567891C1112131415161718192021222324 图6实例2最优解甘特图 实例3数据来源于文献[1,有12个工件、3道工序,每道工序中并行机器数分别为3/3/3.利用木文 提出的PSO-NBH算法对实例独立计算10次,得到问题的最优解为25.所得最优解对应的甘特图如图7所 示,图中数字代表工件编号. 界00 2 b器3 2 器5 机器6 6 2 7 器7 0 8 机器8 678910111213141516171819202122232425 图7实例3最优解甘特图 4.2算法比较 将本文提出的算法与其它几种使用相同数据、已公开发表的具有代表性的方法进行比较.比较结果如表 1所示,符号“-”表示算法未对该问题进行求解 文献[13使用遗传算法进行求解,在解决实例1时,得到的最优值为347而本文算法得到的最优值为 317,明显优趑;文献14使用遗传算法、文献15使用粒子群优化算法对实例2进行了求解,得到的最优解 分别为29、26,本文算法得到的最优解为26.优于文献14],与文献[15]一致,但平均解要优于文献15]:文 献[16提出一种改进的量子粒子群优化算法对实例3进行了求解,得到的最优解为27,而本文算法得到的 最优解为25 从上述比较可以看出.在求解问题的质量上,本文算法是优越的.所引用文献屮并未给出算法求解时的 处理时间表2只列出了本文算法获得最优解的最小计算时间和最少迭代次数.从表2可以看出,本文所提 算法能在较短时间内得到较好的解,算法具有较快的收敛性. 第3期 张其亮等:基于混合粒子群-NFH算法求解元等待柔性流水车间调度问题 809 表1算法比较结果 表2算法得到最优解的计算 问题工件数各工序机器数文献13]文献[1文献[15]文献16本文 时间和迭代次数 实例11233,2,2 317 问题计时间选代 实例212 3,2,4 (单位 次数 实例312 实例1 25 3,3.3 实例2 平均解 29427227317/26.9/258实例316 368 5结束语 针对兀等待柔性流水车问调度问题、提出了一种混合 PSO-NEH算法将该类问题的求解分为三步:首 先利用粒子群优化算法进行机器分配:然后利用改进的NEH算法安排工件加工顺序,并提出差值平移算法 计算问题目标值:最后利用粒子群优化算法进行全局优化、仿貞实验证明了所得算法的有效性 参考文献 ]朱夏,挛小平,王茜.基于总空內时间増量的无等待流水调度混合遗传算法团.计算机研究与发展,2011,48(3):45- Zhu Xia, Li Xiaoping Wang Qian. Total-idle-time increment based hybrid Ga for no-wait flowshop with makespan minimization[J.ournal of Computer Research and Development, 2011, 48(3): 455 463 2 Gupta D. Two-stage, hybrid flow shop scheduling problem(J. Operations Research, 1988, 39(4): 359-364 3 Rock H. The thrcc-machinc no-wait flowshop problem is NP-complctcJ. Association for Computing Machincry, 1984,31(2):336345. 4士利,土梦光.基丁准时制的零等待混合 Flow Shop调度问题[.东北大学学报:自然科学版,198,19(4):349-351 Wang li, Wang m brid flow shop scheduling problem based on just in timeJ. Journal Northeastern University: Natural Science, 1998, 19(1):319-35 阿]轩华,唐立新实时元等待HFS调度的一种拉格朗日松弛算法[.控制与决策,200621(4):376380 ang Lixin. Lagrangian relaxation algorithm for real-time hybrid flowshop scheduling with no-wait J. Control and Decision, 2006, 21(4): 376-380 6]李建唐立新吴会江·带运输和设时间的无等待并行流水车间调度问题研究J.系统工程理论与实践,200626(1): Li Jianxiang, Tang Lixin, Wu Huijiang, No-wait parallel Howshop scheduling with transfcr and setup times[ J ysteIns Engineering- Theory &e Practice, 2006, 26(1): 18-25 7李,李铁克基丁约束规划的无等待混合流水有间调度问题研究J.化工自动化及仪表,2007,34(3):26-29 Li Yan Li Tieke. Research on no-wait hybrid flowshop scheduling problem based on constraint programming Control and Instruments in Chemical Industry, 2007, 34(3): 26-29 8Jolai F, Shaikh S, Rabbani M, ct al. A genctic algorithm for solving no-wait fexible flow lines with duc window and job rejection J. International Journal of Advanced Manufacturing: Technology. 2009, 42 (5 6:523332 9 Garcia J M, Lozano S. Production and delivery scheduling problem with time windows. Computers and Industrial Enginccring, 2005, 48(5): 733-742 l0宋缃伟唐加福基于DPSO的无等待混合流水车间调度方法小].系统仿真学报,2010,22(10):2257-2261 Song Jiwei, Tang Jiafu. No-wait hybrid flow shop scheduling mcthod bascd on discrctc particlc swarm optimiza- tion[J] Journal of System Simulation, 2010, 22(10): 2257-2261 [11 Nawaz M, Enscore E, Ham I. A heuristic algorithm for the m machine, n job fow shopJ. Omega, 1983, 11(1) 12 Grabowski J, Pempera J Some local search algorithms for no-wait How-shop problen with makespan criterionJ Computers and Operations Research, 2005. 32(8): 2197-2212 13]崔建双,李铁克张文新混合流水车闰调度模型及其遗传算法[.北京科技大学学报,20.27(5):623626 Cui Jianshuang: Li Tieke, Zhang Wenxin. Hybrid flow shop scheduling model and its genetic algorithm Journal of University of Scicncc and Tcchnology Bcijing, 2005, 27(5 ): 623-626 14万良,姚明海,吴云高基于遗传算法的混合Flw-shop调度方法小系统仿真学报2002,14(7:863869 Wang Wanliang, Yao Minghai. Wu Yungao. Hybrid flow-shop scheduling approach bascd on genctic algorithm[J Journal of System Simulation, 2002, 14(7): 863-869 1周辉仁:唐万生,魏颖辉基于微粒群算法的柔性流水车间调虔优化J.中国机械工程,2010.21(9):1053-1056 Zhou Huircn, Tang Wansheng, Wci Yinghui. PSO-bascd optimization of flexible flow-shop schcdulingJ. China Mechanical Engineering: 2010, 21(9): 1053-1056 16]宋书强,叶春明.用MC-QPSO算法求解并行流水车间调度问题[.计算机程与应用,2010.46(16):229231 Song Shuqiang, Ye Chunming. Parallel flowshop scheduling problem based on cooperative evolutionary quantum particle swarm optimization algorithm with multi-populationsJ. Computer Engineering and Applications, 2010 46(16):229231

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐