（管理科学与工程专业论文）基于改进蚁群算法的一类单机调度问题研究.pdf

摘要 单机调度问题( s i n g l em a c h i n es c h e d u l i n g ，s m s ) 是一类重要的生产调度问题，在理论上， 单机调度可看作是其它调度问题的特殊形式，是复杂的多机调度系统的一个子系统，深入研 究单机调度问题可以更好地理解复杂调度系统的结构。在生产实践中，复杂调度问题往往可 以分解为多个单机问题来解决。单机调度问题也是一类经典的n p 难题，对单机调度问题求解 算法的研究可以提供求解复杂调度问题的算法基础，因此，设计一种简单高效的求解算法是 单机调度问题研究的重要方面。 蚁群算法( a n tc o l o n yo p t i m i z a t i o n , a c o ) 是一种智能启发式算法，受自然界中真实蚂蚁 觅食行为启发而来，在信息素的帮助下，蚁群在觅食时总能够找到最短路径。蚁群算法的解 构建程序是在搜索过程中通过不断向部分解添加符合定义的解成分从而构建出一个完整解， 从这个意义上说，单机调度问题多阶段决策的属性非常适合蚁群算法求解。而且，蚁群算法 具有系统性、自组织性、分布式计算、正反馈等特点，使得它在理论上比其它算法求解单机 调度问题时有更大的优越性。但在实际应用中，蚁群算法也出现了运算时间较长、容易陷入 局部极小、参数选取过程比较复杂、算法的智能化程度( 自适应能力) 较低等缺点。因此我 们提出了进一步改善蚁群算法性能的策略与技术，发展了求解单机调度问题的改进蚁群算法。 本文以一类单机调度问题为研究对象，以设计求解该类问题的有效算法为研究重点，提 出了求解单机加权延迟调度问题的几种改进蚁群算法。具体的说，本文的主要内容及创新点 包括： 1 、首先指出了论文所要研究的单机调度问题的概念及其研究背景，并从理论研究和生产 实践两方面分别阐述了研究单机调度问题的意义；接着给出了单机调度问题的理论模型和结 构图，建立了一个具有一般意义的基于模块设计的蚁群算法流程框架；然后提出了本文所要 研究的单机调度问题的特征，从理论上分析了蚁群算法求解单机调度问题的可行性和具有的 优势：最后对包括单机调度问题、单机加权延迟调度问题和蚁群算法等相关问题的研究现状 进行了简要的分析总结，提出了存在的问题，指出本文的研究重点是设计适合求解s m t w t 问题的蚁群算法。 2 、从蚁群算法功能模块的角度在方法层面和理论层面总结了蚁群算法的设计思路，分析 了蚁群算法的不足，由此提出了分支蚁群动态扰动算法( d p b a c 算法) ，从以下五个方面对 基本蚁群算法进行了改进：引入分支策略选取初始出发城市；对状态转移规则进行了改进； 引入交叉变异策略改进蚂蚁周游路径；改进信息素更新规则，引入信息素交流策略中和蚂蚁 信息素的差距；引入条件动态扰动策略进行分阶段局部搜索，等等，并且对d p b a c 算法的收 敛性进行了证明。实验表明，该算法可以有效改善基本蚁群算法搜索时间较长、容易陷入局 部极小等缺点，并且与其它类型的蚁群算法相比也有一定的优势。 3 、研究了求解一类强n p 难的单机调度问题单机加权延迟调度问题( s m t 、t ) 的蚁 群算法。首先从一般意义上给出了s m t w t 问题的变量定义和数学模型，并从附加约束、启 发式规则和求解算法等方面对近年来关于s m t w t 问题的研究文献进行了综述，然后基于 d p b a c 算法的设计思想提出了一种求解s m t w t 问题的改进蚁群算法a c s m t w t ，并针对 s m t w t 问题的特征做了相应的改进，包括选用e d d ( e a r l i e s td u ed a t e ) 规则产生问题的初 始解，采用信息素累加规则计算状态转移概率，构建两两交换( i n t e r c h a n g e ) 邻域和插入 ( i n s e r t i o n ) 邻域进行局部搜索，运用信息素中和策略消减各节点间信息素之间的差距，等等， 并且结合算法的搜索机理从理论上推导了算法的参数值。通过大量标准数据实验表明， a cs m t w t 算法在计算结果和计算时间方面均优于遗传算法，而且与其它蚁群算法相比也有 一定的优势。 4 、针对a cs m t w t 算法在求解s m t w t 问题的过程中参数选取过于复杂这一问题，提 出了基于q 学习蚁群算法的s m t w t 问题求解模型。首先，建立了单机加权延迟调度的多阶 段决策问题模型，推导了s m t w t 问题的m a r k o v 性。其次，分析了蚁群算法的m a r k o v 性， 在q 学习理论框架下对蚁群算法的流程进行了解释。再次，对q 学习在单机调度研究中的应 用进行了综述，分析了用查找表方法计算q 函数的不足，在此基础上建立了一个b p 网络模型 对q 函数进行估计。最后，将q 函数的环境无关性、a g e n t 的学习能力和蚁群算法的分布式计 算、正反馈等优点相结合，建立了基于a c q 算法的s m t w t 问题求解模型。实验表明，a c _ q 算法在计算性能上与a cs m t w t 算法基本相当，但对问题参数的依赖度更小，智能度也更 高。 总之，单机调度问题研究不仅在理论上还是在实践中都有重要的意义，由于单机调度问 题是n p 难问题，因此对它的求解算法的研究非常重要。在本文中，首先提出了一种适用于一 般组合优化问题的改进蚁群算法d p b a c 算法，在此基础上设计了一种求解s m t w t 问题 的改进蚁群算法a c s m t w t ，而为了解决a c s m t w t 算法参数选取复杂、蚂蚁智能化程度 较低等问题，又提出了基于q 学习的改进蚁群算法a c _ q ，并建立了基于a c - q 算法的 s m t w t 问题求解模型。可见，本文的研究内容是相互联系自成体系的，本文的研究成果为单 机调度问题的研究提供了一些新的理论和方法，同时也拓展了蚁群算法的理论研究和应用研 究的领域。 关键词：单机调度；蚁群算法；问题结构图：功能模块；单机加权延迟调度问题：多阶段决 策问题；m a r k o v 性；q 学习；b p n - 络 a b s t r a c t s i n g l em a c h i n es c h e d u l i n g ( s m s ) p r o b l e mi sa l li m p o r t a n tp r o d u c t i o ns c h e d u l i n gp r o b l e m i n t h e o r y , s i n g l em a c h i n es c h e d u l i n gc a nb es na st h es p e c i a lf o r mo fo t h e rs c h e d u l i n gp r o b l e m s a n d as u b s y s t e mo ft h ec o m p l e xm a c h i n es c h e d u l i n gs y s t e m s o ，r e s e a r c h i n gd e e p l yo nt h es i n g l e m a c h i n es c h e d u l i n gp r o b l e mc a nm a k eu su n d e r s t a n db e t t e rt h es t r u c t u r eo fc o m p l e xs c h e d u l i n g s y s t e m i nt h ep r o d u c t i o np r a c t i c e ，c o m p l e xs c h e d u l i n gp r o b l e m sc a l lb eo f t e nd i v i d e di n t oan u m b e r o fs m s p r o b l e m st os o l v e s m sp r o b l e mi sa l s oak i n do fc l a s s i c a ln pp r o b l e m , a n dt h ea l g o r i t h m f o rs o l v i n gs m sp r o b l e mc a np r o v i d e 璐t h eb a s i so fs o l v i n gc o m p l e xo n e s t h e r e f o r e 。i ti s i m p o r t a n tt od e s i g nas i m p l eb u te f f i c i e n ta l g o r i t h mf o rs m s a n tc o l o n yo p t i m i z a t i o n ( a c o ) ，w h i c hi n s p i r e db yt h ef o r a g i i l gb e h a v i o ro ft r u ea n t si nt h e n a t u r e ，i sa ni n t e l l i g e n th e u r i s t i ca l g o r i t h m w i t ht h eh e l po fi n f o r m a t i o n ，a n t sc a na l w a y sf i n dt h e s h o r t e s tp a t ht ot h ef o o d s o l u t i o nc o n s t r u c t i o np r o c e d u r eo fa c oi nt h es e a r c hi sj u s tt ob u i l da c o m p l e t es o l u t i o nb ya d d i n gc o n t i n u o u s l ys o l u t i o ne l e m e n t st oi t s oi nt h i ss e n s e ，t h es m s i sv e r y s u i t a b l ef o rs o l v i n gb ya c ob e c a u s eo ft h ea t t r i b u t e 雒am u l t i s t a g ed e c i s i o nm a k i n g m o r e o v e r , t h e c h a r a c t e r s ，s u c h 硒s y s t e m a t i c ，s e l f - o r g a n i z a t i o n ，d i s t r i b u t e dc o m p u t i n ga n dp o s i t i v ef e e d b a c k s ， m a k ea c o s u p e r i o rt oo t h e ra l g o r i t h m sw h e ns o l v i n gs m t w t h o w e v e r , w h e ni np r a c t i c eu s e t h e r e h a sb e e ns o m es h o r t c o m i n g sa sm o r ec o m p u t a t i o nt i m e ，e a s i l yt r a p p e di nl o c a lm i n i m u ma n ds oo n t h e r e f o r e ，w ep r o p o s es o m em e t h o d st oi m p r o v et h ep e r f o r m a n c eo fa n ts y s t e m , a n dd e v e l o ps e v e r a l a c oa l g o r i t h r mf o rs o l v i n gs m s i i lt h i sd i s s e r t a t i o n t h ec h a r a c t e r i s t i c sa n ds t r u c t u r eo fak i n do fs m sp r o b l e mi ss t u d i e d ，a n d t h ee m p h a s i so ft h i sr e s e a r c hi st od e s i g ns o m ee f f e c t i v ea l g o r i t h m sf o rs o l v i n gt h i sk i n do fs m s p r o b l e m ，a c c o r d i n g l ys e v e r a li m p r o v e da c o sa r ep r o p o s e d s p e c i f i c a l l y , t h em a i nc o n t e n to ft h i s p a p e ra l ea sf o l l o w s ： 1 、t h ec o n c e p to fs i n g l em a c h i n es c h e d u l i n gp r o b l e ma n dt h er e s e a r c hb a c k g r o u n do ft h i s d i s s e r t a t i o n a r ep r o p o s e df i r s t l y t h e nt h es i g n i f i c a n c eo fs m sp r o b l e mi sd i s c u s s e df r o mt h e t h e o r e t i c a la n dp r a c t i c ea s p e c t ，a n dt h et h e o r e t i c a lm o d e l sa n dt h ec o n s t r u c t i o ng r a p ho fs m sa l e p r o p o s e dt oi l l u s t r a t et h ec h a r a c t e r i s t i c so fs m sp r o b l e m ，w h i c h a r es u m m a r i z e dl a t e r m o r e o v e r , t h e c h a r a c t e r i s t i c so fa c oa r ea l s oa n a l y s e di nc h a p t e r1 ，a n daf r a m e w o r ki ng e n e r a ls e n s eo fa c o b a s e do nt h em o d u l a rd e s i g ni sp u tf o r w a r d t h e nt h ef e a s i b i l i t ya n da d v a n t e g ea b o u ts o l v i n gs m s b ya c o a r ea n a l y s e df r o mt h e o r e t i c a lp o i n to fv i e w a tl a s t ，t h er e l a t e di s s u e sa b o u ts m s ，s m t w t a n da c oa r eb r i e f l ya n a l y z e da n ds u m m a r i z e dt op r o p o s ee x i s t i n gd i s a d v a n t a g e s ot h ee m p h a s i so f t h i sd i s s e r t a t i o ni st od e s i g naf a v o r a b l ea l g o r i t h mf o rs o l v i n gs m t w t i i i 2 、d i f f e r e n ti d e a sf o rd e s i g n i n gm a i nf u n c t i o nm o d u l e so fa c oa r es u m m a r i z e da c c o r d i n gt o t e c h n i q u ea n dt h e o r ya s p e c t si no r d e rt oa n a l y s et h ed i s a d v a n t a g e so fa c o ，b a s e do nw h i c ha n i m p r o v e da c o ，d p b a ca l g o r i t h m , i sp r o p o s e df o rg e n e r a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s i n d p b a ca l g o r i t h m , s e v a r a la s p e c t so fb a s i ca c oa r ei m p r o v e d , i n c l u d i n gt h a ti n t r o d u c i n gb r a n c h i n g m e t h o dt oc h o o s es t a r t i n gp o i n t s ，i m p r o v i n gs t a t et r a n s i t i o nr u l e s ，i n t r o d u c i n gm u t a t i o nm e t h o dt o s h o r t e nt o u r s ，i m p r o v i n gp h e r o m o n eu p d a t i n gr u l e sa n d i n t r o d u c i n g c o n d i t i o n a ld y n a m i c p e r t u r b a t i o nm e t h o d m o r e o v e rt h ec o n v e r g e n c yo fd p b a ca l g o r i t h mi sp r o v e d b ye x p e r i m e n t s ， t h ea d v a n t a g e so fd p b a ca l g o r i t h m , t h a tc a ns h o r t e nt h ec a l c u l a t i o nt i m ea n da v o i dt h el o c a l o p t i m u m , a r ep r o v e d f u r t h e r m o r e ，c o m p a r e dw i t ho t h e r k i n d so fi m p r o v e da c o ，d p b a ca l g o r i t h m h a si t so w nm e r i t s 3 、as t r o n gn p - h a r ds m s ，s i n g l em a c h i n ew i t ht o t a lw e i g h t e dt a r d i n e s s ( s m mp r o b l e m , i ss m d i c d f i r s t l yt h ev a r i a b l e sa n dt h em o d e lo fs m t w ti ng e n e r a ls e n c ea r ed e f i n e d ，t h e nt h e a r t i c l e sa b o u tt h er e s e a r c ho fs m t w tp r o b l e ma r es u m m a r i z e df r o mt h e p o i n t so fa d d i t i o n a l c o n s t r a i n t s ，h e u r i s t i c a lr u l e sa n ds o l v i n ga l g o r i t h m s b a s e do nd p b a ca l g o r i t h m , a ni m p r o v e da c o f o rs m t w t p r o b l e m , a c _ s m t w ta l g o r i t h m , i sp r o p o s e d a n dt h ep a r a m e t e r so fw h i c ha r et r i e dt 0 b e t h e o r e t i c a l l yc o n c l u d e df r o ms e a r c h i n gm e c h a n i s mo fa l g o r i t h mr a t h e r t h a n o n l yf r o m e x p e r i m e n t s t h ed a t ao b t a i n e df r o mb e n c h m a r ke x p e r i m e n t ss h o wt h a tn o to n l yo nt h ec a l c u l a t i o n t i m eb u ta l s oo i lt h es o l u t i o n ，a c s m t w ta l g o r i t h mp e r f o r mb e t t e rt h a ng e n e t i ca l g o r i t h m , e v e n s u p e r i o rt oo t h e ri m p r o v e da c oa l g o r i t h ma ts o m ea s p e c t s 4 、as m t w tm o d e lb a s e do na ni m p r o v e da c oa l g o r i t h mu s i n gq l e a r n i n gi ss m d i e di no r d e r t oa v o i dt h ec o m p l e xp a r a m e t e rs e l e c t i o ni na c s m t w ta l g o r i t h mf o rs o l v i n gs m t w t p r o b l e m f i r s t l y , t h em u l t i s t a g ed e c i s i o nm a k i n gm o d e lo fs m t w tp r o b l e mi sp r o p o s e d ，a n dt h em a r k o v p r o p e r t i e so fs m t w ta n da c o a r ec o n c l u d e d i nt h ef o l l o w i n g ，t h ef l o wo fa c oi se x p l a i n e db y q l e a f i n gt h e o r y t h e nt h ea p p l i c a t i o no fq l e a r n i n gt ot h es i n g l em a c h i n es c h e d u l i n gi ss u m m a r i z e d ， a n dt h ed i s a d v a n t a g e so fl o o k - u pt a b l ef o re s t i m a t i n gqf u n c t i o nv a l u ea r ea n a l y z e d ，t h e r e f o rab p n e u r a ln e t w o r ki sp r o p o s e dt oe s t i m a t eqf u n c t i o nv a l u e b a s e do nt h e s e ，a ni m p r o v e da c o u s i n g q - l e a r n i n g ，a c qa l g o r i t h m , i sp r o p o s e df o rs m t w tp r o b l e mt o a v o i dt h ec o m p l e x i t yo f a c s m t w ta l g o r i t h mt oc h o o s ep a r a m e t e r s i na c _ qa l g o r i t h m , t h ec h a r a c t e r i s t i c so fq - l e a r n i n g ， w h i c ha r et h ee n v i r o n m e n t - i n d e p e n d e n c eo fqf u n c t i o na n dt h el e a r n i n ga b i l i t yo fa g e n t s ，a l e c o m b i n e d 丽mt h ea d v a n t a g e so fa c o ，w h i c ha r et h ed i s t r i b u t e dc a l c u l a t i o n ，p o s i t i v ef e e d b a c ka n d s oo n a sac o n s e q u e n c e ，t h ei n t e l l i g e n c ea n ds t a b i l i t yo fa c oa r ei m p r o v e d ，w h i c ha r ep r o v e db y t h ee x p e r i m e n t sa tl a s t i nc o n c l u s i o n ，s m sp r o b l e mi sv e r yi m p o r t a n tn o to n l yo nt h e o r e t i c a la s p e c tb u ta l s oo n p r a c t i c a la s p e c t h o w e v e r , s m si sn ph a r dp r o b l e mt h a ti sc r i t i c a lt of m dag o o ds o l v i n ga l g o r i t h m i v i nt h i s d i s s e r t a t i o n ，a i li m p r o v e da c oa l g o r i t h m , d p b a c ；i sf i r s t l yp r o p o s e d f o r g e n e r a l c o m b i n a t o r i a lo p t i m i z a t i o np r o b l c r n s t h e nb a s e do nd p b a c ，a ni m p r o v e da c of o rs m t w t p r o b l e m , a c _ s m t w t , i sp r o p o s e d a tl a s t ，t os o l v et h ed i s a d v a n t a g eo fa c _ s m 州v t , a na c o a l g o r i t h mb a s e do nq l e a r n i n gi sp r o p o s e d s ot h e s et h r e ei m p r o v ea c o s h a v er e l a t i o n s 谢me a c h o t h e r , a n dt h e yp r o v i d en e wt h e o r i e sa n dm e t h o d sf o rs m t w t o ro t h e rc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m , a l s oe x t e n dt h er e s e a r c ho ft h e o r ya n da p p l i c a t i o no f a c o k e yw o r d s ：s i n g l em a c h i n es c h e d u l i n g ，a i rc o l o n yo p t i m i z a t i o n ，p r o b l e ms t r u c t u r eg r a p h ，f u n c t i o n m o d u l e ，s i n g l em a c h i n es c h e d u l i n gw i t ht o t a lw e i g h t e dt a r d i n e s s ，m u l t i s t a g ed e c i s i o n m a k i n g ，m a r k o vp r o p e r t y , q - l e a r n i n g ，b pn e u r a ln e t w o r k v 插图清单 图1 1马钢车轮分公司生产线设备及工序示意图2 图1 2 单机调度问题的结构图4 图1 3 蚁群算法的流程框架7 图2 1 基本蚁群算法的求解步骤。1 8 图2 2 蚂蚁周游路径的变异策略。2 6 图2 3 不同信息素更新规则下d p b a c 算法的收敛过程2 7 图2 4 不同循环代数h 分布变化图( 左1 0 代，右1 5 0 代) 2 8 图2 5 算法有无扰动时不同的收敛过程。3 0 图3 】改进蚁群算法求解s m t w t 问题的算法流程。4 6 图3 2b 的不同取值对倒指数曲线的影响5 l 图3 3 多种启发式信息式对优化目标的影响5 2 图4 1强化学习的框架结构5 8 图4 2q 学习算法流程。6 1 图4 3 蚁群算法的循环嵌套图6 4 图4 4 一个查找表实例6 9 图4 5b p 网络的拓扑结构7 0 图4 - 6 基于b p 网络的q 函数估计算法7 2 图4 7 网络训练曲线图7 3 图4 8 期望输出与实际输出的对比7 3 图4 - 9 基于q 学习蚁群算法的s m t w t 问题求解流程7 5 图4 1 0 两种算法的计算结果7 8 x 表格清单 表1 1t s p 和s m s 的结构图4 表1 2 应用于s m t w t 问题的一些启发式规则。1 2 表2 1d p b a c 算法求解t s p 问题的实验结果3 7 表2 2d p b a c 算法与其它两种蚁群算法的比较3 8 表3 1近年来部分s m t w t 问题的特征和求解算法。4 5 表3 2 蚁群算法与遗传算法性能的比较5 3 表3 3 求解s m t w t 问题的两种蚁群算法计算结果对比5 4 表3 - 4 三种算法计算结果对比表。5 5 表4 1蚁群算法与q 学习的对比6 5 表4 2 三种算法求解4 0 - j o b 算例的结果比较。7 6 表4 3 两种改进蚁群算法的比较7 7 表4 - 4 两种算法计算结果的总体样本分布对比表7 8 x i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金b 巴王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位做作者签名叶殇 签字眺沙嘲月6 日 学位论文版权使用授权书 本学位论文作者完全了解金月垦王些盍堂有关保留、使用学位论文的规定。有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权业 王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 叶 i 签字日期：伽8 年占月6 日 学位论文作者毕业去向： 工作单位： 通讯地址： 导师签名： 纠矾 签字日期：泌旨年6 月厶日 电话： 邮编： 致谢 值此论文完成之际，我首先要感谢辛勤培育我的导师刘心报教授。在博士学习期间，刘 老师对我的学习、科研和生活等各个方面都给予了无微不至的关怀和悉心的指导，我取得的 每一点进步，都凝聚着导师大量的心血。刘老师渊1 尊的知识、严谨的治学作风、勤奋的工作 态度以及正直的思想品格，使我受益匪浅，并将对我的终身产生深远的影响。 衷心感谢杨善林教授对我的指导和关心，特别是在我论文写作期间，杨老师给予了我很 多重要的理论指导和建设性意见，在此谨向杨老师致以诚挚的谢意。 衷心感谢合肥工业大学管理学院和研究生院的各位领导和老师对我的关心和帮助，特别 是梁昌勇教授、倪志伟教授、刘业政教授、朱卫东教授、周永务教授、马溪骏教授、刘林副 教授等老师对我的关心和帮助。 感谢决策科学与技术研究所为本人提供的研究条件，感谢决策所的所有老师和同学共同 营造了一个积极向上的研究氛围。感谢我的同学和师兄弟黄永青、陈增明、柏吴、杨昌辉、 李锋刚、周典、瞿浩、程浩、裴凤、周谧、吴坚、林文龙等人，在数年的学习生活中，我们 一起交流、相互学习，结下了深厚的友谊。在课题研究和论文写作过程中，他们给予了大量 的帮助和启发，使我受益良多。 感谢我的家人对我的理解、支持和奉献，他们无私的爱是我的坚实后盾和精神支持。 感谢各位评审专家在百忙之中抽出宝贵时间所做的评审工作。 最后，谨以此文献给所有关心、爱护、支持和帮助过我的人，以表达我对他们由衷的感 谢和祝福。 v i 作者：叶强 2 0 0 8 年5 月 第一章绪论 第一章绪论 生产调度理论是在满足当前生产条件的约束下对主要生产要素( 包括设备、原材料、劳 动力等) 进行合理配置。自从1 9 5 4 年生产调度理论创立以来【l 】，在全社会提高劳动生产率和 资源利用效率、降低生产成本方面起到了极其巨大的作用。单机调度问题( s i n g l em a c h i n e s c h e d u l i n g 。s m s ) 是生产调度研究领域的一类非常重要的问题，模型虽然简单，但它在理论 和方法研究方面却有着非常重要的地位。单机调度问题是一类经典的n p 难题，设计一种简单 高效的求解算法是单机调度问题研究的重要方面。本文正是研究如何用改进蚁群算法求解一 类单机调度问题，以提高问题的求解效率。 本章首先指出了所要研究问题的背景；其次对单机调度问题的结构图和特征进行了介绍； 接着对基于模块设计的基本蚁群算法流程框架进行了解释，并从蚁群算法具有的特点入手说 明适合求解单机调度问题的原因；然后对相关问题的研究现状进行了综述，并对存在的问题 进行了分析。最后，概括了全篇论文的结构脉络和主要内容。 1 1研究背景 本论文的研究工作是围绕国家高技术发展研究计划( 8 6 3 计划) 课题“面向机械制造业的 连续多时段整体智能优化下料问题研究及系统实现”的前期预研课题“马鞍山钢铁公司车轮 分公司生产决策模型与决策支持系统研究”而展开的。 马钢车轮分公司是亚洲最大的生产火车整体碾钢车轮和轮箍的企业，经营销售车轮、轮 箍、环件等六大系列2 0 0 0 多种规格的产品。近年来，由于国内外市场对车轮轮箍产品的需求 非常旺盛，公司生产面临很大压力。但公司的计划制订过程仍沿用传统流程，不仅费时费力， 而且计划的可执行性比较差，一旦计划需要临时变更或突发设备故障，很难及时对计划做出 相应修改。另一方面，随着钢材、石油、天然气等生产资料价格提高，生产成本增加，公司 面临繁重的节能降耗任务。在这种需求的推动下，合肥工业大学管理学院决策科学与技术研 究所与马钢车轮分公司共同合作，对公司计划调度系统进行研究改造以期进一步提高生产能 力。 该公司拥有两条车轮生产线和一条轮箍生产线，如图1 1 所示。工序流程一般是这样的： 首先是切锭工序，数种型号的连铸锭和钢锭通过圆盘锯及切锭机床被切割成多达两千种规格 的毛坯，经过环形加热炉加热后分别进入轮箍轧机和车轮轧机轧制，接着进行等温、淬火、 回火等热处理工序以改善产品的物理性能，然后对各种车轮、轮箍的半成品进行精加工，经 过检测合格最后包装入库。 1 合肥工业大学博士学位论文 圆盘锯i _ 广- 一轮箍坯加热炉i - 切锭机床i f 磊一 ， ，下 ：；车蓁坯加热炉； ：。 _ l 二二_ 二二j 7 j 一轮箍轧机l 一_ 一1 床l 一等温井式炉卜一炉| _ 一 f + i 车轮新轧机卜一7 0 米冷床l 1 l 上叫车轮老轧机f - 叫s o 米冷床p t 蔓匹h 粗加工机床卜+ il 一淬火加热井式炉卜一淬火水槽卜一回火加热井式炉卜l - l _ 叫淬火加热环形炉r 一1淬火台r 。i 回火加热环形炉| _ _ + 1 一轮箍( 环件) 取样l - 一 轮箍( 环件) 加工机床b r - 叫车轮取样| - 一车轮预加工机床l 一车轮精加工机床l _ - j 1 - i轮箍( 环件) 检测- i 轮箍( 环件) 刷油包装入库 r l -l _ 7 i 车轮检测 i7 i 车轮刷油包装入库 图1 1马钢车轮分公司生产线设备及工序示意图 综观几条生产线，可以在很多环节发现单机调度问题的存在。比如，加热炉和轧机分别 是加热工序和轧制工序中唯一的一台设备，对它们的使用调度显然属于单机调度问题：尤其 在轮箍生产线，轧制工序是瓶颈，整条生产线都必须以轮箍轧机为核心来进行调度排产，而 实际工作中轮箍( 包括环件) 生产线的计划也正是以轮箍轧机生产计划的形式制订的；车轮 生产线由于瓶颈较多，调度排产也相对困难，但可以将复杂的调度问题分解为多个相对简单 的调度问题来处理，其中自然也包括单机调度问题。 1 2 1单机调度问题简介 1 2单机调度问题 在生产调度研究领域，单机调度问题( s i n g l em a c h i n es c h e d u l i n g ，s m s ) 一直是研究热 点。基本问题可以描述为，甩项相互独立的任务需要在系统中的一台机器上序贯处理，每项任 2 第一覃绪论 务都有加工时间、交货期等参数，此外还要满足一些调度环境和约束条件的要求，调度目标 就是要找到个最优的任务序列使得系统总成本最小。 在理论上，单机调度可看作其它调度问题的特殊形式，因此深入研究单机调度问题可以 更好地理解复杂的多机调度问题的结构，同时，求解单机调度问题的启发式算法也可以作为 求解复杂调度问题的算法的基础。在生产实践中，复杂调度问题往往可以分解为多个单机问 题来解决，另外，若一条生产线上的某台机器成为瓶颈，则整条生产线的调度都要围绕该机 器进行。 生产中单机调度的例子不少。比如生产线上的一台机器人负责将半成品从缓冲区搬运至 机床进行加工，这就存在如何合理调度机器人的行进路径以及安排物料搬运次序使得机床利 用率最高且不影响紧后工序生产的问题。再比如钢铁热轧车间一般会配备一座环形加热炉， 切割后的各种坯料将按一定次序进入加热炉加热，再依次取出进行轧制，由于坯料的加热时 间都很长且不同坯料的加热时间不尽相同，因而合理安排坯料加热次序对后续工序的生产意 义重大。 单机调度问题看似简单，然而根据排列组合知识可知，系统中n 个工件加工次序的全排列 为，l ! ，当n = 2 0 时，万! = 2 4 x 1 0 1 8 ，若要对所有可能排序计算出结果进行比较，即使是每秒 运算十亿次