（运筹学与控制论专业论文）供应链环境下批量生产计划问题的研究.pdf

鞍山科技大学硕士论文 摘 要 摘要 供应链环境下的批量生产计划问题是批量生产企业在管理和决策中 不可回避却又十分棘手的问题。可以浼，批量生产企业组织决策的成败在 一定程度上取决于对批量生产计划问题的认识。本文将以市场需求为一条 主线，运用运筹学、概率统计、模糊规划及智能算法等技术，对供应链环 境下的批量生产计划问题展开研究。 研究的内容主要包括以下几个方面： 1 在查阅大量文献的基础上综述了供应链环境下批量生产计划问题 的研究现状及存在的问题。 2 设计了基于经济批量与交货期问题( e l d s p ) 的遗传算法。通过仿真 实验表明该遗传算法有效的改进了以往解决e l d s p 的启发式算法易陷入 局部最优和多项式算法运行时问过长的缺点，能在较短的时间内得到问题 的最优解。 3 研究了供应链环境下基于模糊需求下的批量生产计划问题，建立了 基于降低牛鞭效应影响的使单位时间总成本最小的模糊规划模型，并将其 转化为模糊机会约束规划模型，用清晰等价类对其进行清晰化处理，最后 将模糊模拟技术引入遗传算法对模型进行求解。仿真实例表明了该算法的 有效性。 4 针对由单个制造商、单一产品和多个客户构成的供应链系统，分别 建立了集中控制下客户整体期望利润最大化模型和分散控制下系统期望 利润最大化模型，并设计了遗传算法和分枝定界法对后者进行求解。通过 实例仿真，验证了这两种算法的有效性。 关键词：供应链，批量，不确定，模糊模拟，遗传算法，分枝定界法 鞍山科技大学硕士论文 a b s t r a c l a b s t r a c t t h el o ts i z i n gp r o d u c t i o np l a n n i n gi ns u p p l yc h a i nm a n a g e m e n ti sa h a r db u tt oc r a c k e dt h a tc a nn o tb eo b v i a t e df o rb a t c hp r o d u c t i o ne n t e r p r i s e s s u c c e s so rn o ti s d e p e n d e n to nt h ek n o w l e d g eo ft h el o ts i z i n gf o rac e r t a i n e x t e n t r e s e a r c ho ns u p p l yc h a i nm a n a g e m e n ti sc a r r i e dw i t ht h em a r k e t s d e m a n da sc l u e t e c h n o l o g i e sa so p e r a t i o n a lr e s e a r c h ，p r o b a b i l i t ys t a t i s t i c s ， f u z z yp r o g r a m m i n ga n di n t e l l e c ta l g o r i t h ma r ea p p l i e di nt h i sd i s s e r t a t i o n t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es h o w na sf o l l o w s ： 1 b yr e a d i n ga n dc o l l e c t i n gal o to fm a t e r i a l sa n dl i t e r a t u r e s ，t h ea u t h o rf i n d so u t a n dc o n c l u d e st h ee x i s t i n gr e s e a r c hc o n d i t i o n ，p r o b l e m so ft h el o ts i z i n gp r o d u c t i o n p l a n n i n gi ns u p p l yc h a i n 2 d e v i s eag e n e t i ca l g o r i t h mt os o l v et h ee c o n o m i cl o ta n dd e l i v e r y s c h e d u l i n gp r o b l e m - e l d s p ，a n dc o m p a r e d w i t hh e u r i s t i c a l g o r i t h m a n d p o l y n o m i a lt i m ea l g o r i t h m n u m e r i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t e t h e g e n e t i ca l g o r i t h me f f i c i e n t 3 t h el o ts i z i n gp r o d u c t i o np l a n n i n gi ns u p p l yc h a i np r o b l e mw i t hf u z z y d e m a n di ss t u d i e di nt h ep a p e r t h ei n f l u e n c eo fb u l l w h i pe f f e c ta n dt h ea v e r a g e c o s tp e rt i m eu n i ti sm i n i m i z e da r ec o n s i d e r e di nt h em o d e la n dt r a n s l a t ei n t o f u z z yc h a n c ec o n s t r a i n sp r o g r a m m i n gm o d e l a tl a s t ，a no p t i m a la l g o r i t h m a n dg e n e t i ca l g o r i t h mb a s e di nt h ef u z z ys i m u l a t i o n t h es i m u l a t i o ne x a m p l e s i n d i c a t ef s g a sv a l i d i t y 4 m o d e l sw i t ht h eo p t i m a lp o l i c yf o rt h es y s t e ma saw h o l eu n d e rc e n t r a l c o n t r o la n dd e c e n t r a l i z e dc o n t r o la r ep r o p o s e d f u r t h e r m o r e ，d e v i s eag e n e t i c a l g o r i t h ma n dab r a n c h - a n d - - b o u n da l g o r i t h m t os o l v et h em o d e lu n d e r d e c e n t r a l i z e dc o n t r 0 1 n u m e r i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t et h et w o a l g o r i t h m se f f i e i e n t k e y w o r d s ：s u p p l yc h a i n ，l o ts i z i n g ，u n c e r t a i n l y ，f u z z ys i m u l a t i o n ，g e n e t i c a l g o r i t h ，b r a n c h a n d - b o u n da l g o r i t h m 鞍山科技大学硕士论文 第一章绪论 第一章绪论 1 1 供应链环境下批量生产计划问题简介 1 1 1 供应链简介 进入2 0 世纪9 0 年代以来，世界政治、经济和社会环境发生了巨大变化。 同时，顾客的消费水平不断提高，需求闩益多样化，社会需求的不确定性 大大加强了。“纵向一体化”的战略模式逐渐显示出其无法敏捷地响应市 场需求的弱点。尽管企业采取了许多先进的单项制造技术和管理方法，但 都无法摆脱困境。人们认识到，任何一个企业都不可能在所有业务上成为 最杰出的企业，只有优势互补，才1 能共同增强竞争实力。许多国际上的先 驱企业开始在世界范围内寻求合作，与供应商和销售商建立合作伙伴关 系，结成联盟，共享风险和利润。这样，企业的管理模式就由“纵向一体 化”模式转变为“横向一体化”的战略模式。 “横向一体化”就是在产品的整个生产过程中，核心企业从设计、制 造直至销售，都是在全球范围内选择最优秀的企业，形成了一个利益共同 体，构成了一条从供应商、制造商、分销商、零售商直到最终顾客的物流、 信息流和资金流的网络，由供需关系连接在一起的这些企业所组成的网 络，被称为“供应链”( s u p p l y c h a i n ) ”。 目前，供应链尚未形成统一的定义，许多学者从不同的角度出发给出 了许多不同的定义。s t e v e n so ”认为：“通过增值过程和分销渠道控制从供 应商的供应商到用户的用户的流就是供应链，它丌始于供应链的源点，结 束于消费者的终点”。e v e n s 认为：“供应链管理是通过前馈的信息流和 反馈的物料流及信息流，将供应商、制造商、分销商、零售商，直到最终 用户连成一个整体的的模式”。这些定义都注意了供应链的完整性，考虑 了供应链中所有成员操作的一致性( 链中成员的关系) 。最近几年，供应链 的概念更加注重围绕核心企业的网链关系，如核心企业与供应商、供应商 的供应商乃至与一切前向的关系，与用户、用户的用户及一切后向关系。 h a r r i s o n 将供应链定义为：“供应链是执行采购原材料、将它们转换为中问 产品和成品、并且将成品销售到用户的功能网链”。这些概念同时强调供 应链的战略伙伴关系问题。从功能网链关系的角度，马士华教授等给出一 个供应链的定义：供应链是围绕核心企业，通过对信息流、物流、资金流 鞍山科技大学硕士论文 第一章绪论 的控制，从采购原材料开始，制成中间产品以及最终产品，最后由销售网 络把产品送到消费者手中的将供应商、制造商、分销商、零售商、直到最 终用户连成一个整体的功能网链结构模式”1 。 供应链是由不同的经济实体组成，各自有不同的优化目标和私有信 息，这些优化目标往往与系统整体优化目标相冲突。同时，供应链中存在 许多不确定因素，例如：客户可能会中途改变或取消订单、材料或零部件 不能准时到达、生产过程中设备突然发生故障等等，使得供应链系统具有 很强的动态特性。因此，为了使信息流、资金流和物流在供应链成员企业 之问和企业内部顺畅地流动，从而达到降低成本，缩短交货期，提高顾客 满意度，改善供应链绩效的目标，有效的供应链管理必须协调供应链各个 成员企业之问和企业内部的各项行为和活动，使供应链作为一个整体来运 行。 1 1 2 生产计划在供应链管理系统中的作用与地位 供应链管理主要涉及到四个主要领域：供应、生产计划、物流、需求。 由图卜l 可见，供应链管理是以同步化、集成化生产计划为指导，以各种 技术为支持，尤其以i n t e r n e t i n t r a n e t 为依托，围绕供应、生产作业、物流( 主 要指制造过程) 、满足需求来实施的。供应链管理的目标在于提高用户服 务水平和降低总的交易成本，并且寻求两个目标之问的平衡( 这两个目标 往往有冲突) ”，。 至匠 图1 1 ：供应链管理涉及的领域 鞍山科技大学硕士论文 第一章绪 论 从图中我们看到，生产计划是统一供应链管理活动的神经中枢，成为 企业部门之问、企业之间的联系纽带。对于以产品制造企业为核心的供应 链来说，生产计划在供应链管理中起主导作用，这种主导作用体现在三个 方面：( 一) 生产计划是供应链的信息转化器，通过生产计划，供应链各 节点企业的信息都通过生产计划进行加工转换，把需求信息转化为供应信 息；( 二) 生产计划是供应与需求的调节器，通过生产控制，有效地调节 需求与供应的关系；( 三) 生产计划是供应链的资源调配器，通过生产计 划，向各供应商发出物料需求指令，向分销商发出供货指令。 供应链管理的首要目标是要提高对顾客的服务柔性，及时地满足顾客 的需要。要提高整条供应链的效率，必须在正确的时间将正确数量的产品 送到正确的地点，既不能交货延误或交货不完全，也不能提前交货。交货 延误或交货不完全会导致输入资源短缺，并扰乱运作系统的顺利运行。当 供应不确定时，系统可能就必须保持一定的库存以补偿它对供应的信心缺 乏。当供应和( 或) 需求不确定时，安全库存就会出现。同样，过早到达的 物料有时也不能得到有效的存储，从而降低物料的使用效率。这就要求供x 应链保持很高的柔性。 由此可见，企业的经营活动是受顾客需求驱动的、以生产计划为中心+ 而展丌的，供应链管理思想对企业管理的最大影响是对现行生产讨划模式? 的挑战。只有通过建立面向供应链管理的生产计划，企业才能真正从传统、 的管理模式转向供应链管理模式，进而提高对顾客的服务柔性，提高整条 供应链的效率。 1 1 3 供应链中的批量生产计划问题 批量生产计划问题是批量生产企业管理中一个常见的问题，其主要目 标是确定最优的生产批量，使得生产费用、生产准备费用和库存费用综合 指标最小或利润最大。 批量生产企业的生产任务具有批次多、批量大、不确定性大等特点。 车间生产过程中容易出现资源瓶颈，例如发生设备使用冲突等情况。因此， 车间编制生产计划时必须对生产资源加以重点考虑，尽量避免产生资源的 冲突，避免造成资源不足，从而提高计划可行性。对生产过程中的关键设 备，车问更要做到计划使用合理、设备利用充分的目标。同时，批量生产 企业车问接收的生产任务类型复杂：生产任务中包含的零件有重要零件和 非重要零件。企业在编排车间计划时，对不同种类的零件需要采用不同的 鞍山科技大学硕士论文 第一章绪论 优先级别加以生产。为了实现上述的目标，一般的解决思路是同时对设备、 零件性质等诸多因素进行多目标优化。但这往往会导致模型过于复杂、计 算量大，系统难以实现。 针对上述情况，本文详细地分析了批量生产企业编制车问生产计划需 要考虑的问题，采用组合优先级方法，计算每项任务的加工先后次序，解 决批量生产企业车间编制计划面临的问题。此外本文还研究了随机需求 下，通过协调生产企业的生产批量和客户的订货批量来实现系统整体期望 利润最大化的问题。 1 。2 供应链环境下批量生产计划问题的研究现状 1 2 1 确定性需求下的批量生产计划问题 i 经济批量问题 经济批量问题( e l s p - - e c o n o m i cl o t s i z i n ga n ds c h e d u l i n gp r o b l e m ) 是 确定性需求下的批量生产计划问题的典型问题，对此问题的研究已经有几 十年的历史了。当需要在一定生产设备上生产多种产品，且产品的外部需 求比较稳定，计划期较长时，可以认为满足e l s p 的条件。从不同批量模 型的比较中可以看出”3 ，e l s p 可以看作与单层能力受限的批量问题( c l s p | s l c r - - c a p a c i t a t e dl o t s i z i n ga n ds c h e d u l i n gp r o b l e mis i n g l el e v e lw i t h c o n s t r a i n e dr e s o u r c e s ) 所讨论的情形类似，但后者的时间是连续无穷长的 且需求定常。因此，普通的e l s p 考虑的是在单台设备上生产多个产品的 问题，且对于每个产品，需求率和生产率是给定的常数，库存费用f 比于 库存量和库存时帕j ( 边际库存费用是给定的常数) ，不允许缺货。e l s p 的 目标是确定生产批量，使总生产费用( 只考虑生产策划和库存成本) 最小。 文献 6 ，7 给出了单机e l s p 较完整的综述。由于其考虑的是无限长的计划 期，因此一般假定每种产品都按照固定周期生产，这不仅可以使问题的研 究简化，生产实际中也更易于组织和管理。这时，产品i 的生产周期就是 e l s p 的决策变量。 i i 单机经济批量问题的模型体系 ( 1 ) 独立解模型( i s i n d e p e n d e n ts o l u t i o n ) ；在保证有足够的生产策划 时问的前提下，对每种产品i 分别考虑得到的解称为独立解。该解是e l s p 的一个下界，不1 定是可行解，但若是可行解，就一定是最优解。 ( 2 ) 公共周期模型( c c c o m m o nc y c l e ) ；在保证有足够的生产策划时间 鞍山科技大学硕士论文第一章绪 论 的前提下，假定所有的产品有公共周期并能得到e l s p 的可行解。此方法 的优点在于简单、可行，且容易增加其它额外的约束条件”。 ( 3 ) 基本时段法模型( b p b a s i cp e r i o d ) ：假定所有产品i 的生产周期都 是某个基本时段的f 整数倍，同时为保证可行性，该方法要求每个时段可 以容纳每种产品至少生产一次。由于此方法计算量很大，没有多大的实用 价值。 ( 4 ) 扩展的基本时段法模型( e b p e x t e n d e db a s i cp e r i o d ) ；e b p 方法对 b p 法的约束条件进行了放宽，不再要求每个时段能容纳所有产品的生产， 而是在多个时段考虑可行性条件”“。 ( 5 ) 非周期法模型( n c y 一一n o n c y c l i c ) ；n c y 方法的思想是：在一 个相当长的运行时段内，产品i 可以有不相等的生产周期，从而每次生产 可以有不相等的生产批量”3 。 ( 6 ) 生产准备与生产排序相关的e l s p ( s d s 一一s e q u e n c e d e p e n d e n t s e t u p ) ；上述五种模型都假定产品的生产策划时间( 或成本) 独立于生产产 品序列。而s d s 考虑到实际生产中生产策划时间( 或成本) 与排序有关，可 以先求解旅行商问题，确定生产顺序，然后按照这个固定的生产顺序及相 关的生产策划时问( 或成本) 进行求解“。 1 2 2 不确定需求下的批量生产计划问题 生产批量计划问题是产品制造商经常要而临的一个至关重要的决策 性问题。要确定生产多少产品最合适就必须预测市场需求。然而，市场需 求往往是不确定的。科学技术的发展和生活质量水平的提高更增加了需求 不确定的程度。常用的研究不确定性问题的方法有4 种：随机理论、区问 分析、模糊集理论和转化为确定性问题求解”。其中区间分析是用一个相 对确定的区间去描述参数的不确定性，大都用于工程机械零件大小的确定 等方而；把不确定性问题转化为确定性问题求解虽然可以大大简化处理过 程，但结果与实际值往往存在较大偏差，且解的形式也不符合人们的习惯 表达。本文考虑了模糊不确定下企业的批量生产计划问题和随机需求下的 系统批量生产协调问题。 i 模糊需求下的批量生产计划问题 随着模糊技术的发展，应用模糊数来表示和处理不确定性问题获得了 广泛的关注，并显示出了其他方法无可比拟的优越性和应用前景。2 0 世纪 9 0 年代以来，许多专家学者开始研究和开发模糊条件下的生产库存模型， 鞍山科技大学硕士论文 如：t j c r o y & m m a i t i “”开发了具有不定存储容量的模糊经济订货模型； h m l e e & j s y a o “”和s c c h a n g “”初步研究了需求不确定条件下如何确定 生产量的问题，他们都是直接把决策变量处理成模糊数，而且都是考虑的 允许缺货时的情况；c h i a n gk a o w e n k a ih s u ”o “1 也先后研究了具有不 确定需求的单周期定货存储模型和可重复批量订货模型，在考虑订购成 本、缺货成本和残值情况下得出最佳订货批量。 本文第三章主要考虑了供应链环境下基于模糊需求的批量生产计划， 并应用模糊规划技术来解决问题。关于模糊规划技术，国内外许多学者都 对其做了研究。b o u c h o nm e u n i e r 等“”总结了多种的极大化建立在模糊集上 的数值函数的方法。b u c k l e y & h a y a s h i “”通过选择一个最优的模糊集去极 大化一个实值函数，为此设计了模糊遗传算法，并应用到模糊优化问题、 模糊极大流问题、模糊回归以及模糊控制等领域。更一般地，l i u & 1 w a m u r a “”提供了带有模糊决策的机会约束规划的理论框架，此外l i u ”建立了 带有模糊决策的相关机会规划等一系列模型，并为求解这些模糊模型设计 了基于模糊模拟的遗传算法。赵晓煜、汪定伟”73 提出了供应链中二级分销 网络优化设计的模糊机会约束规划模型，模型中将各个需求地对产品的需 求量以及各分厂的生产能力等难于确定的参数看成是模糊参数，并进一步 讨论了如何将模型中的机会约束清晰化。张立红、任建芳、赵瑞清”针对 实际问题中决策变量通常是模糊的情况，讨论具块角结构的含有模糊决策 的线性分式多目标规划模型。使用a 一水平集，建立了对应的a 一多目标规 划模型。并为解决这类问题，设计了基于模糊模拟的遗传算法。张虹，李 歧强”通过对现有生产调度模糊模型的分析，针对间歇生产过程，提出了 一科t 新颖的参数模糊的通用模糊规划建模方法，模糊模型采用两种基于普 通遗传算法的模糊算法，即模糊模拟和s f a 算法。在该方法中，参数隶属函 数选取灵活，采用合适的模糊表示方式，最后通过实例验证了该模糊建模 方法的有效性。潘永湘，徐前锋，侯志林。“”针对模糊模拟在模糊优化问题中 存在的计算量大、易收敛到次优解等缺点，将实数遗传算法与模糊模拟相 结合，提出一种基于模糊模拟实数遗传算法的优化算法。该算法充分利用 了实数遗传算法的全局搜索能力和鲁棒性强等优点，从而能较快地得到最 优解或准最优解。陈相东o 采用基于模糊模拟的遗传算法进行求解了在 模糊条件下使一个清晰目标函数达到极大或极小和在模糊条件下使一个 模糊事件的可能性达到极大这两个问题。熊红云、杨秀芳、何钺。”1 引入模 糊技术，建立具有模糊能力约束的生产批量计划模型( f c l s p ) 结合遗传算 鞍山科技大学硕士论文第一章绪论 法和参数线性规划方法提出解f c l s p 的混合算法。 1 i 随机需求下的批量生产协调问题 供应链环境下企业制定生产计划必须从供应链整体出发，在考虑自身 利益的同时，还要兼顾客户的订货计划，通过系统协调，实现供应链整体 利润最大化。这时就要在供应链系统中应用某种激励机制，对成员的行为 进行制约和激励，促使其制定出逼近系统最优状态的决策。本文主要通过 制定合理的退货合同来协调企业的生产计划和客户的订货计划。 易逝品( p e r i s h a b l eg o o d s ) ，也称易变质产品、时效品、时令品或季节 性产品等，该类产品具有生产提前期长、销售周期短、期术未售出的产品 残值低、需求不确定性大等明显特征。易逝品的例子很多，如待飞班机上 的舱位、病床、门票、易腐物品、时装、报纸杂志、贺卡、圣诞礼物、玩 具、高科技产品以及定制的特殊零部件等。最近关于易逝品的研究集中在 易逝品供应链合同( s i n g l ep e r i o ds u p p l yc o n t r a c t s ) ，主要研究合同条款及制 订条款的策略。 p a s t e r n a c k 。是最早研究市场学中关于退货问题的学者，他主要研究i 一个制造商、单一产品、一个分销商组成的销售渠道。该产品生命周期短，。 分销商每次完成一个订单，批发价、市场价固定。分销商唯一的决策变量： 是订货量。研究的结果表明：允许退货但且返还部分货款时，可以实现销。 售渠道协调。c a e h o n & l a r i v i e r e “3 考虑制造商在观察到不确定的需求前必 须同供应商制订合同。显然，制造商希望供应商提供充足的产品却不想承 担过多成本。所以制造商把需求信息据为己有，同时向供应商支付终止合 同费用或最小购买量来向供应商可靠地转让信息。当然这还取决于供应商 是否服从这样的安排。张江涛、于吉祥。吲研究了在给定批发价的条件下， 通过对制造商回购合同的分析，得出零售商的最优订货量以及制造商的最 优生产策略。h i n g l i n gl a u ，k e i t hd & h o n s h i a n gl a u ”，k a l 4 a n t r a l a m u r a l i & k a l y a n 等考虑了市场需求不确定条件下制造商如何协调批发价 和回购价能增加零售商的订货量，并能增加双方的期望利润。张欣、阳澎 。从市场风险的角度研究了供应链合同模型。此外g u r n a n i & t a n g 川探讨 了零售商两次订货时的最优订货策略。t s a y 研究了带有数量弹性的订货 契约及一次生产和订货模式下，退货策略和滞销补贴策略的适用条件。 c h e n & x u “”提出了两次订货和两次生产的改进快速反应策略。d o n o h u e “2 3 研究了两次生产和订货模式下，如何设计供应链契约。丁利军、夏国平” 等研究了两次生产和订货模式下，退货策略和滞销补贴策略的适用条件。 鞍山科技大学硕士论文 第一章绪论 在单个制造商和单个客户构成的供应链下研究退货合同的文献很多， 但很少研究单个制造商面对多个不同类型客户时的退货问题。本文第四章 针对单个制造商面对多个不同类型客户建立了随机需求下系统利润最大 化模型，并通过对单位产品的批发价和回购价的调节来协调制造商的生产 计划和客户的订货计划，最后分别设计了遗传算法和分枝定界法解决了该 模型描述的问题。 1 3 本文研究的主要内容 批量生产计划问题是个很早就被提出的问题，国内外许多学者为此进 行了大量而深入的工作，也正是因为研究的深入，使问题也随之展丌，近 年来出现了很多新方向。根据对文献的研究和对实际生产现状的理解，本 文的研究主要包括以下几个方面： 第一章，阐述了供应链环境下批量生产问题的研究背景，在查阅大量 中外文献的基础上，分别综述了确定性需求下批量生产问题和不确定需求 下的批量生产问题的国内外研究现状及存在的问题。 第二章，首先介绍了经济批量与交货期问题( e l d s p ) 的发展状况并分 析了以往解决e l d s p 的启发式算法易陷入局部最优和多项式算法运行时 间过长的缺点；然后设计了基于e l d s p 的遗传算法；最后通过大量仿真 实验证明了用遗传算法解决e l d s p 的可行性。 第三章，首先介绍了模糊理论的相关知识，然后给出了基于模糊需求 下批量生产计划的问题描述，建立了问题的数学模型，并将其转化为模糊 机会约束规划模型，用清晰等价类对其进行清晰化处理，最后将模糊模拟 技术引入遗传算法对模型进行求解。通过仿真，验证了基于模糊模拟的遗 传算法( f s g a ) 的有效性。 第四章，钊对由单个制造商、单一产品和多个客户构成的供应链系统， 首先建立了集中控制下客户整体利润最大化模型，并给出模型的求解方 法；然后建立了分散控制下系统利润最大化模型，并提出客户选择可变方 案与前人提出的客户选择不可变方案进行比较，分别设计了遗传算法和分 枝定界法求解模型；最后通过实例仿真，验证该方案的可行性及两种算法 的有效性。 第五章，在总结全文研究成果的基础上，指出了仍然存在着的不足以 及有待改进的地方，为今后的进一步研究提供了方向。 鞍山科技大学硕士论文 第二章基于e l d s p 的遗传算法 2 1 引言 第二章基于e l d s p 的遗传算法 经济批量与交货期问题( e c o n o m i cl o ta n dd e l i v e r ys c h e d u l i n g p r o b l e m e l d s p ) 由h a h m & y a n o 在文 4 4 中首次提出，是经济批量问题 ( e c o n o m i cl o t s i z i n ga n ds c h e d u l i n gp r o b l e m e l s p ) 的扩展。 h a h m & y a n o 建立了基于e l d s p 的独立解模型。一个制造商在一条生 产线或一台机器上生产一种产品，累积到一定数量向客户送一次货，同时 该客户以一固定速度使用这些产品。这就是e l d s p 的最初特性。e l d s p 的目标是使单位时间制造商的生产策划成本、制造商和客户的库存维护成 本及运输成本的总和最小。文 4 5 扩展产生了该问题的公共周期模型，即 生产的产品种类由单一转为多元，在两次送货之间生产完客户所需要的全 部产品，假定生产所有产品的公共周期( c c - - c o m m o n c y c l e ) 为t ( 这不仅。 可以使问题的研究简化，生产实际中也更易于组织和管理) 。对于制造商。 来说，生产产品的顺序与该产品的库存数目密切相关。例如，三种产品制。 造商可能有六种生产顺序。图2 一l 显示了按照f 2 ，l ，3 顷序生产的两个， 周期的库存水平，其中每个周期为t 。i 库存水平 时间 一t 一t 图2 1 ：制造商以 2 ，1 ，3 ) 顺序生产时的库存水平 h a h m 和y a n o ”“给出了一种启发式算法来解决e l d s p 。这种算法的主 要思想是将库存维护费用低、生产时问长的产品先生产，库存维护成本高、 生产时间短的产品后生产。这种策略能确保生产时间短且易损耗的产品在 送货前不需积压太久。该算法的运行时间很短，但由于运算过程中只要某 次得到的生产顺序与前一次得到的生产顺序相同，计算终止并默认当前得 到的解为最优解。因此这种算法不能进行全局寻优，很容易陷入局部最优 解。 j e n s e n 和k h o u j a “”提出了一种多项式算法来解决e l d s p 。这种算法 的主要思想是将可行周期分成许多段，使得每段的最优生产顺序都是唯一 鞍山科技大学硕士论文 第二章基于e l d s p 的遗传算法 的。比较由每段最优顺序得到单位时自j 的最小成本，进而得到对应的生产 顺序和周期即是最优的生产顺序和最优公共周期。这种策略能确保得到全 局最优解，但是随着产品数目的增加，程序运行的时间大幅度增加。 遗传算法是一种应用最多的随机优化搜索方法。这种算法的虽大优点 是通过群体问的相互作用，保持已经搜索到的信息，这是基于单次搜索过 程的优化方法所无法比拟的。本章设计了基于e l d s p 的遗传算法，并通 过实例仿真对遗传算法与之前的两种算法进行比较，证明了用遗传算法解 决e l d s p 的有效性。 2 2 基于e l d s p 的遗传算法 2 2 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m g a ) 是根据自然界的遗传机理而设计的 一种优化方法，是一种建立在生物界自然选择原理和自然遗传机制的随机 化搜索法，它模拟了生物界中的生命进化机制，在人工系统中实现特定目 标的优化。遗传算法最早由美国m i c h i g a n 大学的j h o l l a n d 教授提出，起源 于6 0 年代人们对自然和人工白适应系统的研究。由于具有搜索效率高、 鲁棒性强、不受搜索空问的约束条件限制等优点，遗传算法一经提出即在 理沦上引起了高度重视，并在实际工程技术和经济管理领域得到了广泛应 用。 遗传算法是一种常用的大规模并行搜索优化算法，它模拟了达尔文 “适者生存”的规律和随机信息交换思想，仿效生物的遗传方式，从随机 生成的初始种群出发，采用选择( s e l e c t ) 、交叉( c r o s s o v e r ) 、变异( m u t a t i o n ) 等算子进行搜索操作，产生优于父代的子代，使优化过程以大概率趋于全 局最优。简单来说，其基本寻优步骡如下”1 ： 步骤一：选择编码策略，随机制始化种群； 步骤二：定义个体适值函数； 步骤三：确定遗传策略，包括选择群体大小，选择、交叉、变异方法， 以及确定交叉概率、变异概率等遗传参数； 步骤四：计算群体中每个个体的适应值； 步骤五：运用选择、交叉和变异算子作用于群体，产生新个体，并形 成新的种群； 步骤六：判断群体性能是否满足某一指标，或者已完成预定迭代次数， 鞍山科技大学硕士论文 第二章基于e l d s p 的遗传算沽 不满足则回到步骤五，或者修改遗传策略再返回步骤五。 由上述运算过程可以发现：参数编码、初始群体的设定、适应度函数 的设计、遗传操作的设计和控制参数的设定是实现遗传算法的五大要素， 下面我们分别对这五方面进行简要介绍： 1 编码方法 在遗传算法中，如何把一个问题的可行解从其解空问转换到遗传算 法所能处理的搜索空间的转换方法就称为编码。目前常用的编码方式有： 二进制编码、实数编码、自然数编码、符号编码方法等。 2 初始化群体 初始化群体中的个体一般是随机产生的。由模式定理我们可以知道群 体规模对遗传算法的性能影响很大，群体规模越大，群体中个体的多样性 越高，算法陷入局部解的危险越小。但是随着群体规模增大，计算量也显 著增加，所以要结合具体问题考虑如何初始化群体。 3 适应度函数 在遗传算法中把度量个体适应度的函数称为适应度函数( f i t n e s s , f u n c t i o n l 。为满足适应度取非负的要求，一般采用下面两种方法之一将目l 标函数值f ( x ) 变换为个体的适应度f ( x ) ： i ( 1 ) 若目标函数为m a x f ( x ) ，则：毒 耻) = 傺卜巳i l l ： i f 厂( x ) + c 。 0 i f ，( x ) + c m 0 式中，c 。为一个适当地相对比较小的数。 ( 2 ) 若目标函数为m i n f ( x ) ，则： 础，= 悟：嬲笨乏 式中，c 。为一个适当地相对比较大的数。 4 遗传操作算子 ( a ) 选择算子： 选择操作是遗传算法中环境对个体适应性的评价方式，也是实现群体 优良基因传播的基本方式。从模拟生物学进化过程来讲，选择算子保证了 g a 迭代中的“适者生存”的群体进化现象，体现了群体中个体求同的意 向，在很大程度上决定了g a 收敛的效果和速度。 鞍山科技大学硕士论文第二章基于e l d s p 的遗传算法 遗传算法采用选择算子来对群体中的个体进行优胜劣汰操作：适应度 高的被遗传到下一代的概率就高：适应度低的被遗传到下一代的概率就 低。选择操作就是确定用某种方法从父代群体中挑选个体。选择操作建立 在对个体适应度进行评价的基础之上，主要目的为了避免基因缺失、提高 全局收敛性和计算效率。常用的选择算子有比例选择、无放回随机选择、 排序选择、轮盘赌选择等方法。 ( b ) 交叉算子 g a 交叉算子是模仿自然界有性繁殖的基因重组过程，在该过程中群 体的个体品质得以提高。直观来讲，选择算子将原有的优良基因遗传给下 一代个体，而交叉算子则可以生成包含更多优良基因的新个体。 常用的交叉算子有部分映射交叉( p m x ) 、顺序交叉( o x ) 、循环交叉 ( c x ) 、基于位置的交叉、基于顺序的交叉、启发式交叉等。 ( c ) 变异算子 由于偶然因素的存在，生物在进行自然进化的过程中，某些基因发生 变异，产生了新的物种。虽然这样的概率很小，但它却是不可忽视的一个 重要过程。遗传算法采用生物的这一性能将个体染色体编码串上的某些基 因进行替换，从而形成一个新的个体。 常用的变异类型有：基本位变异、均匀变异、非均匀变异、倒置变 异、高斯变异算子等。 5 控制参数的设定 在遗传算法的使用过程中要合理的确定编码长度、种群规模，交叉概 率，变异概率及迭代次数等控制参数，这些参数的选择将影响到遗传算法 的最终性能和效率。 2 2 2 基于e l d s p 的遗传算法设计 下面构造解决e l d s p 的遗传算法： 第一步：染色体编码。 就一次具体的排序而言，产品的加工顺序是确定的，并且编码中每个 产品必须而且只能出现一次，各基因码表示产品的编号。本章所用到的染 色体编码采用自然数编码，如：3 2786 5 41 表示编号为3 的产品第一个生产，而编号为1 的产品最后一个生产。 第二步：初始化。按照第一步随机产生初始种群，n 种产品能产生n ! 种 生产顺序，因为初始种群的规模影响到算法的达优率，针对不同问题选择 鞍山科技大学硕士论文第s - 章基于e l d s p 的遗传算法 适合的种群数。 第三步：评价个体的适应度。 ( 1 ) 计算个体目标值f ( x ) 。 ( 2 ) 确定适应度函数。结合求解的实际问题，确定适应度函数为 f ( x ) = 1 f ( x ) 。 ( 3 ) 计算个体的适应值。 第四步：遗传运算。 、 ( 1 ) 选择算子。采用比例选择法选择父代个体，以保证具有较高适应值 的染色体在下一代中的后代个数也较多。设群体大小为m ，个体i 的适应 度为e ，则个体i 被选中的概率成为： m 以= ( 鼻 ( f _ 1 , 2 ，m ) ( 2 ) 交叉算子。采用顺序交叉算予。 ： o x 是d a v is ”们为解决旅行商问题而设计的一种交叉方法。在e l d s 疋 中，生产排序问题也可以看作是旅行商问题，所以在这里我们采用顺序交 又算子。顺序交叉的主要思想是通过从一个父代中随机挑选一个子串并保一 存另一个父代的相对次序来构造予代，具体步骤表示如下： j 步骤1 ：在字符串上随机地选取两点 步骤2 ：两点之间的子串被复制到后代早 步骤3 ：为了得到o l ，我们移走p 2 中已在0 1 中的城市4 、5 、6 和7 后 得到2 1 8 9 3 同理，我们可以得到另一个后代0 2 。 鞍山科技大学硕士论文 第二章基于e l d s p 的遗传算法 ( 3 ) 变异算子。采用倒置变异算子。 顺序交叉两个交叉点之间的子串被保存到下一代，采用倒置变异算子 可以使被保存下来的子串发生基因变异，提高g a 的局部搜索效率。具体 步骤如下： 步骤1 ：在字符串上随机地选取两点： 步骤2 ：将两点间的子串反转得到新个体 第五步：终止条件判断。指定最大迭代次数，若达到最大迭代次数 则输出全局最优的个体、对应的公共周期及其函数值。 2 2 3g a 的实例仿真 上述算法用c + + 语言”在v c + + 上进行编程，并分别对七种和十 种产品的e l d s p 问题进行仿真示例，表2 1 和表2 2 别给出了七种和十种 产品时产品i 的设置成本、产品i 的设置时间、单位产品i 的生产时闻、单 位时问单位产品i 的库存成本、单位时间产品i 的需求量。 表2 1 ：七种产品的参数值 s ? s f p ， h i d j 12 5 8 2 6 l00 3 9 7 3 2o 3 1 9 4 0 7o 5 3 7 9 1 90 4 0 9 4 6 7 215 8 6 7 l0 0 4 9 4 6 4 6o 9 0 1 5 7 80 2 5 2 9 9 800 6 9 0 6 3 4 3l5 4 2 1 4o 0 1 2 6 0 7 70 7 3 3 5 4 30 9 9 7 7 7 2o0 9 9 4 5 9 8 425 1 4 6 2o 0 6 7 13 900 0 2 7 4 6 6 70 1 4 4 2 9 20 9 4 5 6 4 7 524 3 4 2 8 0 0 4 3 9 0 1 90 3 8 7 4 9 40 7 8 4 5 3 90 13 5 2 5 8 6l9 3 9 0 2 9 8 7 8 6 0 0 0 2 7 4 6 6 7 0 0 4 7 8 53 06 3 4 4 4 9 71 7 6 7 7 4 0 0 8 5 9 4 0 9 o 1 8 1 0 9 7 0 9 7 3 9 0 7 03 0 4 3 9 2 a = 0 3 9 3 3 8 4 鞍山科技大学硕士论文 第二章基于e l d s p 的遗传算法 表2 - 2 ：1 0 种产品的参数值 s s fp 。吩口 1l8 6 0 4 80 0 6 2 7 5 9 2 o 1 6 9 9 7 20 5 7 5 9 150 0 5 5 0 2 4 9 2 1 2 8 4 0 4 o 3 2 5 1 9 30 0 4 9 6 8 410 9 5 5 1 3 80 8 9 9 5 6 4 305 8 8 6 0 20 0 0 6 7 0 4 8 90 0 4 9 6 8 410 7 8 3 3 80 0 0 1 1 5 9 7 4 1 8 0 8 5 5o 0 7 0 5 7 6 300 9 0 15 1 70 9 5 2 9 l0 ，4 8 4 7 8 7 5o 1 9 7 1 6 60 0 6 4 5 5 1 8o 7 5 3 4 4l0 0 0 7 7 8 2 2 20 0 0 7 4 7 7 0 3 6 24 9 1 1 6o 0 1 9 7 2 6 20 15 8 7 8 80 9 6 2 7 9 805 2 2 8 2 3 7 05 1 8 6 3 4o 0 1 8 5 6 8 lo 3 2 8 4 7l0 2 9 4 1 6 80 2 3 4 2 9l 8 o 3 7 2 0 3 80 ，0 0 0 6 9 7 2 7o 1 0 3 8 5 40 5 9 6 4 5 4o 7 5 3 5 0 2 926 6 9 1 20 0 0 3 9 2 3 0 50 1 4 5 8 7 80 13 9 2