（计算机应用技术专业论文）双目标无等待流水调度问题的混合算法.pdf

摘要 摘要 最小化“总完工时间”和“最长完工时间”为目标的无等待流水调度是一类典型的n p 完全问 题，广泛存在于：l 程应用中。本文针对该问题研究如何能在较短时间内找到近似最优解的有效混合 算法，对实际工程应用具有重要意义。 考虑最小化“总完工时间”和“最长完工时间”的双口标无等待流水作业调度问题，提出粒子 群加权混合优化算法，通过随机加权的方式将其转换成单目标优化问题，并应用基于升序排列的 r o v ( r a n k e d - o r d e r - v a l v e ) 编码规则，将微粒的位置矢量映射到流水工件的排序，离散化后应用于 无等待流水作业调度问题：应用n e h 方法构造初始种群基于较好的初始值进行粒子群优化；在 粒子群每次迭代之后对全局最优值加入扰动并进行变邻域搜索防j 卜种群陷入局部最优造成早熟收 敛，提高离散粒子群算法的搜索能力：使用交换邻域和插入邻域算子加快算法的搜索速度，进一一步 提高算法搜索的效率，降低邻域搜索算法的复杂度；设计双目标优化中多群体进化操作提高算法的 搜索能力，得到全局近似最优解。 混合优化算法与d p s o 混合调度算法、r a j 算法以及当前已知最好解b e s ( l r ) 在t a i l l a r d b e n c h m a r k 前1 0 0 个标准流水调度问题实例上进行了比较。仿真结果表明：在以总完工时问以及最 长完工时间为目标函数的评价指标中，无论是在所得结果的平均质量、c p u 耗费时间及最优调度的 获取能力等方面该混合调度算法均具有良好的性能，可有效地解决双目标无等待流水调度问题。 关键词：无等待流水调度：交邻域搜索：双目标优化；粒子群算法 东南大学硕士学位论文 a bs t r a c t n o - w a i tf l o w s h o p ss c h e d u l i n gp r o b l e m sw i t hb o t ht o t a lf l o wt i m ea n dm a k e s p a nm i n i m i z a t i o na r e t y p i c a ln p h a r dp r o b l e m ，w i d e l ye x i s t i n gi n i n d u s t r i a le n v i r o n m e n t s t h i st h e s i sm a n a g e st og e t a p p r o x i m a t eo p t i m u ms o l u t i o n sw i t hh i g he f f i c i e n c yf o r t h ec o n s i d e r e dp r o b l e m s ，w h i c hi ss i g n i f i c a n ti n r e a la p p l i c a t i o n s w e i g h t e dh y b r i dp s oa l g o r i t h mi si n t r o d u c e df o r b i - c r i t e r i an o - w a i tf l o ws h o p st om i n i m i z e m a k e s p a na n dt o t a lf l o w - t i m e i ti se s s e n t i a lt oc o n v e r tt h et w oo b j e c t i v e si n t os i n g l eo b j e c t i v ep r o b l e m w i t hr a n d o mw e i g h ti m p o s e do nb o t ho b j e c t i v e s a f t e rd i s c r e f i z a t i o n ，t h ew e i g h e dh y b r i dp s op r o p o s e d i nt h i sp a p e ri sa p p l i e dt on o - w a i tf l o ws h o p sw i t ht h er a n k e d - o r d e r - v a l u er u l e p a r t i c l ep o s i t i o nv e c t o r s a r em a p p e di n t ot h ej o b ss o r t i n go ff l o w s h o p s b yc o n s t r u c t i n gt h ei n i t i a ls w a r mw i t hn e h ，t h e p e r f o r m a n c e sc a nb ei m p r o v e dw i t ham u c hb e a e ri n i t i a lv a l u e t h eg l o b a lo p t i m a li sp e r t u r b e di ne a c h s t e po fp s o t h ev a r i a b l en e i g h b o r h o o ds e a r c hi sp e r f o r m e dt oe s c a p ef r o mt h el o c a lo p t i m a t h e e x p l o r a t i o na n do p t i m i z a t i o na b i l i t yo ft h ea l g o r i t h mc a nb ei m p r o v e d o p e r a t o r s ，s u c ha se x c h a n g ea n d i i 岱e ni n d i v i d u a l si na d j a c e n tn e i g h b o r h o o d , s p e e du pt h es e a r c h i n gp r o c e s sa n dr e d u c et h ec o m p l e x i t y o fn e i g h b o r h o o ds e a r c hs u b s t a n t i a l l y t h en e a r - o p t i m a ls o l u t i o nc a l lb eo b t a i n e db ya d o p t i n gm u l t i g r o u pe v o l u t i o nt ob i - c r i t e r i ao p t i m i z a t i o np r o b l e m s e x p e r i m e n t sa r ep e r f o r m e do nt h ef i r s t10 0i n s t a n c e so ft a i l l a r db e n c h m a r k ，t h es t a n d a r dt e s ts e t f o rf l o w - s h o ps c h e d u l i n gp r o b l e m s t h ep r o p o s e da l g o r i t h mi s c o m p a r e dw i t hd p s oa n dr a j e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eh y b r i ds c h e d ul i n ga l g o r i t h mh a sg o o dp e r f o r m a n c eo na v e r a g e o p t i m a l i t yp e r f o r m a n c eo ft h es o l u t i o n ，t h er u n n i n gt i m eo fa l g o r i t h ma n dt h ec h a n c et of i n dt h eo p t i m a l s c h e d u l ea m o n ga l lt h et e s t e da l g o r i t h m s 。 k e y w o r d s ：n o - w a i tf l o w s h o p s ；v a r i a b l en e i g h b o r h o o ds e a r c h ；b i c r i t e r i o no b j e c t i v eo p t i m i z a t i o n ； p a r t i c l es w a r mo p t i m i z a t i o n l l 东南大学学位论文独创性声明 本人声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我同工作的i 司志对本研究所做的任何贡献。 均已在论文中作了明确的说明，并表示了谢意。 研究生签名：遗丝日期：呈盟：丝塑 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 、w十 研究生签名：丛立丝 导师签名： 左埠期：毕 第1 章绪论 第1 章绪论 无等待流水调度问题( n o - w a i tf l o w s h o p ，n w f s ) 已经被证明是一一类n p 难问题。无法在多项 式时间范围内找到最优解，不过在实际生产中即使一个较优的解也能带来巨大的经济效益，因此产 生了很多求近似最优解的算法。对社会工业生产具有重大的经济效益。本章主要介绍无等待调度问 题课题的背景和目标、课题的来源、论文主要研究的内容以及所用的算法。 1 1 课题背景及来源 i 1 1 课题背景 无等待调度是一类重要的约束流水调度问题，它要求任务的加工从开始到结束必须连续进行， 任务在机器上加工和运送都不能出现等待，即任务在给定机器上的开始时间必须延迟以满足该工序 的完成时间与下一个t 序在下一台机器上的开始时间相符合。这类调度广泛存在于冶金、化工和食 品加- t 等行业。通常被模型化为无等待调度。 无等待流水线调度问题( n w f s ) 可描述为：给定数量的机床和工件，每个工件在各个机床上 的加工顺序相同并且在某一时刻只能够在一台机床上加工，另外在某一时刻每台机床上只能加工一 个工件，同一工件相邻的两工序之间没有等待时间。如何安排生产，使生产周期最优就构成了无等 待流水调度问题。 在许多制造车间中。存在这样一种限制，即一个任务一旦开始在第一台机器上进行加工，直到 它在最后一台机器上加t 完成。这期白j 不允许有任何中断，即必要时。一个任务在一台机器上将要 被推迟加工以便它在其卜的完工时间和在下台机器卜的开始时问相匹配( 凶为下台机器还处于加工 另外一个任务的过程中) 。这样的流水车间称之为无等待流水车间。无等待流水车间应用在现代工业 的各个方面，包括金属、塑料、化学以及食品加工工业。导致无等待或阻塞生产环境产生的最主要 的两个原因之一是生产技术本身。在一些处理过程中，例如，材料的温度或者其他特性( 比如粘度) 需要每一步操作立即接着其上一步操作过程加工。这种情况出现在钢铁生产中，熔融的钢经过一系 列加工，比如进锭，出锭，再加热，浸泡，预轧。类似地，塑料塑造和银制品生产工业中。一系列 的处理过程必须紧密相连以防j 卜衰变。更深层的例子发牛在化学和药学中。由于类似的原因，铝产 品的阳极氧化处理比如管子，卡车格栅也必须以非等待米处理。在食品加工工业中。罐头加上必须 紧跟烹饪以确保新鲜。现代化的生产环境例如及时盘存调节法，复杂的生产体系以及机器化车间提 供了高度的协作生产过程，这些通常都可以被模型化为无等待调度问题。 作为约束流水车间( f l o w - s h o p ) 排序问题中的一种，无等待流水车间( n o - w a i tf l o w s h o p ) 问 题一般情况下满足以下几项假设条件： ( 1 ) 一个工件不能同时在不同的机器上加工，尽管一个工件有时可能包括多个相同的零件，也 不能将其分成几部分，同时在几台不同的机器卜加：【： ( 2 ) 对整个二l ：件米说，在加：l ：过程中采取5 f 行移动方式，即当e 一道工序完工后。立即送下道 工序加工； ( 3 ) 不允许中断，当一个工件在一台机器上一旦开始加工，必须一直进行到完工，不允许中途 停下来，插入其它工件； ( 4 ) 每道工序只在一台机器上完成，每台机器只完成一道工序： 东南大学硕十学位论文 ( 5 ) 工件数、机器数、加工时间已知，只加工时间与加工顺序无关： ( 6 ) 不允许工件在工序之间等待，允许机器在工件未到达时闲置； ( 7 ) 工件加丁技术上的约束事先给定； ( 8 ) 每台机器同时只能加工一个工件。 以总完工时间为目标的无等待流水车间调度问题是一个重要的制造加工系统，广泛应用于工业 生产中。无等待问题是流水车间调度中的一种，是一类典型的n p 完全问题，己被证明在多项式时 间内得不到最优值。好的求解方法可以促进企业提高生产率，降低生产成本。因此，该研究无论从 理论还是实际都有重要意义。日前对这些问题的研究主要町以分为两类方法：启发式方法和元肩发 式方法( 包括遗传算法、模拟退火、人工神经网络、禁忌搜索和蚁群算法等) 。这两类方法在评价算 法性能的两个标准方面各有优缺点：在最优性方面，元启发式算法在总体上优于启发式算法，但是 由于不确定参数的存在其解的稳定性较差：在有效性方面，元启发式算法通常较差，其需要的c p u 时间远远多于多项式复杂度的启发式算法，使得它们很难应用于工程实践，特别是对于大规模的调 度问题。所以本文研究有效的混合算法能在较短时间内找到较好的解对实际的工程应用具有重要 意义。 1 1 2 课题来源 国家自然科学基金项目：基于目标增量的大规模无等待调度复合启发式算法( n o 6 0 5 0 4 0 2 9 ) 。 1 2 研究目标 在生产调度实际问题中，有多个评价指标总完工时间( t o t a lf l o w - t i m e ，本文中用玎v 表示) 和最大完工时间( m a k e s p a n ，本文中用c f 。表示) 是调度问题中两个常用的评价指标，阡7 最小可 以促使资源稳定有效地利用及任务的快速周转，e 。最小能减小总的生产时f s - j ，二者同时最小化可 以极大地减少成本。当优化目标为最小化g 嗽和盯7 的线性组合时，该双目标函数可以等价表示 为： ，( 工) = 口c 。+ 豫丁 ( 1 1 ) 其中，c i n “代表一个调度的最大完工时间矿7 代表一个调度的总完工时间。口和表示权重。 设任务以与以相邻时在第所台机器上的完工时间分别为e 。和巨。两相邻任务完工时间之 差( 即距离) 为q ，可用如下公式列得出( 距离公式推导详见第4 章4 2 节) ： 咆，咆。= 普黑卜乳，叫) 2 ， 由于任务之问的距离是独立的，即与其他任务的时间参数无关，只与这两个任务的加工时间有 关，故可以用一个非对称矩阵d 表示所有任务之白j 的距离。因为一个调度就是任务集的个全排列， 所以一个调度的最大完工时间： c 一= d j ，f + i ( 1 3 ) 设一个调度中的第i 个任务以的完工时间为e ，其总完工时间刀v 可以表示为相邻任务间距 离的加权和。即： 2 第l 章绪论 肿= o f 以j + l ( 1 4 ) 一、 i - 一 j = o 由式( 1 1 ) 、( 1 3 ) 、( 1 4 ) ，得： n 一- i f ( x ) = 口c o r 阡7 = 陋+ ( 刀一i ) f 1 d j ，+ i ( 1 5 ) i - 0 近年来，针对各类优化问题的复杂性和效率等方面的考虑。p s o ( 粒j r 群优化算法) 在离散优 化、多目标优化、约束优化等方【f i i 得到了研究和应用，取得了定的进展。相对于传统多目标优化 方法，p s o 算法在求解多目标问题上具有较大的优势。首先。p s o 算法的高效搜索能力有利于在多 目标意义下得到最优解；其次，p s o 算法通过代表整个解集的种群按内在的并行方式同时搜索多个 非劣解，因此容易搜索到多个p a r e t o 最优解：另外p s o 算法的通用性使其适合于处理多种类型的 目标函数和约束：最后，p s o 算法很容易与传统方法相结合，进而设计解决特定问题的高效方法。 基于p s o 算法的优点，本文针对最小化“总完工时间”和“最大完工时间”的双日标无等待流水作 业调度问题。提出一种新的粒子群加权混合优化算法。该算法以粒子群算法为基础，将其离散化应 用于流水线作业调度问题，为加快算法搜索全局最优值的效率，应用插入邻域及快速邻域搜索方法， 为克服早熟运用变邻域搜索算法，并设计多群体的优化操作解决双目标问题。将提出的算法编码实 现并给出仿真结果。具体如下： ( 1 ) 构造从微粒位置矢量到流水线工件排序的映射，将粒子群优化算法应用于n w f s 问题， 确定算法相应参数，提出离散粒子群混合算法框架： ( 2 ) 提出离散粒子群混合算法的初始解生成算法，构造应用于全局极值的变邻域搜索和扰动， 提高算法解的质量： ( 3 ) 提出交换邻域和插入邻域算子以加快算法的搜索速度，降低邻域搜索的复杂度：设计双目 标优化中多群体进化操作提高算法的搜索能力，得到全局近似最优解。 ( 4 ) 设计并实现完整的离散粒子群混合调度算法，与现有解决同类型问题的算法进行比较，仿 真并分析实验结果。 1 3 研究现状 目前对n w f s 问题的研究主要可以分为两类方法：启发式方法和元启发式方法( 包括遗传算法、 模拟退火、人：i ：神经嘲络、禁忌搜索和蚁群算法等) 。这两类方法在评价算法性能的两个标准方面各 有优缺点：在最优性方面，元启发式算法在总体上优于启发式算法，但是由于不确定参数的存在其 解的稳定性较差；在有效性方面，元启发式算法通常较差，其需要的c p u 时间远远多于多项武复杂 度的启发式算法，使得它们很难应用于工程实践，特别是对于大规模的调度问题。所以，本文研究 有效的混合算法能在较短时间内找到较好的解，对实际的工程应用具有重要意义。 1 3 1 国内研究情况 目前国内研究的较多的是无约束流水调度问题，近年来，郑大钟，王凌、唐立新等采用遗传算 法、进化规划等元启发式算法】对这类问题进行了研究并取得了较好结果；王成思等提出了两个启 发式规则求解最小化总完工时间( 盯7 ) 的流水调度问题【4 1 。但对于无等待调度问题国内研究结果还 不多。 3 东南人学硕士学位论文 1 3 2 国外研究情况 国外对无等待调度问题研究较多主要有： ( 1 ) 最小化f l o w t i m e 为优化目标。v a nd e m a n 和b a k e r t m 提出了分支定界法来寻求最优方案， 并提出了一系列过程来产生最优值的下界：a d i r ia n dp o h o r y l e s t h 证明了2 - 机问题具有最优调度的一 些性质，给出一些定理作为多项式有界求解具有升序或者降序占优机器序列的m 机问题的基础： r a j e n d r a n 和c h a u d h u r i t 7 1 提出两种启发式算法r c i 和r c 2 ，它们初始解的产生方法不同，r c l 按照 任务在所有机器上的加权加工时间和的升序将所有任务排序如果相同则按照加工时间和的升序排 列；r c 2 按照任务在所有机器上的加工时间和的升序将所有任务排序，如果相同则按照加权加工时 间和的升序排列。解的提高过程都应用类似于n e h 的插入方法进行逐渐插入以产生局部最优解， 它们的平均性能明显优于b o n n e y 和g u n d r y 的算法【引、k i n g 和s p a c h i s 算法【射。近年来。b e r t o l i s s i l l o l 提出构造性启发式算法b e b e 算法的性能比r c l 算法有所提高但提高不明显：c h e ne t a l 【i u 研究了 遗传算法求解该问题并将其与r c i 算法进行r 比较；最近a l d o w a i s a n 和a l l a h v e r d i u 2 提出六个肩发 式方法，a l d o w i a s a n 研究了两台机器情况下总平均完工时间的无等待流水车间问题，给出了特殊情 况的最优调度建立了局部支配关系，并且提出了一个一般情况下的启发式方法。g o l d b e r g 研究了 相同的问题，给出了支配关系，提出了一个启发式方法。a l d o w a i s a n & a l l a h v e r d i l 提出六个启发式 方法求解m a x0c n w t f m 问题并与r c i 算法和c h e r t 算法等进行了比较，结果表明所提出p h i ( p ) 算法是目前求解该问题的最好算法。 ( 2 ) 最小化m a k e s p a n ( c 眦) 为优化日标。首先由r e d d i 和r a m a m o o r t h y u 3 1 提出，1 0 年前由 g a n g a d h a r a na n dr a j e n d r a n l l 4 1 分别提出了启发式算法g r 和r a j ：最近a l d o w i a s a na n da l l a h v e r d i i i 别 提出了六个算法，其中三个基于模拟退火算法，另三个基于遗传算法，结果表明所提出的s a 2 算法 和g a 2 算法是目前性能最好的算法，它们优于g r 和r a j 。 ( 3 ) 双优化目标。近几年刚起步，主要有以下几个方面：最小化m a k e s p a n ( c 眦) 和最大化t a r d i n e s s 的双目标问题引；a l d o w i a s a na n da l l a h v e r d i 提出混合模拟退火和混合遗传算法求解最小化 m a k e s p a n ( c 眦) 和最大化l a t e n e s s 的双目标问题“：a l d o w i a s a na n da l l a h v e r d i 首次提出最小化 m a k e s p a n ( c 眦) 和f l o w t i m e ( t f t ) 双目标优化问题的启发式算法l i s l ；b r o w n ，m c g a r v e ya n dv e n t u r a 对准 备时间与加工时间分离的最小化m a k e s p a n ( c 眦) 和f l o w t i m e ( 阡刀双目标优化问题提出了多项式与非 多项式复杂度的算法l l 川。 ( 4 ) m a c c a r t h y l 2 0 】对该领域的研究现状做了较为详细的综述，并指出以总平均完工时间为目标 的无等待流水车间问题是n p 完全问题。即使是两台机器的情况：任务的完t 时间和流程时间在准 备时间是0 的情况下是完全相同的，冈此最小化总完t 时间和最小化平均完工时间是两个等价的准 则。 ( 5 ) 相对传统多目标优化算法。p s o 算法在求解多目标问题上具有很大优势。基于p s o 算法 的多目标优化主要有以下几种思路： 1 ) 向量法和权重法 p a r s o p o u l o s p 6 等利用适应性权重法和向量评价法。首次将p s o 算法用于解决多日标优化问题， 然而对于给定的优化问题，通常权重法很难获得一组合适的权重，而向量评价法往往无法给出多目 标优化问题的满意解。 2 ) 多种群法 p u l i d 0 1 3 7 】等将种群分为多个子种群，每个子种群单独进行p s o 算法运算各个子种群之间通 4 第1 章绪论 过信息交换来搜索p a r e t o 最优解。但由于需要增加微粒数目而增加了计算量。 3 ) 距离法 m o s t a g h i m t 3 8 】等根据个体：。前解与p a r e t o 解之间的距离来分配其适应值从而选择群体最佳位 置。由于距离法需要初始化潜在解，如果初始潜在值太大，不同解的适应性的差别不明显，这将导 致选择压力过小或个体均匀分布。从而导致p s o 算法收敛非常缓慢。 4 ) 领域法 h u 【3 9 】等提出了一种基于动态邻域结构的选择策略，将一个目标定义为优化目标，而将其他所 有目标定义为邻域目标，进而提出了选择群体最佳位置的动态邻域策略。该方法对优化目标的选择 以及邻域目标函数的排序较为敏感。 相对多目标遗传算法的研究，多目标p s o 算法的研究还处于起步阶段，算法与技术方面的研究 还比较少，应用方面大多针对函数优化问题，在多目标组合优化问题上的研究刚刚开始。 1 4 相关算法及其介绍 在分析了遗传算法、模拟退火算法、蚁群算法及粒子群算法的特点后，本文基于粒子群算法思 想，采用n e h 初始化操作、插入邻域和交换邻域算子。离散化后应用于无等待调度问题，针对权 重法和向量法的不足采用随机加权累加函数来有效解决双目标无等待流水调度问题。研究中用到了 以下算法 1 4 1 粒子群算法( p s o ) 【2 l j 算法介绍： p s o 算法是一种基于群体智能的随机寻优算法，它模仿鸟类的觅食行为，将问题的搜索空间比作 鸟类的飞行空间，将每只鸟抽象为一个无质角= 无体积的微粒，j f j 以表征问题的一个候选解，优化所 需要寻找的最优解则等同于要寻找的食物。p s o 算法为每个微粒制定了类似于鸟类运动的简单行为 规则，从而使整个微粒群的运动表现出与鸟类觅食类似的特性，进而用于求解复杂的优化问题。p s o 中。每个优化问题的解都是搜索空间中的一个“微粒子”。所有粒子都有一个由被优化的函数决定 的适应值( f i t n e s sv a l u e ) 。每个粒子还有一个速度决定它们的方向和距离。然后所有粒子就追随当 前的最优粒子在解空间中搜索。p s o 初始化为一群随机粒子( 随机解) 。然后通过迭代找到最优解。 在每一次迭代中粒子通过跟踪两个“最优值”来更新自己：第一个就是粒j f 本身所找到的最优解， 这个解叫做个体最优值( p b e s t ，p b ) ：另一个极值是整个种群目前找到的最优解，即全局最优极值 ( g b 酗t ，g b ) 。另外也可以不川整个种群而只是j j 其中一部分作为粒子的邻居，那么在所有邻居中 的极值就是全局最优值。 p s o 算法描述如下： 设：五( 而。，而2 ，) 为微粒子f 的当前位置，k ( m ，h ：，v 1 ) 为微粒子f 的当前飞行速度： p 岛( p 岛，内：，砘) 为微粒子，所经历的最好位置，即个体最好位置ig b ( g t a ，9 6 2 ，她) 为微粒 群所经j 力的最好位置。p 6 ，加表示微粒群的当前最佳适应度值。 粒子根据以下公式来更新其速度和位置： 巧“= w e + e , r a n d ( p b f 一爿? ) + c 2 r a n d ( g b 一彳? ) x ：= x ：+ y 式中，w 表示惯性系数，c l 表示个体认知系数，c 2 表示社会学习系数，r a n d 为随机数。 5 ( 1 6 ) ( 1 7 ) 东南大学硕士学位论文 式( 1 6 ) 表明微粒子的速度改变由三个凼素决定：其一是原来速度；其二是与自身最优值比较， 学 - - j 自身经验：其，一是向群体最优值学习，学习社会经验，是群体合作行为的体现。 式( 1 7 ) 表明微粒子的新位置是由原来位置与原来速度共同作用改变。 1 4 2 离散粒子群算法( d p s o ) 2 2 】 粒子群算法具有连续本质，一般用于连续函数问题求解，不适宜于求解离散问题。为了将其用 于离散的无等待流水线工件调度问题。引入以下概念： ( 1 ) 微粒子的位置表示 将所有t 件( n 个) 的排列作为粒子的位置矢量，即：x = ( x ，x 2 ，x 。) ： ( 2 ) 微粒子的速度表示 速度将用于改变微粒的位置，因此本文定义为对微粒位置的一种变换： ( 3 ) 微粒速度和位置的更新公式表示 矿+ 1 = w 矿+ ，q ( 爿盏一) + ，乞( 爿盏一) ( 1 8 ) x “1 = x + ( 1 9 ) 其中，x 砷为微粒子个体的最佳位置，为群体的最佳位置，为区间( o ，1 ) 上的随机数，1 4 ；为 惯性系数，c i 是个体认知系数，调节向p 6 的飞行；c 2 是社会系数，调节向9 6 的飞行。 粒子位置的移动方式如下： ( 1 ) 若r w ，粒子进行插入变异，即改变工件的排列顺序； ( 2 ) 若r c l ，粒子根据自身的p b 进行交叉变异，实现自身学习； ( 3 ) 若r ，2 时。加工情况如图2 l 中( a ) 所示。 当t ， l 2 时总加工时间为：五( f ) = 2 t , l + f j 2 + i + t j 2 ；而当t j l 2 时，总加_ - e 时间为： e ( 口) = 2 t , l + 2 f 2 + ，2 由于存在无等待的限制，一个工件在第一台机器上开始加工之前需要一段必 要的等待时间( 第一个开始加工的工件不需要等待) ，这个工件，和它之前的工件i 的开始加工时间 的差d , j 可以表示为： 4 = ”m a x ( o ，麟( 酗一e 搁t j 一) ( 2 1 ) 因此，刀个任务的总完工时间( 目标函数) 表示为： 9 东南大学硕士学位论文 ，( x ) = ( 甩+ l i ) d h j + t u ( 2 2 ) 设任务以与相邻时在第肌台机器上的完工时间分别为目，和e ，。两完工时间差( 即距离) 为口，可用如下公式刚得出： 。u = e ，肿一e ，。= ma x _ 。+ 窆p = kc ，p 一_ ，) c 2 3 ， 由于任务之间的距离是独立的，即与其他任务的时间参数无关，只与这两个任务的加工时间有 关，如果用口，表示任务i 与任务之间的距离，因为一个调度就是任务集的一个全排列，所以一个 调度的最人完工时间： c - - = d f ，+ i ( 2 4 ) 设一个调度中的第i 个任务以的完i 时间为e ，其总完工时间 7 可以表示为相邻任务间距 离的加权和，即： t f t = ( n - f ) d | 。 ( 2 5 ) 当优化目标为最大完工时间和总完工时间最小化的线性组合时该双日标函数町以等价表示为： 口c - - + 册= a + ( n - i ) f 1 d , 川 ( 2 6 ) 其中，c 舶x 代表一个调度的最大完工时间，阡r 为总完工时间，口和表示权重。q + i 为两相邻 任务间距离。 2 2 解决双目标无等待流水线调度问题混合优化算法 2 2 1 算法思想 生产调度问题属于离散组合优化问题，这类问题的解空间为离散点的集合。本混合算法以粒子 群( p s o ) 算法为基础，通过位置矢量编码方法将p s o 算法应川于离散的流水线调度问题；利用 n e h 算子设计局部搜索的初始值以构造有效的初始粒予群：对全局最优值加随机扰动以加快算法搜 索全局最优值的效率：在粒子群每次迭代之后进行变邻域搜索以防1 f ：甲熟：针对蛀小化“总完j l ：时 间”和“最大完工时间”的双目标，设计目标加权算泫解决双目标优化问题：应用插入邻域及快速 邻域搜索以及多群体的优化算法来提高算法效率。 2 2 2 位置矢量编码 由于p s o 算法中微粒的位置为连续值矢量。无法实现流水线调度中工件排序的更新。因此构造 从微粒位置欠量到流水线丁件排序的映射是应用p s o 算法解决n w f s 问题的首要问题。放引入了 一种基于升序排列的r o v 2 8 1 ( r a n k e d o r d e r - v a l u e ) 编码规则，将粒子群优化算法应用予n w f s 问 题。 r o v 规则：对于一个微粒的位置矢量，首先将值最小的分量位置赋予r o v 值1 其次将值次 小的分量位置赋予r o v 值2 依此类推，直到所有的分量位置都赋予个唯的r o v 值。 1 0 第2 章双目标无等待流水调度问题的模型 由于微粒位置矢量的各个位置分量的值有火小次序关系，r o v 规则就是利用这种次序关系结合 随机编码，将微粒的连续位置转换成离散的排序即机器- 上各工件的加工顺序，从咐计算工件( 微粒) 所对应调度的目标函数值。 无等待流水线调度问题，最亢接的编码方法就是采用基于工件序列的自然数编码，用位置矢量 的一维表示一个工件。粒子本身表示所有工件的排列，即个调度。 对于疗个工件m 台机床调度问题，若位置矢量分量用工序表示则从第l 维分量到第n x m 维 分量就形成了一个工序序列。在位置矢量中，同工件所有工序采用相同的符号，而同一工件的不 同工序可根据其在工序序列中的出现次序区分。假定有6 个工件的调度问题，设其位置矢量为【1 8 ， 1 7 ，0 6 。3 7 ，2 8 ，0 9 】。根据粒子各个位置矢量大小分别给r o v 赋值：4 ，3 ，l ，6 5 ，2 ， 从而得到工件的加工次序即调度顺序。表2 1 为粒f 位置欠量与调度之间的对应关系。 表2 l 位置矢量与对应的r o v 值和： 件序列之间的对应关系 为了用粒子群算法解决调度问题，调度顺序通常采用位置矢量的模型。每个粒子的矢量代表任 务的排列顺序，该元素位置的排列就是一个调度顺序 2 2 3 粒子群算法离散化 粒子群算法的实质在于粒子根据自己和同伴的飞行经验不断调整位置和速度，从而向最优位置 飞行。粒子的新位置是粒子的速度、个体极值和全局极值相互作用的结果。结合编码方法，定义位 置和速度的更新操作离散化以适用于无等待流水线调度问题的求解。 ( 1 ) 高散过程 1 ) 粒子的位置： 将所有工件( 刀个) 的排列作为粒子的位置矢量，x = ( 五，k ，以) ： 2 ) 粒子的速度： 速度将用于改变微粒的位置因此本文定义为对微粒位置的一种变换： 3 ) 粒子速度和位置的更新公式： 矿“= w 矿+ ，c l ( 戤一f ) + ，c 2 ( 砖一) ( 2 7 ) z “= z + v ( 2 8 ) 其中，为微粒子个体的最佳位置，如为群体的最佳位置，为区间( o ，1 ) 上的随机数，w 为 惯性系数c i 是个体认知系数，调节向p b 的飞行：c 2 是社会系数，调节向g b 的飞行。 粒子位置的移动方式如下： 若r w ，粒子进行插入变异。即改变：i ：件的排列顺序： 若r c i ，粒子根据自身的p b 进行交叉变异实现自身学习： 若产锄，粒子根据全局的驴进行交叉变异，实现群体学习。 ( 2 ) 基本算法流程 1 确定w 。c l ，c 2 及种群个数； 东南人学硕十学位论文 2 初始化粒子群，得到p 6 、9 6 的初始值； 3 粒子的更新： 3 1 根据式( 2 7 ) 对每一个粒子的速度进行更新： 3 2 根据式( 2 8 ) 对每一个粒子的位置进行更新： 4 计算目标函数更新p 6 、g b ； 5 判断终止条件是否满足，满足则算法结束；否则转3 。 2 2 4n e h 初始化算法构造初始种群及n e h 算子 在求解n w s f 问题算法中，初始粒子群的构造对算法的性能有十分重要的作用，为了使初始种 群具备一定的质量和分散度，本混合调度算法中采用了基于n e h 插入的初始化方法构造有效的初 始粒子群。并设计了n e h 算子算法，而保证整体算法较好的优化性能。 算法首先计算各工件在所有机器上的加工时间总和，并按递减顺序排列先将前两个：r 件进行 最优调度。然后依次将剩余j i ：件逐渐插入到已调度好的1 ：件排列中的某个位置选择目标函数最优 的序列。直到所有工件均调度完毕，从而得到问题的一个调度方案。 ( 1 ) 算法步骤： 1 给定所有工件的一个r o v 排序s ：计算二i = 作的总处理时间，并按照总处理时间从大到小排 列工作顺序； 2 令肛l ，取s 中的前2 个工件，对2 种可能的加工次序进行评价，选择总完工时间较小的序 列作为当前序列： 3 令k = k + i 依次将第七个工件插入到当前序列的七个可能位置，从中选择总完工时问较小的 序列作为当前序列： 4 重复步骤3 ，直到s 中所有工件均得到新的排序。 ( 2 ) n e h 算子实现代码 i _ j = i n d e x 2 0 ； 构造l i s t ： 1 ) l i s t 最前而： a d d ( o ，s e q 【k 】) ； t e m p s e q = l i s t 长度： f o r ( i = 0 ，l i s t 长度1 ) h u m = l i s t g e t ( i ) ； t e m p s e q i - - n u m i n t v a l u e o ； m i n - - c o m p u t e f i t n e s s ( t e m p s e q ) ； 计算适应值 l i s t r e m o v e ( 0 ) ； 2 ) l i s t 中间： c ；0 ： f o r ( i = l ，2 ，k - 1 ) l i s t a d d ( i ，s c q k ) ； t e m p s e q = l i s t 长度： f o 哟= o ，l ，1 i s t 长度- 1 ) h u m 2 l i s t g e t ( j ) ； t e m p s e q j = n u m i n t v a l u e o ；) 1 2 第2 章双日标无等待流水调度问题的模型 c = c o m p u t e f i t n e s s ( t e m p s e q ) ； i f ( c m i n ) m i n 5 c ； i n d e x = i ； l i s t r e m o v e ( i ) ； 3 ) i i s t 末尾： l i s t a d d ( s e q k ) ； t e m p s e q = l i s t 长度； f o r ( i = o ，l i s t 长度- 1 ) h u m = l i s t g e t ( i ) ； t e m p s e q i = n u m i n t v a l u e o ；) c = c o m p u t e f i m e s s ( t e m p s e q ) ； i f ( c m i n ) m i n = c ； i n d e x = k ； l i s t r e m o v e ( k ) ； 2 2 5 变邻域搜索及s w a p 、i n s e r t 算子 考察p s o 的进化过程可知，p s o 初期收敛速度非常快，经若干次迭代，粒子失去了多样性，趋 向同一化，收敛速度明显变慢，容易陷入局部极小，既早熟收敛。因大部分粒子的个体极值等于全 局极值，算法长期徘徊在若干旧状态上，造成早熟。研究表明，p s o 算法尽管局部搜索能力较好， 但其全局搜索能力较弱，而v n s 变邻域搜索则具备较强的全局探索能力。v n s 算法通过系统性地 改变邻域搜索中的邻域结构，使算法获得全局最优解概率高于采用单一邻域结构搜索。 为了加强p s o 算法的全局搜索能力，在上述算法框架中采用v n s 算法，有利于对全局空间探索 能力的提高和局部区域改善能力的平衡。通过搜索不同的邻域来提高求解质量采用交换邻域结构 s w a p 和插入邻域结构i n s e r t 使算法具有跳出局部最优的能力。 ( 1 ) 变邻域搜索算法基本流程 1 确定邻域结构m ( f = 1 ，2 ，k ) 和初始解品，令最优解9 6 = s o ； 2 满足收敛准则输出砂，算法终止；否则转步骤3 ： 3 对瓯进行扰动，随机交换瓯的两个不同工序得到目标值s p a n ： 4 k - o ； 5 开始变邻域搜索： 5 1 两椰b ；复制岛 5 2s p a n i - - s w a p ； 在s i 的邻域中用刑印操作寻找最好邻居 5 3 如果( 扣= o ) s p a n t , - - - s w a p ( s t ) ； 在的邻域中用i n s e r t 操作寻找最好邻居 5 4 如果( 肛= 1 ) s p a n l * - i n s e r t ( s o ； 5 5 如果( s p a n i s p a n ) s o * - s i ：s p a n , - - - s p a n l ：七+ o ； 如果目标值下降 5 6 否则：幻+ ： 6 搜索结束。 其中，s w a p 操作为：在工件序列中随机选择不同的两个位置z 、y ，把工位置上与位置y 上的工 1 3 东南人学硕+ 学位论文 序进行交换，若交换后可使目标值下降，则结束并返回结果，记为s w a p ( x ，力，否则继续选择下一 个位置直到所有可能的位置全部选完。 i n s e r t