（管理科学与工程专业论文）生产作业调度问题的软计算方法研究.pdf

西南交通大学博士研究生学位论文第1 页 摘要 随着市场竞争的日趋激烈，每个企业都在寻求较好的生产与运作管理方 案，以提高企业的生产、经营和管理效率，从而提高企业的核心竞争优势。而 生产与运作管理的核心是生产作业调度问题能否高效地获得优化解，因此，研 究生产作业调度问题具有很大的理论意义和现实价值。 本文详细介绍了生产作业调度问题的目标、类型及研究现状，并着重就流 水型作业调度问题的研究现状和该类问题的数学模型与相关算法，如启发式方 法、进化算法、邻域搜索方法等进行了探讨，指出了存在的问题。然后对解决 组合优化问题的遗传算法的序号编码和基于序号的遗传算子进行了总结和概 括，最后综述了几类典型生产调度问题的遗传优化研究情况。 在论述了遗传算法的思想、与传统搜索算法的比较优势、遗传算法的基本 特征和遗传算法的理论基础( 包括模式定理、隐含并行性、基因块假设、欺骗 问题和收敛性定理) 后，重点探讨了遗传算法在f l o ws h o p 调度问题中的潜力 和有效性；结合启发式规则，提出了一个改进的遗传算法一基于启发式规则的 有序遗传算法，新算法在初始种群中引入了启发式算法的解，在种群结构上采 用了先按适应值优劣排序再分段确定选择概率的新策略。使优质个体有更多的 杂交机会，在变异中设计了变异控制规则，以防种群单一化，而陷入局部优化 解。通过对不同规模的实例进行计算机模拟，结果表明算法对求解f l o ws h o p 排序问题具有全局搜索优势，获得了群体优化解。 在分析不同移动方式对生产实际和投产顺序的影响的基础上，构建了在平 行顺序移动方式下f l o ws h o p 调度问题的数学模型；然后论述了混合算法的结 构形式和三种算法的优缺点，给出了基于遗传算法的混合优化策略和相应的结 构流程；考虑到遗传算法本身存在的“早熟收敛”和局部搜索能力较差等问题， 把模拟退火过程与种群进化过程结合起来，提出了基于启发式规则和模拟退火 的自适应混合遗传优化算法。并用该算法对平行顺序移动方式下f l o ws h o p 调度问题进行模拟计算，结果表明，遗传算法的早收敛现象得到遏制，解的质 量有所提高。 在平行顺序移动方式下f l o ws h o p 调度问题的工件完工时间的计算模型基 础上，分析了带固定交货期和模糊交货期时该问题的工件完工时间的隶属函 数，及总拖期最小化和总满意度最大化这两个目标函数的相互关系，指出前者 西南交通大学博士研究生学位论文 第1 l 页 闻题是后者闯遂的个子集，臻每个工件搂糨交斐镄的隶瘸丞数表示决策者对 该工伴完工时润鹣溃意度，以总满意痰为躁标函数，蝴应地建立了该阅题下带 模糊交货期的数学模型，设计了一个基于遗传算法的计算机模拟系统进行仿真 试验，结果是令人满意的。 讨论了两工序成组生产系统的生产量与作业顺序的优化问题，考虑了组间 平行、组内平行顺序的工件移动方式，通过扩展该模鹜建立了成组流水线上多 品种多工序加工时生产计翊和调度静集成模型，从计算智能优纯的角凄，提出 了一种二避稍编确与有序编码楣结合的二层次遗传像亿方法。实铡模拟结果表 鞠：该二层次遗传优化方法能综合考虑生产量和生产顺序，并能套效地求提整 数优化惩。 在前期研究成果翔相关领域中其他学者的研究成果的基础上，提出了个 用软计算方法解决生产作业调度问题的优化调度系统，作为一个新的研究领 域，本文主要总结了调度问题从基于数学模型的静态系统向基于问题的动态系 统转变的必然趋势，提出了一个遗传篱法与专家系统相结合的方案，讨论了綦 予遗传算法的智能化专家调度系统的系统结构及工作撬制。 疆磊，讨论了生产俸韭调度溺瑟装遴一步硬究方向。 本文工作褥到国家爨然科学基金( 7 9 4 7 0 0 7 2 、7 9 8 7 0 0 3 5 ) 和嬲川省重点矛斗 磺计划项曼( 0 1 g y 0 5 1 - 2 6 ) 资助。 【关键词】生产计划与调度；遗传算法；模拟遐火算法；启发式规则；混合 遗传算法；模糊交货期；专家系统：软计算 西南交通大学博士研究生学位论文第1 i i 页 a b s t r a c t w i t hi n c r e a s i n g l yk e e nm a r k e tc o m p e t i t i o n ，e a c he n t e r p r i s ei s s e a r c h i n g f o ra g o o d m a n a g e m e n ts y s t e m f o r p r o d u c t i o n a n d o p e r a t i o n t o i m p r o v ee f f i c i e n c y i n p r o d u c t i o n ， o p e r a t i o na n dm a n a g e m e n t a sw e l l ，t h e r e b ye n h a n c ei t so w nc o r ec o m p e t i t i v ea d v a n t a g e w h i l e t h ek e yo fp r o d u c t i o na n do p e r a t i o nm a n a g e m e n ti sw h e t h e rt h ep r o d u c t i o na n ds c h e d u l i n g p r o c e s s c o u l da c h i e v et h e o p t i m a ls o l u t i o n ，t h e r e s e a r c ho nt h ep r o d u c t i o np l a n n i n ga n d s c h e d u l i n gi so f g r e a tv a l u e b o t hi nt h e o r ya n di np r a c t i c e t h ep a p e rd e t a i l st h eo b j e c t i v e ，t y p e sa n dp r e s e n tr e s e a r c ho fp r o d u c t i o ns c h e d u l i n g ， d i s c u s s e st h ec u r r e n tr e s e a r c hs t a t eo ft h ef l o ws h o ps c h e d u l i n ga n dt h er e l a t i v ea l g o r i t h mo f t h i st y p eo f p r o b l e m ，p i n p o i n t se x i s t i n gd i s a d v a n t a g e s ，a n dt h e np r o v i d e st h eg e n e r a l i z a t i o no f o r d i n a lc o d i n go f g e n e t i ca l g o r i t h ma n dg e n e t i cc o m p u t i n ge l e m e n t b a s e do nt h eo r d e r f i n a l l y , g e n e t i co p t i m i z a t i o n r e s e a r c hi ss u m m a r i z e do ns e v e r a l t y p i c a lp r o d u c t i o ns c h e d u l i n g p r o b l e m s a f t e re x p o u n d i n gt h eg e n e r a li d e ao fg e n e t i ca l g o r i t h m ，t h ec o m p a r a t i v ea d v a n t a g e si n c o n t r a s tt ot h et r a d i t i o n a l a l g o r i t h m ，t h eb a s i cc h a r a c t e r i s t i c so fg e n e t i ca l g o r i t h ma n di t s t h e o r e t i c a lb a s e ，t h ep a p e rp u t s e m p h a s i s o nt h ee f f i c i e n c yo fg e n e t i c a l g o r i t h mi n t h e s c h e d u l i n go f f l o ws h o p ，a n dp u t sf o r w a r da ni m p r o v i n gg e n e t i ca l g o r i t h m ：t h eo r d i n a lg e n e t i c a l g o r i t h mb a s e d o nt h eh e u r i s t i cr u l e s t h en e w a l g o r i t h mi n t r o d u c e si n t ot h ei n i t i a lg r o u pt h e s o l u t i o no fh e u r i s t i ca l g o r i t h m ，a n di nt h eg r o u ps t r u c t u r ea d o p t sas t r a t e g yo ff i r s to r d e r i n g a c c o r d i n gt ot h ep r i o r i t yo ft h ea d a p t i v es o l u t i o n ，a n dt h e nd e f i n i n gan e ww a y o fc h o o s i n g p r o b a b i l i t yb ys e g m e n t s ，w h i c hp r o v i d e s m o r e h y b r i d i z i n g o p p o r t u n i t y f o r o p t i m i z e d i n d i v i d u a l s ，a n dd e s i g n sv a r i a t i o n - c o n t r o lm l et op r e v e n ts i n g l ep o p u l a t i o na n dp a r t i a lo p t i m a l s o l u t i o n b yt h ec o m p u t e r s i m u l a t i o no f d i f f e r e n ts c a l e so f r e a le x a m p l e s ，t h er e s u l t ss h o wt h a t t h en e wa l g o r i t h me m b r a c e sa l l - r o u n ds e a r c h i n ga d v a n t a g e st o w a r df l o ws h o ps c h e d u l i n g p r o b l e m ，a n d a c h i e v e so v e r a l lo p t i m a ls o l u t i o n i na d d i t i o n ，o nt h eb a s eo ft h ea n a l y s i so ft h ei n f l u e n c e so fd i f f e r e n tm o v e m e n t so nt h e p r o d u c t i o np r a c t i c ea n di n p u to r d e r , t h ep a p e rc o n s t r u c t s am a t h e m a t i c a lm o d e lo ft h ef l o w s h 叩s c h e d u l i n gi nt h es i t u a t i o no f i t s p a r a l l e lm o v e m e n t ，i l l u s t r a t e st h es t r u c t u r eo fh y b r i d a l g o r i t h ma n db o t ha d v a n t a g e sa n dd i s a d v a n t a g e so ft h r e ea l g o r i t h m s a n de x h i b i t sh y b r i d o p t i m a ls t r a t e g yd e r i v e df r o mg e n e t i ca l g o r i t h ma n dr e l a t i v e s t r u c t u r ep r o c e d u r e w i t ht h e c o n s i d e r a t i o no f g e n e t i ca l g o r i t h m si n n a t ed r a w b a c k so f “p r e m a t u r er e s t r a i n t ”a n dp o o rp a r t i a l s e a r c h i n gc a p a b i l i t y , t h ep a p e rp u t sf o r t ha u t o - a d a p t i v eh y b r i dg e n e t i co p t i m i z a t i o na l g o r i t h m ， 西南交通大学博士研究生学位论文第l v 页 c o m b i n i n gt h es i m u l a t e da n n e a l i n gp r o c e s s 州g r o u pe v o l u t i o np r o c e s s t h ea l g o r i t h mi s f u r t h e ru s e dt os i m u l a t et h ef l o ws h o ps c h e d u l i n gi nt h ep a r a l l e lm o v e m e n t t h er e s u l t sd i s p l a y t h a tt h e p r e m a t u r er e s t r a i n t ”i sr e s t m i n e d ，a n dt h es o l u t i o nq u a l i t yi si m p r o v e d w h a ti sm o r e ，b a s e do nt h ec o m p u t i n gm o d e lo f t h e f i n i s h i n gt i m ep e rp i e c eo f f l o ws h o p s c h e d u l i n g i nt h e p a r a l l e lm o v e m e n t ，t h ep a p e ra n a l y z e s t h es u b o r d i n a t ef u n c t i o no fi t s f i n i s h i n gt i m ep e rp i e c ei nr e s p e c t i v ec o n d i t i o n so f d e f i n i t ed u ed a t ea n df u z z yd u ed a t e ，a n d m u t u a lr e l a t i o n s h i po ft w oo b j e c t i v ef u n c t i o n sb e t w e e nm i n i m i z a t i o no fd e l a y e dt e r ma n d m a x i m i z a t i o no fg e n e r a ls a t i s f a c t i o n ，p o i n t i n gt h a tt h ef o r m e ri st h es u b s e to ft h el a a e na n d r e p r e s e n t i n gt h es a t i s f a c t i o nl e v e lo f t h em a n a g e rt o w a r df i n i s h i n gt i m eo ft h ep i e c ew i t ht h e s u b o r d i n a t ef u n c t i o no f f u z z yd u ed a t e ，m a k i n gg e n e r a ls a t i s f a c t i o nl e v e la so b j e c t i v ef u n c t i o n ， t h ep a p e ra c c o r d i n g l ys e t su pam a t h e m a t i c a lm o d e li nt h ec o n d i t i o no ff u z z yd u ed a t e ，a n d d e s i g n sac o m p u t e rs i m u l a t i n gs y s t e mi nl i g h to fg e n e t i ca l g o r i t h mt oe a r l yo na ne m u l a t i o n e x p e r i m e n t t h e r e s u l t sa r es a t i s f a c t o r y f u r t h e r m o r e ，t h ep a p e rd i s c u s s e st h eo p t i m i z a t i o no fp r o d u c t i o na n dp r o c e s so fb i n a r y g r o u pp r o d u c t i o ns y s t e m , b u i l d sa n a s s e m b l e dm o d e l o f p r o d u c t i o np l a n n i n g a n d s c h e d u l i n go f m u l t i - t y p ea n dm u l t i - p r o c e s sb ye x p a n d i n gt h ee x i s t e n tm o d e l ，t a k i n gi n t oc o n s i d e r a t i o no f p i e c e s p a r a l l e lm o v e m e n t se i t h e ra m o n gg r o u p so rw i t h i ng r o u p s ，a n dc o m e su pw i t ht h e b i n a r yg e n e t i co p t i m i z a t i o nc o n n e c t i n gb i n a r yc o d i n gw i t ho r d i n a lc o d i n gf r o mt h ep e r s p e c t i v e o fc o m p u t e ri n t e l l e c t u a lo p t i m i z a t i o n 。t h er e a l i t y - s i m u l a t i o nr e s u l t ss h o wt h a tt h em e t h o d c o u l de f f i c i e n t l ya c h i e v ei n t e g r a lo p t i m a ls o l u t i o n ，w i t ht h eo v e r a l lc o n s i d e r a t i o no f p r o d u c t i o n a n d p r o c e s so r d e n b a s e do nt h ea u t h o r s p r e v i o u sr e s e a r c ha c h i e v e m e n t sa n do t h e ra c c o m p l i s h m e n t so f r e l a t i v ea c a d e m i cf i e l d s ，t h ep a p e r o f f e r s o p t i m a ls c h e d u l i n gs y s t e mw i t ht h es o f tc o m p u t i n g ， a i m i n ga ts o l v i n gp r o b l e m se x i s t e di nt h ep r o d u c t i o np l a n n i n ga n ds c h e d u l i n g a s an e w r e s e a r c hf i l e d , t h ep a p e rm a i n l yg e n e r a l i z e st h ei n e v i t a b l et e n d e n c yo fs c h e d u l i n gf o r ms t a t i c s y s t e mb a s e do nt h em a t h e m a t i c a lm o d e lt od y n a m i cs y s t e mb a s e do nq u e s t i o n s ，p r e s e n ba c o m p r e h e n s i v em e t h o do fc o m b i n i n gg e n e t i ca l g o r i t h mw i t he x p e r ts y s t e m ，a n dd i s c u s s e st h e s y s t e ms t r u c t u r ea n do p e r a t i o nm e c h a n i s mo fi n t e l l e c t u a le x p e r ts c h e d u l i n gs y s t e mb a s e do n t h eg e n e t i ca l g o r i t h m f i n a l l y , t h ep a p e rp r e s e n t st h ef i i r t h e rr e s e a r c ho r i e n t a t i o no ft h ep r o d u c t i o ns c h e d u l i n g p r o b l e m t h er e s e a r c ha b o v ei s s p o n s o r e db yt h en a t i o n a ln a t u r a l s c i e n c ef u n d ( 7 9 4 7 0 0 7 2 ， 7 9 8 7 0 0 3 5 ) a n dk e y s c i e n t i f i cr e s e a r c hp l a n n i n gp r o j e c t so f s i c h u a np r o v i n c e ( 0 1 g y 0 5 1 2 6 ) 西南交通大学博士研究生学位论文第v 页 【k e y w o r d s 】p r o d u c t i o np l a n n i n g a n d s c h e d u l i n g ；g e n e t i ca l g o r i t h m ；s i m u l a t e d a n n e a l i n g ：h e u r i s t i cr u l e s ；h y b r i dg e n e t i ca l g o r i t h m ；f u z z y d u ed a t e ； e x p e r ts y s t e m ；s o f tc o m p u t i n g 西麓交通大学 学使论文版投使黑授权豢 本学彼论文作者完全了解学校有关僳露、使稻学经论文的规 ， 黼意学校保凿并渤国家有关郝f j 或辊梅邀交论文鲶复印件耱电 蔽，允 鑫二论文被奎阚荟嚣键阕，本人授权嚣零交蘧大学霹以、蒜本学 位论文鲶全部或部分态容缡入骞关数糖库避行检索，可以采髑影 印、缡印或扫攒等复制手段保存秘汇编本学位论文。 本学德论文属予 1 保密舀，在年解密盾遥麓零授校书； 2 不保密曰，适耀本授权书。 学袋论文作者篓乡匈吲 基嬲：静专年胃万目| 撂导教癖签名：武窖多毒k 露期移渤害年么月“一霾 西南交通大学 学位论文剑凝隧声鞘 本人郑重声明：所聚交的学位论文，鼹本人狂导师搬导下独立避行研究 工作所取德的成果。赊文中已经注明弓l 用的内容拜，本论文不包念任何其他个 入或集体器经发表或撰焉遗豹研究成果。对本文的研究俸岛贾献酶个人稻集 体，均已在文中做了翳确说暖，本人完全意识到本声明豹法律结聚出本人承担。 本学位论文的主要刨掰点如下： ( 1 ) 提出了个改进的遗传算法，新算法在初始种群中引入了启发式算 法鹣解，在孝孛群结擒上采蘑了先按适斑值键劣排序褥分段确定选撵概率静巍策 略，畿优袋个体育趸多鹏杂交机会，谨变异中设计了变异控制规则，以防辨群 擎一仡，磷照灭弱邦撬纯织。缀嚣溺安饿摸羧诗舞缝果说臻该算法款鸯效犍。 ( 2 ) 针对大多数研究忽视平行顺序移动方式下f l o ws h o p 调度问题的情 鬣，绘出了鏊于遗接算法的溪合俊证策赂嚣鞠盔戆缝擒滤程。并浚诗了镑对该 闷邋静混合遗穆葬法，并用实例遂行了模羧计算。研究表臻，把模拟避火过程 与耪褥进化过程结合起来蓐，遗传算法的早收敛现象得到遏制，解的质量有所 提高。在该润题下还分祈了带固定交货期和模糊交货期时该闷题的工 串完工时 间的隶属函鼗，及总拖期最小化和总满意发最大化这两个蟊标醋数的稽互关 系，精出翁者潮麓是蠢者阏瑟的一令子集，著用遗蒋算法求解了带穰猢交货鬻 的f l o w s h o p 调度问题，结果说明该系统的遗传优化方法是可行的。 ( 3 ) 针对生产计划与酒度分副研究的不足，通过扩展两工序成组生产系 统的生产量与作业顺序的优化模型，建立了成组流水线上多醯种移工序加工时 垒产计划秘谴度谯纯豹数学搂型，针对谈摸艇黪特点，提出了二避制编码与自 然数有序编码相缝合的二层次遗传优化方法。实例模拟结果表明：该二层次遗 传饯l 皂方法畿综食考虑生产羹和生产顺黪，磐8 鸯效地求l 寻楚数优化鳃。 ( 4 ) 在前期研究成栗和相关领域中其他学者昀研究成果的嫠础上，提出 了一个用软诗算方法解决生产髂照调度闷题艟优纯调瘦系统方寨， 乍为一个麟 筑磷究领域，本文主要总结了调度翊繇扶基予数学模麓静静态系统彝鏊予阉题 的动态系统转变的必然趟势，提如了一个遗传算法与专家系统相结合的方案， 讨论了基予遗传簿法的餐能诧专家谲度系统躺系统精擒及工作毒毪耩。 学缝论文 乍砻 日期： 西南交通大学博士研究生学位论文第1 页 1 1 研究背景及意义 1 1 1 课题来源 第一章绪论 本论文“生产作业调度问题的软计算方法研究”，来源于国家自然科学基 金项目“生产系统的计算机动画模拟方法体系研究”与“面向敏捷制造的可视 化柔性决策方法研究”，以及四川省重点科研计划项目“定制模式下供应链计 划调度技术及应用研究”，旨在对生产作业调度问题及其软计算方法进行较深 入系统的研究。 1 1 2 研究背景 在生产计划领域中，调度主要是用于调配资源、合理安排作业顺序，在满 足现有生产条件下，使生产成本最小。调度的质量可用不同的目标函数( 如考 虑时间、费用等目标) 来度量。寻找合理的调度方案的过程就是对工件的作业 顺序进行组合优化的过程。所以，调度( s c h e d u l i n g ) 问题有时候也称为排序 ( s e q u e n c i n g ) 问题。 生产作业调度问题已越来越引起企业界的重视。由于高新技术特别是信息 技术的迅速发展，推动着企业全面变革，同时客户需求的变化也非常迅速，另 外经济的全球化已成必然趋势，这些变化都使企业在国际市场上产品竞争的日 趋激烈，企业要想在激烈的市场竞争中生存，就必须对市场的急剧变化做出快 速反应。因此，加强技术与管理的改造与创新，不断提高企业的竞争力，是企 业的必然选择。企业之间的激烈竞争促使企业引进了越来越复杂的生产制造系 统，如混流生产、柔性制造系统，这些新系统已产生了一些新的生产作业调度 优化问题，这些问题也是企业界迫切需要解决的。而较好的调度方案和快速形 成优化调度方案的计算技术，不仅能够优化资源的利用，降低生产成本，而且 能够提升企业的生产经营效率和快速反应能力，从而为企业带来较强的竞争优 势。 在理论界，由于许多复杂理论研究( 如数学规划、人工智能、控制理论、 西南交通大学博士研究生学位论文第2 页 仿真技术等) 的发展，已经为生产作业调度问题的研究发展积累了丰富的文献。 生产作业调度问题作为生产管理的最为困难的问题，而且业已证明该类问题属 于n p 难题，调度方案随机器数和工件数的增加而呈指数增长。因此，对生产 作业调度问题的研究，吸引了国内外许多学者和实际作业调度人员的关注。研 究生产作业调度问题最初主要采用最优化方法，尽管可以获得最优解，但计算 规模不可能很大，且实用性差。近年来，生物学、模糊数学、人工智能、神经 网络、计算机技术及进化计算的迅速发展，为生产作业调度问题的研究开辟了 新的思路和方向。 1 1 3 研究意义 在企业编制生产作业计划时，经常影响到个工件在m 台机器上加工的 顺序问题，即当多个工件经过多台机器加工时，如何安排加工顺序使某些目标 达到最优，这就是m n 调度问题。尽管调度问题最早是从生产制造中提出来 的，但并不意味着调度问题仅仅在生产制造中有应用。事实上，调度问题在企 业管理、交通运输、航空航天、医疗卫生等诸多领域都有着广泛的应用。因此， 调度问题中的工件和机器都应理解成抽象的概念，可以代表极为广泛的具体对 象，如服务机构、作业设施和操作人员等统称为“机器”，而被服务的顾客、 任务和零件统称为“工件”。 现代经济日益强化的竞争趋势和不断的客户定制化的变化需求要求生产 者要重新估计生产制造战略，如更短的产品生产周期和准时生产系统等，利用 有限的资源满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序 和时间，以保证所选择的性能指标最优，能够潜在地提高企业的经济效益，作 业调度问题具有很多实际应用背景，开发有效而精确的调度算法是调度和优化 领域重要的研究课题。 研究生产作业调度问题的优化方法不仅具有较大的理论意义，而且还有相 当大的实用价值。一方面，生产作业调度问题的解决本身具有现实的应用价值， 一个好的作业调度方案不仅可以降低生产成本，而且可以提高企业产品的准时 交货能力，从而增强企业的竞争力；另一方面，生产作业调度问题的研究推动 了遗传算法、模拟退火算法、启发式方法的优化方法的发展与融合，这也为其 他领域类似问题的解决提供了条件与手段。 西南交通大学博士研究生学位论文第3 页 1 2 相关领域的国内外研究概况 1 2 1 生产作业调度问题 生产作业调度问题直是一个十分活跃的研究课题。它们通常是针对如何 配置资源而实现目标优化而展开的。一般的调度问题可以这样描述：假定有” 个工件 ，止， ) 要经过m 个机器 蚴，) 加工。工件一在 机器必上的加工称为一个操作( 0 ) ，它对应一个加工时间( ，) 和一个等待 时间( 孵，) 。一个工件在一台机器上的加工称为一道“工序”。用“加工路线” 表示工件的加工工艺流程，加工路线是事先给定的。用“加工顺序”表示各台 机器上工件加工的先后次序。加工顺序是作业调度要解决的问题。 在一个生产系统中投放订单，订单即被转换成相应于某个期限的工件。这 个工件按给定的加工路线传递，工件可以在繁忙的机器上等待，当具有优先级 的工件到达时优先加工该工件，一旦完成后，再继续加工原来的工件。为了保 证效率及控制操作，在生产系统中必须通过调度功能完成具有加工任务的详细 顺序。 调度功能是整个企业信息系统的一个重要组成部分。调度结果受到整个企 业的中、长期生产计划的影响，调度过程必须考虑库存水平、预测和资源需求， 以对长期资源进行优化。计划功能做出的决策可能对调度有影响，调度也需要 考虑车间生产现场的状况，另外机器故障、加工时间和交货期变更等事件都会 成为调度的主要影响因素。调度在生产系统中的位置及信息流动示意如图1 1 所示。生产作业调度的结果就是进度计划，进度计划表在执行过程中，视物资、 设备、交货期、优先级等因素的变动进行动态调度。 当每个工件都有其独特的加工路线时，要确定工件的加工顺序，这属于作 业车间调度( j o bs h o ps c h e d u l i n g ，j s s ) 问题；当所有的加工路线都一致时， 要确定工件的加工顺序，这属于流水作业调度( f l o ws h o ps c h e d u l i n g ，f s s ) 问题。在f s s 问题中，还可以分成同顺序f s s 和非同序f s s 两种，同顺序f s s 问题要求工件在每台机器上的先后加工顺序相同，否则就称为非同序f s s 问 题。 从工件加工的机器来看，可以是单机或双机，也可能是多机的；同型号的 机器可以是一台，也可以有几台；一台机器可以只加工一道工序，也可以加工 几道工序；某一道工序在某一台机器上的加工时间可以是固定的，也可以是模 糊的( 加工时间可能是一个区间) 。 西南交通大学博士研究生学位论文第4 页 从用户对产品工件的要求来看，交货期可能是固定的，也可能是模糊的( 交 货期可能是个区间) 。 t ，需求删一蹴h 数量，期限l 能力状况 1 物料需求计划，ll h 能力计划广 调度限制工厂指令，投放日期 i l 一作业进度计划卜 计划表 调度绩效 刊动掣度卜 l1 现场状况i l 一 车间管理1 图1 1生产系统中的信息流动图 为了使生产车间达到均衡生产，减少在制品库存，提高机器利用率，缩短 生产时间，需要对调度( 作业计划) 进行优化。从衡量一个调度优劣的标准( 目 标函数) 来看，可以采用不同的评价标准，如总流程时间( m a k e s p a n ) 、平均 流程时间、最大交货误期、平均交货误期、交货误期的工件数、平均在制品库 存量、设备利用率和费用指标等，也可以采用几者的组合。 1 2 2 生产作业调度问题的算法研究 通过对大量文献的分析将生产作业调度问题的研究方法分为两大类：最优 化方法和近似启发式方法。最优化方法主要包括混合线性整数规划( m i l p ) 、 分支定界( b b ) 法等；近似启发式方法最初是由于计算量小并且算法易实 现而引入作业调度问题的，主要包括优先分派规则、人工智能、神经网络( n n ) 及邻域搜索法( n s ) 。邻域搜索法又包括禁忌搜索( t s ) 【2 1 遗传算法( g a ) 和模拟退火( s a ) 【4 】等，是一类可以称为亚启发式( m e t a - h e u r i s t i c ) 的近似 西南交通大学博士研究生学位论文第5 页 优化方法。 近2 0 年来，关于遗传算法、模拟退火算法、神经网络算法、模糊数学、 学习推理等方面的研究十分活跃，已成为理论与应用研究的热点之一，它们被 称为计算智能技术( c o m p u t a t i o n a li n t e l l i g e n c e ，c i ) ，又称软计算( s o f t c o m p u t i n g ，s c ) 。本文研究的混合算法涉及上述多种软计算方法。不同于人工 智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) ，计算智能依赖于数值而不是知识1 5 。 l a z a d e h 认为，正是由于使用了计算智能技术才使机器智商( m a c h i n e i n t e l l i g e n c eq u o t i e n t ，m i q ) 成为可能l “。 ( 1 ) 最优化方法 最优化方法是能够产生一个精确最优解的方法，1 9 5 4 年j o h n s o n 最早提出 了针对( n 2 f ，r 。) 问题的j o h n s o n 规则1 8 j ，对后续生产作业调度问题的研究 产生了重要影响。人们研究较多的该类算法，如分支定界法、动态规划、拉格 朗日松弛法等都取得了较大成果。分支定晁法由两个基本步骤组成，分枝和定 界。分枝是将一个大问题分成两个或者更多的子问题，然后，再用相同的方法 将子问题分成子问题的子问题等。而定界则是计算每个分枝上子问题的最优 值，以此作为问题的下界，分枝步骤可以表示为查找树，分枝定界法的计算复 杂性也是指数型的【9 】。动态规划法用计算调度这一组合优化问题时，为了计算 k 阶段的任意一个最优的评判指标值，必须先知道扣1 阶段的每一个最优的评 判指标值。因此，如果由n 个元素组成，子集的数量应该是2 ”，即动态规划 的计算复杂性是指数型的【9 】。正如前述，生产作业调度问题大多属于n p 难题 【l 。1 ，会产生“维数灾难”，即求解过程导致组合爆炸。因此，对较大规模的生 产调度问题最优化方法常常无能为力，而且，解决生产调度问题的经济性要求 也不允许用这类方法来求解。为克服数学表示和软件方法的局限性，d a v i s 等 1 1 】提出基于数学规划的分解策略，将调度问题分解成多个子问题，分别考虑 各子问题及其规则，提高了计算能力。国内外学者在这类精确算法方面做了大 量的研究【12 1 ”】，但距实际应用还有相当的距离l l 。”“j ，在可预见的时期内 还无法解决。 ( 2 ) 优先分派规则 由于最优化方法不能有效地求解作业调度问题，于是人们转向借助于启发 式方法，启发式方法成为了人们解决实际调度问题的一类重要方法，它能为多 数调度问题找到近优解，所以得到了广泛的应用。它主要集中在分派规则上 西南交通大学博士研究生学位论文第6 页 ”7 】。最早的分派规则由j a c k s o n 】和s m i t h 20 】等提出，常用的规则有最短 加工时间( s p t ) 、最长加工时间( l p t ) 、最早交货期( e d d ) 、先来先服务 ( f c f s ) 、剩余总加工时间最长( m w r ) 、剩余工序数最多( m o r ) 等。p a n w a l k a r 等1 2l j 通过性能指标对1 1 3 个分派规则进行了总结，w u 【z2 】把调度规则分为三 大类，即同作业信息相关的优先级规则、优先级规则的组合和切换以及加权规 则。对规则之间的切换及由此产生的问题是近期活跃的研究领域。 不同的生产环境和作业调度问题需要不同的优先分派规则，由于生产系统 的动态特性，因此，根据具体情况的不同选用相适宜的优先分派规则是一个关 键【2 “。启发式方法本身存在的一个主要缺点是求出的解不一定满足所有的约 束条件 ? “，并且无法确定解的优劣，这些都决定了调度过程离不开专家的介 入【2 “。另外，这些规则本来就是根据调度人员的经验得到的，加上调度问题 的复杂性，因此，利用优先分派规则求解作业调度问题一般不太可能求得最优 的调度方案。 ( 3 ) 人工智能技术 2 0 世纪8 0 年代出现的人工智能在调度研究中占据重要地位，在人工智能 领域中，专家系统首先被应用于生产计划与调度中。它可以产生比优先规则更 复杂的基于对整个系统的启发式规划，并能从数据库、知识库中获取大量信息， 缺点是计算比较耗时。i s i s t 2 6 】是最早基于人工智能的解决特定作业调度问题 的专家系统，它分三层结构，分别为选择订单、能力分析、执行调度，同时加 入重构和修改调度的学习功能。 虽然已有一些成功的例子【27 , 2 “，但也存在不少的困难。首先，专家系统 的适应性差，专家系统较为适用于相对稳定的系统，而生产环境高度不确定， 计划目标常常是变化、动态的甚至是冲突的，对于瞬息万变的作业调度系统， 专家系统则显得无能为力【29 】：其次，有许多专家对制定调度方案有无专家表 示怀疑 3 0 。他们认为，一方面，复杂性已完全超出专家的认识能力，另一方 面，生产环境的动态特性使表达的知识很快就过时。 尽管如此，专家系统在调度问题中的应用仍在继续，特别是在搜索策略方 面，学者们做了大量工作【3 0 】，但适应性差的问题仍没有解决，学者们预言【3 “， 自学习系统在调度中的应用将成为今后的重要研究方向。目前已提出了许多方 法【3 2 】。未来的自学习系统将侧重以下几个方面： 如何均衡动态、冲突的目标； 确认自学习系统的结果； 西南交通大学博士研究生学位论文第7 页 动态调度学习方法； 实时调度学习系统。 对大规模问题限于单个专家系统的有限知识和能力，加入资源代理、任务 代理及代理间的协作机制，近期出现了分布式调度系统【3 3 】。但如何协调各个 代理之间的关系，目前还没有统一的思路和方法。 ( 4 ) 神经网络方法 神经网络在生产调度上的应用已有十多年的历史，利用指导学习神经网络 找到系统输入、输出之间的关系，输入特性包含作业特性( 如数量、路径、交 货期和处理时间) ，输出为相关排序和性能指标。目前多层前馈的b p 网络是 应用最广泛的网络之一。由于计算时产生大量不可行解且计算时间较长，n n 解决实际调度问题的效率不