（工商管理专业论文）基于约束理论的造纸企业生产调度模型研究.pdf

l 7 ：l r e s e a r c ho nt h ep r o d u c t i o ns c h e d u l i n gm o d e lf o rp a p e r - m a k i n g e n t e r p r i s e sb a s e d o nt h e o r yo fc o n s t r a i n t s b y y a op e n g f e i b m ( h u n a nu n i v e r s i t yo f t e c h n o l o g y ) 2 0 0 4 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f e n t e r p r i s em a n a g e m e n t i n t h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rz h o us h o u h u a o c t o b e r , 2 0 0 9 哪3洲9咖6川9洲37iiim y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 幽e 鸸苫 日期：加，7 年口月g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。 本学位论文属于 1 、保密口，在一年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 翻匕稍z 1 3 期：加7 年o 月8 日 日期：加7 年f 。月窖日 硕士学位论文 摘要 生产调度研究属于运营管理的范畴，是管理学理论和实证研究的热点之一。 如何提高生产计划的精确度、减少计划变更次数，满足不断变化的客户需求已成 为管理者和研究人员关注的焦点问题。目前专门研究生产调度的文献虽然很多， 但国内关于造纸企业生产调度方法的研究还不多，且主要针对纸卷切割、打浆过 程等开展研究。本文立足国内现代造纸企业生产实际，在国内外有关生产调度文 献研究的基础上，对造纸企业的生产调度模型进行了研究。 本文在对生产调度研究进行综述的基础上，根据约束理论、生产调度理论和 最优化理论的原理与方法，提出了模型构建的指导思想和原则，分析了造纸企业 生产调度的目标、约束条件、策略以及生产过程的瓶颈，并以基于浆纸平衡的抄 纸系统合理加工方案为切入点，结合造纸企业生产实际和客户需求，构建了基于 约束理论的造纸企业生产调度模型。为了克服传统遗传算法早熟和收敛慢的特点， 提出了求解该模型的小生境遗传算法，并通过普通遗传算法与小生境界算法运行 结果对比和小生境界算法迭代2 0 0 次与迭代3 0 0 次运行结果对比，发现小生境遗 传算法具有全局收敛、收敛速度快等优点。同时，为了检验已构建模型的有效性， 本文选择沅江纸业有限责任公司作为该模型的应用实例，分析了该公司生产调度 现状，将构建的生产调度模型运用于沅江纸业有限责任公司，算例的结果表明该 模型求解造纸企业生产调度问题的效果好，有实用价值，可用于指导造纸企业实 际生产调度。 本文下一步的工作将结合生产统计数据，进一步优化生产调度模型，使造纸 企业生产调度更科学化。 关键词：造纸企业；生产调度；约束理论；浆纸平衡：小生境遗传算法 n a b s t r a c t t h er 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 gi s w i t h i nt h es c o p eo fo p e r a t i o n m a n a 。g e m e n t a n di sa l s oo n eo ft h eh o ti s s u e so f t h e o r i e sa n de m p i r i c a lr e s e a r c h e so f m a n a g e m e n t h o wt oi m p r o v et h ea c c u r a c yo fp r o d u c t i o np l a n ，r e d u c e t h ec h a n g e f r e q u e n c yo fp l a n ，a n de v e n t u a l l yt os a t i s f yc u s t o m e r c h a n g e a b l ed e m a n d sh a v eb e e n p a i dm o r ea n dm o r ea t t e n t i o n sb ym a n a g e r sa n dr e s e a r c h e r s s of a r ，a l t h o u g ht h e r e a l e al o to fl i t e r a t u r e sa b o u tp r o d u c t i o ns c h e d u l i n gr e s e a r c h ，t h er e s e a r c h e so np r o d u c t i o n s c h e d u l i n gm e t h o do f d o m e s t i cp a p e r - m a k i n ge n t e r p r i s e sa r ev e r yf e w , m o r e o v e rt h e s e r e s e a r c h e sm a i n l ya i ma tp a p e rr o l lc u t t i n g ，b e a t i n gp r o c e s se t c b a s e dm yr e s e a r c ho n t h ep r a c t i c a lp r o d u c t i o no fd o m e s t i cm o d e mp a p e r m a k i n ge n t e r p r i s e s ，w i t ht h ee x i s t e d a c h i e v e m e n to np r o d u c t i o ns c h e d u l i n g ，t h i sp a p e rw i l lm a k eas y s t e m i ca n a l y s i so f p r o d u c t i o ns c h e d u l i n g a f t e rr e v i e w i n gt h es t u d i e so fp r o d u c t i o ns c h e d u l i n g ，a c c o r d i n gt ot h ep r i n c i p l e s a n dm e t h o d so fr e s t r a i n tt h e o r y , p r o d u c t i o ns c h e d u l i n gt h e o r ya n do p t i m i z a t i o nt h e o r y ， t h i sp a p e rp r o p o s e st h eg u i d i n gi d e o l o g ya n dp r i n c i p l e so fm o d e lc o n s t r u c t i n g ，a n d a n a l y s e st h ep u r p o s e s ，r e s t r i c t i v ec o n d i t i o n s ，s t r a t e g i e so fp r o d u c t i o ns c h e d u l i n g a s w e l la sb o t t l e n e c k si nt h ep r o d u c t i o np r o c e s sf o rd o m e s t i cp a p e r - m a k i n ge n t e r p r i s e s t h e n ，t a k i n gt h ep r o p e r l yp r o c e s s i n gs c h e m eo fp a p e r - m a k i n gs y s t e mw i t hp u l pa n d p a p e rb a l a n c ea st h ec u t t i n g i np o i n t ，a n dc o m b i n i n gw i t ht h ep r a c t i c a lp r o d u c t i o no f p a p e r m a k i n ge n t e r p r i s ea n dc u s t o m e rr e q u i r e m e n t s ，t h i sp a p e rp u t sf o r w a r d an e w m o d e lo fp a p e r m a k i n ge n t e r p r i s ep r o d u c t i o ns c h e d u l i n gu n d e rr e s t r a i n tt h e o r i e s - t o a v o i dt h ep r e m a t u r ea n ds l o wc o n v e r g e n c eo ft r a d i t i o n a lg e n e t i ca l g o r i t h m ，t h i sp a p e r p r o p o s e sn i c h eg e n e t i ca l g o r i t h mm o d e lf o rm o d e ls o l v i n g t h i sp a p e r f i n d st h a tn i c h e g e n e t i ca l g o r i t h mh a st h ef e a t u r e so fw h o l ec o n v e r g e n c ea n df a s tc o n v e r g e n c ea f t e r c o m p a r i n gt h er u n n i n gr e s u l t sb e t w e e nc o m m o ng e n e t i ca l g o r i t h ma n dn i c h eg e n e t i c a l g o r i t h ma n dc o m p a r i n gt h er u n n i n gr e s u l t sb e t w e e n2 0 0i t e r a t i o n sa n d3 0 0i t e r a t i o n s o fn i c h eg e n e t i ca l g o r i t h m m e a n w h i l e ，i no r d e r t o t e s t i f yt h ev a l i d i t y o ft h i s r e s e a r c h i n gm o d e l ，t h i sp a p e rs e l e c t sy u a n j i a n gp a p e r c o ，l t da st h ea p p l i e de x a m p l e o ft h em o d e l ，a n da n a l y z e st h i sc o m p a n y sp r o d u c t i o ns c h e d u l i n gs t a t e ，f i n a l l yu t i l i z e s t h i ss c h e d u l i n gm o d e lo ny u a n j i a n gp a p e rc o ，l t d t h ee x a m p l er e s u l t si sg i v e nt o p r o v e lt h a tt h em o d e la n da l g o r i t h md e s c r i b e di nt h i sp a p e ri s e f f i c i e n t ，h a su s e f u l v a l u ef o rp r o d u c t i o ns c h e d u l i n go fp a p e r m a k i n ge n t e r p r i s e s ，a n dc a nb eu s e dt og u i d e i l l 硕上学位论文 t h ea c t u a lp r o d u c t i o ns c h e d u i n gf o rp a p e r - m a k i n ge n t e r p r i s e s t h ef o l l o w i n gr e s e a r c ho ft h i sp a p e rw i l li n t e g r a t ep r o d u c t i o ns t a t i s t i c a ld a t at o m o r e o v e ro p t i m i z ep r o d u c t i o ns c h e d u l i n gm o d e la n dm a k ep a p e r - m a k i n ge n t e r p r i s e p r o d u c t i o ns c h e d u l i n gm o r es c i e n t i f i c k e yw o r d s ：p a p e r m a k i n ge n t e r p r i s e ；p r o d u c t i o ns c h e d u l i n g ；t h e o r yo fc o n s t r a i n t s ； p u l pa n dp a p e rb a l a n c i n g ；n i c h eg e n e t i ca l g o r i t h m i v 基于约束理论的造纸企业生产调度模型研究 目录 学位论文原创性声明和学位论文版权使用授权书一l 摘要i i a b s t r a c t i i i 插图索引v i i i 附表索引一i x 第l 章绪论1 1 1 选题背景与意义1 1 2 研究范围界定与主要解决的问题3 1 2 1 研究范围界定3 1 2 2 解决的主要问题3 1 3 生产调度国内外研究状况4 1 3 1 生产调度问题的建模方法研究4 1 3 2 生产调度方法研究5 1 3 3 生产调度研究的发展趋势一9 1 4 研究内容与方法9 1 4 1 研究内容9 1 4 2 研究方法1 1 第2 章研究的相关理论基础1 2 2 1 约束理论1 2 2 1 1t o c 的基本原则1 2 2 1 2t o c 的调度系统1 4 2 1 3 使用t o c 编制计划的四步骤1 5 2 2 生产调度理论1 7 2 2 1 生产调度理论的基本概念1 8 2 2 2 生产调度模型1 8 2 2 3 生产调度方法一2 0 2 3 最优化理论一2 2 2 3 1 最优化问题的数学模型2 2 2 3 2 最优化问题的分类2 2 2 3 3 最优化问题的解题步骤2 2 第3 章造纸企业生产调度模型的构建2 4 v 硕士学位论文 3 1 模型构建的指导思想与原则2 4 3 1 1 模型构建的指导思想2 4 3 1 2 模型构建的原则2 5 3 2 造纸企业的生产调度2 5 3 2 1 造纸企业生产调度的目标2 5 3 2 2 造纸企业生产调度的约束条件2 6 3 2 3 造纸企业生产调度的策略2 6 3 3 抄纸系统的加工方案2 7 3 3 1 生产过程的瓶颈分析2 7 3 3 2 基于浆纸平衡抄纸系统加工方案研究2 9 3 4 造纸企业生产调度模型3 0 3 4 1 模型假设：一3 0 3 4 2 制定生产计划任务表3 l 3 4 3 生产调度数学模型一3 1 3 5 小生境遗传算法3 2 3 5 1 染色体编码方案3 2 3 5 2 适应度函数评价3 3 3 5 3 基本遗传操作3 3 3 5 4 引入小生境技术3 4 3 5 5 算法评价3 5 第4 章应用实例3 6 4 1 公司总体概况3 6 4 1 1 公司发展情况3 6 4 1 2 主要产品和特色3 6 4 2 公司生产系统3 7 4 2 1 主要生产单位和辅助系统情况3 7 4 2 2 主要生产工艺流程3 7 4 3 公司生产调度现状3 8 4 3 1 生产计划体系一3 8 4 3 2 生产组织系统3 9 4 3 3 生产调度中存在的问题一3 9 4 4 模型应用4 0 4 4 1 初始数据确定4 0 4 4 2 沅纸生产调度模型4 2 4 5 模型求解结论说明4 3 基于约束理论的造纸企业生产调度模型研究 结论4 5 参考文献一4 7 致谢5 1 附录a ( 攻读硕士学位期间所发表的学术论3 c ) 5 2 附录b ( 求解程序) 5 3 l 硕士学位论文 插图索引 图1 1 本文研究的技术路线1 0 图3 1 “集中制浆、多机台分散造纸”生产工艺流程2 9 图4 1制浆生产工艺流程3 7 图4 2 抄纸生产工艺流程3 8 图4 3 普通遗传算法与小生境界算法运行结果对比4 4 图4 4 小生境界算法迭代2 0 0 次、3 0 0 次运行结果对比4 4 l i 基于约束理论的造纸企业生产调度模型研究 附表索引 表2 1常用排序法1 7 表3 1造纸企业生产调度策略2 7 表3 2 染色体编码对应的生产调度表3 3 表4 1造纸机台性能参数4 l 表4 2 产品工艺参数4 1 表4 - 3 加工费用4 l 表4 4 库存情况一4 l 表4 5造纸机台的产能表4 1 表4 6 造纸机台的耗浆能力表4 1 表4 7 生产任务表4 l 表4 8 抄纸系统的合理加工方案表4 2 表4 9 最优解方案4 3 表4 1 0 设备l 的生产明细计划4 3 表4 1 1 设备2 的生产明细计划4 3 表4 1 2 汇总生产计划4 3 i x 硕士学位论文 第1 章绪论 随着计算机技术的进步和互联网时代的到来，世界已进入了网络信息时代， 面对世界经济的全球化与信息化，企业信息化已成为世界各国改造传统产业、提 高企业国际竞争能力的有力工具。近年来，随着我国加入世界贸易组织( w o r l d t r a d eo r g a n i z a t i o n ，w t o ) ，各造纸企业进入了多品种小批量、客户定制与柔性化生 产时代，生产计划变更日趋频繁，传统计划模型( m a n u f a c t u r i n gr e s o u r c e p l a n n i n g ，m r p ) 越来越不能适应快速多变的市场需求，基于约束理论的生产调度方 法一高级排程计划( a d v a n c e dp l a n n i n ga n ds c h e d u l i n g ，a p s ) 应运而生，成为生产管 理的新工具。 高级排程计划是一种基于约束理论、生产优化和模拟技术的生产计划工具， 其基本思想是：在探讨满足生产工艺要求、资源能力限制、物料供应限制等约束条 件的前提下，通过下达生产指令，分配生产任务，以达到预订的生产经营目标， 如使延期交货的总罚金最少、切换费用最小、加工费用最少等。a p s 作为一种先 进生产调度方法，已引起企业管理和理论研究地广泛关注。在企业管理中，产品 竞争日趋激烈，急需先进的生产调度方法来提高企业的生产经营效率，优化资源 分配，提高企业在国际市场上的竞争力。此外，这种激烈的竞争促使企业引进先 进的、复杂的、知识密集型的制造技术和系统，如成组技术( g r o u pt e c h n o l o g y ， g t ) 、柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m ，f m s ) 和计算机集成制造系统 ( 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 gs y s t e m s c i m s ) 等，而这些技术和系统又产生了 新的生产调度问题，从而拓展了理论界的研究领域。在理论研究中，一些新的方 法如系统仿真、人工智能方法、遗传算法、神经网络法等为生产调度的理论研究 开拓了新的领域，促进企业管理中新成果的推广和应用。 近年来，随着a p s 理论与实践的发展，a p s 受到了制造企业的关注与重视， a p s 己代替了传统的生产计划方法。随着客户定制时代的到来以及造纸企业生产 调度模型、算法研究的深化，约束理论、生产优化与模拟技术将成为基于约束理 论的造纸企业生产调度计划的关键技术。 1 1 选题背景与意义 随着产品竞争的加剧、产品生产周期与交货期缩短及客户要求的提高，国内 造纸企业进入了多品种小批量、客户定制与柔性化生产时代，生产计划的变更越 来越频繁，特别是生产计划需经常修正，以随时满足顾客的不同需要。然而，传 统造纸工艺的“惯性”大，生产计划难以调整，因此研究造纸企业的生产调度问题 基于约束理论的造纸企业生产调度模型研究 具有很多的理论意义和现实价值。 2 0 世纪9 0 年代以来，随着科学技术的发展和全球经济一体化进程的推进，企 业经营环境日趋复杂，集中表现市场需求的快速变化，在产品的生命周期和交货 期缩短，顾客对产品的要求也变得多样化、个性化。企业经营环境的改变使得传 统的大批量生产的经营管理方式已经不能满足新环境下市场竞争的需要，需要有 新的生产和管理方式来对其进行替代，多品种小批量、客户定制与柔性化生产就 是在这种新的生存环境中孕育而生的一种新兴的生产和管理模式。 与大批量生产相比，多品种小批量、客户定制与柔性化生产的生产计划变更 成倍增加，且生产计划需经常修正，以随时满足顾客的不同需要。然而，传统造 纸工艺的“惯性”大，切换生产方案时，经常造成某种浆料的不足或积压，生产计 划难以调整，因此造纸企业寻求先进的生产调度方法，提高调度结果的精确度， 减小计划变更次数，是学术界研究的重大课题。 调度问题的研究始于2 0 世纪5 0 年代，约翰逊对两台机床的流水车间( 简称 f l o w s h o p ) 型调度问题进行了研究，提出了解决n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的优化算法，代表调度理论研究的开始；6 0 - 7 0 年代，由于调度问题的复杂 性，不同的研究者开始从不同的角度研究生产调度，产生了许多车间调度问题的 类型和方法，形成了调度理论的主体( 经典调度理论) 。随着7 0 年代后期调度理论 研究的深入及各种交叉学科的发展，涌现出了许多新的生产调度理论与方法，譬 如邻近搜索算法、神经网络算法、人工智能算法等。经过5 0 多年的发展，调度问 题的研究经历了由简单到复杂、从理论研究到应用研究的过程，提高了企业的生 产、经营效率，实现了企业资源的优化配置，提高企业国际竞争力。 造纸企业的生产调度问题已被证明多是n p 难题，随着问题规模的增加，求解 调度问题的计算时间呈指数增加，求解调度问题的算法往往难以搜索整个值域， 常不能求出最优解。这时可通过约束消除不可行值域从而减少有限值域的规模， 通过变量值域的交换逐个评价约束的影响，提高问题的求解能力。因此，以约束 理论为指导，分析造纸企业的生产工艺要求、资源能力限制、物料供应限制等约 束条件，并确定企业经营目标，构建造纸企业的生产调度模型。对这类问题的求 解，人们已意识到应把主要精力放在寻求其满意解上，而采用遗传算法是求解这 类问题满意解的最佳工具之一。但用遗传算法往往只能找到局部最优解，为避免 这种现象，本文在遗传算法中引入小生境技术，以解决这种问题。 综上所述，在多品种小批量、客户定制与柔性化生产时代，造纸企业需要在探 讨其生产工艺要求、资源能力限制、物料供应限制等约束条件及生产经营目标的 基础下，通过构建基于浆纸平衡的生产调度模型，并采用小生境遗传算法求解该 模型，才能真正实现在客户需求不断变化的情况下，造纸企业也能以高效率与低 成本来满足客户的要求。目前，我国关于造纸企业生产调度方法研究还不多，主 2 硕士学位论文 要针对纸卷切割、打浆过程、蒸煮过程、 文主要针对抄纸系统加工方案进行研究， 效性，具有一定的理论价值和实践意义。 纸卷切割与库存问题等开展了研究。本 并通过实例验证了本文模型和方法的有 1 2 研究范围界定与主要解决的问题 1 2 1 研究范围界定 从2 0 世纪9 0 年代末期开始，市场环境的日新月异，客户需求的不断提升， 给造纸企业带来了严峻的挑战。造纸企业必须根据市场以及客户的需求敏捷地做 出反应，以高效率与低成本生产出满足客户个性化需求的任何产品。生产调度中 心接到订单后，会根据生产工艺要求、资源能力限制、物料供应限制的情况，进 行订单分解，各抄纸系统接到分解后的订单，必须严格按照分解订单规定的车速、 规格、型号等要求安排生产，并及时上报生产异常情况，以及时调整生产计划。 制浆系统根据分解后订单制定一定时段的造纸企业耗浆流量图，并按照耗浆流量 图来安排生产，确保企业浆纸平衡，提高企业生产、经营效率。本文针对的是采 用“集中制浆、多机台分散造纸”生产模式的造纸企业。 本文基于多品种小批量、客户定制与柔性化生产的环境，对造纸企业的生产 过程进行了流程性分析、浆纸平衡分析，并结合约束理论，构建了基于约束理论 的生产调度模型，对企业资源进行合理的配置，使得企业既可以按期交货，也可 以使企业运作成本最小。另外，通过多目标模型的设计，使得企业在进行资源配 置时，做到尽可能的均衡利用各类资源，提高企业的柔性，提升承接各类应急订 单与高优先级别订单的能力。 本文研究的造纸企业是指既有制浆生产线，也有抄纸生产线的制浆造纸企业。 他们所生产的产品均需要根据客户的要求进行生产，使用的抄纸设备具有一定的 生产柔性，获取的订单都是定制性订单。 1 2 2 主要解决的问题 根据本文的研究背景与研究范围，本文拟解决的问题主要包括以下五个方面： ( 1 ) 在造纸企业生产调度分析的基础上，通过对造纸企业生产过程进行了瓶颈 分析和浆纸平衡分析，筛选出了抄纸系统合理加工方案。 ( 2 ) 根据模型构建的指导思想和原则，结合造纸企业生产实际和客户需求，以 基于浆纸平衡的抄纸系统合理加工方案为切入点，构建了基于约束理论的造纸企 业生产调度模型。 ( 3 ) 在分析生产调度f 1 题算法的基础上，着重对遗传算法、小生镜遗传算法的 原理进行了分析，并采用c + + 语言对算法求解模型的过程进行了实现，为后续验 证算法的有效性与优越性打下了基础。 3 基于约束理论的造纸企业生产调度模型研究 ( 4 ) 为验证本文提出算法的有效性，对实例分别采用遗传算法与小生镜遗传算 法进行求解，比较调度结果的精确度。 1 3 生产调度国内外研究状况 生产调度是管理出效益的重要方面，特别是随着i n t e r n e t 、b p m ( b u s i n e s s p r o c e s sm a n a g e m e n t ) 、f m s 、c i m s 以及e r p j i t ( e n t e r p r i s er e s o u r c ep l a n n i n g j u s t i nt i m e ) 技术的发展，生产调度成为实现企业信息化、自动化的关键环节之一。因 此，生产调度理论的研究和应用成为学术界和企业界的研究热点之一。本文就生 产调度问题的研究现状从建模、调度方法两方面进行回顾和梳理，并探讨了生产 调度问题研究的发展趋势。 1 3 1 生产调度问题的建模方法研究 生产调度研究的首要问题通常是对具体生产环境中复杂动态、多目标、多约 束调度问题的抽象和简化，即建模。目前建模方法很多，主要有以下两大类： 1 3 1 1 图和网络的建模方法 作为制造系统建模方法，主要有活动循环图、组合网络、p e t r i 网、g r a l 网 等，而其中p e t r i 网以其独特的优势广泛应用在生产系统的设计、分析与仿真中。 这里主要介绍一下p e t r i 网，文献【l 五】详述了其他类型的图和网络建模方法。 p e t r i 网是动态系统建模的重要技术。它可以通过后台的p e t r i 网模型来对前台 用户建立的过程模型进行仿真以及各项性能指标的评价，使过程模型具有较强的 实用性。自p e t r i 网被提出以来，至今已形成了相当规模的研究领域。在理论方面， 提出了基于状态方程和代数分析的技术【3 卅、基于可覆盖树的图分析技术【5 7 】和基于 化简分解的归纳分析技术【8 母】。 p e t r i 网模型主要分为基本p e t r i 网模型、扩展p e t r i 网模型和其他p e t r i 网模型 三类。基本p e t r i 网模型直观、易理解，但由于其在描述复杂系统时节点数目过多， 只适用于简单制造系统的建模。扩展p e t r i 网模型是对基本p e t r i 网模型在有色、 时间、层次、工作流变量、逻辑变量方面进行扩展后形成的p e t r i 网模型【l 们。其他 p e t r i 网模型是p e t r i 网技术和面向对象技术结合后形成的，具有较强的设计描述能 力和功能实现能力，主要有基于对象的p e t r i 网、面向对象的p e t r i 网和对象p e t r i 网。文献【l l j 介绍了面向对象的p e t r i 网在单元控制建模中的发展与应用。 1 3 1 2 非图和网络的建模方法 ( 1 ) 控制论的方法，主要有扰动分析法和极大代数法。 扰动分析法兼顾了仿真法与理论分析的长处，同时也避免了单纯用仿真法的 大量计算和理论分析研究复杂问题所遇到的困难。它主要用于研究生产系统性能 4 硕士学位论文 指标( 生产率等) 对参数变化的敏感性，并以此为基础对系统的运行进行优化。缺点 是多参数扰动很难用表或状态方程描述，且扰动较大时，近似度较差。 极大代数法是以系统运行关系建立起一系列事件发生时间的关系方程来构建 生产系统模型。在用极大代数法时，工件加工顺序须事先确定才能进行建模分析。 因此，极大代数法仅适合生产系统的性能分析，而不适合调度。文献【1 2 】在极大代 数上线性系统描述的框架下，通过关键路径研究了离散事件动态系统( 简称d e d s ) 参数扰动对系统的影响。 ( 2 ) 数学规划建模法 数学规划建模法主要有线性规划法、整数规划法和析取规划法。线性规划是 最基本的数学规划，求解线性规划问题的算法主要有单纯形法、内点法。整数规 划可以看作一个部分变量有整数限制的线性规划，求解方法主要有割平面法、分 支定界法。析取规划是含有一个或多个不连接约束的线性规划。目前，有关数学 规划建模的研究很多。w a g n e r 对m 台机器流水车间最大流程时间的调度问题建 立了整数规划模型【1 3 l 。b l a z e w i c z 、d r o r 和w e g l a r z 给出了一个针对生产调度数学 规划的总体状况综述【l 训。 ( 3 ) 仿真 仿真是研究生产调度系统的另一常用方法，较常见的计算机仿真语言如 s l m s c r i p 、e c s l 、s i m o n 、g p s s 等等。仿真法存在代价高昂的缺点。 1 3 2 生产调度方法研究 在构建生产系统模型后，就要构造相应调度方法进行生产问题求解。经过6 0 多年的发展，生产调度方法经历了从简单到复杂、从单一到多元的过程。总结起 来，现有调度方法大体上可以分为以下几种。 1 3 2 1 数学规划法 数学规划法就是将生产调度问题简化为数学规划模型，并采用整数规划、动 态规划以及决策分析等方法解决调度最优化或近似优化问题的生产调度方法。典 型应用有：d i a z 等运用o a 方法求解实际优化调度问题i l5 j ；为了求解混合整数非 线性规划( 简称m i n l p ) i h 题的全局最优解，k o c i s 等提出了一种基于外部逼近的两 步法【1 6 】；f l o u d a s 等提出了一种广义b e n d e r 分解法，但这种方法只适用具有某种 特殊结构的非凸m i n l p 问题【1 7 l ；r o s l o f 等提出了一种基于混合整数规划( 简称 m i l p ) 的新算法，成功的应用于造纸和制药企业的生产调度中【1 8 1 ；王朝晖等采用 l a g r a n g i a n 松弛法求解m i n l p 问题，减少了求解时州1 9 】；i e t a p e t r i t o u 和f l o u d a s 提出了一种新的基于连续时间表示的m i l p 数学模型的算法，能显著地减少变量 数，从而有效地减少计算时间等等1 2 0 1 。 采用数学规划法，表达清晰，易于在计算机上求解，解的全局性好，但仅适 5 基于约束理论的造纸企业生产调度模型研究 应求解小规模调度问题，不适应复杂多变的大规模调度问题。 1 3 2 2 规则调度法 规则调度法是根据人们在生产实践中所总结、提炼出的很多行之有效的经验 和规则( 通常称其为调度规则) 来决定下一步操作的调度方法。典型的应用有： p a n w a l k e r 等人总结了1 1 3 个启发式调度规则，将其分为简单规则、复合规则、启 发式规则，并对个规则的适应情况做了总结【2 1 】；p a r k 等提出了回归启发式分类原 则和动态启发式分类原则，加快了规则的匹配速度【2 2 】；k i m 等提出了一个基于规 则的再调度系统，处理m u l t i p u r p o s e 型生产过程中的不可预料事件【2 3 】；高红和 熊光楞分析了规则与性能指标的关系，给出了合理选择规则的建议，这在一定程 度上解决了匹配速度慢的问题【2 4 】；任艳频等运用p e t r i 网给规则调度系统建模，得 到调度规则的形式化表示，分析规则调度系统的性能【2 5 】；杨圣祥等在利用神经网 络实现智能选择规则进行调度，表现出与人工智能结合的趋势等【2 6 。2 7 1 。 它的优点是直观、简单、快速求解、便于实现，但它是局部优化方法，难以 得到全局最优解或次优解，常需要专家介入。 1 3 2 3 基于仿真的调度方法 大多数生产系统非常复杂，很难用一个精确的解析模型来进行描叙和分析， 而通过仿真模型来收集数据，可对实际系统进行性能、状态方面的分析，从而辅 助系统选确定合适的控制调度方法。基于仿真的方法不单纯追求系统的数学描述， 尤其是离散系统仿真，侧重于对系统运行过程中逻辑关系的描述。仿真技术不仅 能对生产调度方案进行评价与选择，分析系统的动态性能，而且能够选择系统的 结构参数。典型的应用有：a z z o p a r d i 等通过赋时p e t r i 网对m u l t i m p r o d u c t 型问题 进行仿真调度研究【2 8 。2 9 】；杨盛等提出逆正规p e t r i 网的概念，即根据目标输出标识 确定开放变迁集，再由开放变迁集确定输入标识，由此实现由优化目标向输入变 量确定的转化【3 0 】；b a i l 等提出了一类连续p e t r i 网和一般离散p e t r i 网组合的混合 p e t r i 网【3 l 】；x u 等把连续过程的生灭对应p e t r i 网某个位置一个特定令牌的流入和 流出，提出了一类广义混杂的p e t r i 网等等【3 2 】。 当然，基于仿真的求解方法具有测试时间短、不受时空限制、能选择较优的 调度决策等优点，但也存在对调度理论贡献少、成本高、仿真的精确度受到编程 人员判断能力和技术水平的限制等缺点。 1 3 2 4 基于人工智能的调度方法 2 0 世纪8 0 年代以来，人们把研究重点转移到调度问题应用研究上来，解决实 际调度问题的智能调度方法开始走上历史舞台。基于人工智能的调度方法是利用 模型和知识，通过模拟、推理等手段为人的决策提供支持，从而使人们可以根据 生产实际情况做出相应决策。它主要有如下几种调度方法： 6 硕士学位论文 专家系统是通过收集操作人员经验构成数据库，然后采用在线寻优的生产调 度方法。它在2 0 世纪8 0 年代早期和中期非常流行，并在许多领域也得到了应用。 典型的应用有：黎志成等提出了一种基于专