（机械制造及其自动化专业论文）生产过程的智能调度方法及其应用.pdf

硕 ：学化论文 摘要 实施c i m s 的关键环节之一是生产调度，因此，无论是生产调度理 论的研究还是应用系统的开发都受到学术界和企业界的关注。生产调度 问题通常是多约束、多目标、随机不确定优化问题，已被证明是属于n p 问题。很多研究表明，寻找调度问题的最优解是非常困难的，最有工程 意义的求解算法是放弃寻找最优解的目标，转而试图在合理、有限的时 间内寻找到一个近似的、有用的解。 本文系统研究了生产调度问题的遗传算法、神经网络、模糊理论等 智能求解方法，并对以上方法进行了一些改进，成功的应用于工程实际。 本文取得的主要研究成果如下： 1 系统的研究了多品种、小批量生产调度问题的基于统一时间离散化 表示和非一时间离散化表示的两种建模方法，探讨了两种建模方法的关 系及其转化方法，并将批处理过程优化模型扩展到批处理过程和连续过 程共存的过程。研究了连续并行生产线多产品循环调度模型的建立方法， 以及非线性生产调度模型的线性化方法。 2 系统的研究了运用遗传算法求解柔性车间生产调度问题的方法，详 细讨论了柔性车间生产调度问题遗传算法求解的相关技术。针对实际生 产调度问题中广泛存在的不确定性因素，讨论了模糊柔性车间调度问题 的遗传算法求解方法。给出了用遗传算法求解某汽车发动机厂金工车间 柔性调度问题的实例。 3 改进了基于h o p f i e l d 神经网络求解作业车间调度问题的方法。为 了避免h o p f i e l d 神经网络可能收敛到局部极小的问题，把模拟退火算法 应用于h o p f i e l d 神经网络求解，提出了随即神经网络生产调度方法。与 已有的算法相比，本文提出的方法能保证神经网络的稳态输出可调。 4 研究了基于遗传算法的多品种、小批量生产调度方法，给出了具有 离散变量和连续变量的多品种、小批量生产调度问题的遗传编码方法。 针对企业生产过程中收到订单的时间一般不是预期的情况，提出了由订 单变化引起的具有模糊交货期的连续生产过程动态调度方法，能够依据 收到的订单实现动态调度。 关键词：生产调度；遗传算法；c i m s ；人工神经网络 a b s tr a c t p r o d u c t i o ns c h e d u l i n gi sak e yl i n ki n c a m p s i t ei sg a v ea t t e n t i o n t ot h e i r t h e o r ya n dp r a c t i c ei ns p h e r eo fl e a r n i n ga n db u s i n e s sc i r c l e s p r o d u c t i o n s c h e d u l i n gp r o b l e m sa r es t o c h a s t i co p t i m a lp r o b l e m sw i t h m u l t i 。c o n s t r a i n t s ，m u l t i o b j e c t i v e s i tr a n k sa m o n gt h em o s td i f f i c u l t k n o w nt om a t h e m a t i c a l c o m m u n i t y ，s i n c ei t h a sp r o v e dt o b e l o n gt ot h e c l a s so fn ph a r dp r o b l e m s t h em o s t p r a c t i c a ls o l u t i o na l g o r i t h m sa b a n d o nt h eg o a lo f f i n d i n gt h eo p t i m a ls o l u t i o n ，a n di n s t e a da t t e m p tt of i n da n a p p r o x i m a t e ，u s e f u ls o l u t i o ni nar e a s o n a b l ea m o u n to ft i m e i nt h i s p a p e r ，s o m ei n t e l l i g e n c em e t h o d ss o l v i n gp r o d u c t i o ns c h e d u l i n gp r o b l e m ss u c ha sg e n e t i ca l g o r i t h m ，a r t i f i c i a ln e u r a ln e t w o r ka n d f u z z yt h e o r y a r es t u d i e di nas y s t e m a t i c w a y s o m ea l g o r i t h ma r ei m p r o v e da n da p p l i e dt ot h ep r a c t i c e t h ea c h i e v e m e n t si nt h er e s e a r c h w o r ko ft h i sd i s s e r t a t i o ni n c l u d e ： 1 t w o m o d e l i n gm e t h o d sf o rc o n t i n u o u sp r o c e s sp r o d u c t i o ns c h e d u l i n gb a s e do nu n i f o r md i s c r i m i n a t i o nt i m em o d e la n dn o n u n i f o r md i s c r i m i n a t i o nt i m em o d e la r es t u d i e di n as y s t e m a t i cw a y t h er e l a t i o n s a n dt h e i rt r a n s f o r me a c ho t h e ro ft w om o d e l i n gm e t h o d s a r ed i s c u s s e d t h ea r ee x p e n d e dt ot h e p r o c e s s e sc o e x i s t e n c eo fc o n t i n u o u sa n db a t c hp r o c e s s t h e c y c l i cs c h e d u l i n gm o d e lf o rp a r a l l e lc o n t i n u o u sm u l t i p r o d u c t p l a n t sa r es t u d i e d l i n e a r i z a t i o nm o d e l sf o rp r o d u c t i o ns c h e d u l i n ga r es t u d i e d 2 t h ep r o d u c t i o n s c h e d u l i n gm e t h o d sb a s e do ng e n e t i ca l g o r i t h m a r es t u d i e di nas y s t e m a t i c w a y ，s o m ec o r r e l a t i v et e c h n i q u eo fg e n e t i c a l g o r i t h ma r ee x h a u s t i v es t u d i e d f u z z yf l o w s l o p s c h e d u l i n gm e t h o d s a r ep r o p o s e df o rm u c hu n c e r t a i n t y e x i s t i n gw i d e l y i n p r a c t i c a lp r o d u c t i o n s c h e d u l i n gp r o c e s s e s a ne x a m p l eo fp r o d u c t i o ns c h e d u l i n gp r o b l e mf o rm e t a l w o r k i n gw o r k s h o pi na c a r e n g i n ep l a n ti sg i v e n 3 t h e p a p e ri m p r o v e st h eh o p f i e l dn e u r a ln e t w o r k sa p p r o a c hf o rj o b - s c h e d u l i n gp r o b l e m s t oa v o i dh o p f i e l dn e u r a ln e t w o r k sm a n vc o n v e r g et ol o c a lm i n i m u m ，s i m u l a t e da n n e a l i n gi s a p p l i e dt oh o p f i e l d n e u r a l n e t w o k s c o m p a r e dw i t he x i s t i n gm e t h o d s ，m o d i f i e dm e t h o dc a nk e e pt h es t e a d y 。u t p u t s 。fh o p f i e l d n e u r a ln e t w o r k sa sf e a s i b l e f 。rj o b s h o ps c h e d u l i n gp r o b l e m s 4 t h ep r o d u c t i o ns c h e d u l i n ga p p r o a c hf o r c o n t i n u o u sp r o c e s s ， i n d u s t r y i ss t u d i e db a s e do ng e n e t i ca l g o r i t h m c o d i n gm e t h o d s o fp r o d u c t i o ns c h e d u l i n gp r o b l e mf o rc o n t i n u o u sp r o c e s si n d u s t r y i n c l u d i n gc o n t i n u o u sa n dd i s c r e t ev a r i a b l e si sg i v e n t h em o d e l i n g m e t h o do ft h ed y n a m i cs c h e d u l i n gp r o b l e m sc a u s e db y t h eo r d e rf o r m sf o rc o n t i n u o u s p r o d u c t i o np r o c e s s e so f t h es i n g l ep r o d u c t i o n l i n ea r ep r o p o s e db a s e d o nf u z z vl o g i c a lt h e o r y f i n a l l y ，t h ep r o d u c t i o np l a n n i n g a n ds c h e d u l l n g s u b - s y s t e m i nc i m sf o rc e r t a i nc e m e n tl i m i t e d c o m p a n y1 s r e a l l z e d 儿 c a np l a yd i r e c t i v ef u n c t i o n f o re n t e r p r i s eo p e r a t i o n a n dm a n a g e m e n t k e yw 。r d s ：p r o d u c t i 。ns c h e d u l i n g ；g e n e t i ca i g o r i t h m ；c i m s ；a r t i f i c i a ln e u r a ln e t w o r k s 1 i i 生产过稃的智能调度方法及其晦用 图1 1 图 图 图 图 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图4 1 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 插图索引 a b _ c _ d 次序加工的g a n t t 图7 b - d _ c a 次序加工的g a n t t 图8 均匀时间划分1 2 非统一离散时间表示1 7 流程时间31 工序为7 1 5 946 823 1 0 的甘特图3 2 模糊交货期的满意度3 3 线性模糊交货期的满意度3 4 非线性模糊数函数3 4 混合柔性车间调度的机器编号3 9 调度结果的甘特图4 2 目标函数最小值和平均值的变化曲线4 2 连续h o p f i e l d 神经网络的电子线路4 7 染色体的结构5 5 客户对交货期的满意度5 7 生产线相应处理率的满意度5 7 时间段的划分5 8 生产费用与处理率的关系6 0 时间段的划分6 1 i v 硕l ：学位论文 表1 1 表3 1 表3 2 表3 3 表3 4 表3 5 表3 6 表3 7 表3 8 表5 1 表5 2 附表索引 车铣加工时间7 模拟两台机器问题的集合2 3 加工时间2 9 遗传算法的运行结果3 0 遗传算法与其它启发式算法的比较3 0 加工时间3 1 遗传算法和其它方法的比较3 7 工件在每个机器上的加工时间4 1 1 0 次运行结果4 3 产品定单6 0 定单的完成时间和每个时间段生产线的处理率61 v 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 乏p 课 日期：乃叩年石月f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 黧习黜詈 硕f j 学位论史 第1 章绪论 1 1 生产调度系统的背景与意义 19 7 3 年美国约瑟夫哈林顿博士首次提出了计算机集成制造( c i m ， c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n g ) 的概念。它的内涵是借助计算机，将 企! i k 中各种与制造有关的技术系统集成起来，进而提高企业适应市场竞 争能力。c i m s 是一种基于c i m 哲理构成的计算机化、信息化、智能化、 集成优化的制造系统。 关于c i m s 的基本概念，随着生产实际需要的变化及研究问题的角度 的不同，有不同的定义。狭义上讲，c i m s 定义为应用计算机及网络技术 实现生产过程各个环节集成化的系统。这仅仅是基于纯技术的定义，没 有考虑到经济的、社会的和人的行为因素的影响。广义上讲，c i m s 是一 种在某种环境下为提高企业总体效益的全局性的哲理和方法，这种理念 要求以集成方式组织企业的全部活动，从设计、制造到销售和售后服务 各阶段都要尽可能的利用各种方法和技术工具，以便及时的提高生产率、 降低成本、按期交货、提高质量、确保生产系统全局和局部的柔性等i l j 。 我国自8 6 年成立8 6 3 c i m s 主题，提出c i m s 计划，并根据中国国 情，赋予c i m c i m s 新的内涵：c i m 是一种组织、管理与运行企业生产 的理念，它借助计算机硬件及软件，综合运用现代管理技术、制造技术、 信息技术、自动化技术、系统工程技术将企业生产全过程中有关人、技 术、经营管理三要素及其信息流、物流、价值流有机集成并优化，以达 到产品上市快、高质、低耗、服务好、环境清洁，进而提高企业的柔性、 敏捷性，使企业在激烈的市场竞争中赢得先机。 1 9 8 6 年，欧共体把c i m s 概念拓宽到多品种、小批量生产过程，即 在连续型生产过程中实施c i m s 计划，称为多品种、小批量c i m s 。多品 种、小批量生产涉及的部门很广，如重工、船舶、飞机等。单纯提高生 产装置的控制水平，寻求局部最优的投入产出比，要远远的低于提高整 体调度水平的投入产出比。 多品种、小批量c i m s ，作为c i m 哲理在现代加工工业中的体现， 综合信息技术、计算机技术、自动化技术、管理技术及系统工程等多种 先进技术，实现了企业中多种要素和多个过程的集成优化运行，改善了 企业生产环境、经营环境和决策水平，成为多品种、小批量生产未来发 生产过干口的智能调腰方泫及其应用 展的必然方向。 多品种、小批量c im s 是在计算机网络和数据库基础上的递进结构的 大系统。生产计划与调度居于c i m s 五个层次的中间层，是控制与管理一 体化的接合部，上面是负责整个企业经营战略决策的决策层，下面是生 产过程的监督控制层。因此，生产计划与调度是实现c i m s 的关键，无论 是理论研究还是应用系统的开发都受到学术界和企业界的关注。 1 2 生产调度系统的功能与特点 1 2 1 生产计划调度的任务 生产计划的实施由生产调度系统来完成，生产调度层根据经营决策 层制定的长期生产计划，分解为便于执行的短期计划，如双日和三日滚 动计划，结合生产设备运转的情况，针对工艺切换和生产设备的运转、 原料供给和储存运输等情况，进行合理分配与安排，协调从原料、能源 供给、生产到产品发货各个工序环节，对生产的整个过程进行平衡与控 制，并及时调整偏差，以达到生产过程连续不问断，降低生产成本以获 取最大利润的目的。 生产调度的任务是在满足生产装置和工艺要求的条件下，依据市场 的需求，合理最佳的安排和组织生产过程，以提高过程系统的操作最优 性，为企业带来显著的经济效益1 2 】。其主要内容包括：产品的生产批数 和批量，使用的设备链线，产品的生产顺序和时间安排，能源和资源的 制约等。由于企业的生产过程是动态的，所以当一些因素发生变化时， 例如原料的供应拖延，产品的发货期变化、能源的供应不足、设备出现 异常，再加之一些外部因素的影响，如市场需求的波动、运力不足等诸 多因素等，都会影响到生产计划的完成。因此，要求生产调度系统要柔 性化，能依据生产过程中各种内部和外部的扰动因素对企业的生产过程 进行及时和准确的调整。 生产计划和生产调度具有某种程度的类似性，都是对整个生产过程 的规划和控制，其主要区别是考虑的时间尺度不尽相同。因而，在整个 理论研究领域，生产计划和生产调度都属于调度问题。生产计划主要涉 及产品的需求以及生产该产品所需的资源的粗分配，可以不考虑实际生 产约束或者采用简化的方法粗略的考虑实际生产能力的约束。生产计划 侧重于考虑经营计划与生产能力的平衡，考虑的时间范围为中长期，如 半年或者一年。而生产调度注重的是在较短的时间内进行，最主要的安 排是生产作业的安排与资源的具体分配，涉及实际生产环境中的各个约 2 坝 j 学位论义 束。所以，生产调度可以说是生产计划的可行性验证过程。 1 2 2 生产调度系统的功能分析 生产调度系统的功能包括计划分解、动态监控、统计报表三个方面 1 生产计划的分解 生产调度系统将整个生产计划合理的分解，编制成便于操作的短期 计划。计划分解包括静态计划分解和动态计划分解。静态计划分解是在 正常的生产条件下，对具有充足原料供应和广阔的销售市场，可以根据 选定的目标函数进行分解，一般情况下采用按时间平均分配法。动态分 解又称为滚动计划，是在生产装置加工能力以及生产保障系统状况、生 产、工艺流程要求、公用工程的供应能力以及其它生产保障系统变化的 情况下，遵循上级生产管理层制定的月生产计划，在实际生产现状反馈 的基础上合理的分配各生产要素，把月生产计划动态的分解成两日或三 日不等的生产计划，以便实施和执行。 2 动态监控 为了保证企业在整个生产过程中能够安全、有效、协调的运行并处 于最佳的状态，必须对整个生产过程实施动态监控，其内容包括实时监 控、平衡协调和动态调度。 实时监控是通过数据采集系统、工业控制计算机系统或集散系 统，将生产流程各生产装置中的控制变量与操作变量的实时测量值，生 产设备与辅助设备的状态，关键参数的历史趋势图、全生产运行过程中 的整体状况，各单元间的物流，以及全厂关键设备的异常工况及报警等 等，以图、表、工艺流程图的形式表示出来，以便调度人员对生产情况 进行监视。 平衡协调是平衡协调好各生产经营活动，使企业各部门间建立 良好的配合关系，克服各种矛盾与冲突，从而保持生产过程的连续性， 平稳性和经济性，从而有效的实现企业的目标。协调工作主要有两个方 便的内容，一是外部协调，即协调好生产与经营两大系统，重点协调好 产、供、销、运活动，保证产、供、销三者的平衡，为生产系统提供必 要的原料，保证畅通的销路，为整个生产过程的平稳性创造有利的外部 条件。二是内部协调，即使整个生产过程内部协调配合，以保证各个生 产阶段，各个生产装置间的配合，使物料在流动过程中相互衔接，同时 还应该确保水、电、煤、气的供需平衡。 动态调度当实际生产过程中发生未预期事件使得实际进度与调 度进度表不符合时，对原调度进行修改、调整，以维持生产性能的最优 3 牛产过程的智能渊度方法及疑心用 曼曼曼j, i i i i i 曼毫璺 化。当然，为了维持生产进度表在动态环境中的平滑推进，在对“未预期 事件做出实时响应时，一般采用“未预期”事件影响最小目标函数，对 生产进度表进行实时在线调整，以最终消除执行中的偏差，保证优化表 的实行。 1 2 3 生产调度系统的特点 生产调度问题是非常复杂的问题。通常是多约束、多目标、随机不 确定优化问题1 3 】。求解过程的计算量随问题的规模呈现指数增长，已经 被证明是n p 的问题。 生产调度问题所共有的问题有很多，其中包括：复杂性、随机性、 多约束性、多目标性等。而对于多品种、小批量生产而言，虽然其c i m s 源于离散c i m s ，但是由于多品种、小批量生产与传统的制造业有着明显 的区别，因此多品种、小批量c i m s 不能等同于离散的c i m s 。与离散的 c i m s 调度问题相比，多品种、小批量生产调度问题还包括：多品种、小 批量的工艺过程不连续，工艺流程多变，多品种、小批量的生产过程复 杂，多品种、小批量的物流有其独特的要求，多品种、小批量的存储方 式特殊，多品种、小批量的生产强调生产过程的整体性，多品种、小批 量生产中离散决策变量与连续决策变量共存，多品种、小批量对于生产 的安全性有更高的要求。由于以上的问题，使得多品种、小批量的生产 调度问题更加的复杂多变。特别是对于生产调度方法的实施性、协调性 和可靠性提出了更高的要求。因此，基于从物料单等一系列离散变量概 念出发，生成的物料资源规划、制造资源规划、企业资源规划等优化生 产计划和调度的方法和模型基本上不再适用。必须根据多品种、小批量 生产过程的特点，构筑新的优化思路和框架。 1 3 生产调度问题的描述 1 3 1 生产调度问题 生产调度问题是在一定的时间内，进行可用共享资源的分配和生产 任务的排序，以满足某些指定的性能指标要求。简而言之，生产调度问 题就是按时间分配资源来完成生产任务的问题。 生产调度问题一般可以描述为：针对某项可以分解的工作，在一定 的约束条件下，如何安排其组成部分所占用的资源、加工时间以及先后 顺序，以获得产品制造时间或者成本等要素的最优1 4 l 。 生产调度的性能指标可以是成本最低、库存费用最小、生产周期最 短、生产切换最少、设备利用率最高、三废最少等。实际生产调度的性 4 砀! i j 学位论文 能指标大致可以分为三类： 1 最大能力指标，包括最大生产率、最短的生产周期等，它们都可以 归结为在固定或者无限的产品需求下，最大化生产能力以提高生产效率。 在假定存在连续固定需求的前提下，工厂通过库存满足产品的需求，因 此，调度问题的主要目标为提高生产设备的利用率、缩短产品的生产周 期，使工厂生产能力最大，因此，这类生产调度问题可以称为最大能力 调度问题。 2 成本指标，包括最大利润、最小化运行费用、最小投资、最大收益 等，其实收益指产品销售收入，运行费用包括库存成本，生产成本和缺 货损失。 3 客户满意指标，包括最短的延迟、最小提前或者拖后惩罚等。 调度问题受到工厂管理方法的影响，在不同的管理方法下，调度问 题的优化目标、优化策略及其优化数学模型均不同。而且几乎每一个生 产环境都是唯一的，很难用一个生产环境的调度方案去解决另一个生产 环境的生产调度。又由于生产环境的动态性，生产领域知识的多样性， 调度问题的复杂性，必须将人、数学方法和信息技术结合起来研究生产 领域的管理调度问题。 其次，调度问题也是一个优化问题。优化问题可以自然的分为两类： 一类是连续变量问题；另一类是离散变量问题，称为组合优化问题。对 于连续变量的优化问题，一般是求一组实数或者一个函数；而在组合优 化问题中，是从一个无限集或者可数无限集中寻找一个对象，它可以是 一个整数、集合、排列或者一个图。 生产过程一般按照其输出的产品是呈现连续的产品流、离散的批量、 离散的数量三种情况，分为连续生产过程、间隙生产过程和离散生产过 程。 在连续生产过程中，原料经由不同的专用设备加工转变为产品。每 个设备都是在稳定的工作状态下，完成一项规定的生产操作。一个连续 的生产过程输出的产品是连续的产品流。 间隙生产过程又称为批处理过程，是由一个或者多个按一定顺序执 行的操作步骤( 或操作阶段) 组成的。这些操作步骤是离散的，而每步 中的过程又都是连续的。间隙生产过程一般包括若干个通用设备，多个 产品在有限个设备上生产。 相应的，生产调度问题可以分为面向机加工等连续操作的柔性车间 调度问题和面向多品种、小批量生产过程的离散生产调度或者称为批处 理调度问题。 5 生产过程的智能调度方法及其戍用 1 3 2 车间调度问题 车间调度问题一般可以描述为：n 个工件在m 台机床上加工，一个 工件分为k 道工序，每道工序可以在若干台机床上加工。每一台机器在 每个时刻只能加工某个工件的某道工序，只能在上道工序加工完成后才 能开始下一道工序的加工，前者称为占用约束，后者称为j 顷序约束。 车间调度问题的决策内容包括分配决策( 工序的加工顺序) 和时间 决策( 工件各工序的加工时间) 以及路径决策( 工件工序的加工设备的 分配) 。 车间调度问题的特点是多个工件在有限个机器上加工，每台机器在 切换不同工件生产时需要一定的准备时间。切换加工次数增加有利于减 少工件的库存，但导致生产率下降。因此，需要在库存成本和工件切换 加工频率之间取得平衡。生产的柔性体现在设备使用和设备安排两个方 面，设备使用的柔性是指设备可用于多个零件的多个工序的加工；设备 安排的柔性是指工件的设备加工路径不是固定和预先确定的，具备路径 的可选择性，可以通过若干设备组织为一条或者多条生产线加工一种工 件，使得该工件的生产率最大。 1 3 3 车间柔性生产调度问题 车间柔性生产的调度问题一般可以描述为：n 台工件在m 台机器上 加工，一个工件分为k 道工序，每道工序要求不同的机器加工。n 个工件 在m 台机器上的加工顺序相同，工件i 在机器j 上的加工时间是给定的， 设为t i j ( i _ 1 ，2 ，3 ，n ；j = l ，2 ，3 ，m ) 。调度问题的目标函数是求n 个工件的 最优加工顺序，使最大流程时问最小。 对于车间柔性生产调度问题常常做如下假设： 每个工件在机器上的加工顺序相同，而且是确定的。 每台机器在每个时刻只能加工某个工件的某道工序。 一个工件不能同时在不同机器上加工。 工序的准备时间与顺序无关，且包含在加工时间内。 例1 1 多台机床加工多个工件的最优加工次序 假设有a 、b 、c 、d 四种零件，都需要进行先车后铣，其加工时间 如表1 1 所示： 6 硕 j 学位论史 表1 1车铣加工时间 零件名称车床t 时( 小时)铣床上时( 小时) a1 54 b810 c65 d 127 合计4 12 6 其中a 、b 、c 、d 是调度问题中的四个工件( 或者称为作业) ，车床和 铣床为两台机器，分别为m 1 和m 2 ，车和铣为两个操作，分别为操作1 和操作2 。 在调度中，一般用三元组( i ，j ，k ) 表示作业i 的操作j 在机器上执行。 如果按照a b _ c d 的次序加工，则加工进度即作业操作随时间分配 的顺序，可以用甘特( g a n t t ) 图或称为条形图表示为1 1 。 1 ( 车床) 丐2 铣床 a ，1 ，1 b ，1 ，1 c ，1 ，1 d ，1 ，1 1 52 32 94 1 k2 ，2 b 2 。2c 。2 。2 d 。2 ，2 0 1 5 图1 1 1 92 33 3 3 8 4 8 a _ b c d 次序加工的g a n t t 图 图中，方框表示操作，方框长度表示操作( i ，j ，k ) 的处理时间t i j k 。 在g a n t t 图上，一种可行的调度应确保方框位置满足操作优先顺序要 求，并且方框之间不发生重叠。生产调度的目的是找出总处理时间最短 的g a n t t 图。对于上面这个生产任务，如果将加工顺序改为b d c _ a ， 7 生产过f 甲的智能调度方法及j t 膨用 则相应的甘特图如图1 2 所示。可见，原总方案的加工时间为4 8 小时， 而新的加工方案的加工时间为4 5 小时，所以比原方案优越。 b j1 ，1 d ，1 ，1 c ，1 ，1a ，1 ，1 m 1 ( 车床) 0 82 02 6 掣2 ( 铣床 ) b ，2 ，2d ，2 ，2 c ，2 ，2 a j2 ，2 4 1 0 8l82 02 7 3 2 4 1 图1 2b _ d c _ a 次序加工的g a n t t 图 4 5 如果某一给定的工件在一台或者多台机器上加工时间为0 ，则称为广 义车间柔性生产调度问题，否则称为纯车间柔性生产调度问题。在过去 的3 0 多年里，多数研究工作集中在纯的确定型车间柔性生产调度问题， 常用n m f c m 。x 表示，即n 个工件m 台机器车间柔性生产最大流程时间。 车间柔性生产的调度问题可以分为：确定型、随机型和模糊型。在 确定型车间柔性生产调度问题中，假定工件的加工时间是已知的确定量； 在随机型车间柔性生产调度问题中，加工时间按照一定的概率分布：在 模糊型车间柔性生产调度问题中，每个工件的交货期是一个模糊数，表 示决策者对工件完成时间的满意度。 在实际的工业生产过程中，往往存在多条相互独立的生产线，分配 到某一生产线上的产品不能转移到另一条生产线上生产，称为并行调度 问题。多数实际调度问题都可以转化为并行调度问题，其决策内容分为 两部分，一是组合部分，即产品在各条生产线上的分配和各生产线上产 品的生产顺序；二是连续部分，即各条生产线上产品运行时间和生产循 环周期。 1 4 生产调度方法 虽然对生产调度的研究已经有几十年的历史了，提出了一大批调度 方法，但至今尚未形成一套系统的理论与方法，已有方法可归结为优化 8 坝t + 学位论文 调度方法和启发式调度方法两大类。 优化调度方法是通过精确求解解析模型获得最优解，或通过近似求 解获得次优解。优化方法是从全局的角度出发，在所有的装置、操作任 务和感兴趣的时间段内进行搜索，能够得到优化解。 优化方法建立在数学规划基础之上。尽管数学规划方法比较成熟， 但只能有效的解决小规模优化问题。对于复杂的大规模生产调度问题， 随着装置数和任务数的增加，感兴趣时间段的增长，其解析模型的规模 急剧增大，求最优解往往是n p 难题，一般优化方法难以求解，而启发式 方法在这方面显示了很大的优越性。 启发式调度方法包括基于规则的方法、基于人工智能的方法、随机 搜索方法、基于仿真的方法。启发式方法是从当前角度出发，根据决策 点时刻装置、任务所处的状况进行调度，保证了局部最优，但难以保证 全局最优。 启发式方法与优化方法比较，各有利弊。事实上，两类方法有很大 程度的互补性，将两类方法有机的结合起来研究，会成为今后研究的热 点。 1 4 1 数学规划方法 从数学规划的角度，生产调度问题可以归结为在等式约束或者不等 式约束下，对一个或者多个目标函数的优化，可以表示为m i l p 或者 m i n l p 优化模型，采用各种数学规划方法求解。数学规划方法是隐含枚 举整个空间的搜索方法，搜索效率低，难以解决大规模的调度问题。尽 管m i l p 形式和理论上能够提供调度问题的最优解，但求解实际问题的计 算量大。 传统的求解m i l p 的方法是分支定界法，它是求解组合优化问题的为 数不多的有效方法之一。为了提高求解效率，采用了各种改进b & b 算法， 或者简化计算技术。 采用数学规划的方法，表达清晰，易于在计算机上求解，但生产环 境具有很多不确定性因素，存在建模不确定性和求解空间太大，造成计 算困难，特别是不能反应特定调度领域的自然结构，所以很难应用经验 知识去处理调度问题。 1 4 2 规则调度方法 规则调度是指系统运行时，根据一定的规则和策略来决定下一步操 作的调度方法。它是动态调度的典型代表，它的优点是直观、简单实用， 且花费的求解时间较少、易于实现，在实际生产中获得了广泛的应用。 9 生产过裎的钾能调腰方泫及其应用 产生式规则系统是生产调度中最常用的方法。这主要是由于产生式规则 是有经验的决策管理人员和工程技术人员总结出来的一套行之有效的经 验法则，既有有关专业领域知识的，又有关于问题求解的，较好的反映 了原问题的自然结构，符合人们利用经验处理问题的方法。因此，能较 好的解决一些复杂的实际问题。 基于规则调度直观、简单、易于实现，但它是局部优化方法，难以 得到全局优化结果，当系统规模较大，规则较多时，规则匹配速度很慢， 而且产生式规则系统自适应能力差，很难适应动态调度环境。另外，规 则具有全局敏感性，利用不同的规则可产生不同的调度方案，而且规则 在不同的场合所起的作用也不相同，调度系统的性能取决于规则的选择。 因此，规则的选择成为基于规则调度方法的主要障碍。龚宇等提出了依 靠机器学习动态选择规则，杨圣祥等利用神经网络实现智能选择规则进 行调度，表现出人与智能结合的趋势。 1 4 3 基于人工智能的方法 近年来，人工智能技术被引入生产调度领域，是解决调度问题的有 效途径，成为一个热门课题【5 1 。人工智能方法是采用人工智能研究领域 提供的方法解决各类生产调度问题的总称。包括利用启发式规则引导搜 索并提供有效搜索程序寻找复杂问题的较优解的方法，和优化模型的智 能求解方法。主要有以下几方面的内容： 1 启发式搜索规则：主要有宽度优先、深度优先、b e a m 搜索、f i l t e r e d b e a m 搜索及a 或a 术算法等。a 半算法将分枝定界法和动态规则相结合， 常用于图的路径搜索中。理论上，a 书算法一定能够找到最优解。这些方 法原理上都能够找到可行解，但受到搜索时间和计算机存储空间的限制。 2 基于规则和基于知识的方法：利用人工智能的启发式搜索方法有效 的避免了调度问题搜索空间的组合爆炸；专家系统的多种知识表示方法， 不仅能够表示调度问题中各种定量的、确定的约束条件和优化目标，而 且能够表示调度问题中大量定性的、不确定性的约束和经验，从而能比 较准确地描述调度问题的复杂结构。在基于知识和规则的调度系统中， 常用的知识表示法有产生式规则、语义网、框架等；常用的调度技术有 生产规则、试测法探索、仿真和分级式的分解等。 3 智能求解方法：生产调度问题本质上是大规模组合优化问题，可以 表示为m i l p 或者m i n l p 数学优化模型，但它是n p 完全问题，传统的 数学规划方法难以求解。因此，寻找实用的求解方法一直是研究的重点。 近年来提出的遗传算法、模拟退火、神经网络等智能求解方法，具有普 1 0 坝 ：学何论文 遍适用性和经验复杂性等优点，为解决较大规模的优化问题提供了比较 可行的方法。近年来，在这方面已经取得了不少研究成果，形成了“计 算智能 的研究领域。 神经网络、模糊集理论、和以遗传算法为代表的进化算法，都是仿 效生物处理模式以获得智能信息处理功能的理论。神经网络着眼于脑的 微观网络结构，通过大量的神经元的复杂联系，采用由底到顶的方法， 通过自学习、自组织和非线性动力学所形成的并行分布方式，来处理难 以语言化的模式信息。模糊集理论则可着眼于可用语言和概念作为代表 的脑的宏观功能，采用由顶到底的方法，按照认为引入的隶属度函数和 并行规则，逻辑的处理包含有模糊型的语言信息。而进化算法则是模拟 生物的进化现象，并采用自然进化机制来表现复杂现象的一种概率搜索 方法，以达到快速有效的解决各种困难问题。神经网络、模糊集理论和 进化算法三者目标相近，而方法各异。因此，将它们相互结合，可以达 到取长补短的作用。 1 5 本章小结 本章讨论了生产调度在c i m s 中的地位与作用及其特点，给出了生产 调度问题的描述，综述了生产调度的基本方法，为下文在实际生产中的 应用奠定了理论基础。 1 1 生产过平口的智能调度方法及其心用 第2 章多品种、小批量生产调度问题的数学模型 2 1 引言 日益激烈的市场竞争迫使工厂必须最有效地利用有限数量的操作单 元，在最合适的时间内，生产出需要的产品，因此，生产调度成为工业 生产管理的主要问题之一。特别是那些需求量小和生产形式或者产品的 品种经常变化的批处理生产过程【6 】。 所有批处理调度问题建模的关键是时间的表示，已有文献中的方法 可以根据时间的表示方法分为以下两类： ( 1 ) 离散时间表示。这种方法是将调度时间范围分成许多相等的时 间段，任何类似的事件只能在时间段的边界上发生。离散时| 、日j 表示的主 要缺点是他们对应的是时间域上的近似解。为了达到需要的精度，必须 将调度范围分成大量的时间段，这样就增加了模型规模。 ( 2 ) 连续时间表示。这种方法总体思想是建立许多连续变量表示所 有事件的发生时间。例如，任务开始和结束事件，通过优化可以得到每 个任务的开始和结束时间。其中，时问变量是一个连续变量。 2 2 基于统一时间离散化表示的生产调度模型 2 2 1 统一时间离散化表示的时间划分 统一时间离散化模型是把调度范围分成许多等长度的时间段。任何 类型的事件，如每个任务的开始和结束设备的转换和其它资源的转化 等，只能在时间段的边界发生。把时间从1 标记到h ，这样开始和结束 的时间点分别为1 和h + 1 ，如图2 1 所示。 图2 1均匀时间划分 这种时间表示方法的优点是便于建模，它通过提供一些参考点定位 所有竞争资源的操作。时间段的长度取调度问题中任务处理时间的最大 1 2 硕i 学位沦史 公约数。为了使感兴趣的时间段内可用的资源水平变化，或者一个任务 在其处理时间内所需要的资源量的变化与时间段的边界一致，时间段的 长度就需要足够的小。 2 2 2 生产调度问题的变量 为了建模的需要，定义如下参数： 1 任务( 操作) i 的参数 s ：操作i 的输入状态集 s ：操作i 的输出状态集 玩：操作i 的输入状态s 相对于操作i 批量的输入比例，s e s , 且p u = 1 羁 凡：操作i 的输出状态s 相对于操作i 批量的输出比例，se s ；且万= 1 罨 只：操作i 的输出物料到状态s 的处理时间，s e s , p ：操作i 的处理时间，号= n 擎只 。一i k ：可执行操作i 的设备集 2 描述状态s 的变量 互：从状态s 输入物料的操作集 互：向状态s 输出产品的状态集 e ：状态s 的最大存储量 3 描述设备的变量 i ，：可由设备j 执行的操作集 酽：设备j 执行操作i 时的最大容量 ”：设备j 执行操作i 时的最小容量 ) ，严：设备连续生产j 执行操作i 时的最大生产速率 俨：设备连续生产j 执行操作i 时的最小生产速率 4 描述s t k 中的任务变量 ：如果在时间段t 任务i