（计算机应用技术专业论文）有保质期产品的经济批量调度问题模型与算法研究.pdf

哈尔滨理t 人学t 学顺f ：学位论文 有保质期产品的经济批量调度问题模型与算法研究 摘要 经济批量调度问题，是单一机器为了最小化总生产成本而对多种产品所 进行的生产排序问题。有保质期产品在保管过程中具有较强的时效性，发生 变质会给系统带来额外的成本开支。在过去对有保质期产品的经济批量调度 问题的研究中，大都假设生产满足客户的所有需求，不允许拖欠订单，且生 产系统是完全可靠的，然后采用公共周期法建立该问题的模型。但在实际情 况中，缺货现象是不可避免的，机器也可能会因为长期使用而导致零件损耗 或毁坏，且按照批量变动法调度的成本更低。因此，在对有保质期产品的经 济批量调度问题的研究中，应该把这些影响因素都考虑进去。 首先，本文研究了允许缺货的有保质期产品的经济批量调度问题模型。 采用批量变动法进行调度，当库存时间大于产品保质期时允许缺货，建立允 许缺货的单位时i 、日j 期望总成本模型，提出变换顺序搜索的启发式算法对模型 进行求解，并给出算例分析。 其次，研究了不可靠生产系统下有保质期产品的经济批量调度问题模 型。采用批量变动法进行调度，建立定期检验策略下的单位时问期望总成本 模型，在生产开始时使机器以需求速度进行生产，当空闲时间使用完毕时， 再以最大生产速度进行生产，提出新的算法求解产品生产周期，改进 d o b s o n 的启发式算法求解生产顺序，通过实例，验证了模型与算法的可 行性及有效性。 最后，介绍了生产管理系统的开发，并应用了有保质期产品的经济批量 调度问题模型辅助允许缺货环境下的生产决策，将理论研究结果应用其中， 充分展示有保质期产品的经济批量调度问题模型在实际生产中的可行性和应 用价值。 关键词经济批量调度问题；保质期产品；批量变动法；启发式算法 哈尔滨理t 人学t 学硕l1 学位论文 r e s e a r c ho nm o d e la n d a l g o r i t h mf o re c o n o m i c l o ts c h e d u l i n gp r o b l e mw i t hs h e l fl i f ep r o d u c t a b s t r a c t e c o n o m i cl o ts c h e d u l i n gp r o b l e m ( e l s p ) i st h ep r o d u c t i o n s c h e d u l i n g p r o b l e mt h a tas i n g l ef a c i l i t ym a n u f a c t u r e dm u l t i p l e p r o d u c t si n o r d e rt o m i n i m i z et h et o t a lc o s to fp r o d u c t i o n p r o d u c t sw i t hs h e l fl i f eh a v ea s t r o n g t i m e l i n e s si nc u s t o d ya n dw i l lb r i n ga d d i t i o n a lc o s tf o rd e t e r i o r a t i o n i nm o s to f p r e v i o u sl i t e r a t u r eo ne l s pw i t hs h e l fl i f ep r o d u c t ，i ti sa s s u m e dt h a tt h e p r o d u c t i o ns a t i s f i e dc u s t o m e r sd e m a n d ，o r d e r sa r en o ta l l o w e di na r r e a r s ，a n d t h es y s t e mi sp e r f e c t c o m m o nc y c l ea p p r o a c hi su s e dt oc o n s t r u c tm o d e l a sa m a t t e ro ff a c t ，s h o r t a g ei si n e v i t a b l e f a c i l i t ym a ya l s ob ep a r t l yd a m a g e d b yt h e l o n g t e r mu s e ，a n dt i m e - v a r y i n gl o ts i z ea p p r o a c hc o s t sl o w e r s ot h e s ef a c t o r s s h o u l db ec o n s i d e r e di nt h er e s e a r c ho ne l s pw i t hs h e l fl i f ep r o d u c t f i r s t l y , e l s pm o d e lw i t hs h e l fl i f ep r o d u c tu n d e rt h ec o n d i t i o no fs h o r t a g e i s c o n s i d e r e d t i m e v a r y i n gl o ts i z ea p p r o a c hi su s e dt os o l v et h ep r o b l e m s h o r t a g ei sa l l o w e dw h e nt h es t o c kt i m ei sm o r et h a nt h es h e l f1 i f e t h em o d e lo f e x p e c t i n gt o t a l c o s tp e ru n i tt i m e w i t h s h o r t a g ei sc o n s t r u c t e d ac h a n g e d s e q u e n c es e a r c h i n gh e u r i s t i ca l g o r i t h mi su s e dt os o l v et h em o d e l f i n a l l ya n u m e r i c a le x a m p l ei sa l s op r o v i d e dt oi l l u s t r a t et h ep r o b l e m s e c o n d l y , e l s pm o d e lw i t hs h e l fl i f ep r o d u c tu n d e ri m p e r f e c t e dp r o d u c t i o n s y s t e mi sc o n s i d e r e d t i m e v a r y i n gl o ts i z ea p p r o a c hi su s e dt os o l v et h ep r o b l e m t h em o d e lo f e x p e c t i n gt o t a l c o s tp e ru n i tt i m ew i t h p e r i o d i cr e v i e w i s c o n s t r u c t e d i nt h eb e g i n n i n g ，w ep r o d u c t e da tt h ed e m a n ds p e e d w h e nt h ei d l e t i m ei su s e du p ，w ep r o d u c e da tt h em a x i m u ms p e e d an e wa l g o r i t h mi su s e dt o s o l v et h ep r o d u c t i o nc y c l e i m p r o v e dd o b s o nh e u r i s t i ca l g o r i t h mi su s e dt os o l v e t h ep r o c u c t i o ns e q u e n c e l a s t l yt h e f e a s i b i l i t ya n dv a l i d i t yo ft h em o d e la n d a l g o r i t h mi si l l u s t r a t e db yu s i n gs i m u l a t i o nd a t a f i n a l l y , t h ed e v e l o p m e n to fap r o d u c t i o nm a n a g e m e n ts y s t e mi si n t r o d u c e d t h ep r o d u c t i o nd e c i s i o no fe l s pw i t hs h e l fl i f ep r o d u c tu n d e rt h ec o n d i t i o no f s h o r t a g ei su s e dt ov e r i f yt h et h e o r e t i c a lr e s u l t s t h ef e a s i b i l i t y a n da p p l i c a t i o n v a l u eo fe l s pm o d e lw i t hs h e l fl i f ep r o d u c ti sd i s p l a y e df u l l y k e y w o r d s e c o n o m i cl o ts c h e d u l i n gp r o b l e m ，s h e l fl i f ep r o d u c t ，t i m e - v a r y i n g l o ts i z ea p p r o a c h ，h e u r i s t i ca l g o r i t h m 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文有保质期产品的经济批量调 度问题模型与算法研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学 位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不 包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：划半而华 只期：扣7 年岁月a o 日 哈尔滨理工大学硕士学位论文使用授权书 有保质期产品的经济批量调度问题模型与算法研究系本人在哈尔滨理工 大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归 哈尔滨理工大学所有，本论文的研究内容不得以其他单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以 采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密彤 ( 请在以上相应方框内打、) 作者签名： 剑匕许 导师签名：季氏乡 日期：2 研年弓月a o 同 日期：圳年弓月支d 同 哈尔滨理t 人学丁学硕i j 学位论文 第1 章绪论 1 1课题研究背景及意义 随着改革开放的深入，市场机制逐步完善，竞争同趋激烈。企业合理地 组织安排生产，使得总生产费用降低到最小是重要决策之一。在制造行业 中，一台设备或一条生产线可以生产多种产品的情况很常见。例如，在食品 生产中同一条生产线可生产不同种类的食品。因此在生产中，如何安排各类 产品的生产顺序以及生产数量显得十分重要。当设备或生产线生产不同产品 时，需要进行一些转换，这种转换需要花费一定的成本和时间。为了减少转 换成本，每一次转换都希望生产尽可能多的产品，但这又会导致库存成本的 增加。这就需要科学地权衡转换成本和库存成本，并且在调度时避免产生几 种不同产品在使用设备上的冲突。由于它直接关系到生产系统的成本和生产 率，因此，这类问题具有很强的实用性，是当今国际工业工程领域关注的热 点问题，即经济批量调度问题( e c o n o m i cl o ts c h e d u l i n gp r o b l e m ，e l s p ) 。 经济批量调度问题是针对单一设备或生产线生产两种以上的产品时，探 讨产品的批量大小、生产次数及周期时间，并且调整产品周期性的生产调 度，使其生产计划为可行，又能满足顾客长期的需求，同时使得平均总成本 达到最小。 经济批量调度问题在过去的半个世纪里受到了学者们的广泛关注，并被 大量应用于许多产业当中，例如：金属成型、塑胶生产、食品、化工、制药 等。有保质期产品在保管过程中具有较强的时效性，发生变质会给系统带来 额外的成本开支。就企业而言，对于有保质期的产品，要尽可能采用更加合 理的生产方案，以降低其因变质造成的损失，达到库存成本和转换成本的最 优结合。目f j i 对于有保质期产品经济批量调度问题的研究，主要集中在降低 产品的生产率或者生产周期上，在机器完全可靠的情况下，采用公共周期法 进行调度。但这种方法花费的成本较高，且不一定得到可行的调度。学者们 研究发现在机器具有空闲时问的情况下，降低生产速率进行生产可以有效地 降低库存水平，进而得到更低的总成本。一般情况下，按照批量变动法调度 的成本要低于公共周期法。 在过去对有保质期产品的经济批量调度问题的研究中，大多假定生产满 哈尔滨理t 人学t 学硕i j 学化论文 足所有顾客的需求，并且机器完全可靠，生产出的产品完全符合品质标准。 但是由于生产过程中存在很多不确定因素，无论采用何种调度方法，都只能 在一定程度上减少缺货情况的发生，而无法完全杜绝缺货现象。对于有保质 期的产品，当库存时间超过产品的保质期时发生变质，也会导致缺货。并且 现实的生产系统大多是不可靠的，机器可能会因为长期使用而导致零件损耗 或毁坏，生产出的产品也可能因为机器故障、原料损坏、人员疏忽等因素而 出现瑕疵。因此，本文将采用批量变动法对有保质期产品的经济批量调度问 题进行研究，考虑允许虑缺货及不可靠生产系统的情况，提出新的算法求解 产品生产顺序，并假设机器具有多余的产能可以使用弹性速率法进行生产。 考虑缺货及不可靠生产系统下的有保质期产品的经济批量调度问题的研究比 传统的经济批量调度问题的研究更接近于实际情况，因此具有一定的研究意 义和价值。 1 2国内外研究现状 经济批量调度问题的研究已经有几十年的历史了，当需要在一定生产设 备上生产多个产品，且产品的外部需求比较稳定，计划期较长时，可以认为 满足e l s p 的条件。虽然单件生产是未来生产的典型模式，但在零部件加工 车间等环境中一般仍可按照e l s p 算法排产，因此其研究具有重要应用价 值，仍然是近年来运筹学、管理科学和工业工程等领域的研究热点之一。 自r o g e r s 提出经济批量调度问题之后，此问题受到了学者们的广泛 关注。e l m a g h r a b y l 2j 整合了有关经济批量调度问题的文章，并将该问题 的解法分类为：分析式解法( a n a l y t i ca p p r o a c h e s l 及启发式解法( h e u r i s t i c a p p r o a c h e s ) 。分析式解法主要是将原本的问题加入一些限制，以达到最优 化的目的，在解决如l o 种产品以上的e l s p 问题，会花费过多的演算时 间。常见的分析式解法有：独立解法( i n d e p e n d e n ts o l u t i o na p p r o a c h ) 和公共 周期法( c o m m o nc y c l ea p p r o a c h ) 。启发式解法通常只能达到较好的近似最 佳解，得到的解都会倾向于区域最小值( l o c a lm i n i m u m ) ，因此不能保证所 求的解是全局的最佳解( g l o b a lo p t i m a ls o l u t i o n ) 。常见的启发式解法有：基 本时段法( b a s i cp e r i o da p p r o a c h ) ，扩展的基本时段法( e x t e n d e db a s i cp e r i o d a p p r o a c h ) 以及批量变动法( t i m e v a r y i n gl o ts i z ea p p r o a c h ) 。 1 有保质期产品的情况有保质期的产品在保管过程中具有较强的时 效性，发生变质会给系统带来额外的成本开支。s i l v e r 1 ，c h o w d h u r y 哈尔滨理t 人学t 学硕f j 学位论文 和s a r k e r ，k h o u r y 1 利用公共周期法对有保质期产品的经济批量调度 问题进行了研究，主要集中在降低产品生产率或者降低产品的生产周期上， 但降低生产率在实际生产中不一定可行，并且采用公共周期法花费的成本较 高。l i n 等| 6 1 利用公共周期法研究了有保质期产品的经济批量调度问题，并 确定了连续检验策略下的最佳生产周期。s o m a n 1 利用基本时段法研究了 考虑保质期因素的经济批量调度问题，提出一种类似分枝定界的算法。吴丽 娜等1 8 】利用批量变动法对有保质期产品的经济批量调度问题进行研究，克服 了基本时段法求解复杂，有时得不到可行调度的问题。李天凤等【9 i 也对有保 质期产品的经济批量调度问题进行了研究，并假设库存在降为0 之前开始生 产，采用新的启发式算法求解生产顺序。 2 不可靠生产系统的情况在现实生产系统中，机器可能会因为长期 使用导致零件损耗或毁坏，生产出的产品也可能因此出现瑕疵，此类问题更 接近于实际情况，很多学者对其进行了研究。w a g n e r 和d a v i s 州对不可 靠生产系统下的经济批量调度问题进行研究，并提出了一种新的启发式算 法。b e n d a y a 和h a r i g a 1 也对不可靠生产系统的情况进行了研究，并 建立了不可靠生产系统下的经济批量模型。m o o n 等【1 2 研究了不可靠生产 系统的情况，分别用公共周期法和批量变动法建立了不考虑定时检测和考虑 定时检测时的4 个模型，并得出结论：考虑定时检测时比不考虑定时检测时 的成本要低，同时批量变动法的解也总是优于公共周期法。g i r l 等| 13 j 进一 步对不可靠生产系统下的经济批量调度问题进行了研究。m o o n 等【14 1 针对 以往经济批量调度问题的假设，提出了稳定阶段的概念，在目标函数中考虑 了由生产不合品质的产品带来的损失费。郑家昌15 1 针对不可靠的生产系统， 根据重新报酬理论，建立了期望总生产库存成本及期望生产周期的模型。林 育壮6 对不可靠生产系统下再生产点与固定生产批量的库存模型进行了研 究，讨论了在机器故障问隔时间及维修时l 、日j 为概率分配的情况下，在批量生 产过程中可能的库存水平变化，建立出使单位时间期望总成本最小的库存策 略。但是在这些研究中，都没有考虑到利用机器空闲时问降低生产速率以得 到更低总成本解的做法。 3 生产速度可变的情况越来越多的学者研究发现以变动的速度进行 生产可以有效地降低库存水平，进而得到更低的总成本。e l h a f s i 和b a i 【1 7 1 利用公共周期法研究了生产速度可变的经济批量问题，认为优化的生产速度 只能取3 种值：零、与需求速度相等的速度、最大的生产速度，并在模型中 考虑了缺货的情况。a r i z o n o 和y o k o 8 1 以及s i l v e r 引也利用公共周期法 哈尔滨理t 人学t 学顾l ：学位论文 对生产速度可变的经济批量问题进行了研究，但这些研究都假设一旦决定了 最优的生产速度后，整个生产过程中生产速度将保持不变。m o o n 和 c h r i s t y 心叫利用公共周期法研究了模具生产中的可变生产速度的问题，考 虑了生产速度对模具寿命操作费用的影响。生产速度增加会使人工操作等费 用减少，但又会使模具等的寿命减少，费用增加。e y n a n 他利用公共周期 法对生产速度可变的问题进行了研究，与上述不同之处在于，研究假定生产 转换在设备外部进行，即可以不中断生产进行生产转换。g i r l 和m o o n l 2 2 1 在经济批量调度问题中还考虑了空闲设备成本的影响，使得成本的表达更为 精确，并在生产速度不变和生产速度可变的两种假定下进行研究。张孝裕 利用公共周期法求解可变动生产速率下具有存储限制的经济批量调度问题。 4 多条生产线的情况b o l l a p r a g a d a 和r a o 心引将经济生产批量 调度问题扩展到多种产品分配给多条生产线的问题，并假定每条生产线的费 用、生产速度、生产转换费用和时间各不相同，在模型中还考虑了允许短 缺，每条生产线采用公共周期法和各条生产线的周期时间不必相同的情况。 p e s e n t i 和u k o v i c h 心5 j 对多条生产线的问题进行了研究，假定几条生产 线是相同的，并且允许短缺，生产转换时间为零，每条生产线都是周期性的 计划，但不一定都采用公共周期法，还考虑了有些产品由于需要相同的资源 而不能同时生产的情况。 5 不同的求解方法求解批量变动法的模型一般用到的是d o b s o n l 2 6 1 提出的启发式算法。k h o u j a 等圳提出了使用遗传算法求基本时段法的模 型，利用g a 多点平行搜索及可同时找到最佳b ， 缸) 的优点，快速求得全 局最佳解。a y t u g 等妇8 】也采用遗传算法来求解经济批量调度问题模型。 m o o n 等陀9 1 提出了一种用混合遗传算法求解批量变动的方法，该遗传算法 主要用于产生生产顺序。陈英钦等刚结合使用遗传算法与较可靠的启发式经 济批量调度问题的可行解测试法，有效地解决了经济批量调度问题，找到了 一个更佳的可行解。c h a n g 和y a o b 针对相同设备并行生产的问题，提 出了一种新的遗传算法求解经济批量调度问题的公共周期法模型。h u a n g 和y a o | 3 2 提出了一种新的遗传算法解决车间流水作业的排序问题。 c h a t f i e l d 旧3 i 提出了一种新的遗传算法，有效地解决了经济批量调度问 题。r a z a 等【3 引采用禁忌搜索算法求解批量变动法的模型，并将其与 d o b s o n 启发式算法和遗传算法进行比较，研究结果显示，采用禁忌搜索 算法求解得到的成本要低于另外两种算法。r a z a 和a k g u n d u z 【3 5 】采用变 换的启发式算法，禁忌搜索加模拟退火的方法求解经济批量调度问题。 哈尔滨理t 人学t 学硕l ：学位论文 r a z a 和a k g u n d u z 6 1 对求解经济批量调度问题的多种算法进行比较研 究，结果显示，模拟退火算法要优于其他算法。 6 其他h o c k s t r a l 3 7 i 假定生产转换费用为零，给出了公共周期法是 经济批量调度的最优解或近似最优解的条件，并得出结论：当产品的相似程 度较大时，公共周期法得出的解是经济批量调度问题的近似最优解。 f a a l a n d 等8 】考虑了货物短缺的情况，假定没有空闲时间，生产转换费用 为零，并提出一种新的启发式算法求解该模型，与以往不用之处在于，该研 究以边际利润最大化为目标。g r z n a r 和r i g g l e 阳圳提出了一种基本时段 法的算法，并给出了一种求整体最优的算法。y a o 等0 l 针对采用扩展的基 本时段法求解经济批量调度问题进行可行性测试。c o o k e 等【4 1 】针对基本时 段法不一定得到可行调度的问题，将研究主要集中在生产调度阶段，用混合 整数规划模型来求出具体的计划问题，即产品什么时候开始生产，生产多 少。吴丽娜等【4 副对经济批量调度问题的常用模型和算法进行了分类总结，分 析了不同研究方法的优缺点，并在分类的基础上对近几年的研究进展进行论 述。y a o 川对没有库存限制的经济批量调度问题进行了研究。 总结上述分析，对有保质期产品的e l s p 问题的研究一般都假定不允许 缺货，并且机器完全可靠，生产出的产品完全符合品质标准。并且文献中都 没有考虑到利用机器空闲时间降低生产速率以得到更低总成本解的做法。 1 3课题研究内容 基于有保质期产品的经济批量调度问题的研究在实际生活中的研究价 值，本文在前人的研究和上述研究现状分析的基础上，对有保质期产品的经 济批量调度问题进行研究，具体工作如下： 首先，研究允许缺货的有保质期产品的经济批量调度模型，当库存时间 大于产品保质期时允许缺货，采用批量变动法进行调度，提出变换顺序搜索 的启发式算法对模型进行求解，并给出算例分析。 其次，研究不可靠生产系统下有保质期产品的经济批量调度模型，考虑 定期检验策略下的单位时间期望总成本，假设机器在产品库存降为零时开始 生产，若机器具有空闲时l 日j ，则在生产开始时使机器以需求速度进行生产； 当空闲时间使用完毕时，以最大生产速度进行生产，提出新的算法求解生产 周期，改进d o b s o n 的启发式算法求解生产顺序，将相对生产频率舍入到 最近的整数，这样舍入带来的误差更小，并通过实例对算法进行验证。 哈尔滨理t 人学t 学硕i ：学位论文 最后，应用o r a c l ed e v e l o p e r 2 0 0 0 开发一个生产管理系统，该系统的生 产决策部分应用了本文理论研究成果，并对其进行了实际应用。 1 4本文结构 全文共分五章，具体结构安排如下： 第1 章，介绍课题的研究背景；明确研究的目的和意义；对本文的主要 工作进行简要介绍，并给出全文的整体结构。 第2 章，首先介绍经济批量调度问题的一般模型、常用求解方法；然后 分析了保质期因素对e l s p 的影响及e l s p 模型的约束条件。 第3 章，对允许缺货的有保质期产品的e l s p 问题做详细分析，针对本 问题建立出合理的数学模型，提出了变换顺序搜索的启发式算法对模型进行 求解，并给出算例分析。 第4 章，对不可靠生产系统下有保质期产品的e l s p 问题做详细的问题 描述与基本假设，并为文中使用的符号作定义说明，再针对本问题建立出合 理的数学模型，改进了d o b s o n 的启发式算法对模型进行求解，并给出算 例分析。 第5 章，介绍生产管理系统的设计和实现，将理论研究结果应用于其中 的生产决策部分，充分展示了有保质期产品的e l s p 问题模型在实际生产中 的可行性和应用价值。 哈尔滨理t 人学t 学硕f j 学位论文 第2 章有保质期产品的e l s p 问题分析 许多学者对经济批量调度问题进行深入研究，发表了大量文章，使经济 批量调度研究形成了一个完善的体系。下面将详细介绍经济批量调度问题的 一般模型及常用的求解方法。 2 1经济批量调度问题的一般模型 最常被用来求解经济批量调度模型的方法为独立解法和公共周期法。独 立解法由于忽略了单一机器在同一时间只能生产一种产品的假设，所得到的 最佳解往往不是可行解，但是此解法可为模型提供期望总成本的下界，即模 型的理想解。在公共周期方法中生产按照周期循环进行，每种产品在一个周 期内只生产一次，所有产品的生产周期相同。公共周期法总能得到可行解， 其最佳解为模型提供一个期望总成本的上界。因此，在独立解法求得的最佳 解与公共周期法求得的最佳解没有显著差别时，采用公共周期法求解模型效 率较高。基本时段法假定每种产品的生产周期都是某个基本时段的整数倍， 并利用动态规划算法对模型进行求解。扩展的基本时段法则是改善基本时段 法中假设在第一生产周期时所有产品必须进行生产，导致第二生产周期有过 多空闲时间的缺点。此两种方法得到的解往往并非最佳解，而是近似最佳 解。批量变动法允许产品在一个周期内可以生产多次，并且同一产品一个周 期内几次生产的量可以不同。一般情况下，按照批量变动法调度的成本要低 于公共周期法和基本时段法。各种求解方法的模型分别详述如下： 1 独立解法模型假设单一机器生产n 种产品，产品的需求速度为西， 生产速度为p ，满足对产品的所有需求不允许拖欠订单，且产品的生产速 度已知并使用最大生产速度进行生产。生产转换时间为& ，转换费用彳， 单位时间单位产品f 的库存费用为h r 。f 为产品标号，i = l ，2 ，n 。若产品f 的 生产周期为乃，p 利用率，其中p i = a , p i 。可得产品f 的单位时问期望成本 如公式2 1 所示。 e t c i = 鲁+ 圭m ( 1 刊兀 ( 2 1 ) 兀2 、 7 、 2 公共周期法模型公共周期法最初由h a n s s m a n n 提出，假定每个 周期内每种产品都只生产次，且所有产品的生产周期相同，即 哈尔滨理t 人学t 学硕f ：学位论文 t t = t 2 = t 3 = = 死= t 。所有产品的单位时间期望总成本如公式2 2 所示。 l f i1 e t c = 【詈+ 矗扔( 1 一p ) 丁】 ( 2 - 2 ) 一一巾1 、7o、 i = l j 公共周期法生产周期内所有产品的生产顺序可以任意排列，但每个周期 内每种产品只生产一次。以上两种方法均未考虑生产转换时间的限制，若产 品的转换时间和超过生产周期的空闲时问，则此最佳生产周期时间就必须延 长以满足转换时间的限制。 3 基本时段法模型基本时段法最初由b o m b e r g e r 提出，假定每种 产品都有特定的生产周期，每种产品f 的周期都是某个基本时段的整数倍， 即孔= 胎，b 为基本时段，总的生产周期就是所有岛的最小公倍数乘以8 的 值，且所有产品的转换时间与生产时间之和必须小于基本时段b 。因此，每 种产品不同批次生产的批量大小t d , 都相同。此方法的基本模型如下： m i ne 形= 芝 尝+ 了h i d i ( 1 一p i ) k i b ( 2 3 ) 一。ld1 i = 1 l l 上j l _ s t + p 缸口】b 岛 1 ，2 ，3 )( 2 4 ) 一o o、7，、7 i = 1 基本时段法主要利用动态规划进行求解，假设所有产品在第一生产周期 必须进行生产，之后的每一个周期是否生产则由忽来决定，不同于公共周期 法限定的每种产品在每一生产周期内必须进行生产，因而降低了生产花费的 总成本。一般来说，这种方法获得的解要优于公共周期法，但基本时段法难 以保证收敛到可行解。 4 扩展的基本时段法模型扩展的基本时段法改善了基本时段法中， 限定在第一生产周期时所有产品必须进行生产，而导致第二生产周期机器可 能发生过多闲置，使得总生产费用增加的缺点。假设每种产品都可按其缸进 行调整，不再要求在第一个基本时段曰中能容纳所有产品的生产，而是在多 个基本时段中综合考虑可行性条件，只要满足在每一周期内所有产品的转换 时间与生产时间之和小于基本时段b ，所得到的解即为可行解。由此可知， 扩展的基本时段法相较于基本时段法得到的基本时段曰与期望总成本将会更 小。扩展的基本时段法的数学模型表示如下： 5c 、l 盯 、，、， 一 彩 盯 彩 b b 仃 您 盯 叼 础叩 缈 缈 缈 、=，=，丫u 晟r 晟 + + +曰b 口 n 聆 n g g g ，j、【 nn = 彩缈凡 哈尔演理t 人学t 学硕f 。学位论文 其中疗 为整数且上述第一式必须满足l ，z 女( o ) i 一) p 腰的限制；上述 第二式必须满足l 胁( ( 0 2 一s o p 廖的限制；上述第三式必须满足 l n k m i n ( c o t s o l p 店，( ( - 0 2 一s , ) l p m 的限铝0 。 5 批量变动法模型批量变动法最初由m a x w e l l 、d e l p o r t e 和 t h o m a s 提出，允许产品在一个周期内可以生产多次，并且同一产品在一 个周期内几次生产的量可以不同，当且仅当y p 0 ( 2 10 ) 在上面的模型中，目标函数( 2 6 ) 为单位时间转换费用和库存费用的总 和。约束条件( 2 7 ) 保证给产品f 分配足够的生产时问使之满足整个周期时间 内对产品f 的需求。约束条件( 2 8 ) 保证_ ，顺序生产的产品数量满足从_ 顺序 开始到下一次又生产厂7 产品这一期间的需求。约束条件( 2 9 ) 表示生产周期 长度为m 次生产的生产时间、转换时问、空闲时问的总和。 图2 1批量变动法生产库存状态图 f i g 2 一li n v e n t o r ys t a t eo ft i m e v a r y i n gl o ts i z ea p p r o a c h 上面的问题可以看做是由一个主问题和一个子问题组成。主问题是求解 最优的生产顺序，子问题是求出优化的生产时间t ，空闲时间w 和周期长度 r 。一般情况下，按照批量变动法调度的成本要低于公共周期法和基本时段 法，因此，本文将采用批量变动法模型对经济批量调度问题进行研究。 2 2常用的求解方法 2 2 1遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是模拟生物在自然环境中的遗传和进 化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大 学的h o l l a n d 教授提出，起源于上世纪6 0 年代对自然和人工自适应系统的 哈尔滨理t 人学t 学硕i j 学位论文 研究。h o l l a n d 认识到了生物的遗传和自然进化现象与人工自适应系统的 相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成 以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生 物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变 异等运算策略在自适应系统中的重要性。遗传算法提供了一种求解复杂系统 优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的 鲁棒性，所以广泛应用于很多学科。 k h o u j a 等心7 h1 5 提出了使用遗传算法求解基本时段法数学模型，利用 g a 多点平行搜索及可同时找到最佳口，f 后) 的优点，快速求得全局最佳解。 a y t u g 等【2 引4 1 1 也采用遗传算法来求解经济批量调度问题模型。 由于遗传算法是一种较新的算法，在实际运用中还有许多地方有待于进 一步深入和改进，主要集中在以下几个方面： 1 遗传算法的理论研究比较滞后。由于遗传算法本身也是一种仿生的 思想，尽管实践效果很好，但理论证明比较困难。而且这种算法提出来的时 间还不是很长，因此其理论和实践的研究几乎是平行进行的。 2 遗传算法本身的参数还缺乏定量的标准，目前采用的都是经验数 值，而且不同的编码、不同的遗传技术都会影响到遗传参数的选取，因而会 影响到算法的通用性。 3 遗传算法对处理约束化问题还缺乏有效的手段，传统的惩罚函数法 中对惩罚因子的选取还是一个比较困难的技术问题。 2 2 2 l禁忌搜索算法尔，uj x 尔开，厶 禁忌搜索( t a b us e a r c h ，t s ) 的思想最早由g l o v e r 提出，它是对局部 领域搜索的一种扩展，是一种全局逐步寻优算法。局部领域搜索是基于贪婪 思想持续地在当前解的领域中进行搜索，其搜索性能完全依赖于领域结构和 初解，容易陷入局部极小而无法保证全局优化性。禁忌搜索则是标记对应已 搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对 象，而不是绝对禁止循环，通过设置禁忌表( t a b ul i s t ) 来禁忌一些已经历的 操作，并利用藐视准贝1 ( a s p i r a t i o nc r i t e r i o n ) 来奖励一些优良状态，从而保证 对不同的有效搜索途径的探索。由于t s 算法具有灵活的记忆功能和藐视准 则，并且在搜索过程中可以接受劣解，搜索时能够跳出局部最优解，转向解 空间的其他区域，从而增强获得更好的全局最优解的概率，所以t s 算法是 哈尔滨理t 人学t 学硕f ? 学位论文 一种局部搜索能力很强的全局迭代寻优算法。 简单t s 算法的基本思想是：给定一个当前解和一种邻域，然后在当前 解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“b e s ts of a r ” 状态，则忽视其禁忌特性，用其替代当前解和“b e s ts of a r ”状态，并将相应 的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选 解，则选择在候选解中非禁忌的最佳状态为新的当前解，而无视它与当前解 的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如 此重复上述迭代搜索过程，直至满足停止准则。 r a z a 等1 3 4 l4 1 2 提出了采用t s 算法求解批量变动法的模型，并将其与 d o b s o n 的启发式算法和遗传算法进行比较，研究结果显示，采用t s 算法 求解得到的成本要低于另外两种算法。 2 2 3d o b s o n 启发式算法 问题的最优算法可以求得问题的最优解。启发式算法是相对于最优算法 提出的，启发式算法是一个基于直观或经验构造的算法，在可接受的花费下 给出待求解问题的一个可行解，该可行解与最优解的偏离程度不一定事先可 以预计。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的 答案。在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而 造成那些特殊情况的数据结构，在实际情况中也许永远不会出现。 在批量变动法模型中，求产品的生产顺序通常用到的是d o b s o n 旧引 1 2 提出的算法，算法具体步骤如下： s t e p l 由成本下界模型的解求出相对生产频率船： 崩：m a _ x l j f - - 1 ，2 ，万 ( 2 1 1 ) 崩2 二- 一 l l ，z ，万【z il ， _ f i 其中乃为成本下界模型中求出的产品，的生产周期； s t e p 2 将相对生产频率舍入到2 的幂次，即若x i t ( , 2 ) 2 ，2 2 p ，那么 y i = 2 ，其中p 为整数。r o u n d y 1 证明了这样舍入带来的误差不超过6 ； s t e p 3 用装箱( b i n p a c k i n g ) 启发式算法求生产顺序。对产品f 来说，将y i 个产品分到6 个箱内，b = m a x ( 1 f n ) ，并且要尽可能的在空间上均匀分 配。例如：b = 4 ，y i = 2 既可以将产品分到l ，3 箱也可以分到2 ，4 箱。另 外，求出每个产品的加工时间 g i ，作为每个产品的高度。箱子的高度为装入 箱子产品高度的总和。通过最小化最高箱子的高度，可以得出一个有效的生 哈尔滨理t 人学t 学硕i j 学位论文 产顺序。在分配的过程中，按照( 矽，v ，) 降序顺序安排要分配的产品，即先排 少最大的，如果少值相同，则按v i 降序安排。其中”的计算方法为： y x i s f j r 一 ，= 上l 一 1 一p ：s t + 堕汪一1 ，2 ，t l= + f = ，厶， ( 2 1 2 ) ( 2 1 3 ) p i y i 启发式算法的优点在于它比盲目型的搜索法要高效，一个经过仔细设计 的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解，对于 n p 问题，亦可在多项式时间内得到一个较优解。因此，本文将采用启发式 算法对经济批量调度问题的批量变动法模型进行研究。 2 3保质期因素对e l s p 的影响 保质期产品是指在j 下常条件下有质量保证期限的产品，超过保质期产品 会发生变质。有保质期产品发生变质是批量调度中一种常见的重要现象。 1 9 9 7 年w e e 和y u 给出了变质的定义：变质是指腐烂，受损坏，利用价值 降低以及边际价值损失等使物品的固有价值降低的现象。根据这一定义，同 常生活中食物药品的过期、水果蔬菜的腐烂、挥发性物品的挥发等情况，造 成其固有价值降低的现象都属于变质的范畴。有保质期产品在保管过程中具 有较强的时效性，发生变质会给系统库存带来额外的成本开支。就企业而 言，对于有保质期的产品，要尽可能采用更佳合理的生产方案，以降低其变 质造成的损失，达到库存成本和转换成本的最优结合。因此，研究有保质期 产品的批量调度问题有重要的实际价值，建立起更接近于实际情况的批量调 度模型是十分必要的。 目前已有部分学者对有保质期产品的经济批量调度问题进行了研究，主 要集中在降低产品的生产率或者生产周期上，大都采用公共周期法，假定每 个周期内每种产品都只生产一次，所有产品的生产周期相同。但降低生产率 在实际生产中不一定可行，并且采用公共周期法花费的成本较高。针对这些 问题s o m a n l 7 1 6 采用基本时段法对该问题进行研究，提出一种类似分枝定 界启发式算法求解。基本时段法假定每种产品的生产周期都是某个基本时段 的整数倍，但这种方法得到的是基本周期长度和每种产品生产周期相对基本 周期的倍数，常常得不到可行的调度。般情况下，按照批量变动方法调度 哈尔滨理t 人学t 学硕l ：学位论文 的成本要低于公共周期法和基本时段法。因此，本文将在以往研究的基础 上，采用批量变动法模型对有保质期产品的经济批量调度问题进行研究，并 提出新的算法对模型进行求解。 2 4e l s p 模型的约束条件 2 4 1允许缺货 以往对经济批量调度问题的研究大多以假定不允许缺货为前提，但在实 际生产过程中，由于受到各种客观条件的限制，无论采用何种调度方法，都 只能在一定程度上减少缺货情况的发生，而无法完全杜绝缺货现象；另一方 面，为保证不缺货，必然要保有过大的库存量方能满足需要，从而增大了库 存费用。适当的缺货，虽然要支付缺货损失费，但可以减少库存。综合考虑 为达到库存