（管理科学与工程专业论文）粒子群优化算法在柔性作业车间调度中的应用研究.pdf

摘要 摘要 传统的作业车间调度问题是求解每个工件具有特定加工机器的一类调度问 题，而在实际生产中，可以加工某个工序的机器往往不止一个，这就产生了柔性 作业车间调度问题。 柔性作业车间调度问题( h e x i b l ej o bs h o ps c h e d u l i n gp f o b l e m ，f j s p ) 由于 具有路径柔性的特点，从而可以避免传统作业车间在正常运行过程中容易出现的 阻塞和拥挤等现象，并且当加工过程中出现机器故障等一些异常情况的时候，作 业车间系统仍然能够维持生产的继续进行，这样可以提高作业车间调度系统的灵 活性。然而，柔性路径的特点也使得这类问题的可行解范围的增大，从而给问题 的求解带来新的挑战。在实际生产中，柔性作业车间调度问题往往需要同时面向 多个目标进行决策分析。因此，寻找有效的方法对多目标柔性作业车间调度问题7 进行求解具有重要的理论价值和应用意义。 本文主要探讨了如何使用粒子群优化( p a n i c l es w 锄o p t i m i z a t i o n ，p s o ) 算法求解柔性作业车间调度问题，特别是多目标柔性作业车间调度问题。本论文 的主要工作与创新点如下： ( 1 ) 研究了基于混沌的p s o 算法在柔性作业车间调度问题中的应用。利用混 沌优化技术的随机性、遍历性特点和易跳出局部极值的能力，在p s o 算 法中引入混沌技术以提高p s o 算法的性能，提出了一种混合p s o 算法。 首先，利用混沌对p s o 算法的参数进行自适应优化，实现全局搜索与局 部搜索间的有效平衡；然后，在p s o 算法的搜索过程中引入混沌局部搜 索策略，以提高求解的精度和收敛速度。并且将该算法分别应用于若干个 单目标和多目标柔性作业车间调度问题的求解，实验结果表明算法具有良 好的全局搜索性能。 ( 2 ) 探讨了基于多目标权重聚合优化策略的p s 0 算法。在p s o 和混沌的混合 优化算法的基础上，针对多目标存在的量纲问题，采用一种基于模糊逻辑 的适应度函数形式。同时，为了进一步保持种群的多样性，最大可能的搜 索到所有的非劣解，利用随机思想生成适应度函数的权系数。实验表明这 种方法使得算法获得的非劣解具有很好的分布行和稳定性。 ( 3 ) 研究了f u l l y i n f 0 珊e d 粒子群( f i p s ) 算法在多目标柔性作业车间调度问 题中的应用。首先，基于p a r e t o 最优概念对种群进行排序，同时将属于相 同p a r e t o 等级的个体定义为邻居，并将这种基于p a r e t o 等级的近邻拓扑 结构用于f i p s 算法中。其次，通过计算同p a r e t o 等级中个体的拥挤距离 a b s t r a c t a b s t r a c t t h et r a d i t i o n a lj o bs h o ps c h e d u l i n gp r o b l e mi sal 【i n do fs c h e d u l i n gp r o b l e m s w h e r ee a c hj o bi sp r o c e s s e db yas p e c i f i e dm a c h i n e b u ti np r a c t i c e ，t h ej o bg e n e r a l l y c a i lb ep r o c c s s e db ym o r et h 锄o n em a c h i n e ，w h i c hb 血g st h en e x i b l ej o bs h 叩 s c h e d u l i n gp r o b l e m s i n c en e x i b l ej o bs h 叩s c h e d u l i n gp o s s e s s e st h ea d v a n t a g co fr o u t en e x i b i l i t y ，i t c a na v o j dt l l e p r o b l 锄0 fj a m u p a n dc o n g e s t i o ni nt h et r a d i t i 彻a lj o b s h 叩 m e 删h i l e ，t h ef i e x i b l er o u t e sc 锄m a k et h es y s t e mp r o c c e dw i t ht h ee x c e p t i o n e n c o u n t e r e dh lt h em 锄u f a c t u r i n gp r o c e d u r es u c h 嬲m a c h i n ef a i l u r e 1 1 l e r e f o r e ，t h e n e x i b l er o u t e sa r ec a p a b l eo fe n h 柚c i n gt h ea g i l i t yo ft h ej o bs h o ps c h e d u l i n gs y s t e m h o w e v e r t h i sn e wf e a t u r ee n l a r g e st h er a n g co ft h ea v a i l a b l es o l u t i o n sf o r t h ef l c x i b l e j o bs h o ps c h e d u l i n gp r o b l e m s 觚db d n g sn e wc h a l l e n g c st 0t h e 西v e np r o b l e m s m o r e o v e r ，m a k i n gd e c i s i o n so nm u l t i p l eo b j e c t i v e si so n e nn e e d e dw h e ns o l v i n g 锄d 觚a l y z i n gt h en e x i b l ej o bs h 叩s c h e d u l i n gp d 0 b l e m si np r a c t i c c t h u s ，s e e k i n gt h e e 虢c t i v em e t h o d st os o l v em u l t i o b j e c t i v ef l e x i b l ej o bs h o ps c h e d u l i n gp f o b l e m si so f i l i l p o n a n tt h e o r e t i c a lv a l u e 蛐dp r a c t i c a ls i 印i f i c a n c e ，n l i sd i s s e n a t i o n m a i n l y d i s c u s s e st l l e a p p l i c a t i o n0 f t h e p a n i d es w a m o p t i m i z a t i o na l g o r i t h mo nn e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m s ，e s p e c i a u yt h e m u l t i - o b j e c t i v ef l e x i b l ej o bs h o ps c h e d u l i n gp r o b l 锄s t h em a i na n dp i o n e e r i n g 、) l ，o r k so ft h i sd i s s e n a t i o nl a r ea sf o l l o w s ： ( 1 ) r e s e a r c h0 nt h ep 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 t l l i i lb a s e do nc h a o sa n di t s a p p l i c a t i o ni nn e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m s a san e wo p t i m i z a t i o n t e c h n i q u e ，c h a o sb e a r sr a n d o m i c i t y ；e r 9 0 d i c i t ya n dt h es u p e r i o r i t y0 fe s c a p i n g 讯姗al o c a l0 p t i m u m b yi n t e 铲a t i n gt h ea d v a n t a g e0 fc h a o s0 p t i m i z a t i o na n d p a n i d es w 痂o p t i m i z a t i o na l g o r i t h m ，ah y b r i dp a r t i c l es w a 咖o p t i m i z a t i o n a 1 9 0 r i t h mi sp r o p o s e d f i r s t l y ，p a r a m e t e l l s0 fp a n i d es 、v a 咖o p t i m i z a t j o n a l g o r i t h m a r e a d 叩t i v e l y c h a o t i c o p t i m i z e d t 0 e l j f i c i e n t l y b a l a n c et h e e x p l o r a t i o na n de x p l o i t a t i o na b i l i t i e s t h e n ，d u t i n gt h es e a r c hp r o c e s so f p a r t i c l e s w a 珊 o p t i m i z a t i o na l g o r i t h m ， t h ec h a o t i cl o c a l o p t i m i z e r i s i n t r o d u c e dt or a j s ei t sr e s u l t i n gp r e c i s i o na n dc o n v e 唱e n c er a t e t 1 l ea l g o r i t h m i sa p p l i e dt 0s o l v i n gt h es i n 醇eo b j e c t i v ea n d m u l t i - o b j e c t i v en e x i b l ej o b - s h o p s c h e d u l i n gp r o b l e m sa n dt h e 醇o b a ls e a r c hp e r f o 姗a n c e0 ft h en e wa l g o r i t h m l i i ( 3 ) i sv a l i d a t e db yt h er e s u l t so fm ec o m p a r a t i v ee x p e f l m e n t s d i s c u s s i o no fm em u h i o b j e c t i v ew e i g h t i n gc o m p o s i t eo p t i m i z a t i o n w l t h p a n i c l es w a 咖o p t i m i z a t i o na l g o r i t j u l l ，r e s u l t i n g i nam u l t i o b j e c t i v eh y b d p a r t i c l es w 舢o p t i m i z a t i o na 1 9 0 r i t l l l l l b a s e do nt h ec o m b i n a t i o no fp a i t i d e s w 锄o p t i m i z a t i o n 觚dc h a o s ，af i t n e s sf u n c t i o nw i t hf u z z yl o 舀ci sp r o p o s e d t 0e v a l u a t et h ep a n i c l c sf o rt h ed i m 即s i o np r o b l e m so fm u i t i p l eo b j e c t i v e s m e 觚w l l i l e ，t l l ew e i g h t i n gc o e 伍c i e n t s a r er a n d o m l yg e n e r a t e dt 0 f u n h e f m a i n t a i nt h ed i v e r s i t y0 ft h ep 叩u l a t i o n 觚d6 n da l lt h en o n d o m i n a t e d s o l u t i o n s 弱m o r ea sp o s s i b l e e x p e r i m e n t so nf o u rt y p i c a lf l e x i b l ej o bs h o p s c h e d u l i n gi n s t 锄c e sa r ep r c s e n t e dt os h o wt h e9 0 0 dd i s t r i b u t i o na n ds t a b i l i t y o ft h en o n d o m i i l a t e ds o l u t i o n sf o u n db yt h ep r 叩o s e d 叩p r o a c h r e s e 鲫c ho nt h ea p p l i c a t i o no ft h ef u l l y - i l l f 0 皿e dp a n i d es w 锄a l g o r i t l 啦i n t h em u l t i o b j e c t i v e n e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m s f i r s n y t h e p o p u l a t i o ni s 删1 1 【e db 硒e d 册p a r c t o0 p t i m a lc o n c 印t a n dt h en c i g l l b o r h 0 0 d t o p o l o g yu s e di nt h cf u l l y i n f o m e dp a n i c l es w 锄a l 鲥t l l l l l i sb a s e d0 nt h e p a r e t or a l l k s e c 0 n d l y ，t l l ec f o w d i l l gd i s t a n c eo fi n d i v i d u a l si sc o m p u t e di nt h e s a m ep a r c t ol e v e lf o rt l l es e c o n d a r yr a i l l 【1 1 l i r d l y ，a d d r e s s i n gt h ep r o b l e mo f t r a p p i n gi n t ot h el o c a lo p t i m a l ，t w om u t a t i o no p e r a t o r sb a s e do nt h ec o d l n g m e c h a i i i s ma f ei n t r o d u c e di n t oo u ra 1 9 0 r i t h m r e s e a r c h0 nm ea p p l i c a t i o no fp a n i d es w 绷o p t i i i l i z a t i o na l g o r i 她b a s e d o n t h ed y n a i n i cp r o b a b i l i s t i cs c a r c h i nt h em u l t i o b j e c t i v ef l e x i b l ej o bs h o p s c h e d u l i n gp r o b l 锄s a tt h ee a l l i e fs t a g e ，t h ea v e r a g eo ft h en e i g l l b o r i n gb e s t i n d i v i d u a l si i l s t e a do ft h eg e n e r a ls i n 酉eo n ei se m p l o y e di nt h ea l g o r i t l l mt 0 g u i d et h es e a r c h i i lt h el a t t c rs t a g e ，t h en e x tg e n e m t i o ni n d i v i d u a l s p o s i t i o n s a r cs 锄p l e df r o mag a u s s md y n 锄i cp r o b a b i l i s t i cd i s t r i b u t i o n 啪u n dt h e e x p e c t e dp o s i t i o n0 ft h ep a r t i d ea tt h en e x tg e n e m t i o nw i t l lt l l ep u 叩o s e o f i i i l p r o v i n gt h el o c a lc x p l o i t i n ga b i l i t yo f0 u rm e t h o d n e n ，b o r r o w i n gi d e a s f 内mp a r e t 0o p t i m i z a t i o n ，m en o n d o m i n a t e ds o l u t i o n sa r cs t o r e db yu s m g 姐 e l i t i s mr e p o s i t 0 珊 a n dan e wf i t n e s s a l l o c a t i o n a p p f o a c h i s p r o p o s e d m e 锄w h i l e ，t l l es e l f - a d a p t i v em u t a t i o no p e r a t o r sa r e i n t r o d u c e dt oe n h a n c et h e d i v e i ，s i t yo fs o l u t i o n s f i n a l l y ；c o m p a r a t i v ee x p e r i m e n t sa r ec o n d u c t e d w i t h s e v e r a l 鲈o u p so ff l e x i b l ej o bs h 叩s c h e d u l i n gi n s t a n c e s t h ee x p e r i m e n t a l r c s u l t ss h o wt h eb e t t e rs e a r c ha b j l j t y0 ft h ea l g o r i t h m ，w h i c hi n d i c a t e st h a tt h c p r o p o s e da l g o r i t h mi sf c a s i b l ei ns o l v i i l gm u l t i o b j e c t i v e n e x i b l ej o bs h o p l v a b s t r a c t s c h e d u l i n gp l o b l e m s k e yw b r d s ：r e x i b l ej o bs h o ps c h e d u l j n gp r o b l e m ( f j s p ) ； 0 p t i m i z a t i o n ( p s o ) ；m u l t i o b j e c t i v e0 p t i m i z a t i o n ； p r o b a b i l i t y v p a r t j d es w a 彻 c h a o s ；d y n a m i c 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：盈蝗乏! 锄占年乡月乡日 第一章绪论 第一章绪论 调度问题，简单地说就是在满足一些约束条件的前提下，对共同使用的资源 进行时间分配。调度问题最早是从制造业中提出来的，但这并不意味着调度只能 在生产制造业中得以应用，实际上，调度在编制作业计划、企业管理、交通运输、 航空航天、医疗卫生、现代化柔性制造系统等众多领域都有着广泛的应用。高效 的调度算法和优化技术是高效的调度方案的基础，而好的调度方案可以提高资源 利用率、降低成本、降低物耗和能耗，从而提高生产效益和企业的竞争力。所以 调度优化算法性能的好坏对这些行业的高效运作有着重要影响，其研究也具有重 要的理论意义和实用价值。 1 1 车间调度问题 1 1 1 问题描述 在离散制造系统中，工件一般经过一系列的工序加工完成，每道工序需要特 定机器和其他资源共同完成，各工件在各机器上的加工顺序( 称为技术约束条件) 通常是事先给定的。车间调度的作用就是根据现有的资源状况合理地安排作业加 工顺序，以满足特定生产目标的要求，一般包括作业排序和资源分配两个目标( 尹 文君等，2 0 0 1 ) 。典型的车间调度可以用四元域表示为：ai 卢i ，l6 ，其中，口和 卢分别为工件数和机器数；y 表征加工过程的特点；6 为性能指标( c o n w a yr v e ta 1 ，1 9 6 7 ) 。如下给出了一个以励觚。，调度问题的数学描述( 卢冰原，2 0 0 6 ) ： m i nm a x m a xc 雎) ，1s 七s 所，1s fs 刀 ( 1 1 ) s ，g 一最+ m ( j n m ) 乏巳，f - 1 ，2 ，刀，j l ，七一1 ，2 ，l ； c 弦一巳+ m ( 1 一) 2 & ，f ，j 一1 ，2 ，珂，七一1 ，2 ，加； c k 芑0 ，f 一1 2 ，刀，i i l ，七；1 2 ，_ r ，l ； 王独s0 或1 ，f ，j = 1 ，2 ，咒，七一1 ，2 ，所 ( 1 2 ) 公式( 1 1 ) 表示目标函数制造跨度为m i nm a x m a xg ) ，公式( 1 2 ) 表示 工艺约束条件决定的各工件工序的先后加工顺序以及加工各个工件的机器先后 顺序。g 和最分别表示作业f 在机器七上的完成时间和加工时间；m 是一个足 第一章绪论 够大的正整数；为指示系数，若机器厅先于机器七加工作业f 则为1 ，否 则为0 ；为指示变量，若作业f 先于作业在机器七上加工，则为1 ，否则 为0 。 1 1 2 车间调度问题的分类 根据研究的侧重点不同，车间调度问题有多种分类方式。这里，根据研究对 象的复杂性可以将车间调度问题分为以下几类( g 硪v e ss t e p h e nc ，1 9 8 1 ) ： ( 1 ) 单机调度问题 在单机调度问题中，加工系统只有一台机器，待加工的零件也都只有一道工 序，所有零件都在该机器上加工。 ( 2 ) 并行机调度问题 在并行机调度问题中，加工系统有一组功能相同的机器，待加工的零件都只 有一道工序，可任选一台机器来加工零件。 ( 3 ) 作业车间调度问题( j o b s h o ps c l l e d u l i n gp r o b l e m ，j s p ) 在作业车间中，加工系统有一组功能不同的机床，待加工的零件包含多道工 序，每道工序在一台机床上加工，零件的加工路线互不相同。在工件加工路线约 束和设备能力约束的双重限制下，作业车间调度问题成为n p - h a r d 完全问题中最 难的问题之一。 ( 4 ) 流水车间调度问题( 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 ) 在流水车间中，加工系统有一组功能不同的机床，待加工的零件包含多道工 序，每道工序在一台机床上加工，所有零件的加工路线都是相同的。流程工业( 如 化工、石油加工、油漆等) 是流水车间的典型例子。流水车间调度问题是作业车 间调度问题的一个特例，它是在作业车间调度问题的基础上统一了工件的加工路 线，因而比一般的作业车间调度问题要大大简化。然而，流水车间调度问题仍然 是与城市距离不对称情况下的旅行商问题难度相当的同一类型问题( 谷峰， 2 0 0 6 ) 。 ( 5 ) 开放式车间调度问题( o p e n - s h o ps c h e d u l i n gp r o b l e m ，o s p ) 在开放式车间中，工件的加工没有特定的路线约束，同一工件各个工序的先 后关系是任意的。在这样的前提下，要获得一个可行调度是相当容易的，并且工 序先后关系的任意性也使可行调度的种类大大增加。但是当调度问题规模较大 时，要从可行调度解空间中搜索到最优或次优调度仍然十分困难。 同时，实际生产中的调度还存在着混合型车间调度，这类问题通常是由以上 两种或是三种调度类型混杂组成的。 就工序数而言，单机和并行机调度属于单工序加工类型，其他为多工序加工 第一章绪论 类型；从加工路径看，并行机和开放式车间调度属于路径不确定类型，其他则为 加工路径确定类型。单机调度问题是最简单的一类调度问题，当生产车间出现瓶 颈机器时的调度就可视为单机调度。作业调度问题是最复杂的一种调度问题，生 产车间中的大多数调度问题都是作业调度，而目前大多数研究也集中在作业车间 调度问题上( 潘全科，2 0 0 3 ) 。 1 1 3 车间调度问题的特点 车间调度问题具有以下一些特点： ( 1 ) 计算复杂性 用公式表达车间调度问题可能不是很难，但是此类问题的求解就是另外一回 事了。大部分车间调度问题都具有n p h a r d 特性( g a r e ym e ta 1 ，1 9 7 9 ) ，其表 现之一是，在实际求解时获得一个最优调度解的时间会随着问题规模的增大呈指 数级增加，因此常规方法难以适应大规模车间调度问题的求解( c h a p t e r1 ，2 0 0 3 ) 。 ( 2 ) 动态随机性 制造系统的加工环境是不断变化的，在运行过程中有很多随机和不确定的因 素。如实际生产线中常常会随机出现交货期改变、机器故障、紧急订单插入等情 况，此外，实际工件的达到时间、加工时间等也有一定的随机性。 ( 3 ) 多约束性 实际车间调度要受到设备、人力及其他辅助生产工具等多种资源的约束，同 时，工件的处理往往也要受到严格的工艺路线约束，各道工序的先后关系不能颠 倒。所以，车间调度问题本质上也可以看作是一个在若干等式和不等式约束下的 组合优化问题。 ( 4 ) 多目标性 在车间调度问题中，针对不同的加工任务有不同的调度目标，如基于加工时 间的指标、基于交货期的指标和基于成本的指标等，并且这些目标之间往往是存 在冲突的。如何使车间调度系统适应不同的任务类型和规模，一直是该领域所面 临的难题之一。 1 1 4 车间调度问题的研究方法 车间调度问题的学术研究始于1 9 5 4 年( j o h n s o ns m ，1 9 5 4 ) ，虽然经过5 0 多年的发展，提出了大批的调度方法，但是至今尚未形成一套系统的理论与方法。 已有的方法可以归结为最优化方法和启发式调度算法两大类( a n d r e a sc n ， 2 0 0 4 ) 。最优化方法是指通过对解析模型精确求解获得最优解，或通过近似求解 第一章绪论 禁忌搜索已经成功地应用于车间调度问题。嘣l l a r de ( 1 9 9 0 ) 提出了解决流水 车间调度问题的禁忌搜索算法。c 血i ar s 等人( 2 0 0 4 ) 基于禁忌搜索提出了两 种启发式算法求解以缩小总延迟为目标的柔性生产车间调度问题。 模拟退火法 模拟退火是基于m e n t ec 矾。迭代求解的一种全局概率型搜索算法，它是一 种串行优化算法。模拟退火算法也广泛地被应用于车间调度问题的求解中。 k 0 l o n k om ( 1 9 9 9 ) 证明标准作业车间调度问题的邻域具有非对称性，鉴于模拟 退火的弱收敛性，提出了将模拟退火和遗传算法结合在一起的混合启发式方法。 e m i na m 和t e r e n c e cf ( 2 0 0 4 ) 应用分布式进化的模拟退火算法在合理的时间 内找到了调度问题的最优解或近似最优解。c l l i n y a 0l 等人( 2 0 0 4 ) 采用模拟退 火算法使搜索过程有更强的鲁棒性。 遗传算法 遗传算法是h o l l a l l d 基于自然选择机制提出的一种并行搜索方法。遗传算法 是一种很好的鲁棒性技术，且易于和其他技术( 如模拟退火、神经网络、启发式 规则等) 相结合，形成性能更优的算法。它已成为近年来解决车间调度问题最主 要的方法之一。q ij g 等人( 2 0 0 0 ) 使用平行多种群的遗传算法成功地解决了 动态车间的调度问题。c h e u l l gw m 和z h o uh ( 2 0 0 1 ) 提出了一种基于遗传算 法和启发式的混合算法来解决与安装顺序有关的车间调度问题。t 锄gl x 等人 ( 2 0 0 2 ) 采用一种改进的遗传算法解决了批量生产的车间调度问题。 1 2 柔性作业车间调度问题 1 2 1 问题描述 一个规模为以朋的作业车间调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) 包含珂个工件( j o b ) ，以，以) 和肌台机器 m ，心，心) ，组成每个工 件，的七，个工序( o p e r a _ t i o n ) 序列d ，= ( d l ，d 2 ，吼，) 描述了，所包含工序的加 工顺序。工件的加工顺序有时也称作技术约束。工件，上的第f 个工序记为0 ：f ， 在确定的机器上加工，加工时间为黾( j e i l s e nm t ，2 0 0 1 ) 。除了技术约束条件 外，作业车间调度问题中通常还要做出以下假设：每一时刻每台机器只能加工一 个作业，且每个作业只能被一台机器加工，加工过程不间断，整个加工过程中机 器均有效；整个加工工程中，每个作业不能在同一台机器上加工多次；各作业必 须按照工艺路线以指定的次序在机器上加工；不考虑作业加工的优先权；操作允 许等待，即一个操作未完成时，后面的操作需要等待；作业的加工时间事先给定， 第一章绪论 且在整个加工过程中保持不变。 由上面的定义可以看出，传统的作业车间调度问题是求解每个工件具有特定 加工机器的一类调度问题，而在实际生产中，可以加工某个工序的机器往往不止 一个，这就是柔性作业车间调度问题( f l e x i b l ej 0 b s h o ps c h e d u l i n gp r o b l e m ， f j s p ) 。 柔性作业车间调度问题具体可以描述为：有九个相互独立的工件，； ( ，一1 2 ，以) 表示第_ 个工件；每个工件都由拧，个工序组成，q ，表示工件，上 的第f 个工序：有小台机器组成的机器集为m ，其中m 。表示第七台机器：对每 个工序0 ：f ，有一组机器可以用来加工，该组机器表示为m i j ，m 盯n 2 ，肌；工 序q ，在机器七上的加工时间k 是预先确定的。此外，加工过程还需满足以下约 束条件：同一工件的工序之间有先后约束，不同工件的工序之间没有先后约束； 每个工序在某一时刻只能在一台机器上加工，且在加工期间不可以被中断；任意 时刻任一台机器最多只能加工一个工序：不同工件具有相同的优先级。问题的目 标通常是找到满足某个评价标准的最优调度方案： 柔性作业车间调度问题是对作业车间调度问题的扩充，它假定一个工序可以 由多台机器加工，因而增加了将每个工序分配到一个可用机器上的路径问题，其 问题的可行解空间增大，这使得柔性作业车间调度问题不仅是n p _ h a r d 问题，而 且是比作业车间调度问题更复杂的一类问题( g a r e vm e ta 1 ，1 9 7 6 ) 。柔性作业 车问调度问题能够充分发挥调度系统的灵活性，其复杂性、约束性、动态性决定 了对该问题的研究能够反映实际生产过程，具有一定的意义。路径或机器柔性的 特点使得它不仅可以避免作业车间加工过程中的阻塞和拥挤现象的发生，而且在 系统出现机器故障等异常状况时，仍能维持生产的继续进行。但是柔性作业车间 调度问题的可行调度数目较相同规模作业车间调度问题的可行调度数目大得多， 在这样大的可行解范围内搜索最优解难度自然要大得多，因而也给作业车间的优 化调度问题带来新的挑战( 姜思杰等，2 0 0 3 ) 。 根据膨，的大小，柔性作业车间调度问题可以分为两类：一种称作完全柔性 作业车间调度问题( t 0 t a lr e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ，t - f j s p ) ，即对 每个工序d f ，有m 。；m ，每个工序可以被机器集m 中的任一个机器加工；另一 种称为部分柔性作业车间调度问题( p a n i a lf l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ， p 。f j s p ) ，即至少有一个工序d f ，的m 。cm 。实际生产系统中的调度问题在机器 选择方面具有柔性的同时也可能具有一些限制，因此p f j s p 比t - f j s p 更具有普 遍意义。但是p f j s p 由于增加了问题的搜索空间和计算时间，也是相对更难的 一类问题( i ( a c e mi e ta 1 ，2 0 0 2 a ) 。 第一章绪论 1 2 2 常用的性能标准 针对柔性作业车间调度问题，有许多不同的性能标准。在介绍这些性能标准 之前，先引入一些符号和定义( h o o g e v e e nh ，2 0 0 5 ) ：每个工件，有一个加工 时间p ，表示这个工件必须被加工的时间长度；给定一个调度方案仃，用s ，( 仃) 表示工件，的开始时间，c ，( 盯) 表示j ，的加工完成时间也即，的最后一个工序 的加工完成时间；如果不允许抢先占有，那么每个工件一旦开始被加工则必须无 中断地进行直到加工完成，则有s ，+ p ，= c ，；工件，被加工的概率会因为其具 有的到达时间一或加工期限d ，而降低，因为它们分别决定了，起始加工时间的 下界和加工完成时间的上界。对于每个工件，可以定义一个交货期d ，来表示特 定的加工完成时间。此外，工件，可以用一个权重w ，来表示其重要性。对某个 给定的调度方案仃，三，p ) = c ，( 仃) 一d ，定义为工件，的延迟，而工件，的拖期 定义为乃( 盯) = m a ) ( 三，( 力，o ) ，最大延迟通常可以记为最大成本厶。每个工件， 都有自己的成本函数f ( c ，) ，该函数可以定义为任何只要在c ，上是非减的函数。 则对某个调度方案盯，其最大成本可以定义为厶戡( 盯) = m a ) 【，乃( c ，( 仃”。可以使 用一个指标函数u ，( 盯) 来标志工件，在调度方案仃中是延迟的( 则u ，= 1 ) 还是 按时( 则u ，= o ) 的。对工件，来说，与延迟相对的是提前，这可以定义为 弓( 伊) = m a ) 【 乃一q ( ，o ) 。 在关于柔性作业车间调度问题的研究文献中，常用的性能标准有如下几种： 最大完成时间或制造跨度：c m 麒( 盯) = m 觚c ，p ) ，指的是调度的最小生 ， 。 产周期，即所有工件的最大完成时间的最小值。这个指标被使用的频率最高 ( k a c e mi ，2 0 0 3 ，v a r a d b a r 萄a nt k e ta 1 ，2 0 0 5 ，a n g e le e ta 1 ，2 0 0 5 ) ； 总体加权完成时间：q = ：吩q p ) ； 最大延迟时间：k 瓤( 仃) = n 弓( 力； 最大拖期时间：瓦。p ) 。甲乃p ) ； 最大成本：五戡p ) = n 乃( q p ) ) ； 总体加权延迟时间：毛= 2 叶乃( ； 第一章绪论 最大提前时间：e 。“( 仃) ；m 尹x e j p ) ； 总体加权提前时间：呸= ：。e j p ) ： 加权延期工件数：u ；：。叶u ，p ) 。 上述的所有性能指标在使用时都是最小化。通常，总体提前的时间指标乓不 单独作为一个性能测试指标来使用，而是与其他性能指标( 如总体延迟时间指标 瓦) 合成在一起形成一个综合指标( 如口瓦+ 卢e 亨) 来使用。这个综合指标 通常用于以最小化存储成本为目标的问题中( d i m i t r ig ge ta 1 ，2 0 0 2 ) 。成品存 储成本是指工件提前完成却又不能提前交货时，制造商需要一定的费用来保管成 品，问题的目标就是要使工件的加工完成时间尽量接近于交货期。实际上，提前 时间和延迟时间都是指工件的完成时间与交货期时间的差值，差值为正时表示延 迟时间，差值为负时表示提前时间，提前交货和延期交货都要受到惩罚。对于实 时调度领域中的问题，这两个指标是最重要的( m u 伯tke ta 1 ，2 0 0 3 ，r a g a oc ， 2 0 0 4 ，n i c i u sa a ，2 0 0 4 ) 。在带有机器柔性的作业车间调度问题中，机器的 总负荷和瓶颈机器的最大负荷是两个最常见的指标，前者指一个调度方案产生的 所有机器负荷的总和，后者指负荷最大的机器的负荷值，它们对于合理分配资源 和提高生产效率有着重要的意义( 勋c e mi ，2 0 0 3 ，夏蔚军等，2 0 0 5 ) 。 1 2 3 进化算法在f j s p 中的研究现状 作业车间调度问题的复杂性是不言而喻的，而柔性作业车间调度问题由于包 含了两个子问题，即机器的分配问题和工序调度问题，成为比经典作业车间调度 问题更难的一类组合优化问题。 目前关于车间调度问题的文献中研究作业车间调度问题的很多，而关于柔性 作业车间调度问题的很少。第一个尝试用进化方法来求解作业车间调度问题的是 d a v i sl ( 1 9 8 5 ) ，而最先研究柔性作业车间调度问题的是b u c k e rp 和s c h l i er ( 1 9 9 0 ) 。他们提出了工序可以在多台机器上加工的问题并通过深入研究开发了 一个多项式方法求解两个工件的柔性作业车间调度问题，这标志着关于柔性作业 车间调度问题研究的开始。在此以后，学术界逐渐开展了对柔性作业车间调度问 题的研究。有的研究者也将柔性作业车间调度问题称作具有柔性加工路径的j s p ( 姜思杰等，2 0 0 3 ) 或带有机器柔性的j s p ( d a u z e r e p e r e ss e ta 1 ，1 9 9 8 ) 。 柔性作业车间调度问题的研究方法按照求解步骤可以分为两类：一种是分解 第一章绪论 法，即分别求解柔性作业车间调度问题中的机器分配问题和工序调度问题，这类 方法因为贴近实际情况，可以简化问题而被大多数研究者所采用；另一种是集成 法，即同时考虑两个子问题。从相关的文献中可以看到数学规划法( 加培e le e t a j ，2 0 0 5 ，t 0 r ；a b is a c ta j ，2 0 0 5 ) 、启发式等多种优化方法被应用到柔性作业 车间调度问题的求解中，其中启发式方法包括分派规则法( h o n b e ta 1 ，2 0 0 4 ， 舢v a r e zv r e ta 1 ，2 0 0 5 ，d i m i t r ig gc t2 1 1 ，2 0 0 2 ) 和人工智能法( 潘全科，2 0 0 3 ) 。 进化算法通过群体搜索策略和个体间的信息交互，使整个种群不断进化，具 有简单、通用和鲁棒性强等优点，从而适合各种优化问题的求解。自2 0 世纪8 0 年代中期以来，用进化算法求解各类组合优化问题的研究蓬勃发展，并显出较强 的潜力。最近，以遗传算法( g e n e t i c 础9 0 r i m m ，g a ) 为代表的进化算法引起研 究者的兴趣并被成功地应用到柔性作业车间调度问题的领域中。c h e n