（控制理论与控制工程专业论文）递阶流水线整体生产计划的研究.pdf

摘要 递阶流水线整体生产计划的研究 硕士研究生：范熙导师：蒋珉副教授 东南大学 摘要 本文在研究了国内外车间生产计划问题的进展和对制造企业生产现场进行的调研分析并对规划理论 进行深入研究的基础上，建立了含有限缓冲区的具有一定普遍性的上下游生产线部件成品关联结构，并 以此结构为对象，研究递阶流水线整体建模问题从车间生产计划建模、生产计划优化算法和算法的具 体实现出发研究了制造企业生产计划的制定问题。 在生产计划建模方面，本文根据生产中的实际情况和上下游生产线部件成品关联结构的特点与要求， 突出了一个核心产品的概念，并且围绕着核心产品采用推动和拉动相结合的建模方式建立了生产效益最 高的整体计划模型。考虑到模型规模的复杂性，结合生产线的实际情况又对模型进行了分解和简化。建 立的模型主要考虑了以下几种情况：优先满足用户核心产品需求、解决生产线之间成品同步、防止缓冲 区溢出。 在生产计划优化算法方面，本文建立的生产计划模型其目标函数是非线性的且目标函数的梯度是分 段常数，而约束是线性的，因此通常的做法是将非线性目标函数通过增加约束化为线性目标函数，从而 将一个本来比较难以解决的非线性规划问题转化为线性规划问题，然后采用线性规划算法对其进行仿真 求解，但本文将尝试直接应用遗传算法求解该非线性规划问题。 在仿真软件设计方面本文运用面向对象的技术来设计生产计划仿真模型，并以v c 6 0 为开发工具 设计了仿真模型库和算法库。 最后本文给出的仿真实例说明了围绕着核心产品采用推动和拉动相结合的方式建立的模型及算法 是合理且有效的，同时也指出了本文所提出的模型和算法的一些局限性和有待改进的地方 关键词：生产计划，关联结构，核心成品，缓冲区，同步，简化，遗传算法，仿真 摘要 s t u d y f o ri n t e g r a t e dp r o d u c t i o np l a n n i n go f h i e r a r c h i c a lf l o wl i n e f a nx is u p e r v i s e db yv i c ep r o f h a n gm i n s o u t h e a s tu n e k s i t y a b s t r a c t o nt h eb a s i so fa n a l y z i n gt h er e s e a r c hs t a t u so fp r o d u c t i o np l a n n i n ga n di n v e s t i g a t i o nf o r m a n u f u c t u r e , - e n t e r p r i s ep r o d u c t i o n - s c e n ea n ds t u d y i n gt h o r o u g h l yp r o g r a m m i n gt h e o r y , a r e l a t i o n a ls t r u c t u r eo f u p - d o w ns t r e a mp a r t sw i t hl i m i t e db u f f e ri se s t a b l i s h e d , w h i c hh a sac e r t a i n u n i v e r s a l i t y a ni n t e g r a t e dp r o d u c t i o np l a n n i n gp r o b l e mf o rh i e r a r c h i c a l p r o d u c t - l i n ei sp r e s e n t e d b yr e g a r d i n gi ta sa no b j e c to fr e s e a r c h t h ep a p e rs t u d i e st h ep r o b l e mo fp r o d u c t i o np l a n n i n g f r o mt h r e ew a y sw h i c ha l ep r o d u c t i o np l a n l l i i n gm o d e l i n g , o p t i m i z a t i o na l g o r i t h ma n da l g o r i t h m r e a l i z i n g b ya n a l y z i n gt h er e l a t i o n a ls t r u c t u r eo f u p - d o w ns t l a f f lp a r t sa n d t h ew o r k s h o p sp r o d u c t i o n p r o c e s s 。t h ep a p e re m p h a s i z e st h ec o n c e p t i o no fo o r ep r o d u c ta n de s t a b l i s h e sm a x i m a lb e n e f i t p r o d u c t i o np l a n i n gm o d e lw h i c hc o m b i n e st h ep u l lm o d e l i n gw a y sw i t ht h ep u s hw a y sa n da i m s a tb e f i t t i n gv a r i e dp r o d u c t i o np r o g r a m m i n gd e m a n d s s u c ha ss a t i s f y i n gp r i o r i t yo ft h ec l i e n t s c o r ep r o d u c td e m a n d , h a r m o n i z i n gt h es y n c h r o n i z a t i o na m o n gt h ep r o d u c t i o n - l i n e s ，a v o i d i n gt h e o v e r f l o wo f t h eb u f f e r c o n s i d e r i n gt h ec o m p l e xs c a l eo f t h em o d e l ，ad e c o m p o s e da n ds i m p l i f i e d m e t h o di sa l s oa p p l i e di nt h ep a p s r o nt h ea s p e c to f t h eo p t i m i z a t i o nf l g o f i t h ma p p l i e dt ot h ep r o d u c t i o np l a n n i n gp r o g r a m m i n g , b e c a u s et h eo b j e c t i v ef u n c t i o no f t h em o d e l si nt h i sp a p e ri sn o n l i n e a r , a n dt h eg r a d i e n to f w h i c h i sp i e c e w i s ec o n s t a n t , s ot h eu s u a la p p r o a c hi sc o n v e r t i n gt h en o n l i n e a ro b j e c t i v ef u n c t i o nt o l i n e a ro b j e c t i v ef u n c t i o nb ya d d i n gt h ec o n s t r a i n t s b u tt h i sp a p e ra t t e m p t st oa p p l yt h eg e n e t i c a l g o r i t h mt os o l v et h ep r o b l e md i r e c t l y t h ep a p e ri 塔嚣o o pm e t h o d sf o rd e s i g n i n gp r o d u c t i o np l a n n i n gs i m u l a t i o nm o d e l s t h e s i m u l a t i o nm o d e l sl i b r a r ya n da l g o r i t h ml i b r a r yc a nb es e tu p b yv c 6 0 a tt h ee n do ft h i sp a p e r , s i m u l a t i o nr e s u l t so ft h ee x a m p l ea r eg i v e nt oi l l u s t r a t et h e e f f i c i e n c yo f t h ep r o p o s e dm o d e la n da l g o r i t h m i na d d i t i o n , t h ep a p e rf i n a l l yg i v e st h el i m i t a t i o n a n dm o r e w o r ko f t l l et h e o r ya n d a l g o r i t h m k e yw o r d s ：p r o d u c t i o np l a n n i n g , r e l a t i o n a ls t r u c t u r e ，c o r ep r o d u c t , b u f f e r , s y n c h r o n i z e ， s i m p l i f i c a t i o n , g e n e t i ca l g o t i t h m , s i m u l a t i o n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸 质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：撼师签名：题日 期。 地脚、z 第一章绪论 i i研究背景及意义 第一章绪论 在社会主义市场经济条件下，企业实行自负盈亏的经营机制，因此争取利润的最大化自然成为了企 业的一种内在运行机制。由于企业面临国内外激烈复杂的市场竞争，受到市场各种条件的强烈制约，这 样，企业要想在市场竞争中生存求发展，就必须尽可能地最大限度地进行资金积累，增强经济实力，提 高自身技术，采用科学管理，而这一切又是以利润最大化作为前提。所以，追求利润最大化成为企业的 运行目标，其在经济活动中有着积极的效应。 2 0 世纪，随着数学和计算机技术的不断发展以及先进的管理技术和信息技术的引入，制造业得到了 迅猛的发展，并提出了许多先进的制造管理模式，如：准时制生产模式( j u s ti nt i m e ，j i t ) 、物料需求 计划( m a t e r i a l r e q u i r e m e n t p l m m i n g ，i v l r p ) 、制造资源计划( m a n u f a c t u r i n g r e s o u r c e p l a n n i n g ，m r p i i ) 、 企业资源计划( e n 帅r i s er e s o u r c ep l a n n i n g ，e r p ) 、计算机集成制造( 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 ， c i m ) 等。其中最有意义的应该是1 9 7 3 年美国约瑟夫哈林顿( j o s e p hh a r r i n g t o n ) 博士在( c o m p u t e r i n t e g r a t e dm a n u f a c t u r i n g ) 一书中首次提出的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 ) 概念”j 它的内 涵是借助计算机，将企业中各种与制造有关的技术系统地集成起来，进而提高企业适应市场竞争的能力。 计算机集成制造系统吲( 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 ，c i m s ) 就是在此基础上结合新 的生产组织原理和概念从而形成的一种新型生产模式，它是以计算机网络和数据为基础。利用计算机技 术将经营管理、产品设计、加工制造、销售服务等生产经营活动集成起来，以实现更短的生产周斯、更 好的产品质量以及对市场和用户需求做出更迅速的响应，从而达到整体优化和综合效益的提高。而生产 计划是c i m s 的一个核心组成部分，也是c i m s 实现和应用过程中的一个难点 我国制造业目前正处在一个成长的阶段，还远远落后于发达国家，通过引入先进的生产管理技术， 制订合理的生产计划对降低制造企业的生产成本、提高其生产效率和核心竞争力都具有十分重要和深远 的意义 1 2国内外研究的概况 生产计划解决的是做什么( w h a tt od o ) 的问题，是在满足成品需求过程中实行资源高效分配的关键 唧。目前，在制造业中相当一部分产品在生产过程中的等待时间占到了生产过程总时间的9 0 1 4 ，而这 些时间大部分都浪费在等待原材料和相关工序的加工上面。通过制定一个合理的生产计划往往可以在一 定程度上缩短等待时间增加机器的利用率，从而可以保证产品的按期完工并充分利用现有生产能力使企 业获得更大的利润。 1 9 6 5 年，a n t h o n y 提出了计划与控制结构模式，他把企业中的计划与控制分成战略计划、战术计划、 作业控制三个层次。1 9 7 5 年，h a x 和m e a l 从生产管理的角度将a n t h o n y 的计划与控制结构发展为厂级 生产计划、总体能力计划和详细生产作业计划三个层次，成为较有代表性的分层递阶生产计划 ( h i e r a r c h i c a l p r o d u c t i o n p l a n n i n g ，h p p ) 方法。该优化方法是以h p p 中的某一层为对象，着重解决某 一层中的具体决策问题。o r l i c k y l 9 6 5 年提出的物料需求计划( m a t e r i a l r e q u i r e m e n t p l a n n i n g ，i v l r p ) 也 是一个典型的分层递阶计划系统。h a s t i n g s 等人于1 9 8 2 年提出了将m r p 与车间作业计划集成的方法： 通过“基于作业计划的m r p ( s c h e d u l e - b a s e dm i u ) ”，用有限生产能力为约束，使提前期可变，但它通 过顺排方法保证了零件配套和产品按期交货。1 9 8 8 年h a l e v i 提出过一种主生产计划( m a s t e rp r o d u c t i o n p l a n n i n g ，m p p ) 的概念，他认为m p p 可以取代m p s 、m r p 和车间生产作业计划三者，但只停留在概 念上，并不清楚如何生成这个m p p 。l a s s e r r e 于1 9 9 2 年提出了一种p l a n n i n g 和s c h e d u l i n g 两级计划集成 的模型，该模型首先确定在能力约束下一组给定顺序产品的批量大小( 得到一个可行的p l a n n i n g ) ，然后 再在批量固定情况下确定加工顺序( s c h e d u l i n g ) 。 东南大学硕士学位论文 在传统的制造系统中，一般将生产计划分层按照t o p - , l o w n 的方式来分解。如m r p 系统中习惯将生 产计划分为长期生产计划、中期生产计划和短期生产计划三种问题分别进行求解p j 。其中长期生产计划 和中期生产计划主要考虑了中长期生产过程中的任务决策问题，而短期生产计划则是中期生产计划的一 个分解。 目前实际应用的生产计划方法主要有运筹学、启发式规则和专家系统等，而理论的研究已经不仅仅 局限于运筹学方法上。研究方法涉及模糊数学、系统仿真、控制理论、神经网络、人工智能和邻近搜索 技术等。这些方法无疑给生产计划理论的研究开辟了一片新天地 1 3课题研究对象与内容 在车间生产计划研究方面，国内外已有大量文献，也取得不少成果。以往的论文都是在已知下游生 产计划的情况下推出上游生产计划( 即所谓的“拉动”模型) 6 - ”i 或者是在已知上游生产计划的情况下 推出下游生产计划( 即所谓的“推动”模型) ，而现在很多制造企业为了追求利润的最大化，在安排生产 时往往要优先考虑实时地满足客户提出的效益较高的产品的需求，例如有些企业有军工产品的需求，这 时候不光对产品的数量有严格的要求，对交货的时间也有严格的限制，而这些产品往往利润较高( 本文 中将这种利润较高需要优先加工供给用户的产品定义为核心产品) ，优先加工这样的产品势必会影响到上 下游生产线的原生产计划，所以将拉动模型和推动模型结合起来考虑不仅具有重要的理论意义，更具有 广泛的应用价值另外对上下游生产线之间存在着有限缓冲区与各生产线之间存在成品同步情况方面 的研究文献相对较少，大部分研究生产计划问题的文献没有考虑缓冲区大小或成品同步方面的约束情况， 或者只将它们作为车间调度问题进行研究。而在制造企业中。缓冲区有限以及各生产线之间存在成品同 步的现象是普遍存在的所以对于这方面的研究也具有一定的意义。还有就是模型的简化，这方面的工 作对于提高模型的求解速度起到了至关重要的作用。 本文针对上述存在的问题在前人工作的基础上开展研究，通过对制造企业生产现场进行调研，发现 上下游生产线之间普遍存在着大小不一的缓冲区( 在本文中将其作为下游待加工零部件输入缓冲区) ，并 且一部分下游生产线还要求与之关联的上游生产线同步输出主成品零部件。同时，考虑到生产任务有时 并不饱满，部分生产线还可以做一些外协加工，加工生产一些核心成品和副成品( 或产品) 因此，基于 以上的分析，可以构勒出如图1 1 所示的单条生产线输入输出结构框图 核心成品缓冲区- 核心成品输出 主成品缓冲区、 工位工位工位 主成品输出 m t 女口“、h f ：- 鹪舾腩 副成品输出 l ：，7 生产线 同步剐成品输出一 同步副成品缓冲宣 + 图1 1 生产线输入输出结构图 分析产品或成品的生产过程，可以发现从毛坯到产品或成品一般要经过零件、部件、组件几个状态( 如 图1 2 所示) 。 每两个状态之间的转换过程都是在某条生产线上实现的，对应于各个转换过程的各条生产线根据其 输入输出关系就构成了一条具有多级上下游关系的供需关系。由于产品结构的复杂性，这种供需之间的 关系也是复杂的。但通过分析不难发现整个生产线按照上游生产线输出部件成品与下游生产线输入待加 工零部件之间的关系可以看作是如图l _ 3 所示的一个简单的上中下游生产关系模型按照某种方式组合得 到的结果。 图1 2 产品或成品的诞生过程 2 第一章绪论 图1 3 一个简单的上中下游生产线关联结构 在制造环境中，生产计划是为满足产品需求进行有效资源分配的关键。由于生产计划问题的复杂性往 往不允许采用整式建模方法，因而在生产计划文献中普遍提倡采用递阶生产计划方法【7 1 “”。考虑到问题 的复杂性，针对图1 3 所示的三级简单生产模型。存在着如下假设： ( 1 )中游生产线为m 条非柔性生产线； ( 2 ) 核心产品优先满足加工需求，然后再考虑满足下游对主成品及其他用户对副成品和同步副成 品的需求； ( 3 ) 中游生产线成品需求的种类为：核心产品为绣种、主成品为啊种副成品为以种，同步副 成品为两种( i = l 2 ，胸。焉、啊，鸭与两均可以为零； ( 4 ) 下游的计划区间由 r 个周期组成； ( 5 ) 同步副成品组为组； ( 6 ) 各成品对应的缓冲区大小可以不等； ( 7 ) 该生产线使用传送带传输零件，所以不同的零件对应的传输速度不同； ( 8 ) 目标：建立一个怎样的模型、制订一个什么样的生产计划才能使整个生产线的效益最高 在求解模型的过程中，本文将通过增加几个时间约束来简化模型，并且将整体模型分解到每个周期 内每条具体的生产线上，从而提高求解速度。在求解算法的选择上，由于遗传算法非常适宜于组合优化 问题的求解，并且具有其他算法所不具有的优点，所以考虑采用遗传算法求最优解。 1 4论文的结构 针对课题的研究对象及其内容以及本人在本课题中所做的研究开发工作，论文具体的内容安排如下： 1 第一章介绍了本课题的背景、目前国内外研究动态以及本课题的研究对象和内容。 2 第二章围绕课题涉及的问题，综述前人工作情况，包括近几年以来的国内外动态、前人的工作 水平、目前尚存在的问题、本课题的主攻方向等。 3 第三章将首先为各级生产线建立一个生产效益最高的整体计划模型，详细地描述了模型建立的 基本思想和物理意义。考虑到问题规模的庞大性和求解的复杂性，将逐步简化模型，最后建立 3 东南大学硕士学位论文 具体到每条生产线在每个周期内的计划模型。 4 第四章介绍了论文中要用到的遗传算法，主要介绍了算法的原理及其一些需要注意的地方 5 第五章介绍了仿真算法的总体设计、仿真软件结构。 6 第六章针对上面介绍的整体模型和分解模型构建了一个实例，并对仿真结果进行了分析比较 4 第二章生产计划问题综述 第二章生产计划问题综述 2 1生产计划的分类 生产计划主要解决的问题是在一段时间跨度上，各级管理人员所做的跟企业的生产活动有关的各种 决策，且根据决策的目标不同。生产计划的侧重点也有很多不同。文献【5 】中按照计划周期将生产计划划 分为： 1 ) 长期计划：上层管理者( c e o a n d v p ) 作出的决策。一般是未来一到两年的计划。比如： 乱总体战略计划( c o r p o r a t es t r a t e g i cp l a n n i n g ) b 业务预钡f f b u s i n e s sf o r e c a s t i n g ) c 产品和市场计划( p r o d u c ta n d m a t k o tp l a n n i n g ) 正财务和资源计划( f i n a n c i a la n dr e u r p l a r m i n g ) 2 ) 中期计划：中层管理者( p l a n t m a n a g e r s ) 的决策一般是未来3 到1 8 个月的计划。比如： & 总生产计划( a g g r e g a t ep r o d u c t i o np l a n n i i l g ，a p ) b 项目预测( i t e mf o m a s t i a g ) c 主生产调度( m a s t e rp r o d u c t i o ns c h e d u l e 。m e s ) d 粗能力计划( r o u g h - c u tc a p a c i t yp l a n n i n g ) 3 ) 短期计划：底层管理者的决策( s h o ps u p e r i n t e n d e n t s ) 一般是未来几天或几周的计划。比如： 乱物料需求计划( m a t e r i a lr e q u i r e m e n tp l a n n i n g , m r p ) b 能力需求计划( c a p a c i t yr e q u i r e m e n tp l a n n i n g , c g p ) c 装配调度( f i n a la s s e m b l ys c h e d u l e ，f a s ) 正输入输出计划和控制( i n p u t o u t p u tp l a n n i n ga n dc o n 协o o e 生产活动控$ 0 ( p r o d u c t i o na a i v i t yc o n 卸o d 购买计划和控制( p m i m p l a n n i n ga n dc o n t r 0 1 ) 长期生产计划主要解决的是企业在较长一段时期的发展规划，时间跨度以年为单位，至少为1 年或 更多，一般受市场环境影响比较大，不确定性因素多，很难建立一个合适的数学模型进行定量优化，多 是定量和定性分析相结合。中期生产计划是企业在近期内的一个生产规划，时间跨度以月为单位，主要 确定最近几个月或半年左右的生产任务，比长期生产计划考虑的不确定因素要少，但是考虑的生产因素 更细致，比如总生产计划主要根据需求预测和订单来组织和优化生产率，人力资源和库存以尽量减少相 关生产费用，并尽量维持一个稳定的生产能力以及利用库存来缓冲需求波动中期生产计划一般也比较 复杂，通常使用一些简单的方法( 直觉的方法绘制相应图形或者表格、计算机仿真和启发式决策规则) 来解决，如果费用结构比较简单时也可以采用建立数学模型来解决。而短期生产计划则是中期生产计划 的一个分解，主要是制定数个工作日或工作周内的生产任务，通过该计划可以清楚的知道每个工作日生 产何种产品和产品的生产数量。短期生产计划考虑的生产环节最细致，不确定性因素也最少，因此可以 建立详细的生产计划模型，并采用相应优化方法进行解决。 2 2生产计划递阶分解方法 实际制造环境中的生产系统一般是十分复杂的，如果建立单一的生产计划模型往往存在着表达和计 算上的困难i l “。因此传统生产计划的制定一般不采取建立单一模型的方法，而是根据大系统理论中的分 解和协调思想采取递阶生产计划( h p p ) 模型和方法给予解决i j i m 。g e r s h w i n 等认为制造系统属于一种大系 统，描述制造系统需要大量的数据，因此全面的建模和优化是不可能的，基于递阶分解的次优策略是唯 一有希望且具有实际意义的方法i ”1 。目前，递阶生产计划分解方法常见的有五种：分别按产品结构、工 艺过程、时间和事件发生的频率进行分解，另外还有多方式组合分解。 东南大学硕士学位论文 1 ) 按产品结构分解 h a x ：和m e a l 首次提出一种在许多工业环境中都能见到的按产品结构分解的方法1 1 7 】。这种方法将递阶生 产计划分成三层，第一层是产品的类型( t y p e ) 层，第二层是产品的族( f a m i l y ) 层，第三层( 最底层) 是产品的 项( i t e m ) 层。这里，类型由族组成，族又由项组成，产品的项是交付给顾客的最终成品；产品的族是某一 产品类型的项的集合，这些项可以共享一次生产准备；产品的类型是具有相似的单位成本，直接成本( 劳 动力成本除外) ，每周期的单位保存成本、生产率和季节性的项的集合。文献0 7 仅提出了这种方法的启 发式概念模型。或者说是一种分解结构。 2 ) 按工艺过程分解 v i l l a 研究了由个串行联结的车间所组成的制造系统l “i ，这里每个车间能同时加工肘种不同的工件， 每种工件必须顺序经过每个车间。对于这种情况，v i l l a 给出了如下生产计划模型： m 。( ，) mg ( 力2 兰瑶+ ”联c j _ ( f ) i x ? ，c ( r ) ，q ( f ) 弦 ( 2 1 ) s 上i ，( f ) = a j ( x j ( f ) ，“，o ) ，巳( f ) ) + ，( 0 ( 2 2 ) j ，“) = 霉 ( 2 3 ) z ( f ) ；_ o ( r ) ，“j ( f ) ) 缈i 乃z j 暾_ t ( t ) ) ) 2 篙 x ( ) x j ；“j ( ) u j ，l ( f ) 胄( f ) 2 ( ，) d ( f ) j = l 2 ，n ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 式中，j ( f ) 是向车间输入缓冲区供给的工件流率，x ，( f ) 是第个车间的输入缓冲区的存储水平( 车 间状态) ，。，( f ) 是车问的内部控制变量( 与工件路径和车间工作站的服务控制有关) ，勺o ) 是车间输出的 工件流率，a j ( f ) 是车间的加载率。r ( t ) 、x j ( t ) 、j ( f ) 、2 j ( f ) 和4 ( f ) 都是吖维列向量，每一个分量都 对应着一种工件。只( f ) 同车间中的设备故障有关，q ( r ) 同计划长度内的订单释放有关。由于m 种工 件的工艺过程都顺序经过个车间，所以v i l l a 将这个生产计划问题分解成个相互关联的子问题网络， 然后提出用大系统理论中的关联预测法、关联平衡法、分解协调法和以后向为条件的局部反馈分解法对 这个子问题网络进行求解。但是，文献【1 8 】并没有具体给出a j 0 ，”( f ) ，巧( f ) ) 和h j ( ( f x “( f ) ) 的表达 式，也没有举例。显然，它们俩都是非线性函数，涉及很多因素，关系也很复杂，因此，该生产计划模 型能否得到应用关键在于确定4 j o o ) ，“( f ) ，弓( f ) ) 和一o ，o ) ，“o ) ) 的有效函数关系 3 ) 按时间进行分解 m a l a k o o t i 把递阶多指标生产计划按时问分解成5 层【1 9 1 ：第一层是长期计划( 年) ，负责设备布局，生 产和资源计划；第二层是中期计划( 月) ，负责工程计划，集结计划；第三层是短期计划( 周) 。负 责调度和排序；第四层是短期计划( 天) ，负责生产准备和质量控制；第五层是瞬时计划( 实时) ，负责加 工设备和机器的在线检测，管理和控制。每一层的三个冲突的目标函数是生产率晟高、质量最高、成本 最低( 或利润最高) 。每一层都有三个决策变量，即生产率、质量和成本( 或利润) ：这三个决策变量也是 6 第二章生产计划问题综述 下层目标函数的约束或界限。决策变量的求取采用基于梯度的目标规划法。刘琦和顾幸生l l ”将产品按照 生产加工流程的不同进行了分类，然后按照时间关系将原计划问题分解成三层递阶生产计划问题。第一 层是按产品类进行计算的年度总生产计划，第二层是各个产品类的以季为单位的生产计划，第三层是按 月进行的生产计划。在这一模型中，主要存在着以下几个方面的耦合关系：不同产品类对有限生产原料 的占有之间的耦合关系；不同产品对部分生产设备的使用之间的耦合关系( 属于调度的问题) ；计划的上 下层问存在耦合关系，即下层计划必须满足上层的要求。该文中考虑了企业的各类原料和产品的价格以 及产销情况的不确定性，建立了一个模糊规划问题，利用提出的一种“中间值最大隶属度”的改进算法 对其进行求解。算法中采用人工交互调整参数的方法，直至各层计划都得到满意解。 4 ) 按事件发生的频率进行分解 g e r s h w i n 首次提出按事件发生的频率分解递阶生产计划的算法和概念 2 0 1 。这里，递阶结构中的每一 层都对应着一种事件发生的频率范围，层与层之间的频率范围不能重迭，不同层的事件在频率上可以显 著区分。对每一层来讲，高层的事件变化很慢。可视为常量；低层的事件变化很快可忽略细节，用其 平均值或布朗噪声来描述。 5 ) 多方式组合分解 严洪森将按时间分解和按工艺过程分解相结合，针对柔性自动化车间( f a w ) 给出了一种新的递阶生 产计划分解方法l z l j 。该递阶结构中考虑到f a w 中的各f m s 之间的关系并不一定是串行联结的，而是相 互之间构成嘲状联结，任意f m s 之间都可能发生联系。另外，还考虑了不同周期的f m s 之间的延迟关 联因此该递阶生产计划分解方法更有实际意义文中建立的递阶生产计划分解模型为一个线性二次型 模型通过提出的关联预测算法可以较快的速度将中期生产计划分解为短期生产计划。 2 3解决生产计划问题的优化算法 对生产计划问题，目前虽然提出了很多算法，对于多数问题，由于生产计划问题本质上的复杂性， 目前唯一可行的方法是使用近似或启发式的方法( a p p r o x i m a t eo rh e u r i s t i cm e t h o d s ) 1 2 2 1 ，近似算法包括迭代 算法。局部搜索启发式算法包括模拟退火算法( s i m u t a t e da n n e a l i n g ) 1 2 3 、禁忌搜索算法( t 曲us e a r c h ) 2 4 - 2 5 1 、 定向搜索( b e a ms e a r c h ) 、遗传算法( g e n e t i ca l g o r i t h m ) t * 2 ”、进化算法( e v o l u t i o na l g o r i t h m ) t z s l 等。另外，模 糊数学、系统仿真、控制理论、神经网络和人工智能等技术的引入也给该问题的研究带来了新的活力 1 ) 运筹学方法 2 0 世纪3 0 年代产生的运筹学是传统生产计划问题的主要研究方法，运筹学的运用方式主要有两种： 建立数学的，经济学的和统计学的描述或决策和控制问题的模型，来处理各种复杂的和不确定的情况： 分析决定所选决策方案将来的可能结果的各种因素及其关系，并拟定出适当的效果度量方法，以便评价 各种可供选择的行动方案的利弊。目前，用来解决生产计划问题的运筹学方法一般分为如下两类： a ) 解析法：解析法包括数学规划与随机优化。数学规划方法主要有：线性规划( 单纯形法) 、整数规 划( 分枝定界法、割平面法、0 1 规划) 、动态规划( 网络计划技术) 、非线性规划、目标规划、多目标规划 和拉格朗日乘子法等。随机优化方法中有：排队论和存贮论等。解析法可以用来求解一些简单的生产计 划问题，但是由于该问题属于一类复杂组合优化问题，具有明显的n p - h a r d 特性，随着问题规模的增大 很快会出现组合爆炸现象，因此对大规模问题解析法往往显得力不从一t ) , 1 2 9 j 。另外，由于实际生产过程的 复杂性，并不是所有问题都可以给出精确的模型并采用解析法进行解决的。因此解析法的应用是有一定 局限性的，但是由于解析法可以给出问题的最优解，所以对解析法的研究还是很有意义的。 ”启发式方法：启发式方法是寻求解决问题的方法和策略删j 。它建立在经验和判断的基础上，体现 了人的主观能动作用和创造力。用启发式方法解决问题时强调“满意”，常常是得到满意解，决策者就认 为可以了，而不去追求最优性和探求最优解。启发式方法具有如下优点：计算步骤简单，可由未经高级 训练的人员实现；比优化方法常可减少大量的计算工作量，从而显著节约开支和时问；易于将定量分析 与定性分析相结合。对启发式方法的研究主要集中在调度规则和一些近似算法的研究上。 2 ) 智能算法 7 东南大学硕士学位论文 智能算法侧重于数值计算。智能算法主要有：人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 、模拟退火 ( 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 ) 、禁忌搜索( t a b us e a r c h ) 等。其中模拟退火和遗传算 法属于概率搜索算法，其应用范围都比较广泛且不依赖于问题的具体结构，实现简单，还可以和其他算 法进行混合，从而改善算法的计算性能。 a ) 神经网络： 神经网络的研究主要有两种：生物神经网络和人工神经网络。用于工程的主要是人工神经网络。 年代中期，美国加州理工学院生物物理学家h o p f i e l d 首次将人工神经网络成功地应用在组合优化问题中 1 3 0 l 他提出了两种神经网络模型：离散型h o p f i e l d 神经网络和连续型h o p f i e l d 神经网络模型，通常简称 为h o p f i e l d 网络模型。引入了“计算能量函数”的概念，给出了网络稳定性判据，尤其是给出了h o p f i e l d 神经网络的电子电路实现，为神经计算机的研究奠定了基础。同时开拓了神经网络用于联想记忆和优化 计算的新途径，从而有力地推动了神经网络的研究这两种模型是目前最重要的神经优化计算模型之一 ”模拟退火： 模拟退火是一种基于局部搜索的优化方法，但是不同于局部搜索，它是以一定的概率选择邻域中费 用值大的状态模拟退火算法最早的思想由m e t r o p o l i s 在1 9 5 3 年提出，k i r k p a t r i c k 在1 9 8 3 年成功地将 模拟退火应用在组合最优化问题中t 2 3 1 。模拟退火算法将组合优化问题与统计力学中的热平衡问题相类 比，通过模拟晶体的冷却过程，在晟小能量条件下达到最终物理状态( 问题的解) ，另辟了求解组合优化 问题的新途径。从理论上来说，模拟退火算法可以得到一个全局最优解，但是按照理论要求达到平稳分 布来应用模拟退火算法是不可能的，因为要达到平稳分布需要迭代无穷次或者要求温度下降的迭代步数 是指数次 c ) 禁忌搜索： 禁忌搜索是由g l o v e r 提出的用于获取组合优化问题近似解的一种邻域搜索方法1 2 * , - 2 5 1 搜索将从一个 可行解开始逐步移向一个最优或者次优解。首先按照某种方式产生一初始可行解，并根据具体问题确定 当前解的相邻解集，然后评估每一个相邻解，作一次移动，移动到相邻解集中的展好解。其中有些移动 是禁忌的，因为他们会使搜索陷入局部最优或导致循环。这些禁忌移动被存在一个禁忌表中，一般禁忌 表的长度越长，则搜索陷入局部最优的可能性越小但是如果禁忌表太长，则花在扫描禁忌表上的时间 无疑会大大增加。算法的计算速度会受到严重影响。目前，还没有一个比较明确的方法用来确定禁忌表 的长度。 d ) 混合算法： 目前，将各种优化算法组合起来解决生产计划问题也是一个热点研究方向。混合算法一般都比单独 的算法计算性能要好，所以如何综合各种算法的优点以解决相应的组合优化问题将是未来一段时间的研 究热点 2 4生产管理技术的发展 自2 0 世纪七十年代以来，世界市场由传统的相对稳定逐步演变成动态多变的特征，由过去的局部竞 争演变成全球范围内的竞争；同行业之坷、跨行业之间的相互渗透、相互竞争日益激烈。为了适应变化 迅速的市场需求，为了提高竞争力，现代的制造企业必须解决自身的t q c s 问题，即以最快的上市速度 ( t - 币m et om a r k e t ) ，最好的质量( q - - q u a u t y ) ，最低的成本( c - - c o s 0 ，最优的服务( s s e r v i c e ) 来满足不同 顾客的需求，而解决这些问题的最好办法就是加强生产管理j 。因此相应生产管理技术的出现和应用也 就很正常，下面针对制造业目前常用的一些生产管理技术进行简单的描述。 1 ) 物料需求计划m r p 早期的m r p 可定义为利用主生产调度m p s 、物料清单b o m 、库存和未交货单( o p e no r d e r ) 计算未 来的物料需求，并进行订单的补充和修改1 3 2 1 。发展过程中，m r p 得到不断完善，既是一种精确的排产系 统又是一种有效的物料控制系统，并且当环境发生变化而需要修改计划时，它又是重新排产的手段。物 料需求计划的主要目标是同时达到：保证按计划生产所需的物资、零件和产品，并向用户及时交货；维 持最低库存水平；有计划地安排生产活动、交货日程和采购活动。随着系统论、信息论、控制论等理论 8 第二章生产计划问题综述 和管理方法的不断发展和改进，物料资源计划发展成为闭环物料资源计划( c l o s el o o pm r y ) ，它加强了 各个子系统间的关系，既能适应主生产计划的改变又能适应现场情况的变化。 2 ) 制造资源计划m r p l l 2 0 世纪8 0 年代以来，m r p i i 逐渐取代m r p j 。m r p i i 认为人力、资金、设备和时间是材料之外的 企业资源，应同时加以控制。m r p i i 的运用能满足制造企业所有经营和生产管理的需要，因此也被称为 全面资源计划与控制系统。表面看来m r p i i 是在m r p 基础上的功能自然扩充，实际上是由于市场竞争 激化，促使企业扩大自身的资源管理范围，并细化和精确化制造资源计划的结果。m r p i i 包括主生产计 划、物料清单、能力需求计划、最终装配计划等十几个功能模块，它们通过先进的计算机技术和网络技 术，集成为一个有机整体。 3 ) 准时制生产j i t 准时生产j i t 是日本丰田汽车公司推行的一种新的生产管理模式，其要点在于只在必要的时候，按 照必要的数量，生产必要的产品旧。1 i t 通过生产同步化、均衡化和看板管理来实现最小化在制品和成 品存储量，并保证最大限度地节约资金、提高工作效率和降低生产成本。由于j i t 减少缓冲存量的前提 条件是高度可靠的产、供、销体系和劳动力供给以及设备维修能力，加上1 i t 的看板管理系统适合在生 产规律性强的制造企业中应用，这就决定它较适合在经营环境规范的、大量或大批量生产的企业中运用。 j r r 的特点可归纳如下：各个工序只生产后