（机械制造及其自动化专业论文）敏捷化车间智能调度仿真系统的研究与开发.pdf

瞅愀学位做 r 。r d 8 9 敏捷化车间智能调度仿真系统的研究与开发+ 机械制造及其自动化专业 研究生：唐茂指导教师：刘胜青 摘要 现代制造企业的敏捷化制造模式，以其面向订单组织生产的特征，能够适 应当前快速多变的市场需求。而在这样的组织模式下，灵活的生产单元重构机 制、动态的生产计划和作业调度技术，成为实现快速优化配置企业资源、提高 生产效率的重要问题。 企业敏捷化机制使企业车间的生产任务由面向计划的模式转变为面向订单 的模式，导致车间生产计划调度问题的动态性大大增加，订单任务频繁变化、 紧急订单任务的出现概率增加等。而传统的车间生产调度技术无法对这些动态 变化做出及时有效的响应。e r p 系统及现有调度技术通常假定车间的生产资源 无限，不考虑实际生产过程中可能出现的瓶颈资源和资源变动情况，难以实现 资源的动态负载平衡。因此传统的生产调度方法和调度系统不能适应车间敏捷 化的要求。因此，研究适应现代敏捷化企业车间需要的生产作业调度技术有现 实的理论意义和实用价值。 本文在对敏捷化车间调度作业流程和调度功能需求进行深入分析的基础 上，研究提出了适用于典型车间动态生产作业调度的智能算法模型，可以解决 并行多机( p m s p ) 生产类型和作业车间( j s s p ) 生产类型的最优生产调度问 题。文中采用组件和图形仿真技术，实现了车间智能调度仿真系统，用于验证 调度结果，并可用于人工调整调度方案。计算实验和调度仿真表明本文提出的 算法模型计算效率较高能够适应企业需要。 + 本文研究工作受到四川大学青年科技研究基金项目“敏捷化车间生产过程智能规划模型及其在机电设 备下料生产中的应用研究”的资助。 i 论文摘要 本文研究工作主要包括： ( 1 ) 根据敏捷化车间的生产管理和作业规划模式，对与之相适应的调度技 术的进行了深入研究，明确了智能优化调度在敏捷化车间作业规划管理系统中 的地位和作用，提出了建立车间智能调度仿真系统的思路，分析了该系统的功 能需求，明确指出该系统必须满足的两个核心功能：有限资源调度功能和实时 动态调度功能。文中建立了系统的工作模式，设计了系统的功能模型和软件体 系结构。 ( 2 ) 对两种典型车间的调度问题的数学模型：并行多机调度( p m s p ) 和 作业车间调度( j s s p ) ，进行了有限资源和实时动态化改造，依据该数学模型 设计了多种解决该类调度闯题的智能优化算法。针对作业车间调度问题，本文 设计了基于关键路技术的混合智能优化算法；针对并行多机调度问题，设计了 用于产生预调度方案的近似算法和用于大规模优化的遗传算法，提出了禁忌搜 索算法的改进策略并付诸实践。 ( 3 ) 针对敏捷化车间必须面对的随机动态生产任务，本文采用了基于事件 驱动的重调度策略及任务窗口策略建立了动态调度算法模型。 ( 4 ) 本文采用组件技术实现了智能调度系统原型。对调度问题实例的计算 实验证实了该系统能够对调度问题取得较好的优化结果。应用图形仿真技术在 智能调度系统中实现了调度仿真功能，该功能可直观验证调度方案的可行性， 评判其性能优劣，允许调度员介入调度过程并调整调度结果，实现了人机交互。 关键词：敏捷制造调度计算智能关键路组合优化混合优化 i 【 四川大学硕士学位论文 r e s e a r c ha n d d e v e l o p o i lt h es i m u l a t i n g s y s t e m o ft h e i n t e l l i g e n ts c h e d u l i n g i nt h e a g i l ew o r k s h o p s p e e i a n y m e c h a n i c a l m a n u f a c t u r i n ga n d a u t o m a t i o n p o s t g r a d u a t et a n g m a oa d v i s o rl i us h e n g q i n g a b s t r a c t b e c a u s eo fi t sf b a t u r eo fo r d e r - o r i e n t e d p r o d u c t i o np l a n n i n g t h ea g i l e m a n u f a c t u r i n gm o d eo fm o d e mm a n u f a c t u r e sc o u l da d a p tt h ec u r r e n tc h a n g e f u l m a r k e t u n d e rt h i sk i n do fo r g a n i z a t i o nm o d e ，t h ea g i l er e c o n s t r u c t i o nm e c h a n i s m f o rp r o d u c t i o nu n i t ，a sw e l la st h ed y n a m i c p r o d u c t i o np l a n n i n ga n dj o bs c h e d u l i n g h a v eb e c o m ei m p o r t a n tf o ra t t r i b u t i n gt h er e s o u r c eo f e n t e r p r i s er a p i d l y ，a n df o r i m p r o v i n g t h ep r o d u c t i o ne f f i c i e n c y t h ep r o d u c t i v et a s ko ft h e a g i l ew o r k s h o pc h a n g i n g f r o mt h em o d e lo f o r i e n t i n gp l a nt ot h em o d e lo fo r i e n t i n go r d e rf i r s t l yr e s u l t si nt h ev a s ti n c r e a s eo f t h ed y n a m i co ft h ep r o d u c t i v es c h e d u l i n gp r o b l e mi nw o r k s h o p ，s u c ha st h ec h a n g e o nt h eo r d e rt a s k ，t h ea p p e a r a n c eo ft h ee m e r g e n to r d e rt a s ka n ds oo n ，h o w e v e r , t h e t r a d i t i o n a ls c h e d u l i n gm e a n sc a nn o tr e a c to nt h e s ec h a n g e so fd y n a m i ci nt i m e t h ee r p s y s t e ma n dt r a d i t i o n a ls c h e d u l i n gm e a n sa s s u m e st h a tt h er e s o u r c ei nt h e w o r k s h o pi sl i m i t l e s s ，d o n tc o n s i d e rt h e “b o t t l e n e c k ”p r o b l e mw h i c hm a y h a p p e ni nt h er e a lp r o d u c t i v ep r o c e s s ，a n dc a n tr e a l i z et h el a d e nb a l a n c eb e t w e e n a l lk i n d so fr e s o u r c e s ，s ot h et r a d i t i o n a l s c h e d u l i n gm e a n sa n ds c h e d u l i n gs y s t e m t h er e s e a r c h w o r ks u p p o r t e db y t h e p r o j e c t “a g i l e w o r k s h o p m a n u f a c t u r i n g p r o c e s s i n t e l l i g e n c es c h e d u l i n g a n di t sa p p l i c a t i o ni ne l e c t r o m e c h a n i c a le q u i p m e n t s s t o c kp r o c e s s ”w h i c hf u n d e db yt h ey o u t hs c i e n c ea n d t e c h n o l o g yr e s e a r c hf u n do f s i c h u a nu n i v e r s i 廿 i i l 堡壅塑茎 c a nn o tm e e tt h ed e m a n do f t h ep r o d u c t i v ea g i l i t y s or e s e a r c h i n gap r o d u c t i o nj o b s c h e d u l i n gt e c h n i q u e ，w h i c ha d a p t st h er e q u i r e m e n to f m o d e m a g i l ew o r k s h o p ，h a s a c a d e m i c s i g n i f i c a n c ea n dp r a c t i c a lv a l u e b a s e do nt h ed e e p a n a l y z i n g t ot h ea g i l ew o r k s h o p j o bs c h e d u l i n gf l o w a n dt h e r e q u i r e m e n to f t h es c h e d u l i n gf u n c t i o n ，t h ep a p e rb r o u g h tf o r w a r dt h ei n t e l l i g e n t a l g o r i t h mm o d e l ，w h i c hf i t s t o t y p i c a ld y n a m i cp r o d u c t i o nj o bs c h e d u l i n g o f w o r k s h o p ，a n dc o u l dr e s o l v et h eo p t i m a lp r o d u c t i o ns c h e d u l i n gp r o b l e m so fp m s p p r o d u c t i o nt y p ea n dj o b s h o pp r o d u c t i o nt y p e u s i n gt h ec o m p o n e n t sa n dg r a p h i c e m u l a t i o nt e c h n i q u e ，t h ep a p e rh a sr e a l i z e dt h e i n t e l l i g e n tw o r k s h o ps c h e d u l i n g e m u l a t i n gs y s t e m w h i c hc o u l db eu s e di nv e r i f y i n gt h er e s u l to fs c h e d u l i n ga n d i n m o d i l y i n gt h es c h e d u l i n g s c h e m e a r t i f i c i a l l y t h ec a l c u l a t i n ge x p e r i m e n t a n d s c h e d u l i n ge m u l a t i o ns h o w st h a t t h ea l g o r i t h mm o d e ld e s c r i b e di nt h i s p a p e ri s e f f i c i e n ta n dc o u l dm e e tt h ed e m a n d so f e n t e r p r i s e t h e r e s e a r c h i n go f t h ep a p e rm a i n l y i n c l u d e s ： ( 1 ) a c c o r d i n g t ot h ep r o d u c i n gm a n a g e m e n ta n dt h em o d e lo f t h ew o r k i n gl a y o u t i nt h ea g i l ew o r k s h o p ，t h er e l a t e ds c h e d u l i n gt e c h n o l o g yr e l a t e di sr e s e a r c h e dd e e p l y , a n dt h et h i n k i n gb u i l d i n gt h es i m u l a t i n gs y s t e mo ft h ei n t e l l i g e n ts c h e d u l i n gi nt h e w o r k s h o pi sp u tf o r w a r d ；a n a l y z et h en e e do f t h es y s t e m sf u n c t i o n ，p o i n tc l e a r l yo u t t h et w oc o r ef u n c t i o nw h i c hm u s tb em e t b yt h es y s t e m ：t h es c h e d u l i n gf u n c t i o no f t h el i m i t e dr e s o u r c ea n dt h es c h e d u l i n gf u n c t i o no ft h er e a l - t i m e d y n a m i c t h e f u n c t i o nm o d e lo ft h es y s t e ma n dt h ed e t m ls y s t e ms t r u c t u r ei sb u i l t ，t h ew o r k i n g m o d e lo ft h es y s t e mi sd e s i g n e d ，a n dk n o w c l e a r l ya b o u tt h es t a t u sa n df u n c t i o no f t h ei n t e l l i g e n ts c h e d u l i n gs y s t e mi nt h em a n a g i n gs y s t e mo ft h ew o r k i n gl a y o u to f t h ea g i l e w o r k s h o p ( 2 ) t h es c h e d u l i n gp r o b l e mo ft y p i c a lw o r k s h o p ：t h em a t h e m a t i cm o d e lo ft h e p m s pa n dj s pi sr e b u i l tw i t ht h el i m i t e dr e s o u r c ea n dt h er e a l - t i m ed y n a m i c ，a n d t h es e v e r a l i n t e l l i g e n to p t i m i z i n ga l g o r i t h m s a r e d e s i g n e da c c o r d i n g t o t h e m a t h e m a t i cm o d e l a sf o rt h e s c h e d u l i n gp r o b l e m o ft h e w o r k s h o p ，t h e a p p r o x i m a t e l ya l g o r i t h m sp r o d u c i n gp r e s c h e d u l i n g m e t h o da n dt h e g e n e t i c a l g o r i t h m su s e di nt h ec o s m i c a l l yo p t i m i z ei sd e s i g n e d ；a sf o rt h ed y n a m i ct a s k i v 四j i i 大学硕士学位论文 a p p e a r i n gi nt h ew o r k s h o p ，t h et h e s i sb u i l d sd y n a m i cs c h e d u l i n ga l g o r i t h m sm o d e l ， a d o p t i n gt h er e s c h e d u l i n gs t r a t e g i cb a s e do ne v e n t - d r i v ea n ds o l v i n gi t w i t ht a s k w i n d o ws t r a t e g y ；i na d d i t i o n ，t h et h e s i sa n a l y z e sa n dr e s e a r c h e st h et h e o r yo ft h e i n t e l l i g e n to p t i m i z i n ga l g o d t h r a s ，a n dp r o v i d et h e n e w s t r a t e g yo f t sa n dp r a c t i c ei t ( 3 ) t h e t h e s i sr e a l i z e st h e i n t e l l i g e n ts c h e d u l i n gs y s t e m w i t ht h e g r o u p w a r e - t e c h n o l o g y , a n d t h et e s tt ot h es c h e d u l i n gp r o b l e mp r o v e st h a tt h es y s t e m c a nm a k eag o o da c h i e v e m e n t ；t h es c h e d u l i n gs i m u l a t i n gf u n c t i o ni sr e a l i z e di nt h e i n t e l l i g e n ts c h e d u l i n gs y s t e mw i t hd r a w i n gs i m u l a t i n gt e c h n o l o g y , w h i c hc a nt e s t t h es c h e d u l i n gm e t h o da n dj u d g ei t ，w h i c hp e r m i tt h ed i s p a t c h e rt oi n t e r v e n et h e p r o c e s s o ft h e s c h e d u l i n g a n d a d j u s t t h e s c h e d u l i n g r e s u l t ，s o t h a tt h e c o m m u n i c a t i o nb e t w e e n p e o p l e a n d c o m p u t e r i sr e a l i z e d k e y w o r d ：a g i l e m a n u f a c t u r e s c h e d u l i n g c o m p u t i n gi n t e l l i g e n c e c r i t i c a lp a t h c o m b i n a t o r i a l o p t i m i z a t i o n h y b r i do p t i m i z a t i o n v 四川大学硕士学位论文 第一章绪论 1 1 敏捷制造模式 传统的机械制造是以机械制造中的加工工艺问题为研究对象的一门应用技 术学科“。它是各种机械制造方法和过程的总称。它是结合生产实际，利用各 种基础理论知识，为数学、物理、力学、机械原理和金属切削原理等进行分析 对比，找出客观规律，解决生产制造工艺问题的学科。 近3 0 年来，随着科学技术的进步，微电子技术、光电子技术、计算机技术 已经得到广泛的应用，社会环境因素也发生了很大变化。在科技高速发展的推 动下制造业的资源配置沿着“劳动密集设备密集信息密集知识 密集”的方向发展。在市场需求不断变化的驱动下，制造技术的生产方式沿着 “手工机械化单机自动化刚性流水自动化柔往自动化智 能自动化”的方向发展。 当代制造技术的前沿已经发展到以信息密集的柔性自动化生产方式满足多 品种、变批量的市场需求，并向知识密集的智能自动化方向发展。在这个发展 过程中，制造技术的内涵不断延伸与发展，经历了重视辅助工序、工装、生产 过程，不断更新工艺方法，引入和集成信息技术以及更新管理观念，促进生产 组织变革等四个环节，逐渐形成了先进制造技术( a d v a n c e dm a n u f a c t u r i n g t e c h n o l o g y ，a m t ) 。其本质就是信息技术、制造工艺技术、自动化物流技术、 现代管理技术的有机融合，具有系统、通用、柔性、集成、智能、机电一体等 特点。 敏捷制造系统( a g i l em a n u f a c t u r i n gs y s t e m ，a m s ) 是美国在l9 9 1 年提出 的一种生产方式。它利用人的智能和信息技术，通过多方面的协作改变企业沿 用的复杂的梯阶结构，来改变传统的大批量生产。其实质是在先进的柔性生产 技术的基础上，通过企业内部的多功能项目组与企业外部的项目组合作组建一 个虚拟公司。这种动态的组织结构把全球范围内的各种资源集成在一起，实现 技术、管理和人的集成，从而在整个产品生命周期最大限度地满足用户需求， 提高企业竞争能力”1 。 第一章绪论 1 2 敏捷化车间生产作业管理的技术特点 ，2 1敏捷制造模式下车问作业生产管理方法的特点 传统的制造企业中，车间或相当于车间的生产系统，是构成企业的重要环 节。在制造企业的三个层次( 工厂层，车间层，控制层) 中，车间层具有重要的 作用，企业的产品最终将在车间物化出来。车间生产作业管理和控制系统负责 在制造车间环境中协调物流和信息流，它是上层生产计划、生产管理模块与底 层设备控制系统的接口。在实现敏捷制造模式中，车间的敏捷化是整个企业实 现敏捷化的重要基础。 我国的制造企业随着全球性的企业小型化趋势，车间级生产系统出现了深 层次的变革。一方面。大型企业调整其内部结构，使车间级生产系统逐渐具有 了独立制造单元和经济实体的特征：另一方面，由于中小型企业在竞争中具有 较大的灵活性，更能满足多元化和个性化的市场需求，具有车间级生产系统特 征的小型化企业不仅在数量上占绝对优势，而且发展速度也呈上升趋势。 但是，与传统的适应大规模生产模式的大型制造企业不同，车间的生产管 理有其自身鲜明的特点“： 1 ) 一般以多品种单件小批量生产模式为主，在客户订单驱动下安排生产： 2 ) 高度专业化，仅在个别方面具有有限的优势生产能力； 3 ) 由于生产任务随客户订单不断变化，需要动态调整生产进度，但由于生 产能力是有限，系统中剩余生产能力不断变化，生产进度规划非常复杂； 4 1 车间生产系统一般相对独立，结构完整； 5 ) 完成复杂生产任务时需要频繁的对外协作。 1 2 ，2e r p m r p | l 在车间生产作业管理中的不足 目前国内应用最广泛的生产管理系统是m r p l i 系统，m r p i 系统使用规划 技术改善企业内外的坍调、跨部门活动的协调和发现潜在的客户货运与供应接 收问题。8 0 年代中期j i t 技术开始引入，推和拉、看板技术的应用。丰富了 m r p i i 系统的功能，后来由m r p i i 系统扩展，引入供应链管理、电子商务等技 术概念形成了e r p 技术系统。 但是，e r p m r p i i 系统很难产生符台车问实际的生产作业规划，也很难实 四川大学硕士学位论文 现企业内部生产车间之间的协同作业。原因在于“”“1 ：缺乏有限资源调度功 能。e r p m r p i i 系统的主要缺陷就在于先假设制造系统的资源( 人、材、物) 是 无限的。在此假设的基础上采用前向推理策略等到最后的生产规划产生后， 若发现超过了某些资源的能力上限，再相应调整规划。循环往复，直到规划可 行。由此很难产生符合车间实际生产能力的生产计划。缺乏实时的生产控制 和处理来自生产现场反馈的能力，很难产生及时的、准确的、符合当前生产状 况的生产作业规划。 e r p m r p i i 系统一般是按照独立需求和相关需求的概念，运用b o m 表展 开计算的，面向订单制造的大量技术与工艺工作不能纳入管理，增加了对整个 订单生命期的全过程进行计划与控制的难度。由于这一技术特点，e r p l 冲i i 系统特别适合重复性生产和产品结构不复杂的产品，直接对b o m 表中全部自 制零件按照无限能力计划方法，编制生产进度计划。而对单件小批生产、品种 繁多、结构复杂的情况，适应性较差。 因此，e r w m r p i i 系统应用于车间一级的生产管理时，缺乏面向订单生产 的生产过程管理机制。e r p m r p i i 的核心是围绕着“如何在需要的时间内生产 所需要的物料和所需要的数量”进行工作，其本质是面向库存的生产，而对订 单生产的支持不足。面向订单的生产需要解决生产管理系统，适应产品进度计 划根据产品发展的阶段，逐步细化的特点，并对其实施有效控制的实际需求。 计划在执行过程中需要动态调整、滚动和细化。而e r p l v l r p i i 缺乏来自车间各 个环节的信息反馈，也不能根据车间的现有剩余生产能力调整进度计划。 1 2 3 单元化制造系统和制造执行系统的基本思想 围绕提高企业车间的柔性和敏捷性这两个主题，西方产生了制造执行系统 ( m a n u f a c t u r i n g e x e c u t i o n s y s t e m ，m e s ) 和单元化制造系统( c e l l u l a r m a n u f a c t u r i n gs y s t e m ，c m s ) 等技术概念。其基本思想可以弥补e r p m r p i i 在 车间生产管理上的不足。 m e s 是九十年代初产生的技术概念，它是针对m r p i i 在生产执行管理方面 的限制和不足而产生的，是e r p m r p i i 的必要补充。m e s 强调”3 ： 1 ) m e s 的优化目标是整个生产过程： 2 ) m e s 需要收集生产过程中的实时数据并对实时事件进行及时处理； 3 第一章绪论 3 ) v i e s 同时与e r p m r p i i 系统级计划层和车间中制造设备控制层保持双 向通信能力，从上下两层接收相应数据并反馈处理结果和生产指令。 v i e s 可以填补e r p m r p i i 系统在生产计划与生产控制之间的信息鸿沟。同 时由于可以对生产过程中的实时事件做出反应，m e s 在按订单进行生产的单件 小批生产方式下的优越性是其它生产管理系统所无法比拟的。 c m s 是构成敏捷制造企业的基本组织元素和功能元素，是多品种小批量制 造具有竞争力的组织方式，是一种订单驱动的生产系统”。c m s 通常是依据成 组技术原理，将传统机群式生产组织按产品再工程( r e e n g i n e e r i n g ) ，重新组成 综合生产组( 制造单元) ，一组相似的零件或一类相似产品在单元内完成全部或 大部分加工任务。这样可减少零件物流路线和生产准各时间，简化管理提高 生产率和零件质量，有利于组织管理。在c m s 中每一个单元是制造的中心， 也是一个利润中心，有全部的管理职能甚至包括财务。因此，传统车间的构 成和管理要素是机床而c m s 中整个单元对外是统一的整体和基本管理要素。 以c m s 为基础的企业结构，抛弃了传统生产系统的金字塔式的管理结构，和 过细、固定的分工方式，形成相对独立的制造单元，再由若干单元通过网络进 行生产管理和协调。制造单元作为相对独立的组织元素，是现代制造系统的组 织基础，它较好地体现了敏捷制造生产模式所蕴涵的专业化、小型化和转包加 工的企业建设和经营思想0 1 。 显然，m e s 可以作为实现c m s 的重要标准和关键技术。c m s 强调面向订 单的制造过程管理与控制模式，强调单元间过程的协同，是制造执行的范畴， 因此m e s 作为c m s 的执行控制模型具有普遍意义，m e s 涉及的集成接口、计 划、调度、旋工的管理等，是实现c m s 的重要标准和关键技术。 m e s 与c m s 相结合构成单元化制造执行系统的技术思想，可作为企业车 闫生产管理技术的基础，用以提供生产活动中从订单到成品闯的最优化信息， 利用实时准确的数据指导、响应并报告车间发生的各项活动、对现场变化条件 做出快速反应、减少非增值活动，最终达到高效的车间操作。这一技术系统能 够很好地联结和沟通上层的企业管理计划与底层控制信息，与制造车间的本质 特征如物料流动、质量控制、工艺集成等实现有机集成，并与制造车间的重要 任务( 生产过程及设备的控制) 之间的实现集成。 4 四川大学硕士学位论文 1 3 敏捷制造模式下的调度问题 调度是为了实现某一目的而对共同使用的资源实旌时间的分配。1 。一个调 度满足问题( 调度问题) 是一个约束满足问题，它的一个状态是集合r 和t 间 的二元关系其中r 是资源的集合( 资源空间) ，t 是任务的集合( 任务空间) 。 调度问题涉及的范围也是极其广泛的，包括制造业、交通运输业、经济金融业、 管理领域等。现实世界中的调度问题各式各样，如：t i m et a b l es c h e d u l i n g ( 时 间表调度) 、c r e ws c h e d u l i n g ( 人员调度) 、j o bs h o ps c h e d u l i n g ( 车间作业调度) 等。 调度和优化有着密切的关系。优化是调度的目的，而调度是优化的一种具体表 现形式。所以调度问题又称为优化调度问题。 至今为止人们对优化和调度问题得研究已经相当深入，形成了较为系统 的理论体系，很多成果得到了实际应用。现已开发出了很多基于约束的调度系 统，如i s i s 、s o j a 、f l 塘s t 、s o n i a 、d a s 和最近在基于工业的程序设计 工具范围内资源约束的实现，如c h i p 、o z 、c l a i r e 和l o g s c h e d u l e 等 产品“。 1 3 1生产调度问题的提出 调度问题来源于不同的领域，如柔性制造系统、生产计划、计算机设计、 后勤及通讯等。敏捷制造作为2 1 世纪企业的先进制造模式，综台了j i t ( j u s ti n t i m e ) 、并行工程、精益制造等等多种先进制造模式的思想，其基本特征是采 用标准化和专业化的计算机网络，在信息集成和共享的基础上，以分布式结构 连接各类企业，构成虚拟制造环境，从而快速高效地实现企业内外部资源( 包 括管理、人员、技术) 合理、优化地配置，阻便赢得市场竞争。在这种模式下 如何进行组织管理，包括如何组织动态联盟，如何重构车间和单元、如何安排 生产计划、如何进行调度都是我们面临的问题。其中车间作业调度与控制技术 是实现高生产率、高柔性和高可靠性的关键，有效实用的调度方法和优化技术 的研究与应用已成为先进制造技术实践的基础。 1 3 2 生产调度问题的分类 生产调度问题的分类方法很多，主要有以下几种：根据加工系统的复杂 5 第一章绪论 程度可分为单机、多机并行、f l o ws h o p 和j o bs h o p 。根据性能指标分为基于 调度费用和调度性能的指标两类。根据生产环境的特点，可分为确定性调度 和随机性调度。根据作业加工的特点，可分为静态调度和动态调度“”。 1 3 3 生产调度问题的特点 1 高复杂性 调度问题所涉及的变量繁多由于装卸作业、设备、库房，搬运系统之间 的相互影响、相互作用；每个作业又要考虑到它的到达时间、装卸时间、准备 时间、操作顺序、交货期等，致使实际调度问题相当复杂。这就使得想要精确 描述其问的各种约束关系并建立其数学模型变得困难和复杂。 此外，从计算量来说，调度问题往往是n p c 或n p - h a r d 问题，即求其最 优化解的计算量随着问题规模的增长呈指数关系的增长，一般的优化方法对此 无能为力。比如约束单机调度问题就属于n p c 问题”( 当装箱问题的c t 全部 相同时，可以多项式转化为单机调度的一个特殊情况) ，而对于一般的装卸系统， 问题就变得更加复杂。 2 多目标性 实际的调度一般往往是多目标的，而且这些目标问可能发生冲突。o r a v e s 曾将调度目标分为基于调度费用和调度眭能的指标两大类：a l i a 等人曾将调度 目标分为三类：基于交货期的目标、基于完成时间的目标、基于生产成本的目 标。这种多目标性导致调度问题的复杂性和计算量剧增。 3 动态随机性 在实际的生产调度中存在很多随机的和不确定的因素，比如作业到达时间 的不确定性、作业加工时间的随机性，而且生产系统中常出现些突发偶然事 件，如设备的损坏维修、交货期的改变等等“”。 1 3 4 生产调度问题的研究方法 调度问题的研究方法经过五十多年的发展，经历了由简单到复杂，从一元 到多元的过程。一般的调度问题都是对于具体生产环境中的复杂的、多目标、 动态的调度问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这 6 四川大学硕士学位论文 些复杂性进行分类。而能否适应千差万别的实际生产环境，能否取得令人满意 的优化效果，就成为了评估一个调度算法的主要标准。历史上，人们最初曾使 用了整数线性规划、简单规则等方法，可这些方法要么不能解决复杂问题，要 么所取得的调度结果不能令人满意。随着2 0 世纪8 0 年代初期如禁忌搜索、神 经网络、模拟退火、遗传算法等新兴的优化技术的建立与发展。人们把这些算 法的模型、理论和技术应用到调度领域，使调度问题的研究朝着复杂、多元化 的方向发展，取得了大量的研究成果。 1 基于规则的方法 调度问题是伴随着社会化大生产出现的，其历史远远早于优化技术。在长 期的生产实践括动中，人们积累了相当丰富的调度经验。利用这些直观的、感 性的经验，人们在一定程度上解决了许多实际调度问题，求得了性能满足需要 的次优解。 p a n w a l k a r 和i s k a d d e r 对基于规则的方法总结了13 3 条规则“，并将它们 按形式分成了三类：简单规则、复合规则和启发式规则：m o n t a z e i i 等列举了常 见的2 0 条规则，并针对一个实际的柔性制造系统( f m s ) 分析了这些规则对 系统性能( 如作业的平均等待时间、设备的平均利用率、作业的总加工时间等) 的影响；除此之外，人们还对多规则组合、决策规则在调度问题中的应用和规 则库的实现等等问题进行了研究并取得了一定的成果。随着计算机运算速度的 迅速提高，出现了以花费合理的计算时间来换取较好的优化效果的方法，比较 典型的是瓶颈移动法( b o t t l e n e c kp r o c e d u r e ) ，用以解决以最小流程时间的 j o b - s h o p 问题。 总的来说，启发式规则直观、简单、易于实现。但研究表明，它们的有效 性依赖于对特殊性能的要求和生产条件，无法得到一个全局优化结果且无法对 结果进行评估。 2 系统仿真方法 由于制造系统的复杂性很高，多数情况下很难用一个精确的解析数学模型 来进行分析和描述。而基于仿真的方法不单纯追求系统的数学模型，侧重于对 系统中运行的逻辑关系进行描述，能够对生产调度方案进行比较评价，分析系 统的动态性能并选择系统的动态结构参数。通过运行仿真模型来收集系统资料， 就能够对实际系统进行性能、状态等方面的分析，从而能够采用合适的方法对 第一章绪论 系统进行调度过程控制。仿真方法最早被用于测试调度启发式规则及分配规则 的工具，后来人们发现，将简单的优先权规则进行组合，或者用一个简单的优 先权规则将一些启发式规则进行组合，如此形成的调度结果优于单独的优先权 规则。于是仿真方法逐渐发展成为一种人机交互的柔性仿真工具，并被用来 进行车间调度。这样就能通过仿真动态地展现作业车间的状态，分析在不同调 度方法下的系统性能，并运用知识和经验去选择合适的调度方法( 规则) ，从而 改善调度性能。 3 基于排序的方法 此类方法的思路是先确定个可行的加工次序，由此确定每个操作的开完 工时间，然后对这个次序进行优化。这类方法属于近似算法，但有可能得至最 佳的调度方案，故近年来学者们对这些方法的研究比较多。“。 该方法主要包括局部搜索( l o c a ls e a r c h ) 、禁忌搜索( t a b us e a r c h ) 、模拟 退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 等。”，统称为邻 域搜索算法。其特点是在搜索解空闻时，仅对所选定的成本函数做出响应，因 而通用性强，在实际生产调度中应用十分广泛。邻域搜索方法虽然可能得到最 优的调度结果，但也都存在各自的不足，因此，目前很多学者试图混合各种算 法，充分发挥各种算法的优势来弥补单一方法的缺陷，本文基于这样的思路进 行研究。这些方法的原理、模型、优缺点等本文将在后续章节做出详细介绍。 4 基于智能的调度方法 人工智能在6 0 年代就将计划问题作为其应用领域之一。但直到8 0 年代， 以f o x 为代表的学者们开始的基于约束传播的i s i s ( 1 u t e l l i g e n ts c h e d u l u a ga n d i n f o r m a t i o ns y s t e m ) 的研究才真正将人工智能应用于调度领域。基于知识的调 度方法是用专家系统自动产生调度或辅助人去进行调度是将传统的调度方法 和基于知识的调度评价相结合的方法；在8 0 年代后期，一些学者开展了基于调 度系统处于不同状态采用不同的调度规则策略的动态调度方法的研究其特点 是：在支持某些活动发生的资源条件( 称为决策点) 具备时，根据系统当时所 处的属性状态，决定采用何种规则( 策略) ，确定或选择活动发生的顺序和时间， 即状态指导的智能调度方法。 总的来说，这些方法包括基于佩特网的决策支持系统“、智能调度专家系 统、基于智能搜索的方法以及基于多代理技术m a s ( m u l t i - a g e n ts y s t e m ) 的 四川大学硕士学位论文 合作求解方法等”7 “”1 。其中专家系统有知识获取和推理速度这两个瓶颈，存 在训练速度慢、搜索能力差等缺点，基于m a s 技术的方法提供了一种动态灵 活、快速响应市场的生产调度机制，是一种较新的智能调度方法。 1 4目前调度方法存在的问题 调度领域中的大部分问题是n p 问题，虽然对其的研究已经有几十年的历 史了，但至今理论研究和实际应用之间还存在着很大的差距。 随着先进制造模式在企业中的全面应用，j i t ( j u s t i n t i m e ) 思想的推广， e t m a r l i n e s s t a r d i n e s s ) 调度问题，即使得工件按交货期完成，变得越来越突出。 实际应用中的调度方法必须能够响应生产系统的动态变化。在敏捷制造模 式下，企业、车间、班组的结构发生了巨大的变化，不再是传统的、机械的层 级式结构而转变为分布式、并行式结构，生产的组织模式也由面向计划转变为 面向任务订单，因此，生产系统的实时动态性大大增强，原有的调度方法和系 统已不能满足生产系统的这种实时动态性。 传统生产模式下的调度方法总是假定生产系统可用的资源是无限的，但实 际上生产过程中的资源并非一成不变的，这种变化随系统特性不同而不同，因 此，解决调度问题的方法必须适应这样的变化，即具备有限资源调度能力“。 在实际车间调度中，车间计划和调度往往是分层迸行的，有可能造成计划 在实际调度中的不可行问题，如何将计划与调度综合考虑，以求得总体的优化 也是需要进一步研究的。此外还有很多问题需要解决，如车间调度的多目标性 等。总之，调度理论、方法和应用的研究是一项非常艰巨的工作。 1 ，5 本课题的研究意义 1 5 1 本课题的生产实践背景及意义 随着社会化生产的进一步细化和市场竞争的日益加剧，制造企业面临着前 所未有的挑战，为了适应市