（管理科学与工程专业论文）带外包情形的单产品批量问题.pdf

带外包情形的单产品批量问题 摘要 制造业是国民经济的支柱产业，其发展水平是衡量一个国家综合国力的重 要标准。近几年来，随着全球经济一体的不断深入，制造业面临新的机遇和挑 战。企业仅靠自身的能力很难适应快速变化的市场需求和竞争。通过实施业务 外包，企业不仅可以有效获取系统外的资源，从而实现转移风险，降低和控制 成本，同时可以最大限度地增强企业核心竞争力。 批量问题是生产采购计划中的核心问题之一，主要研究在成批生产中中 期或短期约束下生产采购计划的优化问题，其目标是在有限的时间段内，针 对不同的生产要素要求，确定相应的生产采购的批量，确保总成本最小。研 究批量问题已经有几十年历史了，但随着新的生产经营模式的出现，一些新的 生产计划理论不断涌现出来。本文在国内外在批量问题领域的最新研究成果的 基础上，主要运用动态规划的思想分析研究单产品批量问题。 本文的研究工作主要包括两个方面。( 1 ) 针对单产品无能力约束批量问 题，考虑了允许产品外包的情形，同时还考虑到实际生产中存在很多易变质产 品，建立带外包情形的易变质产品单产品无能力约束批量模型，设计了算法复 杂度为o ( y 2 ) 的动态规划算法。( 2 ) 针对带外包情形的单产品能力约束批量问 题，本文仔细讨论单位生产成本和库存成本是恒定的和时变的两种情况。当单 位生产成本和库存成本是恒定时，本文设计了算法复杂度为0 ( t n 2 ) 的动态规 划算法；在单位生产成本和库存成本是时变的情况时，本文提出可以将该问题 转换成最短路径问题，从而可以利用最短路径求得最优解。 关键词：生产计划批量问题外包单产品 s i n g l e - - i t e ml o t - s i z i n gp r o b l e mw i t ho u t s o u r c i n g a b s t r a c t m a n u f a c t u r i n gi sm a i n s t a yi n d u s t r yo fac o u n t r y i t sd e v e l o p i n gl e v e li st h e s t a n d a r dw h i c hr e f l e c tc o m p r e h e n s i v en a t i o n a lp o w e ro fa c o u n t r y r e c e n ty e a r s ， s c i e n c ea n dt e c h n o l o g yh a v ed e v e l o p e dr a p i d l y r a p i d l yd e v e l o p i n gs c i e n c ea n d t e c h n o l o g ys p e e du pt h ep r o c e s so fg l o b a le c o n o m yi n t e g r a t i o n t h em a r k e ts c a l ei s e x p a n d i n gc o n t i n u a l l y t h ec o m p e t i t i o nw h i c hm a n u f a c t u r i n gi si nf a c eo fb e c o m e m o r ea n dm o r ef i e r c e i ti sd i f f i c u l tf o re n t e r p r i s et os a t i s f yt h er a p i d l yc h a n g i n g m a r k e td e m a n dw i t h o u te x t e r n a lr e s o u r c e s s oe n t e r p r i s e ss e e kc o o p e r a t i o nw i t h o t h e r s b yc o m b i n i n go u t s i d e r e s o u r c e s ，e n t e r p r i s e s c a n s t r e n g t h e nt h e i r a d a p t a b i l i t yt om a r k e te n v i r o n m e n t a sa ne f f i c i e n tt o o lf o rc o m b i n i n gi n s i d ea n d o u t s i d er e s o u r c e s ，o u t s o u r c i n gh a db e e ni m p l e m e n t e db ym o r ea n dm o r eb u s i n e s s m a n a g e s l o t - s i z i n gp r o b l e m i so n eo fc o r e p r o b l e m so fp r o d u c t i o n p u r c h a s e p l a n n i n g t h eo b je c to fs t u d y i n gl o t s i z i n gp r o b l e mi st oo p t i m i z ep r o b l e mi n m i d d l e 。t e r mo rs h o r t t e r mp r o d u c t i o np l a n n i n g t h ea i mo fs t u d y i n gi st om a k ea p r o d u c t i o n p u r c h a s ep l a n n i n gi nl i m i t e dh o r i z o n ，w i t ht h ev a r i e dc o n s t r a i n t so f p r o d u c t i o n ，w h i c hc a nm i n i m i z et h eo v e r a l lc o s to ft h ep r o d u c t i o n l o t s i z i n g p r o b l e mh a sb e e ns t u d i e df o rs e v e r a ld o z e n sy e a r s h o w e v e r ，w i t ht h o s en e w p r o d u c t i o n sa n dm a n a g e m e n tp a t t e r na p p e a r i n g ，s o m en e wt h e o r yo fp r o d u c t i o n p l a n n i n gc o m ef o r t h o nt h eb a s i so fn e ws t u d y i n gr e s u l ti nl o t - s i z i n gp r o b l e mf r o m h o m ea n da b r o a d ，s i n g l e i t e mp r o b l e mw i t hd y n a m i cp r o g r a mi ss t u d i e di n t h i s p a p e r t h e r ea r et w ob a s i cl o t s i z i n gm o d e l si n v e s t i g a t e di n t h i sp a p e r ( 1 ) f o r u n c a p a c i t a t e ds i n g l e i t e ml o t s i z i n gp r o b l e mw i t ho u t s o u r c i n g ，w ec o n s i d e rt h e c a s eo fa l l o w i n go u t s o u r c i n ga n db a c k l o g g i n g c o n s i d e r i n gt h a tt h e r ea r es om a n y d u r a b l ep r o d u c t si n r e a l l i f e ，w eb u i l td e t e r i o r a t i n gi t e ml o t s i z i n gm o d e lw i t h o u t s o u r c i n ga n db a c k l o g g i n ga n dd e r i v ea no ( t 2 ) d y n a m i cp r o g r a m ( 2 ) f o r c a p a c i t a t e ds i n g l e i t e ml o t s i z i n gp r o b l e m ，a l s ow ec o n s i d e rt h ec a s eo fa l l o w i n g o u t s o u r c i n g t w oc a s e sa r eb e e nc o n s i d e r e di n t h i sm o d e l i no n ec a s e ，u n i t p r o d u c t i o nc o s ta n du n i ti n v e n t o r yc o s ta r ec o n s t a n t w ed e r i v ea no ( t n 2 ) d y n a m i cp r o g r a m i nt h eo t h e rc a s e ，u n i tp r o d u c t i o nc o s ta n du n i ti n v e n t o r yc o s ta r e t i m ev a r y w es e a r c hf o rf e a s i b l es u b p l a n sf i r s t l y ，t h e nc o m p u t e rt h e i rc o s t s a n d 2 n o w l o t s i z i n gp r o b l e mi st r a n s f e r r e di n t os h o r t e s tp a t hp r o b l e m w ec a l ls o l v et h e p r o b l e mw i t hr e a d y m a d ea r i t h m e t i c 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 s i n g l e i t e m 3 l o t 。s i z i n gp r o b l e m o u t s o u r c i n g 图2 1 图3 1 图4 1 图4 2 图5 - 1 图5 - 2 图5 - 3 图5 - 4 图5 - 5 表5 - 1 图表清单 多阶段生产系统1 0 业务外包结构模型1 5 单周期生产成本曲线2 1 允许延期交货和外包的批量问题的各阶段位置图2 2 权衡生产、外包及库存成本图2 5 带外包情形的批量问题网络流图2 6 允许外包的批量问题的各阶段位置图2 9 能力约束单一周期的生产函数曲线3 0 批量问题的有向图3 4 运算结果3 5 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金旦巴王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者粹期私字啡缉节月纱日 学位论文版权使用授权书 本学位论文作者完全了解金魍王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金起王些太 当兰一可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 储诫试 签字日期：2 优辟4 , e j9 - 0 日 电话： 邮编： 1 钼雹m 岛 钟 签 ， 挫 棚 致谢 值此论文完成之际，衷心地向我的导师储诚斌教授表示诚挚的谢意和崇高 的敬意。很荣幸在三年的硕士研究生课程学习和学术研究过程中，得到了储老 师的指导和帮助。储老师渊博的知识、严谨与实事求是地治学态度、谦和的处 事风格、高深的学术造诣、敏锐的学术思想、积极开拓创新与忘我的工作精神 使我受益菲浅。 感谢管理学院左春荣老师和任明仑老师三年来在生活学习上给与我无微 不至的关心和照顾，感谢戴道明老师和马英在学术研究及学位论文的撰写过程 中给我的指导和帮助，感谢张述初老师在学位论文的修改和成稿过程中提出了 宝贵的意见。感谢我的师兄师姐及企业建模与优化实验室的所有老师和同学， 正是因为有他们的关心、鼓励和帮助，我才得以不断的提高。 感谢管理学院的全体领导和老师，他们的工作和努力为我们创造了良好的 学习条件和融洽的研究氛围。感谢所有关心、帮助过我的老师、同学和朋友们。 最后，衷心感谢我的父母、家人和朋友，正是他们的支持和鼓励，我才得 以完成我的学业。 4 徐丽萍 2 0 0 8 年4 月 1 1研究背景 第一章绪论 2 0 纪9 0 年代以来，随着科学技术的飞速发展和社会经济的不断进步，各种 有形产品和无形服务的生命周期大大缩短，产品更新速度加快，社会消费水平 不断提高，需求呈现出多样化，个性化发展态势。全球化信息网络和全球化市 场形成，技术变革加速，企业所处的环境与过去相比，发生了深刻的变化。企 业面临着日趋激烈的竞争。 2 l 世纪全球市场竞争的主要特点有：( 1 ) 产品生产周期越来越短。由于 科学技术迅猛发展，企业的产品研发能力不断提高，产品的研制周期缩短，产 品更新速度加快，产品在市场上的存留时间也大大缩短了。( 2 ) 产品的品种 数量飞速膨胀。科学技术日新月异，企业为了在激烈的竞争中占据优势，努力 将新技术应用到新产品的开发研制中，一些新的产品不断问世。( 3 ) 需求多 样化、个性化。顾客己不再满足市场上标准化生产的产品，而更希望为自己 量身定做的产品。( 4 ) 对市场响应速度越来越快。在竞争日益激烈的今天， 速度己成为取胜的关键因素之一。随着社会的发展，科学技术的不断进步，人 们的消费观念，消费需求也在不断的变化，而且变化速度越来越快。市场机会 稍纵即逝，留给企业的时间极为短暂。如果企业对市场需求反应慢，就会被竞 争对手抢占先机。缩短产品的研发周期，加快上市时间是赢得市场的关键问题， 谁能以最快的速度满足需求，谁就会在竞争中占据优势。 传统的经营模式是企业通过“纵向一体化”实现对资源的直接控制，这适 合于市场环境相对稳定的情况，但对于市场的快速变化很难快速响应。为了摆 脱困境，人们提出了一系列先进的经营管理方式和方法，如柔性制造( f 1 e x i b l e m a n u f a c t u r i n gs y s t e m ，f m s ) ，精益生产( 1 e a np r o d u c t i o n ) ，制造资源计 划( m a n u f a c t u r i n gr e s o u r c e sp l a n n i n g ，m r pi i ) ，企业资源计划( e n t e r p r i s e r e s o u r c ep 1 a n n i n g ，e r p ) 等。这些方法以高度柔性、集成化为特征，对提高 生产效率，提高企业对市场的应变能力及企业的竞争力，有着重大的促进作用。 但是，面对快速变化的市场，企业要满足现在多样化和个性化的需求，快速响 应市场，仅仅依靠这些经营管理方式和方法，还是不够的。人们不断寻求更好 的经营管理方式和方法，以适应社会经济和市场环境的快速变化，在日趋激烈 的竞争中取得胜利。 1 2研究意义 制造业是国民经济的支柱产业，是一个国家国民经济的基础，制造业的发 展水平是衡量一个国家综合国力的重要标准。近几年来，科技迅猛发展，日新 月异的科学技术也加快了全球经济一体化进程，市场规模不断扩大，市场竞争 日益激烈。科技的迅猛发展带给市场越来越多、越来越好的产品，顾客对产品 的要求也越来越高，在要求功能和质量提高的同时，还要求个性化，多样化。 产品生命周期缩短，品种数量飞速膨胀，对企业运作模式提出了更高的要求。 要想在这种日益激烈的市场竞争中生存，企业必须降低自己的成本，提高 自己的竞争力水平，而随着科技发展，自动化和信息技术在制造业的不断应用， 生产率已被提到了相当高的程度，产品成本通过压缩原材料价格和劳动力价格 已经很难有再降低的空间，为了进一步挖掘降低产品成本和满足客户需要的潜 力，人们开始将目光投向这第三利润源泉一物流。优化物流系统是当前大部 分企业降低成本的有效手段之一。 生产物流系统是将与生产目标完成和生产顺利进行所必备的物料、设备、 部件、动力、加工件等，整合为一个物流系统并能使生产物流总体趋于合理化 的综合体。随着小批量、多批次的客户需求的增加，物流成本在制造性企业 产品成本中的比重逐渐增大，物流成本的减少成为降低产品成本的关键。有资 料显示，在整个产品生产销售过程中，有5 的时间在加工制造，其余9 5 的时 间都用于储存，装卸，等待加工运输，控制物流成本就成为企业的首要任务。 在物流优化过程中，一个非常重要的问题是建立一个综合供应、生产和分 配计划，以在满足客户需求和能力约束下，使由库存、订货和运输所引起的总 成本最小化。批量问题是一类重要的生产采购计划问题，且一直是运筹学、 工业工程等领域研究的热点问题之一，其目标是在有限时间段内不同的生产过 程约束下计划生产采购数量，使得总成本最小化。 当前外包已成为制造业比较普遍采用的策略，尤其是对行业中的佼佼者来说外包 给企业带来了很多好处：可以有效地降低资金占有率，降低库存成本，化解投入大量 资金建造生产线所引起的高额投资风险，增强企业的灵活性和快速反应能力。本文主 要研究带外包情形的单产品批量问题。研究带外包情形的批量问题，就是为了给 企业提供科学的决策方法，辅助企业的管理者在战略战术层做出合理的决策，优化物 流系统，降低企业成本，挺高企业核心竞争能力。本文的研究将为采取外包战略的企 业的提供了科学的决策方法，对企业制定生产计划采购计划的实践具有一定的指导 意义。 萋毳本文的主要研究工作和结构安排 1 3 i 本文的主要研究工作 2 本文主要研究了带外包情形的单产品批量问题。自从1 9 13 年，美国的 h a r r is 就研究了静态需求、单件产品、无能力约束的生产批量问题，学者们采 用各种方法和技术研究解决批量问题，然而，面对许多生产实际问题，仍然需 要在理论上和应用上作进一步的扩展研究，以更好的指导实践， 本文主要用运筹学方法分析研究批量问题，本文的研究包括两个基本模 型：个是无生产能力约束时带外包情形的单产品批量模型。另一个是有生产 能力约束的带外包情形的单产品批量模型。 由于实际生活中存在大量的易变质产品，在本文中我们将讨论易变质产品 的特性，研究生产能力无约束时的批量问题的最优解的性质，在允许生产外包 的情况下，将无生产能力约束的单产品批量问题拓展为无生产能力约束的易变 质产品的单产品批量问题。 研究生产能力约束的单产品批量模型，分别在单位生产成本和单位外包成 本是常数和时变的情况下，建立数学模型，运用动态规划思想将问题分解成子 问题求解。在单位生产成本和单位外包成本是常数的情况下，提出复杂度为0 ( t n 2 ) 的动态规划算法，其中t 为计划时期数，n 为最大持有周期数。在单位 生产成本和单位外包成本是常数的情况下，先用搜索算法搜索出可行子计划， 将问题变为最短路径问题，用现有的最短路径方法求解除最优解。 1 3 2 结构安排 本文内容共分六章，具体安排如下： 第一章为绪论部分，介绍了本文的研究背景及研究意义。 第二章介绍批量问题理论，介绍了批量问题的几个基本模型，分析总结了影 响批量问题建模的主要因素。回顾有关批量问题的文献资料，研究解决批量问 题的方法和技术。 在第三章中，研究了业务外包：外包的概念及理论解释，企业采取外包战略 的动因及我国现有的业务外包的运作模式，介绍了生产外包。 在第四章中，研究了允许外包和脱销的变质性产品批量问题。我们将带外包 情形的批量问题扩展，将其应用到变质性产品的生产模型中，研究了易变质产 品的生产特点，建立数学模型并提出一种基于动态规划的精确算法，分析了算 法计算复杂性。 第五章，带外包情形的能力约束单产品批量问题。研究了有生产能力约束 的批量问题，并在此基础上，考虑允许外包的情况，分别在单位生产成本和单 位外包成本是常数和时变得情况，建立数学模型，在单位生产成本和单位外包 成本是常数的情况下，提出复杂度为0 ( t n 2 ) 的动态规划算法。在单位生产 成本和单位外包成本是时变得情况下，先用搜索算法求得可行子计划的集合， 将其变为最短路径问题，从而取得最优解。 第六章，总结与展望。对本文所作的研究工作进行总结，同时展望批量问 题的进一步发展。 4 第二章批量问题理论及解决技术方法 批量问题( 1 0 ts i z i n g ) 一直是运筹学、工业工程领域研究的热点之一。 批量问题考虑的是成批生产中中期或短期生产计划的优化问题。所谓某一产品 的生产批量，就是每通过一次生产准备生产该产品时的生产数量，它同时决定 了库存水平，因此库存理论可以认为是批量理论的一部分心1 。由于在生产过程 中存在生产调整生产准备( s e t u p ) 费用，如果每个时期都生产给定数量的产 品，就会引起很大的成本；相反，如果为了减少生产准备成本，而生产大量的 产品来满足未来几个时期的需求，又会增加库存成本。研究批量问题的目的就 是决定哪个时期生产，生产多少，以满足需求，并最小化生产、调整和库存成 本的总和。 在批量模型中，生产、库存和延期交货或外包水平可以有很多限制。成本 包括：生产成本，持有成本，延期交货或外包成本，其中生产成本又可以包含 生产准备成本和生产制造成本中。研究单一产品批量问题的目标是为满足各个 时期的需求而决定各个时期的生产或采购和或外包的数量，以及最小化整个 计划时段中生产、库存和延期交货或外包的总成本。 2 1 几类经典的批量模型 2 1 1 基本的批量模型 基本的批量问题是指单产品、不允许需求延迟且无能力约束批量问题。它 是研究多产品、允许需求延迟、能力受限或其它更加复杂批量问题的前提和基 础。基本的批量问题的建模相对简单，易于求解。许多复杂的生产批量问题， 诸如能力受限的单产品批量问题、能力受限的多产品、多层批量问题，通常可 以分解成基础的批量问题。通过求解基本批量问题得到原问题的下界，再经过 调整得到性能较好的满意解。因此，研究基本的批量问题具有重要意义。 ( 1 ) w w 模型 第一个批量问题就是由w a g n e r 和w h i t i n 口3 于1 9 5 8 年设计的，他们针对具 有线性生产和存储成本的单件产品、动态需求批量问题，提出了混合整数线性 规划模型，该模型被称之为w - w 模型，在模型中假设生产能力足够大，不需要 考虑生产能力约束。他们提出了一种计算复杂度为0 ( t 2 ) 的动态线性规划算 法。 数学模型： 7 r a i n ：( 只( 誓) + 红( ) ) t = l 服从下列约束： i t = i c - + x t d t 0 五m y , x ，l 0 i o = i t = 0 片= o ，1 ) 其中m 为足够大的正数。 生时，只= 0 。 t ：l ，t t = 1 ，2 ，t t = 1 ，2 ，t t = 1 ，2 ，t m 为二进制变量，当生产发生时”- - 1 ，生产不发 人们对w w 模型进行了很多拓展研究，设计了一些新模型。 ( 2 ) 没有库存变量的数学模型( f o r m u l a t io nw i t h o u ti n v e n t o r y v a r i a b l e s ，n i f ) 由于对于任意t ，t = 1 ，2 ，t ，有t = 一谚且o ，将约束 = 一。+ 薯一4 与之合并，则可以得到没有库存变量的数学模型 7 rrr m i n i m i z e 饥+ ( n + 瑰k 一曩4 ， f = i，= li = tt = l 服从下列约束条件： 7 = 西r t = l f 薯4 ， f = l f = 1 ，2 ，t t = 1 ，2 ，t 一1 薯名，只t = l ，2 ，t t 0f = 1 ，2 ，r 只= o ，1 ) t = 1 ，2 ，t 其中， 碣，= 谚 i = l ( 3 ) 最短路径数学模型( s h o r t e s tp a t hf o r m u l a t i o n ，s h p ) 将批量模型用有向图表达出来，每个节点都代表一个时期，其中 包含了一个虚构时期t + i 时期。任意两点t ，q 间的弧表示选择在t 时 期生产满足从t 到q l 时期的需求。从1 时期到t + i 时期的最短路径 即为批量问题的解。 e v e a n s h 3 再此基础上设计了最短路径数学模型 m i n i m i z e ( 钒+ i ) t q z t q ) t = l q = t + l 服从下列约束条件： 毛，= 1 j = i t - it + l = 乙 f = li = t + l 6 r + l z 。m i = l + l z t q 0 f = l ，2 ，t v t ，q m = o ，l t = l ，2 ，t 其中z t q 是q 时期生产产品的数量与从t 时期到q 一1 时期的累积需 求量的比值。是在t 时期生产d 。数量的产品所耗费的生产和库存成 本，其中，矗= 4 + 吃+ l + + 哝一l 。 ( 4 ) 选址数学模型( f a c i l i t yl o c a t i o n b a s e df o r m u l a t i o n ，f a l ) r7 + 1 m i n i m i z e ( 向乃+ c , i x , i ) r = i q = + l 服从下列约束条件： 7 五j = 4 i = l x q ts d t y q v t ，q 0 v t ，q 乃= o ，1 ) f = 1 ，2 ，t 其中表示在q 时期生产的用来满足t 时期的需求的产品数 量。 c q ，= p q + + “+ + 红一2 + 红一l ( q f ) 。 基于选址数学模型，w a n g l m a n s 等哺3 设计了算法复杂度为 ( o ( t l o g t ) ) 的动态规划算法。 2 1 2 允许延期交货模型 以延期交货惩罚为代价，每个时段的需求可以用未来某一个或几个时期的 生产来满足。也就是说，每个时段的需求可以用当前时期的生产，或来自上一 时期的库存，或者未来某一时期的生产来满足。 数学模型： r r a i n m i z e ( k t y t + p t x t + h l + b t j i 、) t = l 服从下列约束： i ：+ i ：= i + 、七i + x t d t 0 五m y , 只= o ，1 ) i ：，i ，x t2 0 2 1 3 允许外包批量模型 7 t ：1 ，t t = l ，t t = l ，t t = l ，t 允许生产外包的批量模型中，在所有时期里，需求无须完全由内部生产来 满足，可以由生产外包来满足。即使当前时期的库存量是大于零的，需求也可 以外包。这样的时期又被称为持有时期。如果随后时期里企业内部生产成本很 高，而当前时期外包成本相对比较小时，在当前时期选择持有库存而把用生产 外包来满足当前时期的需求，这样做可能是节省成本的。在这样的情况下，人 们喜欢持有手上的库存而外包当前时期的需求，即：持有库存中的产品来满足 随后时期的需求而不是用它来满足但前时期的需求。 数学模型如下： 三 m i n i m i z e ( 饥+ p 砗+ 鸠+ 允厶) f = l 服从下列约束条件： i t = i l + x l + l t d t 0 m y , 厶0 t 芝0 儿= o ，1 i o = = 0 f = 1 ，2 ，t f = l ，2 ，t t = 1 ，2 ，r f = 1 ，2 ，t t = 1 ，2 ，t 2 1 4 能力约束批量模型( c a p a c i t a t e dl o ts i z i n gp r o b l e m ，简称c l s p ) 带能力约束的单产品动态批量问题可如下定义哺1 ：在某一计划时间范围t 内，每个时段的需求是变化的。这些需求必须通过前一时段的生产或和库存、 或和后一时段的拖期生产、或和生产外包、部分或全部失去来满足。生产数 量、库存持有水平和拖期数量或失去需求的数量分别受它的上界和下界限制。 在能力约束批量模型中主要考虑的成本函数有：生产成本、库存持有成本拖期 生产惩罚成本和失去需求的惩罚成本，其中生产成本可能包含生产准备成本。 建立能力约束批量问题的目标就是确定在哪些时段设立生产，生产多少从而实 现生产成本、库存持有成本拖期生产惩罚成本和失去需求的惩罚成本所构成的 总成本最低。 数学模型如下： 三 m i n i m i z e ( 饥+ 见+ 鸠) ，- 1 服从下列约束条件： i t = i i + x i d t 0 c ， 0 只= o ，1 8 ，= l ，2 ，t f = 1 ，2 ，t ，= 1 ，2 ，t f = 1 ，2 ，t i o = i t = 0 2 。2 影响批量模型分类的因素 影响批量问题建模的因素有以下几类： l 计划期( p l a n n i n gh o r i z o n ) 计划期可以是无限的也可以使有限的，有限的计划期通常是动态的需求， 而无限的计划期的需求一般为恒定的系统可以被看成是连续的，也可以是离散 的时间点，所以又可以被分为连续或离散系统。 2 需求类型 需求按类型分为静态需求( s t a t i cd e m a n d ) 和动态需求( d y n a m i cd e m a n d ) ， 静态需求意味着需求值不随时间变化而变化，它是静态的，甚至也许就是一个 常数。而动态需求的需求值是随时间变化而变化的。 需求从可预见性上分为确定性需求( d e t e r m i n i s t i cd e m a n d ) 、随机性需 求( p r o b a b i l i s t i cd e m a n d ) 和不确定性需求( u n c e r t a i n l yd e m a n d ) 。如果对物 资的需求量和需求时间是己知的、确定的，则是确定性需求；如果对物资的需 求量是随机发生的，但其概率分布函数是可知的，则是随机性需求；如果对物 资的需求时间和数量都是不确定的、不可知的，则是不确定性需求，一般通过 统计分析把它近似的纳入随机性需求。 带动态需求的问题比带静态需求的问题要复杂些，同样，随机性需求的问 题比确定性需求的问题复杂。 按照需求的主从关系可以将需求分为独立需求( i n d e p e n d e n td e m a n d ) 和 非独立需求( d e p e n d e n td e m a n d ) ，独立需求是不依赖于其它需求的自主需求， 通常来自于客户订单或市场预测，独立需求中各物资的需求是不相关的。非独 立需求，对某种物资的需求由其更高层的物资需求引发和决定，可由对更高层 物资的需求导出。通常，该物资是其高层次物资的一个部件。在求得高层次物 资中该物资数量的基础上，该物资的需求量可以简单的计算出来。 3 生产阶段( s t a g e l e v e l ) 生产系统可能是单阶段( s i n g l e s t a g e l e v e l ) 也可能是多阶段的 ( m u l t i s t a g e l e v e l ) 。在单阶段生产系统中，产品通常是简单的，原料通 过类似锻造或浇铸等简单的操作直接变成最终产品，换句话说，最终产品没有 经过中间的半成品，直接由原材料或外购的材料制造而成。单阶段生产系统中 的产品需求是独立需求，直接来自客户订单或市场预测。而在多阶段生产系统 中，原材料一般要经过几道生产程序才能变成最终产品，一个阶段出来的产品 又是下一个阶段需要的材料，所以，在多阶段生产系统中，每个阶段的需求量 都是取决于其高层的需求量，其需求属于非独立需求。 9 图2 1 多阶段生产系统 如图2 - 1 所示，这是一个多阶段生产系统，产品2 是某一程序的产品又是 生产其上层产品1 的材料。它的需求量取决于其高层产品1 的需求量，所以是 非独立需求。 4 产品数量 按照产品的数量的多少，批量问题分为单产品批量问题( s i n g l e i t e ml o t s i z i n g ) 和多产品批量问题( m u l t i i t e ml o ts i z i n g ) 。 5 生产准备费用( s e tu pc o s t ) 生产准备费用是在准备生产某种产品时发生的费用，主要指每次设备由停 机到开机所发生的损失或费用及因品种更换所发生的设备调整、工装调整的损 失或费用。在模型中通常引入一个0 - i 变量来指示生产的生产准备行为。o l 变量的引入使批量模型变为混合整数规划( m i x e d in t e g e rp r o g r a m m i n g ， m i p ) 模型。将生产准备成本看成是生产成本的一部分，则生产函数变为 p u t ) = k t y i + p i x i 其中毛表示生产准备费用，这里只是引入的o 一1 变量，当t 时间段发生生 产准备行为时儿= 1 ，若t 时间没有发生生产准备行为则只= o 。 存在约束：0 置m y , v t 其中m 为生产量的上限。若只= 0 则= 0 ，若乃2 1 则0 。 6 生产能力约束 生产系统中，影响生产能力因素包括：人力、机器设备、资金预算等，当 生产能力不受这些约束时，称之为无能力约束( u n c a p a c i t a t e d ) ；反之，当 生产能力约束很明确存在时，该问题称之为能力约束( c a p a c i t a t e d ) ，能力 约束直接影响问题解得算法复杂度。 存在生产能力约束即存在约束 薯c f 其中q 表示t 时间段生产能力的上限， v f 生产能力上限c f 可以时变的也可以是恒 1 0 定，恒定时一般表示为c 。 7 库存能力约束 我们通常所说的能力约束批量问题( c a p a c i t a t e dl o ts i z i n gp r o b l e m ) 主要是指生产能力约束，而有限的库存能力约束在英文中表述为 b o u n d e d li m it e di n v e n t o r y 在数学模型中，若存在库存能力约束，一般表示为： i t s t v t 其中鼠表示t 时期库存能力的上限，库存能力上限可以是时变的或是恒定 的。 8 延期交货( b a c k l o g ) 允许延期交货，意味着需求可以被拖期生产满足，或者说允许用将来某时 段的生产来满足当前时段的需求。通常当客户接受延期交货惩罚补偿时，在目 标函数中引入延期交货惩罚成本。带延期交货惩罚成本的批量问题比不带延期 交货惩罚成本的批量问题难解。允许延期交货意味着库存量可以为负，在数学 模型中延期交货时期库存量一般表示为负值，延期交货时的库存量绝对值等于 延期交货量。若延期交货量存在上限则在数学模型中一般如下表示 0 6 f 町1 v t 或 一1 v t 其中1 为t 时期库存量下限的绝对值，也即累积延期交货量的上限，包为 t 时期累积延期交货量。 一 9 外包( o u t s o u r c i n g ) 允许生产外包意味着可以利用外部生产资源来满足部分或全部需求。生产 外包使企业生产弹性变大，适应市场环境能力增强。单位生产外包成本一般比 单位生产成本要大一点，但由于内部生产存在生产准备费用，所以当需求量很 小时可以采取生产外包，以降低总成本。在允许生产外包的模型里，外包能力 一般都被假设成无限大的，换句话说外包数量没有上界限制。 2 3 单产品批量问题解决技术及方法 有关单产品批量问题解决方法的研究主要集中在两大类：精确方法和近似 启发式方法。精确算法主要包括动态规划算法( d y n a m i cp r o g r a m m i n g ，d p ) 、 基于枚举思想的分支定界法( b r a n c ha n db o u n d ，b b ) 。 动态规划算法大约产生于1 9 世纪5 0 年代，1 9 5 1 美国数学家贝尔曼等人创 建的，贝尔曼等人根据一类多阶段决策问题，提出了最优性原理，从而创建了 解决最优化问题的一种方法一动态规划。确切的说动态规划不是一种特殊算 法，而是解决一类问题的方法，考察问题的一种途径，是把难解决的大问题分 解为较容易解的子问题的方法。动态规划的理论基础就是最优性原理，最优性 原理可如下理解，作为整个过程的最优策略具有这样的性质：即无论过去的状 态和决策如何，对前面的决策所形成的状态而言，余下的诸决策次序构成最优 策略。简而言之，一个最优策略的子策略总是最优的。 动态规划算法在解单产品批量问题中有着很重要的地位。1 9 5 8 年w a n g n e r 和w h i t i n 1 针对具有线性生产和库存成本函数的无能力约束、单产品、动态需 求产品批量问题( s in g l e i t e ml o t - s iz i n gp r o b l e m ，简称s l s p ) ，建立了数 学模型，在他们的模型中不允许延期交货，生产准备成本( s e t u pc o s t ) 恒定， w a n g n e r 和w h i t i n 设计了一个0 ( t 2 ) 动态规划方法。后来很多学者考虑条件 的变化，迅速出现了大量的以w a n g n e r - w h it i n 模型为基础的s l s p 模型和算法， 1 9 6 6 年w i l l a r di 和z a n g w i l l 阴1 推广了w a n g n e r w h i t i n 的模型，允许延期交 货，分析了分段凹库存成本函数，并提出了一个完全多项式的动态规划算法。 f l o r i a n 四1 在生产能力是恒定的情况下，设计了0 ( t 4 ) 的动态规划算法。c h u n g 和l i n 1 们研究了n i g n i n d 能力受限批量问题，设计0 ( t 2 ) 动态规划算法。 s a n d b o t h e n 卅在设置成本、单位生产成本、单位缺货成本都是常数的情况下， 针对能力约束批量模型，给出有效的动态规划算法，在假设累计生产能力大于 累计需求的情况下，当生产能力是恒定时，该算法的算法复杂度为0 ( t k 2 ) ， 当生产能力是变化的时，算法复杂度为0 ( r 2 足) ，其中k 为最大持有时间。 s a n d b o t h e n 2 3 研究生产能力和库存能力同时受限，且允许直接销售损失，设计 了有效的动态规划算法求解该问题。s h a w “3 1 在生产成本函数是分段线性情况 下，用动态规划方法在o ( 刀2 刁) 时间内解生产能力约束批量问题。w i l c ow a n d e nh e u w e l 4 1 在设置成本和生产成本是非增的情况下，研究了能力约束力批量 问题，提出了以o ( r 2 ) 的动态规划算法。2 0 0 2 年a k s e n 等人n 列研究了直接丢 失销售的无能力约束批量问题，提出了在o ( t 2 ) 时间内可解得动态规划算法。 l i u 【1 6 1 等在a k s e n 等n 引的基础上又考虑了库存限制，并提出了在o ( r 3l o g t ) 时 间内可解得动态规划算法。c h un 7 1 等分别考虑了脱销和产品外包的情况，给出 了拟多项式时间内可解得动态规划算法。c h uf e n g 等n 8 1 考虑了外包能力受限 制的情形，给出了o ( r 2l o g t ) 时间内可解得动态规划算法。z h o n g 等h 明在c h u f e n g n 刚的基础上拓展为有库存能力限制的脱销和外包混合模型并提出 o ( t 3 l o g t ) 的动态规划算法2 0 0 5 年c h u 和c h u 乜。研究了允许延期交货的带有 限库存容量的批量问题，他们假设生长成本函数是线性的且时变的，在库存成 本和延期交货惩罚成本是凹函数的情况下，提出了一个o ( r 2 ) 动态规划算法， 当库存成本函数是线性的时，算法复杂度可将为d ( r ) 。2 0 0 5 年，g u t i e r r e z 等心研究了允许缺货的有库存容量限制的批量问题，提出了伙丁3 ) 的动态规划 算法。 分支定界算法：将全部可行的解空间不断分割成越来越小的子集( 称为分 1 2 支) ，确定每个子集内的解的值得上下界( 称为定界) ，删掉那些超出己知可 行解值得那些子集，从而不断缩小搜索的范围。1 9 7 8 年b a k e r 比副假设生产成 本和库存成本均为常数，他们运用分值定界方法设计