（管理科学与工程专业论文）基于库存策略的生产计划问题的研究.pdf

，jjjljjj】-一 ad i s s e r t a t i o ni nm a n a g e m e n ts c i e n c ea n de n g i n e e r i n g r e s e a r c ho np l a n n i n gp r o b l e m w i t hd i f f e r e n ti n v e n t o r ys t r a t e g y b yz h a n g j i a n s u p e r v i s o r ：a s s o c i a t ep r o f e s s o r l i ux i a o n o r t h e a s t e r nu n i v e r s i t y j u l y2 0 0 7 i 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 = 此 思0 学位论文作者签名：z 0 。 日 期：z 矽7 7 哆 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： -hrkii- 。1 二 1 主 东北大学硕士学位论文摘要 基于库存策略的生产计划问题的研究 摘要 生产计划问题是贯穿了整个生产制造过程的重要问题，该问题是保证生产能够及 时、准确的满足需求的基础。本文主要针对石化工业来设计生产批量计划解决方案。由 于石化工业中产品对库存条件要求高、供应链体系复杂并且用户的需求多样，使得生产 计划的制定必须具有精确控制成本和快速响应的特点，因此，本文在计算精度满足工业 要求的前提下，重新模型化该问题并开发了高效率的启发式算法。 生产计划包括资源的分配，如原材料和生产能力等，合理的安排生产计划以便能够 及时地生产出满足需求的高质量产品，能力约束则是指在生产过程中资源能力约束包括 人力、设备、机器、资金等等。本文讨论的是基于库存策略的能力约束生产计划问题， 以定量分析的方法，最终目的是为生产管理提供理论和方法支持。 首先，本文总结了目前对生产批量问题研究的理论成果，在此之上，提出基于库存 策略的能力约束下的生产批量计划模型，对于外包策略的生产计划模型和清仓策略的生 产批量模型，给出了算法建立的理论依据、具体的数学模型和解决该模型的启发式算法。 其次，本文对传统的遗传算法进行改进，使之能够更好的适用于能力约束下的基于 策略的生产计划模型。对于一般的外包策略模型，设计了实数编码的遗传算法，并提出 了如交叉过程中的边界搜索、变异可行区间的判定、和解的修复过程等的针对问题的改 进；对于清仓策略模型，设计了专门解决该问题的二进制编码的遗传算法，重点介绍了 算法中将二进制编码解码为实际解的过程。 最后，本文分别设计两种库存策略的生产计划模型的数据仿真实验来证明算法的有 效性，实验表明，本文涉及的算法无论在搜索的精确性和计算的时间都能达到很好的效 果。 关键词：生产计划；遗传算法；能力约束；生产批量；外包腈仓 - i i -l- 1-j r r e s e a r c ho np l a n n i n gp r o b l e mw i t hd i f f e r e n ti n v e n t o r ys t r a t e g y a bs t r a c t p r o d u c t i o np l a n n i n gp r o b l e mi sav e r yi m p o r t a n tp r o b l e mi nt h ep r o c e s so fp r o d u c t i o n m a n a g e m e n t ，a n di ti st h ef o u n d a t i o no fm a k i n g t h ed e l i v e r ye f f i c i e n t t h i sa r t i c l ed i s c u s s e s t h es o l u t i o no fp r o d u c t i o np l a n n i n gp r o b l e mi nm o d e mp e t r o c h e m i c a li n d u s t r y i nm o d e m p e t r o c h e m i c a li n d u s t r yt h e r ea r et h r e em a i nf e a t u r e s ：a ) t h ei n v e n t o r ys t a n d a r di sh i g h ；b ) t h e s u p p l yc h a i ns t r u c t u r ei sc o m p l e x ；c ) t h ec u s t o m e r sd e m a n d sc h a n g ef i - e q u e n t l y 1 1 1 ef e a t u r e s m e n t i o n e da b o v em e a nt h a tn e wm e t h o dh a st ob ed e v e l o p e d ，a n dh e n c ew er e m o d e l e dt h i s k i n do f p r o b l e ma n dd e v e l o p e dn e we f f i c i e n th e u r i s t i ca l g o r i t h m i np r o d u c t i o np l a n n i n gp r o c e s s ，m a t e r i a l sa n dp r o d u c t i o nc a p a c i t i e sa r er e s o u r c e sw h i c h n e e dt ob ep l a n n e d i nt h i sp a p e rw ed i s c u s s e dt h ec a p a c i t a t e dp r o b l e m sw i t hd i f f e r e n t i n v e n t o r ys t r a t e g yu s i n gt h eq u a n t i t a t i v em e t h o d s ，a n dt h e f i n a lp u r p o s ei sp r o v i d i n gt h e t h e o r ya n dm e t h o df o rp r o d u c t i o ns u p p o r t f i r s t l y , w es u m m a r i z e dt h er e s e a r c ho np r o d u c t i o np l a n n i n ga n db a s e do nt h i s ，w e p r e s e n t e dm o d e l so fc a p a c i t a t e dp l a n n i n gw i t h d i f f e r e n ti n v e n t o r ys t r a t e g y f o rt h e o u t s o u r c i n gp r o b l e ma n ds t o c k o u tp r o b l e m ，w ep r o v i d ep r o b l e m s p e c i f i ch e u r i s t i ca l g o r i t h m s e c o n d l y , w ei m p r o v e dt h et r a d i t i o n a lg e n e t i ca l g o r i t h mt o m a k et h ea l g o r i t h mm o r e e 瓶c i e n ti ns o l v i n gt h ep r o b l e mc o n s i d e r e di nt h i sa r t i c l e f o rg e n e r a lc a p a c i t a t e do u t s o u r c i n g p r o b l e m ，w eu s er e a lc o d i n gs t r a t e g yt oo v e r c o m et h ec o m p l e x i t yo f t h ec o s tf u n c t i o n i nt h e p a p e rt h ec o n s o l i d a t e dp r o c e s so ft h ea l g o r i t h mi si n t r o d u c e da n dt h ei m p r o v e m e n to fs o m e o p e r a t i o n sa r ed e t a i l e d f o r s t o c k o u tp r o b l e m w ei l l u s t r a t ea ni m p o r t a n tf e a t u r eo ft h e o p t i m a ls o l u t i o na n da c c o r d i n gt o t h i sf e a t u r e ，ap r o b l e ms p e c i f i cb i n a r y - c o d e dg e n e t i c a l g o r i t h mi sd e v e l o p e d ，i nw h i c h , w ed e s i g n e da s m a r td e c o d i n gs t r a t e g y f i n a l l y , w ed e s i g n e dt h es i m u l a t i o ne x p e r i m e n t s ，i nw h i c hw eu s es t a t i s t i cm e t h o dt o t e s t i f yt h es e a r c h i n ge f f i c i e n c y ，i n c l u d i n gt h es e a r c h i n ga c c u r a c ya n d t h ec o m p u t i n gt i m e , a n d t h et e s t i n gr e s u l t ss h o wt h a tt h et w og e n e t i ca l g o r i t h m sc a ns a t i s f ya c t u a li n d u s t r yr e q u e s t s w e l la n dh a v es t r o n gp o t e n t i a l s 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 ； g e n e t i ca l g o r i t h m ；c a p a c i t a t e d ；l o t s i z i n g ； 一 o u t s o u r c i n g s t o c k o u t 公 i i i rli _- r l 东北大学硕士学位论文 目录 目录 独创性声明i 摘要。i i a b s t r a c t i i i 第l 章绪论1 1 1 研究背景。1 1 2 问题的提出l 1 3 问题的描述2 1 4 研究的目标与方法5 1 5 理论和实际意义6 1 6 本文的主要工作6 1 7 论文结构安排7 第2 章文献综述8 2 1 单产品批量问题的基本模型8 2 1 1 能力资源约束。8 2 1 2 存在库存短缺9 2 1 3 存在调整成本9 2 1 4 需求类型1o 2 2 无能力约束的单产品批量问题研究现状l o 2 3 能力约束下生产批量计划问题研究现状1 1 2 3 1 能力约束下不拖期模型l l 2 3 2 能力约束下拖期模型1 2 2 3 3 能力约束下清仓模型1 2 2 3 4 能力约束下单持有模型1 2 2 3 5 能力约束下外包模型1 3 2 3 6 不同模型的比较分析1 3 2 4 启发式求解技术1 4 2 5 存在的问题1 5 第3 章供应链下外包计划模型与算法1 7 3 1 模型建立1 7 3 2 模型求解1 8 3 2 1 算法的比较18 i v 东北大学硕士学位论文 目 录 3 2 2 遗传算法概述1 9 3 2 3 算法的设计2 0 3 3 本章小结2 9 第4 章求解外包计划问题的仿真实验3 0 4 1 仿真实验设计3 0 4 1 1 仿真环境3 0 4 1 2 仿真实验的模型参数3 0 4 2 仿真结果与分析3 0 4 3 本章小结1 ：3 3 第5 章供应链下清仓计划模型与算法3 4 5 1 模型建立3 4 5 2 模型求解3 5 5 2 1 最优解特性及分析3 5 5 2 2 遗传算法的设计3 6 5 3 本章小结4 0 第6 章求解清仓计划问题的仿真实验4 1 6 1 仿真实验设计4 1 6 1 1 仿真环境。4 l 6 1 2 仿真实验的模型参数4 1 6 2 仿真结果与分析4 l 6 3 本章小结4 4 第7 章结论与展望4 5 7 1 结论4 5 7 2 创新点。4 6 7 3 展望4 6 参考文献4 7 攻读硕士学位期间发表的学术论文5 0 参与科研项目5 1 致谢5 2 一v - 一1-j-， 东北大学硕士学位论文 第一章绪论 第1 章绪论 本章概括介绍了论文的背景和本研究的动机和目标，描述了本文的研究价值。 1 1 研究背景 现代社会再生产过程中，供应链管理作为一种新兴的管理形态，是促进国民经济发 展的基础重要环节之一，并已成为我国经济向更高层次发展和优化产业结构的重要手 段。在国际上，供应链管理的发展水平已成为衡量一个国家现代化程度和经济发展效率 的重要标志。在经济全球化的背景下，我国国内供应链管理迫切需要与国际接轨。 库存是供应链管理的一个重要环节。无论是原材料、半成品或调成品，其增加或积 压，都意味着企业运作处于一种不良的状态，都是一种直接的或潜在的损失。因而，每 个行业都视库存为畏途。 制定有效的批量计划，可以合理的安排生产，取得最大的经济效益。由于带能力约 束的批量计划问题广泛存在于工业生产的各个领域，因此，对带能力约束的批量问题进 行研究，探索有效和实用的算法，一直是国内外理论界所关注的热点研究领域之一【l j 。 1 2 问题的提出 因为石化工业在国计民生中占据重要地位，对企业资源合理优化的问题成为政府、 企业界和科技界普遍关注的问题【2 】，新的生产模式及对精益生产的要求对生产计划的研 究提出了新的要求。 第一，在石化工业中，原料的研发及生产周期直接影响到最终产成品的产出。生产 商必须对其原料供应商的供货量、供货周期和研发周期有这详细的掌握，从而降低成本， 提高自身产品的竞争力。 第二，石化工业中产品及原料的存储需要更多的成本，而且库存难以扩充。对于石 化工业中的在库原料或产品通常需要一些额外的外用来防止变质，而且由于存储于储罐 中，储罐的容积一般是不能改变的，所以库存能力约束对生产计划的限制更加严格。 第三，生产的多级化是需求量随时间的变化变得更加随机。如图1 1 所示，在各级 生产厂商的分布上来看，高级产品生产厂商的数量大于低级生产厂商的数量，呈倒三角 形分布，多个高级产品厂商对一个低级配件厂商会产生不同时段的产品需求，如果多级 生产企业，需求的产生的时段数就会增加，各时段的需求就会变化更大，需求量的多时 段性和无规律性使生产计划的制定更加困难。 东北大学硕士学位论文第一章绪论 图1 1 各级生产企业数量分布图 f i g u r e1 1t h ed i s t r i b u t i o no fm a n u f a c t u r i n ge n t e r p r i s e si nd i f f e r e n tl e v e l s 第四，个性化生产使生产计划变动更频繁。由于客户通常会对原料生产厂商提出一 些特殊的产品特性要求，所以高度的个性化意味着客户极易变化的需求使对原料的需求 更加难以预测。 以上四个问题是本文所要解决的问题，本文以石化工业为背景，通过对各种能力批 量生产采购计划问题进行研究，旨在为企业批量生产和优化采购问题的实际应用奠定理 论基础。 尽管多年以来人们采用各种方法和技术研究解决批量计划问题。然而，面对许多生 产实际问题，仍然需要在理论上和应用上作进一步的扩展研究，以更好的指导实践。 1 3 问题的描述 生产计划包括资源的分配，如原材料和生产能力等，以便生产出满足需求的高质量 产品。生产计划的目标通常是合理分配这些资源，以使生产的总成本最小化。由于一些 能力约束的存在，在生产计划中很难做出有效的决策。在生产的一系列层次中，这些决 策的制定是非常必要的【3 j ；例如，以年、月为周期的总战略计划是必要的，但制定以周， 甚至以日为周期的更详细计划也是很必要的。典型的生产计划包括：长期、中期和短期 生产计划，如图1 2 所示。 挚 长期生产计划“擎孑7 中期生产计划7 i纱 短期生产计巍 7 j 关于产品、过程、工厂 关于物料需求计划、主生产关于排序和车间层控制 设置和装备方面的决策计划和批量计划方面的决策方面的决策 图1 2 生产计划按周期分类图 f i g u r e1 2p l a n n i n gp r o b l e mw i t hd i f f e r e n tp e r i o ds p a n 从数学规划的角度来看，生产批量计划问题都可以归结为一类混合整数规划问题， 表达为在等式或不等式的约束下。 东北大学硕士学位论文 第一章绪论 早在1 9 1 3 年，h a r r i s 就提出了静态环境下的定常需求的著名经济定单公式e o q ( e c o n o m i co r d e rq u a n t i t y ，e o q ) 4 1 。19 5 8 年，w a n g e r 和w h i t i n ( w a n g e rw h i t i n ，w w ) 对这一理论进行了开创性的发展，提出了动态环境下的需求可变的动态批量计划模型【5 】。 在此基础上，人们对生产批量计划问题的研究逐渐扩展和深入，并开始考虑多产品 ( m u l t i i t e m ) 、多级产品结构( m u l t i s t a g e ) 和带能力约束( c a p a c i t a t e d ) 等更复杂的情况，从 而形成了各种各样的生产批量计划的类型。在生产批量计划的分类中，主要考虑的因素 有以下几种： ( 1 ) 需求信息的确定性程度 确定性( d e t e r m i n i s t i c ) 随机性( s t o c h a s t i c ) ( 2 ) 需求类型 静态需求( s t a t i c ) 动态需求( d y n a m i c ) ( 3 ) 计划期长度 有限时段( l i m i t e dh o r i z o n ) 无限时段( u n l i m i t e dh o r i z o n ) ( 4 ) 产品数量 单产品( s i n g l e - i t e m ) 多产品( m u l t i - i t e m ) ( 5 ) 服务策略和相关成本 允许缺货( b a c k l o ga l l o w e d ) 不允许缺货( b a c k l o gn o ta l l o w e d ) ( 6 ) 资源约束情况 带能力约束( c a p a t i t a t e d ) 无能力约束( u n c a p a t i t a t e d ) ( 7 ) 调整时间是否占用能力 考虑调整时间( s e t u pt i m e ) 忽略调整时间( n os e tu pt i m e ) ( 8 ) 生产阶段 单生产阶段( s i n g l e - s t a g e ) 多级生产阶段( m u l t i s t a g e ) 随着对带能力的批量问题的研究不断深入，人们从不同的角度和计划阶段，建立了 不同的批量模型。 c l s p c a p a c i t a t e dl o ts i z i n gp r o b l e m s 能力的批量问题 e l s p e c o n o m i cl o ts i z i n gp r o b l e m s经济批量问题 东北大学硕士学位论文 第一章绪论 d l s p d i s c r e t el o ts i z i n gp r o b l e m s 离散批量问题 c s l p c o n t i n u o u ss e t u pl o ts i z i n gp r o b l e m s连续批量问题 j s p j o bs c h e d u l i n gp r o b l e m s 作业排序问题 同时，根据产品结构的不同可以分为： 串行生产结构( s e n a l ) 组装产品结构( a s s e m b l y ) 一般产品结构( d i s a s s e m b l ya n dg e n e r a l ) 批量计划问题根据有无资源约束和产品结构的复杂程度又可以简单分为以下几种： s l u r s i n g l el e v e l ( 或s t a g e ) u n c o n s t r a i n e dr e s o u r c e s - ( 或u n c a p a c i t a t e d ) 单层无能力约束批量问题 s l c r s i n g l el e v e l ( 或s t a g e ) c o n s t r a i n e dr e s o u r c e s吨 ( 或c a p a c i t a t e d )单层带能力约束批量问题 m l u r m u l t i - l e v e l ( 或s t a g e ) u n c o n s t r a i n e dr e s o u r c e s ( 或u n c a p a c i t a t e d ) 多层无能力约束批量问题 m l c r - 一m u l t i l e v e l ( 或s t a g e ) c o n s t r a i n e dr e s o u r c e s ( 或c a p a c i t a t e d )多层带能力约束批量问题 此外，根据优化目标的不同还可以将生产批量计划问题分为： 生产总费用最小 满足一定的服务水平 本文主要讨论能力约束下的生产批量计划问题模型的算法研究，所以主要对能力约 束下的生产批量计划问题进行详细介绍。 本文的研究内容是面向炼油厂的带能力约束的单产品批量计划问题。 首先，我们将面向炼油厂的带能力批量计划问题简要描述如下： 图1 3 炼油生产过程 f i g u r e1 3r e f i n e r yp r o d u c t i o np r o c e s s e s 4 东北大学硕士学位论文 第一章绪论 我们考虑了一个炼油厂的带能力约束的单产品批量生产计划问题。典型的炼油生产 过程由三个处理单元组成：一套蒸馏设备和两套加氢处理设备，其生产过程示意图如图 1 3 所示。某种原油首先经过蒸馏装置c d u ( c r u d eo i ld i s t i l l a t i o nu n i t ) 把原油转化为 沥青、石脑油和蒸馏物，再经过加氢处理设备l t ( l i g h th y d r o t r e a t m e n t ) 和h t ( h e a v y h y d r o t r e a t m e n t ) ，将进一步把馏分转化为特殊组分的油。 由于生产过程在某一时段只加工一种原油产品，且受到设备能力约束，我们把该问 题归结为带能力约束的单产品批量问题，或者全部生产过程可以按单产品生产过程来考 虑。在炼油厂的生产批量计划中，由于调整成本和库存持有成本需要占用大量的资金， 同时，批量计划受生产能力和罐存( 库存) 能力的双层制约。所以，充分考虑炼油厂生 产的这一特点，合理安排生产批量是本项研究的关键问题所在。 另外，传统的模型和算法主要考虑如何满足需求的情况。然而，对现实生产中经常 出现的不完全满足的情况，文献中却很少考虑。例如，当市场需求大于能力时，要求决 策者首先确定满足哪些需求，或者说确定生产多少，失去多少以及在哪里失去，以实现 利益最大化；另一方面，即使需求小于能力，如果满足需求会增加大量的调整成本和库 存持有成本。为了降低成本，我们考虑拖期生产或失去全部或部分需求以实现利益最大 化。因此，为了增强竞争能力，有效的制定批量优化生产计划，最小化总成本，是炼油 厂批量生产计划中的关键问题。 本书所研究的另一类问题是基于分布式供应链环境下的多产品、多炼油厂、多原油 供应商的原油采购计划问题。问题产生的背景是中石化集团公司下属的各炼油厂将他们 的原油采购任务外包给国家原油采购中心进行统畴安排。本书的研究正是以采购中心的 角度分析如何在这种分布式供应链环境下建立优化采购的数学模型，以实现成本和供应 链的循环时间最小化。同时能够合理选择供应商，优化资源配置，满足各炼油厂对原油 质量和交货期的要求。 1 4 研究的目标与方法 本文研究基于对各种策略下的供需链计划模型提供有效的算法，旨在为企业的经营 业务过程分析与企业经营模式提供智能化的模型分析方法，以促进企业实现从经验型管 理向智能型管理的转变、从定性表达向定量描述的转变，使敏捷、精确地制定生产计划 成为可能。 本文试图通过中所讨论的方法，来有效的解决扩展后的带能力约束的单产品批量生 产采购计划问题的模型。所提供的遗传算法在针对特定问题进行改进后，不仅能构满足 约束，并且能使最优解的精确程度和计算效率有大幅的提高。 对一类通用的带各种能力约束的单产品批量问题的生产采购计划问题进行有效求 解。包括允许不允许拖期和不完全满足情况。 对于一类生产能力大于库存能力的情况时，以库存能力取代生产能力的特殊情况下 的单产品批量问题的生产采购计划问题进行有效求解。两种模型和算法，不同于传统的 5 东北大学硕士学位论文 第一章绪论 是：所提出的模型与算法不但要考虑哪些需求应当满足，同时要考虑失去哪些需求以最 小化成本。这类问题的模型和决策可以在企业的外包决策中有潜在的应用价值。例如， 当市场的需求大于企业的能力时，企业的批量决策问题要考虑在哪里生产、失去，同时 要决策生产、失去多少，以取得最大的经济效益；另一方面，当企业的能力大于市场的 需求，传统的模型中，全部满足需求的情况可能会导致过高的调整费用或库存持有费用。 所以，考虑失去某时段的全部或部分需求，以取得最大的经济效益。 本文采用启发式算法对模型进行近似求解，以满足实际生产中对计算时间的要求。 1 5 理论和实际意义 带能力约束的单产品批量问题广泛存在于各类工业中，如化学工业、玻璃、钢铁、 造纸和食品工业等生产实际中。对该问题的有效求解，可以降低产品成本，提高效益， 是企业增强竞争力的一个重要手段。 同时，由于多产品问题可以看成多个独立的子问题，常常可将其考虑为求解单产品 问题。由于单产品算法还经常作为求解其它复杂问题的子算法，所以，对单产品的模型 及其算法复杂度的研究有重要的理论意义。 对一般情况下的带能力约束的单产品批量问题的有效求解，可以考虑应用到其它特 殊情况的问题中去。相反，对一类特殊情况的问题的好的算法，可以对具有普遍意义的 问题的求解给予借鉴和启迪。 在算法的改进方面目前遗传算法已经普遍应用在各个领域，但是，对于解决带约束 问题的遗传算法仍一直是学术界讨论的热点，也是难点。对能力约束的生产批量问题， 目前的研究在处理约束上大多采用了复杂的修复策略，大大增加了问题的复杂程度，这 已经不能够满足现代工业决策支持系统中对算法及时性的需要。 启发式算法的研究的最根本意义就是通过研究问题本身的规律来进一步通过忽略 大量的比较差的可行解来寻找较优解，其虽然牺牲了一定的准确性，但却更大程度上的 提高了算法的运行效率。本文的研究内容，提出了一种新的基于边界搜索的解决能力约 束问题的一个新思路，目的是进一步提高算法的准确性和计算速度；还提出了解需要尽 快出货的清仓问题的二进制解码方案。可以说，本文不仅是提供了一个能力约束的生产 计划问题的有效算法，同时也是一种新型的遗传算法在具体问题上的实现。 本文所建模型建立源于具体的工业制造和商业采购实例，其在工业及商业计划中有 很好的指导意义。同时，本文所涉及的遗传算法同样可以应用于其他运输、调度等普通 离散编码的遗传算法所不能解决的运筹学问题。 1 6 本文的主要工作 本论文的主要工作如下： ( 1 ) 本文分析了石化工业中的生产流程，对石化工业生产管理的库存管理模块进行 了分析，提炼出了能力约束下的生产计划问题。 6 东北大学硕士学位论文 第一章绪论 ( 2 ) 本文总结了目前对生产计划问题研究的理论成果，在传统生产批量模型的基础 上，增加了库存策略因素，提出基于库存策略的能力约束下的生产批量计划模型。 ( 3 ) 本文构建了基于外包策略的能力约束生产计划数学模型，并将该模型扩展为成 本函数任意的一般性问题。针对该问题，本文设计了实数编码的遗传算法，并且在算法 的各个环节都进行了改进，在初始解的生成过程采用了判断机制，在交叉过程中采用了 边界搜索策略和特定的修复策略，在变异过程中采用了可行域内的变异策略。 ( 4 ) 本文还构建了基于清仓策略的能力约束生产计划数学模型，并从理论上分析了 该问题最优解所具有的特点，针对该特点设计了专门解决该问题的二进制编码的遗传算 法，重点介绍了算法中将二进制编码解码为实际解的过程。 ( 3 ) 本文针对两种库存策略的生产计划模型分别设计的数据仿真实验来证明算法的 有效性，在本文中，列举了大量的图表来证明算法的精确度和执行效率。 1 7 论文结构安排 本文的后续章节内容安排如下： 第二章对与本文所作研究所要用到的参考文献进行综述，给出了国内外对批量问 题，生产采购策略问题的研究现状，分类介绍目前热点的能力约束下的不拖期、拖期、 持有和外包问题。然后对遗传算法的研究进展进行综述，进一步阐明本文的理论意义。 第三章和第四章，详细介绍了外包批量计划问题，并给出了相应的数学模型与算法， 理论上分析了问题的特点和求解的关键，然后给出详细的算法，并进行仿真实验，系统 的评价算法的有效性。 第五章和第六章，详细介绍了清仓批量计划问题，并给出了相应的数学模型与算法， 理论上分析了问题的特点和求解的关键，然后给出详细的算法，并进行仿真实验，系统 的评价算法的有效性。 第七章进行结论与展望，总结本文的结论与创新点，同时也交代了本文研究进一步 需要做的工作和相关研究的发展方向。 东北大学硕士学位论文 第2 章文献综述 第2 章文献综述 本章主要介绍了有生产批量计划问题( s i n g l ei t e mc a p a c i t a t e dl o ts i z i n gp r o b l e m ， s i c l s p ) ，以及所采用的相关算法的研究状况；第2 2 节介绍了单产品批量计划问题的 基本模型现状；第2 3 节总结了求解单产品批量优化问题的各种精确求解方法，主要阐 述了目前几种算法的复杂度；第2 4 节介绍了启发式算法，主要是遗传算法在计划批量 问题中的应用；最后，第2 5 节提出现有方法所存在的问题，这也是本研究具体要解决 的问题。 2 1 单产品批量问题的基本模型 批量问题的计算复杂度取决于模型中所考虑的特征因素。如：产品数量、能力约束 及其性质( 恒定的或变化的) 、生产周期的长度，等等。以下几个主要特征影响单产品批 量问题的分类、建模及其计算复杂度。 带有限生产能力约束的单产品批量问题的数学模型可以描述如下： 三 m i n i m i z e ( p ，x ，+ h l i ，) ( 2 1 ) f = l s t i ，= i “+ 五一d ， v t = l ，t( 2 2 ) t 0 和置0 ( 2 3 ) 其中，h ，表示从一个计划期到下一个计划期的单位库存占用成本，p ，表示单位生产 成本，d ，表示在时段t 末的需求。 决策变量置表示在时段t 内的生产数量，状态变量表示在时段t 末的产品库存量。 目标是使生产成本和库存成本之和最小。 下面分别介绍影响批量问题建模及算法的四个主要特征 2 1 1 能力资源约束 在生产过程中资源能力约束包括人力、机械设备、机器、资金预算，等等。当批量 计划问题不受这些资源约束的时候，本文称该问题为无能力约束问题。反之，当问题受 到资源约束的时候，本文称该问题为有能力约束问题。由于能力约束直接影响问题的复 杂度，当存在能力约束的时候，对问题的解决将变得更难。 一般来说，文献中提到的能力约束主要是指生产能力约束和库存能力约束两类。通 常所说的带能力约束的批量计划，主要是指生产能力( c a p a c i t a t e d ) 。另一种情况是批量 计划问题受到有限的库存能力约束，本文通常称该问题为有限的库存能力约束模型 ( b o u n d e d l i m i t e di n v e n t o r y ) 。尽管这两种问题是相关联的，但在最优解特性方面存在很 大区别。 模型中所包含的能力约束表述如下： 一8 - 东北大学硕士学位论丈 第2 章文献综述 x 。c (24)t v t 一l + 置c ： v t ( 2 5 ) 这里，c t 表示某一时段t 内的生产能力，c f 表示某一时段t 内的库存能力。 2 1 2 存在库存短缺 库存短缺( b a c k l o g ) 是另一种影响建模和求解问题复杂性的特征。如果允许库存短 缺，即意味着在将来某时段生产满足目前时段的需求是允许的，或者需求被拖期生产满 足是允许的。这里，通常在目标函数中引入库存短缺惩罚成本。带有库存短缺成本的问 题比没有库存短缺成本的问题更难解决。 如果在生产中允许拖期现象存在，则问题变为如下形式： 7 m i n i m i z e ( p ，x t + 吃r + j i l f r ) ( 2 6 ) t = l s t r 0 ，f o 和x t 0 v t = 1 ，t ( 2 7 ) 和能力约束( 2 2 ) ，( 2 4 ) 和( 2 5 ) 。 其中，参数j l l f 表示从一个计划期到下一个计划期由于拖期而引起的单位惩罚成本。 r 和f 分别表示某一时段末的库存持有数量和拖期数量。当1 1 0 时，= ，? ；否则， i t = 一f 。目标是最小化整个时段的生产成本，库存持有成本和拖期惩罚成本之和。 2 1 3 存在调整成本 调整成本( s e t u pc o s t ) 是指在某时段设立生产某产品所发生的费用。由于采取通过在 某一时段生产一定数量的产品来满足后边时段的需求，同时支付一些库存持有成本的方 法进行生产，其结果可能比在每个时段都生产产品所导致的成本要小，因而本文的目 标是在引进调整成本后，使总调整成本、生产成本和库存占用成本最小。 如果存在调整成本，则目标函数变为： 7 m i n i m i z e z ( k ，1 3 r ，( x ，) + p , x ，+ j j l ，f + ，一f ) ( 2 8 ) f = i 其中，k ，表示调整成本，这里，引入二进制变量q ( 置) 是必要的。如果生产的调整行 为发生在时段t ，那么盯，( x t ) = l ：否则，o r ，( 置) = 0 。也就是说，在某时段，如果q ( x t ) = o ， 那么x ，= 0 ；相反，如果q ( 五) = l ，那么x t 0 。 置m ，q ( 置) v f ( 2 9 ) 其中m ，是置的上限 到目前为止，问题由线性规划( l i n e a rp r o g r a m m i n g ，l p ) 模型已经转变为混合整数 规划( m i x e di n t e g e rp r o g r a m m i n g ，m i p ) 模型。 东北大学硕士学位论文第2 章文献综述 2 1 4 需求类型 本文考虑以下几种需求( d e m a n d ) 类型：静态需求和动态需求。静态需求意味着 随着时间的变化，需求值保持不变，或者说需求值是恒定的或是常数；而动态需求是指 随着时间的变化，其需求值发生改变。如果需求值是预先知道的( 包括静态需求和动态 需求) ，它就属于在时间上是确定的；但是，若需求值不是能预先准确知道的，而是基 于一些概率预测的，它就属于在时间上是不确定的或随机的。带有动态和或独立需求的 问题比带有静态和或独立需求的问题更复杂；同样地，带有非确定性需求的问题比带有 确定性需求的问题更复杂。 本文所研究的问题是属于多时段带有动态需求、带能力约束、单产品批量计划问题。 下面，本文将对单产品批量问题的解决技术及方法做一些简要回顾。 2 2 无能力约束的单产品批量问题研究现状 1 9 1 3 年美国的电气工程师h a r r i s 最先提出了一种库存管理模型，也就是著名的经济 定单批量e o q 模型1 4 j 。在早期的论文中，著名的e o q 公式被称为平方根公式。由于该 公式在1 9 3 4 年被w i l s o n 用于实践中，所以它又被称为w i l s o n 批量公式【6 】。目前，该公 式仍然广泛应用于许多库存控制的计算机软件包中。 e o q 模型假定了一个无限的计划范围丁，恒定速率的连续需求d ，无限的生产率， 并且不存在拖期现象。e o q 模型中的生产和储存成本函数不随时间变化，它们分别表 示为c ( q ) = p 8 (