（计算机软件与理论专业论文）序列流水车间调度问题的混合粒子群优化算法研究.pdf

中山大学硕士学位论文 序列流水车间调度问题的混合粒子群优化算法研究 论文题目：序列流水车间调度问题的混合粒子群优化算法研究 专业：计算机软件与理论 硕士生：李强 指导老师：衣杨副教授 摘要 序列流水车问调度问题( p e 肌u t a t i o nf l o w s h o ps c h e d u l i n gp r o b l e m ，p f s p ) 在物流、交通、流水线生产等实际工业领域有大量应用，合理的时间内高效地 解决p f s p 关系到许多领域的生产效率。p f s p 中最大完工时i 自j ( m a k e s p a n ) 的 最小化可以促使总生产运营的最小化、稳定的资源利用、快速的作业周转和在 制品库存的最小化，而最大延迟( m a x i m u ml a t e n e s s ) 的最小化可以最大程度 减小企业延误交货期的损失。所以研究p f s p 的最大完工时问和最大延迟最小 化对于最大化企业利润意义重大。 本文使用提出的混合粒子群优化算法( h y b r i dp a r t i c l es w a n n0 p t i m j z a t i o n ， h p s o ) 分别最小化p f s p 的m a k e s p a n 和最大延迟。本文的主要贡献包括：为 避免混合p s o 算法过早陷入局部最优值，提高其持续寻优能力，提出自适应 排斥计算技术；为更好地平衡混合p s 0 算法中粒子的全局探索和局部丌采能 力，提出自适应非线性变化的认知因子和社会因子；根据p f s p 的离散特性， 提出从连续问题空问到离散问题空间转化的启发式规则一s d v ( s m a l l e s t d i 舵r e n c ev a l u e ，s d v ) ，s d v 能使混合p s 0 算法更加智能地做出调度决策以 分别最小化p f s p 的m a k e s p a n 和最大延迟基准；为提高混合p s o 算法求解 p f s p 的解的精度，提出改进的i n e h 局部搜索技术；为公正地评估混合p s o 算法的性能，将基于业内使用最普遍的t a i l l a r d 和d e m i r k o l 基准实例进行评估， 此外，还充分对比了混合p s o 算法与其他p s 0 算法在求解p f s p 时的效率。 关键字：人工生命；混合粒子群优化；序列流水车问调度 t i t l e ：ah y b r i dp a r t i c l es w 黜o p t i m i z a t i o na l g o r i u nf o r p e m l u t a t i o nf l o w s h o ps c h e d u l i n gp r o b l e m m a j o r ：c o m p u t e rs o r w a r e a 1 1 dt h e o r ) ， n a m e ：l iq j a n g s u p e n ，i s o r ：y iy a n g a b s t r a c t t h ep e 咖u t a t i o nf l o w s h o ps c h e d u l i n gp r o i b l e m ( p f s p ) h a sb e e na p p l i e dt o l o g i s t i c s ，t r a 踊c s ，a n da s s e m b l ep r o d u c t i o n1 i n e ，w h i c hi so f t e ne n c o u n t e r e di nr e a l w o r l d s o l v i n gp f s pe 骶c t i v e l yi nr e a s o n a b l e t i m ei s k e yt o t h ep r o d u c t i o n e 衔c i e n c y t h em i n i m i z a t i o no fm a k e s p a ni sk n o w n t ol e a dt ot h em i n i m i z a t i o no f t o t a lp r o d u c t i o nr u n ，s t a b l eu t i l i z a t i o no fr e s o u r c e s ，r a p i dt u m - r o u n do f j o b s ，a n dt h e m i n i m i z a t i o no fw o r k i n p r o c e s s( w i p )i n v e n t o r y ， a n dt h em i n i m i z a t i o no f m a x i m u ml a t e n e s sc a nl e a dt ot h em i n i m i z a t i o no fl o s s ，w h i c hi sc a u s e db yt h ed u e d a t eo fi o b s s ot h er e s e a r c ho nt h em i n i m i z a t i o no fm a k e s p a na n dm a x i m u m l a t e n e s si np f s pi sv e r yi m p o r t a n t i nt h i sp a p e r ，ah y b r i dp a i r t i c l es w a n no p t i m i z a t i o na l g o r i t h mi sp r e s e n t e dt o r e s p e c t i v e l ym i n i m i z ep f s pw i t hb o t hm a k e s p a na n dm a x i m u ml a t e n e s s c “t e r i a t h em a i nc o n t “b u t i o n so ft h ep a p e ri n c l u d e ：t ba v o i dt h eh y b r i dp s ot r a p p i n gi n l o c a lo p t i m at o oe a r l ya n di n c r e a s et h ec o n t i n u a lo p t i m i z a t i o na b i l i t y ，t h er e p u l s i v e c o m p u t a t i o ni sp r e s e n t e d ；t bm a k eab e t t e rb a l a n c eb e t w e e ng l o b a le x p l o r a t i o na n d l o c a le x p l o i t a t i o no fh i b r i dp s o ，t h en o n l i n e a rv a r i a t i o nr e c o g n i t i o nc o e f n c i e n ta n d s o c i a lc o e m c i e n ta r ep r e s e n t e d ；d u et ot h ed i s c r e t ec h a r a c r i s t i c so fp f sp ，ar u l e ， c a l l e ds d v ( s m a l l e s td i f f e r e n c ev a l u e ，s d v ) i sp r o p o s e dt ot r a n s f o mt h ec o n t m o u s p r o b l e ms p a c ei n t ot h ed i s c r e t ep r o b l e ms p a c e ；t bi m p r o v et h ep r e c i s i o no fh y b r i d p s os o l v i n gp f sp ，t w oi m p r o v e dl o c a ls e a r c ha l g o r i t h m ，r e s p e c t i v e l yc a l l e di n e h a n di v n s ，a r ei n c o r p o r a t e di n t ot h eh y b “dp s 0 ；t be v a l u a t et h ep e r f b r m a n c eo f h y b r i dp s 0 ，t h es i m u l a t i o ne x p e r i m e n t sa r eo nt h eb a s i so fm o s tp o p u l a rb e n c h m a r k ， o fw h i c ha r e7 r a i l l a r d sa n dd e m i r k o l s ，i na d d i t i o n ，t h ep a p e rc o m p a r e st h ee h l c i e n c y o fh y b r i dp s ow i t ho t h e rp s o k e y w o r d s ：a r t i f i c i a ll i f e ；p a n i c l es w a n no p t i m i z a t i o n ；p e 咖u t a t i o nf l o w s h o p s c h e d u l i n gp r o b l e m 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名疗；诙 同期：n 8 军5 月尹h 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者躲专3 谖导师躲习枷 眦游5 月夕同嗍腓岁月7 同 中山大学硕士学位论文序列流水车问调度问题的混合粒了群优化算法研究 1 1 研究背景 1 1 1 p f s p 研究现状 第1 章引言 流水车间调度问题( f l o w s h o ps c h e d u l i n gp r o b l e m ，f s p ) 由j o l m s o n 于 1 9 5 4 年首次提出，在此后的几十年吸引了越来越多研究人员的关注。流水车 间调度问题一般可以描述为门个作业要在聊台机器上加工，每个作业需要经过 垅道工序，每道工序要求不同的机器。，2 个作业在肌台机器上的加工顺序相同。 作业f 在机器上的加工时间是给定的，设为0 ( 净1 ， ；= 1 ，垅) 。问 题的目标是求刀个作业在每台机器上的最优的加工顺序，使最大完工时间或其 它基准达到最小，f s p 也常称为序列流水车间调度问题( p e r m u t a t i o nf 1 0 w s h o p s c h e d u l i n gp r o b l e m ，p f s p ) ，序列流水车间调度的性能衡量包括最常见的最小 化最大完工时问( m a k e s p a n ) 或总流动时问( t o t a lf l o 州i m e ) ，此外，还包括 最小化最大拖期( m a x i m u mt a r d i n e s s ) 、最大延迟( m a x i m u ml a t e n e s s ) 等。 对于p f s p 的计算复杂性，r i n n o o yk a n 【2 1 证明了m a k e s p a n 的最小化是一个 n p c ，g a r e y d 等【3 1 证明了总流动时问的最小化是一个n p c ，l e n s t r a 等1 4 1 证明 了最大延迟的最小化是一个n p c ，因此，p f s p 是一个非常难解决的组合优化 问题。相关研究主要集中于通过启发式优化技术在合理的计算时问内找出高质 量的解，而不是最优解。p a l m e r l 5 1 、c 锄p b e h 等【6 1 、n a w a z 等【7 1 、t a i l l a r d l 8 1 和 f r a m i n a n 等【9 】等通过传统启发式优化算法最小化p f s p 的m a k e s p a n 。进来，许 多研究人员应用元启发式算法解决p f s p 的m a k e s p a n 最小化，获得比传统启发 式算法更优的解，求解方法包括模拟退火【10 1 、禁忌搜索】、遗传算法【1 2 1 、蚁群 算法【13 1 、粒子群优化算法【1 4 】【2 1 1 等。为了测试这些启发式算法的性能，使用的基 准问题实例一般是由t a i l l a r d 【2 2 】提供的1 2 0 个基准问题实例和由d e m i r k o l 等吲 提供的1 6 0 个基准问题实例。对于最小化p f s p 的最大延迟，业内相关的参考 文献较少，求解的方法也不多【2 3 】- 【2 6 1 。为了评估算法的性能，使用的基准问题实 中山人学硕士学位论文 序列流水车间调度问题的混合粒子群优化算法研究 例一般是由d e m i r k o l 等【2 7 】提供的1 6 0 个基准问题实例。 1 1 2p s o 研究现状 粒子群优化( p 硪i c l es w a m0 p t i m i z a t i o n ，p s o ) 由k e n n e d y 和e b e r h a n ( 1 9 9 5 ) 受鸟群和鱼池社会和认知行为启发而提出【2 8 】【2 9 1 。经过十多年的不断完 善和发展，其在进化计算领域已成为遗传算法( g a ) 和蚁群优化算法( a c o ) 的一个强有力竞争对手。由于p s o 具有模型简单、参数少和易实现等优点，吸 引了越来越多学者的关注，已成功应用到神经网络的训练问题【3 0 】【3 l 】、追踪和优 化动态系统【3 2 】、人类的震动分析、反应的电力和电压控制【3 引、约束资源配置 【3 5 】、旅行商问题【3 6 】、流水车间调度问题【1 8 】、多目标优化问题吲以及其它许多工 程应用问题1 3 8 】。【4 0 】。 虽然p s 0 在运行初期收敛速度比较快，但在运行后期容易因缺乏全局拓展 ( g l o b a le x p l o r a t i o n ) 能力而陷入局部最优。为缓解此问题，s h i 和e b e r h a r t 在 原创的p s 0 中引入了惯性权重【4 ，使原来的速度对新速度的更新产生权重影 响，此举使p s 0 的性能得到一定程度提升。随后他们引入了一个随迭代次数线 性递减的惯性权重【4 2 】【4 3 】，并在粒子搜索空间的每一维引入一个能有效控制粒子 全局探索能力的最大可允许飞行速度甜，在此基础上提出了惯性权重线性递 减p s o 算法( 1 n e n i aw e i 曲tl i n e a r l yd e c r e a s i n gp s o ，i w l d p s o ) 。i w l d p s o 有效地平衡了粒子的局部探索( l o c a le x p l o i t a t i o n ) 和全局拓展能力。除引进惯性 权重改进p s o 的策略外，也有研究人员分别引入约束因子策略f 4 4 h 4 5 1 、邻域拓扑 策略4 6 】【5 2 1 、混合其他进化算法思想策略5 3 】【5 7 1 改进p s 0 。 1 1 3p s o 求解p f s p 研究现状 p s o 优化各种连续的非线性函数的成功，使得近来许多研究人员将p s 0 的 应用扩展到组合优化领域。但是，将p s o 应用于组合优化领域最大的困难是 p s o 的连续特性，为解决这一问题，许多研究人员做了大量相关的研究工作。 相关的研究可以分为两大类，一类是应用连续的p s 0 求解p f s p 问题，在这类 求解方法中一般嵌入了某种从连续问题空i 、日j 向离散问题空间转化的启发式规 中山大学硕士学位论文序列流水车间调度问题的混合粒了群优化算法研究 则，而另一类是将离散的p s 0 应用于p f s p 的求解，本文属于第一类。 对于使用连续的p s o 求解p f s p ，首先需要克服的问题是设计高效的从连 续问题空间向离散问题空间转化的启发式规则。t a s g e t i r e n 等借鉴b e a n 【5 8 1 在求 解序列优化问题时的随机键表示( r a n d o mk e y sr e p r e s e n t a t i o n ) 思想，提出一 种称为s p v ( s m a l l e s tp o s i t i o nv a l u e ，s p v ) 的启发式规则，结合s p v 的p s o 算 法已成功应用于单机总权值拖期问题【5 9 1 和p f s p 中m a k e s p a n 【6 0 1 、总完工时剐1 4 】 和最大延迟的最小化f 2 6 】。 对于使用离散版本的p s o 优化p f s p ，需要客服的问题是粒子的速度更新 和位置更新的表示，常见的方法有两种，一种是利用e b e r h a r t 和k e n n e d y 提出 的专门用于求解离散问题的二进制版本p s o 算法i 6 1j ，此时粒子表示为一个二进 制数，应用此方法求解p f s p 的有l i a o 等。另一种是应用非二进制版本的p s o 算法，这种方法直接将粒子表示为一个调度序列，在粒子的速度更新和位置更 新表示方式上，应用的不是原来的连续的实数操作，而是离散的插入和交换操 作，应用此方法求解p f s p 的有l i a n 等f 1 6 1 【1 7 】、p a n 等【1 5 】、r a m e s h k u m a r 等【1 9 】。 目前大多数应用p s o 求解p f s p 的方法中大多数属于第二种，因为这种方法最 简单、形象，不需要复杂的转化规则。 1 2h p s o 求解p f s p 研究意义 p f s p 是工业领域内生产问题的抽象，它的高效解决对于机械制造f 6 2 】、化学 品生产f 6 3 】、食物生产【删和药物生产【6 5 1 的效率提高意义重大。解决p f s p 的方法 包括启发式算法和元启发式算法，这些算法在求解p f s p 时大多是最小化p f s p 的m a k e s p a n 或总完工时间，求解p f s p 的过程中忽略了很多现实因素：比如作 业的准备时间、作业的最早丌始时间、作业的交货时间、机器的故障。工业生 产的目标是生产成本的最小化，仅最优化m a k e s p a n 或总完工时间已不能满足工 业生产的要求，工业生产要求能分别对多个基准同时优化。目前p s o 求解p f s p 时大多仅是针对一个基准进行求解，且大部分是针对m a k e s p a n 基准，本文将使 用h p s 0 分别最小化m a k e s p a n 和最大延迟，在一定程度上缩短了p f s p 距离实 际应用的距离。 中山大学硕士学位论文序列流水车间调度问题的混合粒子群优化算法研究 在应用p s o 算法求解p f s p 时，大多数研究人员是应用简单的p s o 算法结 合一些转换规则进行求解。t a s g e t i r e n 等1 4 】【6 0 1 利用i w l d p s o 结合s p v 求解 p f s p 的m a k e s p a n ，l i a o 等利用离散的二进制版本p s o 求解p f s p 的 m a k e s p a n ，k u o 等和l i u 等利用离散的非二进制版本p s o 结合g a 的交叉 和变异思想求解p f s p 的m a k e s p a n 。利用其他的性能更优的p s o 结合转换规则 求解p f s p 的m a k e s p a n 或其它基准的研究不多。本文深入探讨了混合p s o 优化 p f s p 的效率，h p s o 中融合了排斥计算等智能策略，此外，基于s p v 规则提出 s d v 规则以帮助h p s o 做出更加合理的调度。 在评估p s o 算法求解p f s p 问题的性能时，许多研究人员使用的是自己随 机产生的测试实例，如果要对诸多求解p f s p 问题的p s o 算法作一个比较是很 困难的，因为使用的测试实例不同。目前，只有“a o 等1 8 1 将自己的p s o 算法 和t a s g e t i r e n 等1 4 】【6 0 】的p s o 算法进行了性能对比。本文将基于业内使用最普遍 的t a i l l a r d 提出的1 2 0 个基准实例和d e m i r k o l 等提出的1 6 0 个基准实例来评估 h p s 0 优化p f s p 的m a k e s p a n 和最大延迟时的性能，此外，本文还将与t a s g e t i r e n 等、l i a o 等、r e e v e s 等、n a w a z 等【7 1 的方案进行了对比，为业内提供了一个 更加具体的p s o 算法求解p f s p 的性能的参考。 综上所述，使用h p s o 分别优化p f s p 的m a k e s p a n 和最大延迟，对于提高 工业生产效率、丰富p s o 求解p f s p 的方法和评估p s 0 算法求解p f s p 问题的 性能意义非常重大。 1 3 本文主要研究内容和贡献 本文主要研究针对混合粒子优化算法最小化p f s p 的m a k e s p a n 和最大延迟 进行研究，主要研究工作可以分为两部分：提出混合粒子群优化算法、应用 h p s o 最小化p f s p 的m a k e s p a n 和最大延迟。内容包括： ( 1 )提出混合粒子群优化( h y b r i dp a n i c l es w a n n0 p t i m i z “o n ，h p s o ) 算法。本文将改进的排斥计算技术应用于p s o 中，排斥计算有效地 克服了p s o 算法后期由于缺乏全局探索能力而容易陷入局部最优的 缺点，较大地改进了p s o 算法的性能。此外，本文还将自适应的非 4 中山人学硕士学位论文序列流水车间调度问题的混合粒子群优化算法研究 线性变化的认知因子和社会因子应用于p s o 算法中。 ( 2 )使用h p s o 分别最小化p f s p 的m a l ( e s p a n 和晟大延迟基准上。为了 将连续的h p s o 应用于p f s p ，提出了s d v 启发式规则。为公正地 评估h p s 0 的性能，对于p f s p 的m a k e s p a l l 基准，本文将使用业内 使用最普遍的t a i l l a r d 基准包和d e m i r k o l 基准包，对于p f s p 的最大 延迟基准，本文将使用业内使用最普遍的d e m i r k o l 基准包。本文不 仅将h p s o 与传统启发式算法进行比较，而且还将h p s 0 和其他求解 p f s p 的p s o 、c a 进行比较。 本文的主要贡献包括： ( 1 )为避免混合p s o 算法过早陷入局部最优值，提高其持续寻优能力， 提出自适应排斥计算技术。 ( 2 )为更好地平衡混合p s 0 算法中粒子的全局探索和局部丌采能力，提 出自适应非线性变化的认知因子和社会因子。 ( 3 ) 根据p f s p 的离散特性，提出从连续问题空问到离散问题空问转化的 启发式规则一s d v ，s d v 能使混合p s o 算法更加智能地做出调度决 策以最小化p f s p 的m a k e s p a n 和最大延迟基准。 ( 4 )为提高混合p s o 算法求解p f s p 的解的精度，提出改进的i n e h 局部 搜索技术，并结合了i v n s 局部搜索技术。 ( 5 )为公正地评估混合p s o 算法的性能，将基于业内使用最普遍的 t a i l l a r d 和d e m i r k o l 基准实例进行评估。此外，还充分对比了混合p s o 算法与其他p s o 算法在求解p f s p 时的效率。 1 4 论文组织 本文主要分成六章，其结构和相关章节的主题如下。 第1 章引言部分介绍了求解p f s p 的研究现状，通过对研究现状的分析， 明确了目前工作中存在的问题及本文的主要研究内容。 第2 章详细介绍了求解p f s p 的各种传统启发式算法和元启发式算法，分 中山大学硕士学位论文序列流水车间调度问题的混合粒子群优化算法研究 析了目前最小化p f s p 的m a l ( e s p a n 和最大延迟基准存在的不足，给出了相关的 应对策略。 第3 章对p s o 的相关理论研究现状进行了介绍，阐述了各种著名的改进策 略，最后总结出目前改进策略中存在的问题和解决问题的方法。 第4 章在第3 章的基础上提出了混合粒子群优化算法，给出了排斥计算和 新的算法参数更新方式，并结合本文提出的s d v 规则阐述如何将混合粒子群优 化算法应用于p f s p 的m a k e s p a n 和最大延迟基准的最小化。 第5 章实验仿真分析了混合粒子群优化算法的性能，包括解的质量、算法 的性能、收敛性等。评估了混合粒子群优化算法与其他解决方法的优劣。 第6 章总结全文并讨论进一步的研究工作。 中山人学硕士学位论文序列流水车间调度问题的混合粒子群优化算法研究 第2 章p f s p 相关理论研究 2 1p f s p 阐述 自从j o h n s o n 【1 11 9 5 4 年发表第一篇关于流水车间调度问题( f l o w s h o p s c h e d u l i n gp r o b l e m ，f s p ) 的文章以来，流水车间调度问题引起了许多学者的关 注。流水车间调度问题一般可以描述为聆个作业要在所台机器上加工，每个作 业需要经过m 道工序，每道工序要求不同的机器。 个作业在所台机器上的加 工顺序相同。作业f 在机器上的加工时间是给定的，设为，f ，( 净1 ，刀；= 1 ，m ) 。问题的目标是求门个作业在每台机器上的最优的加工顺序，使最大 流程时间或其它基准达到最小。对该问题常常做如下假设： ( 1 )每个作业f 在同一时刻只能在一台机器，上处理； ( 2 )每台机器所在同一时刻只能处理一个作业f ； ( 3 )不允许抢占，即不允许中断币在机器，上处理的作业f ； ( 4 )作业之问是相互独立的，准备时间为0 ； ( 5 )机器持续可用； ( 6 )持有在制品库存缓冲。如果作业f 需要的下一台机器正忙，那么作 业f 加入机器，的队列并等待机器，空闲； 流水车间调度问题可以分为：确定型流流水车间调度问题、随机型流水车 问问题、模糊型流水车间问题。在确定型流水车问调度问题中，假定作业的加 工时间是已知的确定量；在随机型流水车间调度问题中，加工时间按照一定的 概率分布而变化；在模糊型决策情况下，每个作业的模糊交货期表示为决策者 对作业完工时间的满意度。此外，如果某一给定的作业在一台或多台机器上的 加工时j 、日j 为o ，则流水车间问题称为广义流水车i 自j 调度问题，否则称为纯流水 车间调度问题或序列流水车间调度问题。在过去的5 0 多年罩，多数研究工作集 中于纯的确定型流水车间调度问题，常用”m 雕删甜表示，即行个作业聊台 机器流水车间最大完工时间。 对于流水车间调度问题的计算复杂性，尽管当机器数m = 2 时，j o h n s o n 证 中山大学硕士学位论文序列流水车间调度问题的混合粒子群优化算法研究 明流水车间调度问题在二项式时间内可最优化，但当，l = 3 时，严格来说流水车 间调度问题就是一个n p c ，一般需要考虑( 甩! ) 所种情况，这也是为什么在大 多数研究工作中进一步限制不允许作业跳跃的原因，即对于所有的机器，处理 作业的顺序都是相同的，所以一个作业不能跳过后面的机器而去另外一台机器 加工。在这种情况下，只需考虑( n ) ! 种调度情况，后来这种问题被称为序列 流水车间调度问题( p e r m u t a t i o nf l o w s h o ps c h e d u l i n gp r o b l e m ，p f s p ) 并且分 类为 聊户凡搬或者为，p r 聊“g 槲。序列流水车间调度的性能衡量包括最 常见的最小化最大完工时间( m a k e s p a n ) 和总流动时间( t o t a lf l o i m e ) ，此 外，还有最小化最大拖期( m a x i m u mt a r d i n e s s ) 、最大延迟( m a x i m u m l a t e n e s s ) 等。对于p f s p 的计算复杂性，r i n n o o yk a n l 2 j 证明了m a k e s p a n 的最小 化是一个n p c ，g a r e y d 等1 3 j 证明了总流动时间的最小化是一个n p c ，l e n s t r a 等【4 】证明了最大延迟的最小化是一个n p c ，因此，p f s p 是一个非常难解决的 组合优化问题。相关研究主要集中于通过启发式优化技术在合理的计算时间内 找出高质量的解，而不是最优解。 2 2p f s p 数学模型 给定作业在机器后上处理时间枷刀( = 1 ，2 ，玎) 个作业顺序通过肌台 机器的作业序列万= 乃，万：，以) ，p f s p 就是查找对于每台机器都有效的最好 的作业序列。对于刀朋尸g 撇问题，c ( 万，历) 表示作业万，在机器朋上的完 工时间。给定作业调度序列刀= 巧，砭，) ，对于玎个作业朋台机器的问题， 完成时i 日j 的计算方法如下表示： c ( 乃，1 ) = ( 2 1 ) c ( 万，1 ) = c ( ，一l ，1 ) + f 勺，1 ：2 ，3 ，刀( 2 2 ) c ( 7 r l ，尼) = c ( 万l ，七一1 ) + 7 1 ，k ：2 ，3 ，聊( 2 3 ) c ( z ，七) = m a x c ( 啊，七) ，c ( 哆，七一1 ) ) + 勺， ( 2 4 ) 定义2 1 ：p f s p 的m a k e s p a n 基准定义如下： c i 。( 万) = c ( 死，m ) ( 2 5 ) 中山大学硕士学位论文序列流水车间调度问题的混合粒子群优化算法研究 所以对于m a k e s p a n 基准的p f s p 就是查找出一个序列万，使其在所有序列 集合兀中，如下关系成立： c m 。( 万) c ( 死，川，v 万n ( 2 6 ) f ( 万，) 表示作业乃的流动时间，由于作业的准备时间为0 ，所以它和作业万， 在机器聊上的完成时间c ( 万，朋) 相等，总流动时问 可( 万) 就是所有作业的总流 动时问或完工时间的和。 定义2 2 ：p f s p 的总流动时间基准定义如下： 聊( 万) = f ( 乃) = c 协户所) ，一，- 1 ( 2 - 7 ) 因此，总流动时间基准的p f s p 就是要发现一个序列7 r + ，使其在所有序列 集合兀中，如下关系成立： 册( 万) 聊( 万) ， v 万兀 ( 2 8 ) 定义2 3 ：作业万，的延迟( 万，) 定义如下： 三( 哆，) = c ( 7 ，所) 一d ( 万，) ( 2 9 ) 定义2 4 ：p f s p 中序列万的最大延迟基准定义如下： 三。( 刀) = m a x ( c ( 7 r ，竹) 一d ( 一，) ) ( 2 - 1 0 ) 在定义2 3 到2 4 中，d ( 万，) 表示作业7 r ，的预期完工时间，所以，p f s p 的 最大延迟基准就是要发现一个序列万+ ，使其在所有序列集合n 中，如下关系成 立： k 。( 刀) k 。( 万) ，v 万n ( 2 11 ) 本文针对p f s p 的m a k e s p a n 基准和最大延迟基准进行研究。 2 3 p f s p 国内外研究现状 2 3 1 传统启发式算法求解p f s p 国内外研究现状 对于作业或机器大于一定数量的实例，p f s p 问题的复杂性使得精确解决方 案不实际，这就是为什么在业内会有各种启发式算法优化p f s p 的主要原因。 这些启发式算法可以分类为构造的启发式算法和改进的启发式算法，前者丌始 先建立可行的调度，然后通过j 下常应用某种形式的特定问题知识试图改进前面 中山大学硕上学位论文序列流水车间调度问题的混合粒子群优化算法研究 产生的调度。 对于应用构造的启发式算法求解p f s p 的m a k e s p a n 或总流动时间，j o l l l l s o n 的算法是最早已知的解决p f s p 的启发式算法【l 】，此算法为2 台机器的实例提供 了最优解决方案。通过将聊台机器聚簇为2 台虚拟的机器，它可以用作聊台机 器实例的启发式算法，这个启发式算法的计算复杂性为( 门l o g 一) 。其他许多研 究人员在他们的算法中已使用j o h n s o n 规则的一般思想，例如：当通过j o h n s o n 规则处理每个作业时，c a m p b e l l 等【6 】设计了一个启发式算法，其本质上就是 j o h l l s o n 算法的扩展，在这种情况下，构造多个调度，最好的一个作为结果，这 种启发式算法被称为c d s ，并且当聚簇脚台原始机器为2 台虚拟机器时建立肌 1 个调度，通过重复运用j o l l l l s o n 规则柬解决得到的2 台机器的问题，c d s 启 发式算法的计算复杂度是( 所2 刀+ 朋门l o g 门) 。近来，k o u l a m a s 【9 2 】提出了一个新 的两阶段启发式算法，称为h f c 。在第一阶段，h f c 启发式算法大量运用j o h n s 0 n 算法的扩展，在第二阶段通过允许作业在机器问跳跃来改进第一阶段得到的结 果。这是个非常有趣的想法，因为众所周知，置换调度只对三机实例才是控制 性的。在通常的m 台机器实例中，置换调度不再必须是最优的。h f c 启发式算 法最大的特点就是允许作业的跨越。在考虑两个阶段的情况下，这个启发式算 法的计算复杂性通常大约是( m 2 刀2 ) 。还有一个值得一提的方法是委派一个权 值或索引给每个作业，然后根据委派的索引对作业进行排序后再安排顺序。这 个想法最初是由p a l m e r 【5 】提出的，他设计了一个非常简单的启发式算法，在这 个启发式算法中，对于每个作业，都累积了一个“斜面索引”，作业是根据这个 索引的非递增排序进行调度的，其计算复杂性是( 聊门+ 力l o g 门) 。d a n n e n b r i n 9 3 】 的r 印i da c e s s ( r a ) 启发式算法是先前j o h n s o n 算法思想和p a l m e r 斜面索引的 混合物，在这种情形下，一个虚拟的2 台机器问题被和在c d s 启发式算法中一 样定义，但是不直接应用超过处理时间的j o h n s o n 算法，而是积累了两个权重 方案，每个方案针对每台机器，然后才应用j o l l n s o n 算法。在两台虚拟的机器 中，带权重的方案为作业产生一个处理时间。就像此启发式算法的名字所暗示 的，r a 在很短的时问内以简单的方法得出了好的解，其计算复杂性是 ( m 玎+ n l o g 玎) 。n a w a z 等【7 】的n e h 启发式算法被认为是求解p f s p 性能最好的 启发式算法，它基于这样的思想：在所有机器上需要较多处理时间的作业应该 中山人学硕_ 上学位论文序列流水车间调度问题的混合粒子群优化算法研究 在序列中尽早调度。n e h 启发式算法描述如下： p s e u d o c o d ene h s t e p l ：计算作业的完全处理时间。计算方法为：v f ，f = 1 ，2 ，胛，f = 乞? 勺， 其中，f 是作业的序号，白是作业f 在机器，上的加1 ：时问。 s t e p2 ：作业以，的非递增顺序排序，然后选取最前的两个作业，评估两个包含它们的 可能调度。 s t e p3 ：选取作业f ，f = 3 ，4 ，玎，通过将其放在已经调度了的作业序列的有可能的f 个位置。例如，如果卢4 ，已经调度的序列就会包含开始的三个在步骤2 中计 算得山的排序表，然后第四个作业可以放置在第一、第一二、第三或第四个位置 上，在卜一个迭代中选取这四个序列中最好的一个。 就像我们所看到的，n e h 启发式算法既不是基于j o h n s o n 算法也不是基于 斜面索引，它唯一的不足就是总共有【刀( 门+ 1 ) 2 】- 1 次调度需要评估，这使得 n e h 启发式算法的复杂度提高到o ( 聊) ，对于较大的问题实例来说，计算时 间有点过长。后来，t a i l l a r d 【8 】通过在仅仅的一步中的一次迭代计算所有的部分 调度，将n e h 的计算复杂度减少到( 朋聆2 ) 。 与构造的启发式算法相反，改进的启发式算法起始于一个已建立的方案并 试图通过一个既定的程序改进它。d a n n e n b r i n g 【9 3 1 提出了两个简单的改进启发式 算法，分别是r a c s ( r a p i da c e s sw i t hc l o s e0 r d e rs e a r c h ，r a c s ) 和r a e s ( r a p i da c e s sw i t h e x t e n s i v es e a r c h ，r a e s ) 。这两个启发式算法的基础是 d a n n e n b r i n g 发现简单地交换由r a 启发式算法得到的序列中的两个邻近作业会 产生一个最优的调度。r a c s 通过交换序列中每一个相邻的作业对，在胛1 次 中产生的最好调度作为结果。在r a e s 启发式算法中，当结果有改进的时候， r a c s 被重复应用。r a c s 和r a e s 都起始于一个由r a 构造的启发式算法产 生的调度。此外，许多其他研究人员也对改进的启发式算法做了大量研究，细 节请看i n i z 和m a r o t o 【9 6 】的关于启发式算法求解p f s p 的调查。 中山大学硕士学位论文 序列流水车间调度问题的混合粒子群优化算法研究 2 3 2元启发式算法求解p f s p 国内外研究现状 当前，可以归结为元启发式算法的大致有禁忌搜索算法、模拟退火算法、 g a 、a c o 和p s o 等，这些元启发式算法首先通过传统启发式算法构造一个序 列，然后迭代直到满足结束标准。o s m a n 和p o t t s l l o l 提出了一个简单的模拟退火 算法，算法中使用了妫圻邻域结构和随机邻域结构。m o c c e l l i n 】的禁忌搜索 主要是基于w i d m e r 和h e n z 的s p i r i t 启发式算法，唯一的不同之处在于计算 问题初始解的每步，保留了和t s p ( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 的相似 性，但是作业之间的距离的计算和w i d m e r 和h e i r c z 的计算方式有所不同。还有， 与t s p 的求解细节也不同，因为m o c c e l l i n 使用了f i t s p ( f a n h e s ti n s e n i o n t r a v e l i n gs a l e s m a np r o b l e m ，f i t s p ) 。r e e v e s l 。2j 提出g a 求解p f s p 的方法，在 这种方法中，算法每步得到的后代不是取代它们的双亲而是取代当前这代中适 值低于平均值的个体。r e e v e s 使用了一个称为c 1 的交叉操作符，c 1 和o p o c ( o n ep o i n to r d e rc r o s s o v e r ，o p o c ) 是等效的。方法的另一个显著特点是使用 了自适应的变异率，算法使用了砌所变异，它能简单地改变一个作业的位置。 此外，r e e v e s 还通过n e h 启发式算法来获得较好的初始解，在双亲的选取中， 双亲1 是通过适值排名而双亲2 是通过均匀随机选取的。 2 3 3p s o 求解p f s p 国内外研究现状 在将p s o 算法应用于求解p f s p 的相关研究工作中，研究人员要么是将 k e n n e d y 和e b e r h a r t 【4 3 1 提出的简单改进p s o 应用于p f s p ，要么就是将 k e n n e d y 和e b e r h a n 【6 1j 提出的离散的二进制版本p s o 应用于p f s p ，这些p s o 算法没有涉及复杂的改进策略，比如约束因子策略、邻域拓扑策略等。目前大 多数应用p s o 求解p f s p 的算法属于离散版本的p s o 算法。不管是将何种形式 的p s o 算法应用于p f s p ，都面