（计算机软件与理论专业论文）多级多项目批量调度算法研究.pdf

哈尔滨理工大学工学硕上学位论文 多级多项目批量调度算法研究 摘要 多级多项目批量问题的求解是商业管理软件的核心部分，用于求解批量 问题的算法在提升商业管理软件运行效率过程中扮演重要的作用。在算法运 行阶段，常常会出现许多不可行解，这些不可行解挤占种群并扰乱最优解的 搜索进程。另外，目前多数算法对批量问题求解时，其结果的质量非常依赖 初始解的种群在解空间的分布。 本文提出了两种考虑提前期以及c a r r y o v e r 类型调整结构的多级多项目 批量问题的模型。首先，采用二进制编码方式的自适应遗传算法对能力约束 的多级多项目批量问题进行求解。自适应遗传算法通过控制交叉操作和变异 操作的概率，使批量计算在计算初期倾向于全局搜索，而到了计算后期倾向 于局部搜索。引入了免疫算法中的记忆细胞增强算法搜索效率，最后通过算 例证明算法的搜索效率。 其次，本文对带有c a r r y o v e r 调整形式、考虑提前期的多级多项目无能 力约束批量问题进行研究。由于数据结构中的森林和物料清单的相似性，本 文中将森林编码方式引入到单亲遗传算法中，并采用该算法对无能力约束的 多级多项目批量问题进行求解。以往在二进制编码中，对前继和后继进行搜 索时，需要对二进制矩阵进行遍历。在新算法中，只需要通过基因中的指针 就可以直接找到该任务的前继。由于单亲遗传算法的特性，种群的初始解的 分布不影响算法运行结果的优劣。 最终，实现一个生产计划原型系统，本文中提出的算法被应用于其中， 算法的在实际生产中的可行性和应用价值得到了验证。 关键词批量调度问题：多级多项目；自适应遗传算法；单亲遗传算法 哈尔滨理工人学工学硕。 ：学位论文 r e s e a r c ho n a l g o r i t h m f o rm u l t i l e v e lm u l t i i t e m l o t - - s i z i n gs c h e d u l i n gp r o b l e m a b s t r a c t s o l v i n gm u l t i - l e v e lm u l t i i t e ml o t - - s i z i n gp r o b l e mi st h ec o r ec o m p o n e n to f b u s i n e s sm a n a g e m e n ts o f t w a r e t h ea l g o r i t h md e a l i n gw i t hl o t s i z i n gp r o b l e m p l a y s a n i m p o r t a n t r o l ei n e n h a n c i n go p e r a t i n ge f f i c i e n c y o f b u s i n e s s m a n a g e m e n ts o f t w a r e m a n yi n f e a s i b l e s o l u t i o n so c c u ri ns o l v i n gl o ts i z i n g p r o b l e m ，o c c u p yt h ep o p u l a t i o na n d d i s t u r bt h ep r o c e s so fs e a r c h i n gf o rt h e o p t i m a ls o l u t i o n i na n o t h e ra s p e c t ，t h ee f f i c i e n c yo fm a n ya l g o r i t h m sd e p e n d s o n t h ed i s t r i b u t i o no fi n i t i a ls o l u t i o n st i g h t l y t h i sp a p e rp r e s e n t st w of o r m u l a t i o n sf o rm u l t i l e v e lm u l t i - i t e ml o t - s i z i n g p r o b l e mw i t hl e a dt i m e a n ds e t u pc a r r y o v e rc o n s t r a i n t s f i r s t l y , i tp r e s e n t s b i n a r yc o d i n ga d a p t i v eg e n e t i ca l g o r i t h m t os o l v i n gm u l t i - l e v e l m u l t i - i t e m c a p a c i t a t e dl o t - s i z i n gp r o b l e m a tt h eb e g i n n i n go fc o m p u t i n gp r o g r e s s ，a d a p t i v e g e n e t i ca l g o r i t h m t e n d st od og l o b a ls e a r c hi ns o l u t i o ns p a c eb yc o n t r o l l i n g c r o s s o v e rp o s s i b i l i t y , a n di tt e n d st od ol o c a ls e a r c hb yc o n t r o l l i n g m u t a t e p o s s i b i l i t y a sa p p r o a c h i n gt ot h ee n do fc o m p u t i n gp r o g r e s s t h i sp a p e r i m p l e m e n t st h i sa l g o r i t h ma n dt e s ti t se f f i c i e n c yw i t hae x a m p l eo fm u l t i - l e v e l m u l t i i t e ml o t s i z i n gp r o b l e m t h ee f f i c i e n c y o ft h e a l g o r i t h m i sd u et o i n t r o d u c i n go fm e m o r yc e l li ni m m u n ea l g o r i t h m s e c o n d l y , t h i sp a p e r r e s e a r c h e sm u l t i l e v e lm u l t i - i t e mu n c a p a c i t a t e d l o t s i z i n gp r o b l e mw i t hc a r r y o v e rs e t u ps t a t ea n dl e a dt i m e t h i sp a p e ri n t r o d u c e s f o r e s tc o d i n gi n t op a r t h e n og e n e t i ca l g o r i t h m f o rm u l t i - l e v e lm u l t i _ i t e m u n c a p a c i t a t e dl o t s i z i n g f o r e s tc o d i n gi si n s p i r e db ys i m i l a r i t y o ft h eb i l lo f m a t e r i a l s s t r u c t u r ea n df o r e s ti nd a t as t r u c t u r e s ，a n dt h es e a r c ho p e r a t i o nf o ra i t e m sp r e d e c e s s o ra n ds u c c e s s o ri sa c t e db yp o i n t e ri ng e n ei n s t e a do fs e a r c h i n g i nb i n a r ym a t r i xo n eb yo n e b e c a u s eo ft h ec h a r a c t e ro fp a r t h e n og e n e t i c a l g o r i t h m ，r e s u l to fa l g o r i t h m i s i n d e p e n d e n t t ot h ed i s t r i b u t i o no fi n i t i a l s 0 1 u t i o n s i i 哈尔滨理工大学工学硕上学位论文 f i n a l l y , ap r o d u c t i o np l a n n i n gp r o t o t y p es y s t e mi sd e v e l o p e d ，t h ea l g o r i t h m s p r e s e n t e di nt h i sp a p e ra r ea p p l i e di ns o l v i n gl o t - s i z i n gp r o c e s 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 nv a l u eo ft h ea l g o r i t h m sp r e s e n t e di nt h i sp a p e ri sd i s p l a y e df u l l y k e y w o r d sl o t s i z i n gs c h e d u l i n gp r o b l e m ，m u l t i l e v e lm u l t i i t e m ，a d a p t i v e g e n e t i ca l g o r i t h m ，p a r t h e n og e n e t i ca l g o r i t h m i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文多级多项目批量调度算法研 究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰 写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方 式注明。本声明的法律结果将完全由本人承担。 作者签名：狄帆 日期：2 口。夕年3 月2 1 日 哈尔滨理工大学硕士学位论文使用授权书 多级多项目批量调度算法研究系本人在哈尔滨理工大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大 学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子 版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或 其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密留。 ( 请在以上相应方框内打) 日期：2o o9 年；月上f日 日期：) 卯7 年弓月) 1 日 凡 一d 了 桷 哆 甜枷 名 名 签 签 者 师 作 导 哈尔滨理工大学工学硕上学位论文 第1 章绪论 1 1课题研究背景及意义 随着现代制造业企业规模的扩大和工艺的日趋复杂，相应的生产管理模 式和系统也得到了丰富和发展，如物料需求计划、制造资源计划、企业资源 计划及为其服务的软件系统等。生产计划是各个理论系统中的重要环节，生 产计划一般被划分为战略层计划、战术层计划及作业层计划，其中战术层计 划的决定取决于物料需求计划和批量问题，批量问题解决的质量和效率直接 影响到管理工作的效率。批量问题是为得到最有效的生产计划而在调整准备 费用与维持库存费用之间做出的权衡，确定生产时间和生产数量。批量问题 的概念最早由h a r r i s 于1 9 1 3 年提出。其后有许多专家对此进行了研究。批 量问题的范围很广，根据其中的一些特性可以将它分为几类。多级多项目批 量问题就是其中比较重要，且在实际工作中应用较多的一类。本课题具体研 究的就是多级多项目批量问题。 目前求解批量问题的算法一般分为五类，数学规划启发算法、拉格朗日 启发算法、分解集结法、元启发算法、特定问题的贪婪算法，这其中由元启 发算法应用最多。常用的元启发算法有：模拟退火算法、禁忌算法、遗传算 法及蚁群算法等，其中遗传算法应用最多。利用遗传算法对批量问题进行求 解时，尚有以下问题未解决：第一，种群中可行解的所占的比例不能保证， 对解的可行性检验操作复杂。目前的算法中对不可行解进行大量计算的原因 是现广泛采用的染色体的二进制编码方式和与之相对应的遗传算子的随机性 造成的。染色体种群越大，所进行的多余计算就越多，在一定程度上限制了 算法的效率。第二，对初始解的依赖程度较高。目前，算法的初始解的生成 一般为随机生成或先验经验。采用随即生成的初始解不能保证对解空间的合 理分布。采用先验经验一般可以保证初始解的合理分布，但是如果不存在初 始解或者需求变动的过于频繁、幅度过大，先验经验就是很可能失去其分布 的合理性。本文分析多级多项目批量问题相对于其他批量问题的特殊性，进 行数学建模和分析，更改染色体的编码方式及相关遗传算子，以遗传算法的 思想为基础，引入其他算法中的优秀的方法对多级多项目批量问题进行求解， 由对算例的分析揭示出新的混合算法对解决多级多项目批量问题的效率优势 哈尔滨理工大学工学硕士学位论文 和实际应用价值。 1 2国内外研究现状 1 2 1批量问题国内外研究现状 对批量问题的研究始于经济订货量模型的研究，经济订货量模型用以解 决静态需求条件下，无能力约束单级单项目批量问题而提出并研究，所以经 济订货量模型并不具有多大的现实意义。其后，对此模型进行了很多发展， 其中经济批量问题就是一种基于循环时段，对需要相同设备的若干个不同的 项目的生产调度问题，所以经济批量是有静态需求条件下的能力约束的单级 多项目批量问题。目前国际上对批量问题的研究内容可以分为两大类，静态 批量问题和动态批量问题。经济批量问题就是一种静态批量问题。而动态批 量问题分为单级批量问题和多级批量问题，其中又分别分能力约束和无能力 约束两种情况。 目前，对批量问题已经进行了以下研究。d eb o d t 等人研究了在动态需 求条件下，滚动展望期的作用和需求的不确定性对批量决策的影响他1 。 f a b r i z i o 等人对一个源于食品公司的能力约束的批量调度问题进行了研究， 将该问题模型建立成一个基于混合连续生产调整方式能力约束批量问题，并 提出了解决方案阳1 。b a h l 等人对能力约束的批量问题进行了研究，并且按照 需求的类型、资源约束及生产计划的规模对能力约束批量问题进行了划分h 1 。 k u i k 等人讨论了在一个公司的不同的决策层中，批量问题和生产计划所起的 作用。主要讨论了与实际计划和控制相关的批量的计划与选择的区别晦1 。 w o l s e y 研究了单项目无约束批量问题的问题模型及解决算法拍1 。d r e x l 和 k i m m s 对批量和排产问题中的不同类型进行了研究，并按生产周期的不同划 分为离散和连续周期批量问题盯1 。b e l v a u x 与w o l s e y 对在基本批量问题模 型基础上添加不同变量的方式进行了讨论，如延迟、调整费用等，并对不同 模型的批量问题计算结果进行了研究阳1 。k a r i m i 对能力约束单级批量问题进 行了研究，并对求解方法进行了总结阳1 。b r a h i m i 等人对能力约束和无能力 约束条件下的单级批量问题的研究进行了总括引。j a n s 与d e g r a e v e 对单 级动态批量问题进行了研究，并对近期的研究成果进行了总结n 。 唐立新等人对单级无能力约束批量问题进行了研究，并提出有关生产量、 调整费用、库存量之间的相互关系的性质和推论n 副。唐立新等人对能力约束 哈尔滨理t 大学t 学硕 ：学位论文 的单级多项目动态批量问题进行了研究，采用遗传算法和线性规划结合来求 解带多资源的c l s p 问题n3 1 。唐立新等对多资源约束的多级批量问题进行研 究，对带有多资源的生产批量计划构造了遗传算法和线性规划混合算法，用 遗传算法产生可行调整模式，对应每一调整模式，则将原问题变换为一个线 性规划模型进行求解1 。 易成林等通过对单级多项目无能力约束生产批量问题模型进行分析，得 出了一些重要的结论。当生产调整变量给定时单击多项目无能力约束批量问 题的各个时间段内的生产数量和时间段末的库存数量的最优解，由生产调整 费用确定。另外还有调整变量和生产数量的关系、生产调整变量与需求的关 系以及库存与生产数量及库存之间的关系。这些性质和定理对于简化编码有 重要的作用n 引。 综上，对于单级批量问题的研究占大多数，对多级批量问题研究较少。 1 2 2批量问题算法研究现状 目前，在对批量问题进行求解过程中，主要分为五类方法。数学规划启 发算法、拉格朗日启发算法、分解聚合启发算法、元启发算法和基于特定问 题的贪婪启发算法。 数学规划法是只对解空间的部分进行搜索，在可以接受的时间内寻找较 优的可行解的求解算法。s u r i e 和s t a d t l e r 将能力约束的批量问题扩展为 多级批量问题，在多级情况下对c a r r y o v e r 变量类型的调整费用、调整时间进 行了讨论n 引。s t a d t l e r 采用相重叠的计划窗口方法对能力约束的多级批量 问题进行了求解，所得结果比较高效，但是在该模型中没有对提前期进行考 量n 7 1 。 拉格朗日启发算法的基本思想是拉格朗日松弛算法的迭代的应用。 s a m b a s l 埘与y a h y a 应用拉格朗日松弛算法在考虑生产调整费用的情况 下，对多车间类型能力约束的单级批量问题进行了求解。在该模型的目标函 数中，通过库存约束和相应的开销来表示相应的资源和项目的能力约束。这 里采用了一种叫做s h i f t i n g - s p l i t t i n g - m e r g i n g 的方式来产生可行解，该方法的 思想是当一个车间的能力不足时，将这部分批量移至同一时间段的另一个车 间，若都无法满足则将这部分批量留到该车间的下个时间段n 引。b r a h i m i 等人为带有时窗的能力约束批量问题提出几个拉格朗日松弛计划。在传统能 力约束批量问题中，生产过程只要在产品需求前产生就可以满足约束，而该 哈尔滨理工大学工学硕士学位论文 模型中对成产时间加入最早时间的限制n 引。 分解集结法的思想是将一个问题分解为多个小规模的问题进行求解。 s a m b a s i v a n 和s c h m i d t 对多车间的能力约束批量问题进行了求解。首先 他们对单级无能力约束批量问题进行求解，之后应用修匀过程进一步处理。 各个无能力子问题被重新的表示为最短路径问题，并有效解决。其中，修匀 过程的思想是在各个车间及各个时段间转移生产量来解决已有能力冲突。 b o c t o r 和p o u l i n 对有特定项目的资源约束的多级能力约束批量问题进行 了求解。该模型假设有多台机器、允许加班、考虑生产调整费用的情况，产 品结构为串行结构而且各级的批量相同。他们将多级问题转化为一个单级问 题，之后用贪婪算法进行求解心。 采用贪婪算法对批量问题进行求解的近期有如下研究。g u p t a 和 m a g n u s s o n 对单级批量问题进行了求解，该模型中考虑调整时间、s e t u p c a r r y o v e r 变量。他们的处理过程为先采用贪婪算法对不考虑调整时间的能力 约束批量问题求解，得出可行解。之后，在假设调整费用的c a r r y o v e r 持续发 生在每一个时段的基础上引入调整时间，并应用修匀过程进一步处理。最后 应用后向改进过程对结果进行处理心钉。b o u r j o l l y 等人对单级批量问题进 行求解，该模型考虑了调整时间和s e t u pc a r r y o v e r 变量，并且引入滚动展望期 模式【2 3 1 。 d o g r a m a c i 等人改进l o t f o r - l o t 调度方式，提出一种4 步骤算法，通过 完全或部分转移批量，减少生产调整费用，抑制能力约束，最终降低库存费 用比引。b o c t o r 与p o u l i n 对多能力约束的批量问题进行了求解，该模型为 串行多级系统。他们着重考虑了批量集中于某一级时引发的能力瓶颈情况， 求解思想为首先得出一个可行解，对各级能力的饱和程度进行统计，之后采 用增加、转移等操作，对批量进行重新分配心4 。 元启发算法是求解最优解问题中普遍采用的算法。用于求解批量问题的 算法一般用生产计划中的变量直接表示为它的解，比如生产调整费用的二进 制数组表示一个解，一些算法甚至将求解过程化简为对二进制数组的求解。 目前，很多先进的启发算法利用已有搜索数据来指导之后的搜索，如模拟退 火算法、禁忌算法、遗传算法、蚁群算法等等，其中应用最广的是遗传算法。 模拟退火算法是最早的思想由m e t r o p u s 提出心5 1 ，由k i r k p a t r i c k 最 先应用于最优化问题。b a r b a r o s o g l u 和o z d a m a r 采用模拟退火算法对 考虑调整时间的多即批量问题进行了求解他6 1 。o z d a m a r 和b o z y e l 采用模 拟退火对多级批量问题进行求解，该模型考虑生产调整时间并且允许加班托 。 哈尔滨理工人学工学硕士学位论文 禁忌搜索最早由g l o v e r 提出这一概念。g o p a l a k r l s h n a n 等人采用 禁忌搜索在不同排序方式和批量规则下，对单级批量问题进行求解，该模型 考虑调整费用的c a r r y o v e r 变量心引。h u n g 等人采用改进的禁忌算法对单级能 力约束批量问题进行求解，该模型考虑延时和调整费用幢9 1 。 蚁群算法是由d o r i g o 、m a n i e z z o 等人最先提出，目前在批量问题上 没有较多应用。p i t a k a s o 等人将蚁群算法和f i xa n dr e l a x 算法将结合起来对 多级能力约束批量问题进行求解训。 在对复杂模型求解时，通常采取引入不同算法中算子来生成混合算法的 方式，对批量问题进行求解。混合算法的优势就是将几种算法中的优势相结 合，可以达到取长补短的作用。相关内容可以参看b e r r e t t a 等人为解决带 提前期和调整时间的资源约束多级批量问题所提出的元启发算法随，以及 h u n g 为解决多级能力约束模型提出的算法2 1 。 遗传算法是利用进化和遗传原则对复杂问题进行搜索近优解的方法口3 1 ， 由美国密西根大学的h o l l a n d 教授其它学生与2 0 世纪6 0 年代提出。第一个 把遗传算法函数化的是h o l l s t i e n 。目前，国外采用遗传算法针对多级批量 问题的应用如下： 多级无能力约束批量问题：x i e 最先将遗传算法用于对无能力约束批量 问题进行求解。调整费用变量由染色体中的二进制数组成，其他的决策变量 有这些变量计算得出口引。之后d e l l a e r t 与j e u n e t 提出混合遗传算法来解 决无能力约束多级批量问题。他们通过时段需求技术、s t i l 算法和 w a g n e r w h i t i n 方式的产生初始解，与该文中其他技术相比说明这个混合 算法可以在一个可以接受的时间内得出有效解5 1 。p r a s a d 和c h e t t y 提出 一种新的启发算法一b i tm o d 遗传算法，用这种算法来对固定和滚动展望期的 多级批量问题进行求解，通过仿真实验评估在固定和滚动展望期条件下需求 变量、批量规则、产品结构预测模式等不同参数对搜索结果的影响b 引。 多级能力约束批量问题：k i m m s 提出一个混合整形规划数学模型和一个 遗传算法方法来解决多级多机器批量排产问题。他提出一个用二维矩阵来对 解进行编码的步骤。计算结果显示新的方法在搜索时间和解的质量上较禁忌 算法都有明显的优势 。o z d a m a r 与b a r b a r o s o g l u 为多级批量问题提 出两种混合算法。第一种算法是模拟退火和遗传算法的混合算法，第二种算 法是拉格朗日算法与模拟退火算法的混合算法。实验结果显示拉格朗日算法 与模拟退火算法的混合算法能够在相同的时间、相同的运算量的条件下得到 更好的结果b 引。h u n g 和c h i e n 对多需求型的能力约束的多级批量问题进行 哈尔滨理工大学工学硕上学位论文 了研究，其中每个需求型对应于一个混合整形规划模型。他们首先通过按顺 序对混合整形规划模型进行求解产生可行解，之后采用禁忌搜索、遗传算法 和模拟退火来解决这个问题。实验结果显示禁忌算法和模拟退火算法的效果 要优于遗传算法引。x i e 和d o n g 对有生产调整时间和允许加班的能力约束的 批量问题进行了研究，并用遗传算法进行了求解。他们仅用调整费用变量作 为染色体，其他决策变量都由此派生，如库存和批量。因此这个问题考虑能 力限制，一个基于批量调度的启发算法被包含在这个遗传算法的循环过程里， 用来限制不可行染色体h 引。j u n g 等人对有制造业合作的情况下整合的生产计 划问题用遗传算法进行了求解。这个研究的目标是为生产能力有限的制造业 合作者和地方性公司提供协同有效的生产计划，并使总的生产费用最小。他 们通过修改多级批量问题来对混合整形规划进行建模。在独特的染色体结构、 染色体复制方式、遗传算子的作用下，与商业优化软件优化包相比该启发算 法得到更好的解“。 国内对批量问题的遗传算法的应用如下：唐立新等人采用了遗传算法对 单级无能力约束批量问题进行求解，其结果和采用动态规划算法计算得出的 最优解进行比较，证明其具有较高的近优率n 2 。唐立新等人对能力约束的 单级多项目动态批量问题采用遗传算法和线性规划结合来求解带多资源的 c l s p 问题。该算法是遗传算法在求解批量问题上的首次应用，为带能力约 束生产批量问题的研究开创了一个新的角度。他们对c i m s 中的带能力约束 的生产批量计划问题，构造了遗传算法和线性规划算法，用遗传算法产生调 整模式，对应没每一调整模式，则产生一个线性规划程序n 3 n 。唐立新等对多 资源约束的多级批量问题构造了遗传算法和线性规划混合算法，用遗传算法 产生可行调整模式，对应每一调整模式，则将原问题变换为一个线性规划模 型进行求解通过遗传算子进行迭代和进化，从而获得近优解，分析和计算 结果表明了算法的有效性n 4 1 3 7 。易成林等分析了基本遗传算法的缺陷及其产 生的原因。对该问题在遗传算法的编码、适应度函数、选择复制操作、交叉 方法、交叉概率、变异概率和终止条件等各个环节进行了改进。对算法进行 了实现并对单级多项目无能力约束生产批量问题改进遗传算法进行了性能分 析n 钉3 。 综上，首先，目前对单级多项目批量问题和多级单项目求解的研究很多， 而求解多级多项目批量问题的研究很少。其次，生产提前期是现实生产中非 常实际的问题，但是对批量问题求解时，往往不考虑生产提前期，甚至连s m a l l b u c k e t 情况下，提前期也经常被忽略。c a r r y o v e r 类型生产调整方式是实际生 哈尔滨理t 大学t 学硕十学位论文 产中比较常用到的生产线配置方式。目前对批量问题的研究更注重简单生产 调整方式，对多级批量问题下的c a r r y o v e r 类型的调整方式研究较少。建立适 应于多级批量问题的c a r r y o v e r 类型生产调整方式的处理方法有助于促进生 产调度工作。最后，目前算法在对批量问题求解的过程中，对解的可行性验 证的过程繁琐，而解的可行性验证是在对批量问题计算过程中非常重要且调 用次数较多的一个运算步骤，简化解的可行性验证可以大幅提高求解速度。 1 3课题主要研究内容 基于多级多项目批量问题的研究在实际生活中的研究价值，本文在前人 的研究和上述研究现状的分析的基础上，对多级多项目批量问题的求解算法 进行了推广和引申研究，具体工作如下： 第一，学习和研究了批量问题及求解批量问题的算法，主要研究了多级 多项目批量问题和相关算法。 第二，对考虑提前期和c a r r y o v e r 类型的生产调整方式的多级多项目能 力约束批量问题进行分析，采用二进制编码自适应遗传算法对其进行求解， 使遗传算子对种群更新的倾向与对解空间搜索进度相匹配。为加快更新速度， 加大自适应概率，引入免疫算法中的记忆细胞保留种群中优秀个体。 第三，对多级多项目无能力约束批量问题进行研究，对物料清单与数据 结构中的森林结构的关系进行讨论，提出森林编码方式。为减少运算过程中， 不可行解对计算进程造成的影响。对不可行解的产生过程进行研究，并采用 森林编码的单亲遗传算法对考虑提前期和c a r r y o v e r 类型的生产调整方式的 多级多项目无能力约束的批量问题进行求解。 最后，应用c # 2 0 0 5 实现一个生产计划原型系统，该系统的批量决策部 分应用了研究的多级多项目批量问题算法，并进行了验证。 1 4论文结构 全文共分五章，具体结构安排如下： 第1 章，介绍课题的研究背景及发展现状，明确研究的目的和意义，对 本文的主要工作进行简要的介绍，并给出全文的整体结构。 第2 章，研究多级多项目批量问题，建立多级多项目批量问题的数学模 型，针对多级多项目批量问题的特点研究已有遗传算法的不足和原因。 哈尔滨理工大学工学硕士学位论文 第3 章，对能力约束多级多项目批量问题进行研究，以二进制编码方式 和自适应遗传算法进行求解，进行模拟实验和结果分析。 第4 章，对无能力约束多级多项目批量问题进行研究，以森林编码方式 构造染色体，引入模拟退火和记忆细胞的思想进行求解，进行模拟实验和结 果分析。 第5 章，介绍了生产计划原型系统的设计和实现，将理论研究结果应用 于其中，验证多级多项目批量调度算法在实际生产中的可行性和应用价值。 哈尔滨理t 大学t 学硕士学位论文 第2 章多级多项目批量问题数学模型及求解算法 在对批量问题求解时，对该批量问题进行数学建模是问题解决的前提。 同时，在模型中表述的各种约束也是影响批量问题复杂度的关键。本章对批 量问题的模型参数进行说明。对批量的解决方法进行了分析，着重分析了目 前批量问题中应用最广的遗传算法。 2 1多级多项目批量问题的数学模型 2 1 1批量问题数学模型参数 在对多级多项目批量问题进行数学建模之前，首先对模型的各个特性进 行说明。 1 计划期计划期分有限计划期和无限计划期两种。有限计划期一般与 动态需求问题相结合，无限计划期一般与静态需求问题相结合。 批量问题按照时段的生产能力可以划分为b i gb u c k e t 和s m a l lb u c k e t 。 b i g b u c k e t 问题是一个时段足够长可以生产多个项目的问题，而s m a l l b u c k e t 问题是每个时段只能生产一个项目( 有时可以是两个，但最多是两个) 的批 量问题。 另一个计划期的变形是滚动展望期，一般用来考虑数据的不确定性。在 这种假设下，最优的求解算法是启发算法，但并不能保证最优解。 2 产品级数生产系统可以按照所生产产品的产品结构分为单级和多级 两种。 原料在经过一个操作步骤后( 如锻造、铸件等) ，不经过其他中间环节， 直接生成最终产品的生产结构为单级批量问题。在多级批量问题中，整个产 品机构中最少有两个项目，并且其中一个输出必是其它项目的输入，原料需 经几道工序来生成最终产品。每一级操作的输出就是下一级操作的输入，输 出的项目是输入的项目的前继，输入的项目是输出的项目的后继。因此，需 求某个项目的需求由它的后继决定。 多级批量问题的解决要比单级批量问题要难一些。多级系统被细分为多 种产品结构，包括串列、装配、分解和一般或m r p 系统。 3 产品的数量生产系统中的最终产品或最终项目的数量是另一种影响 哈尔滨理t 大学工学硕士学位论文 问题数学模型的约束和生产计划问题的复杂度的重要的因素。生产系统由产 品数量分为两种系统类型：单项目批量问题和多项目批量问题。在单项目生 产计划中，只需要为一个最终产品组织计划，但多项目生产计划需要为几个 最终项目制定生产计划。多项目问题的复杂要比单项目高的多。 多项目批量问题和多产品批量问题在概念上有不同之处，多项目批量问 题强调的是产品结构中的有相互约束的各个项目，所考虑的是各个项目之间 的能力约束，多产品批量问题的多产品是物料清单中的最终产品，所考虑的 是物料清单中的最终产品的所有直接或间接前继的生产顺序和数量。由于对 批量问题研究深入，各个项目间的能力或资源约束常常被考虑到，很多情况 下，多项目和多产品已经被混用。 4 能力或资源约束在一个生产系统中，能力或资源约束包括人力资源、 设备、车床和预算等在一段时间内有可能对生产能力存在着限制。当没有关 于资源的约束时，这类批量问题就是无能力约束的批量问题。当有明确的能 力限制的存在时，这种问题就是能力约束的批量问题。能力约束直接影响批 量问题的复杂度，当能力约束存在时，批量问题的解决将变得更加困难。 5 项目的变质在一些情况下，将项目的变质条件算入考虑中是非常重 要的。这类问题一般用库存时间来处理这种约束。这是另一种影响批量问题 复杂度的特性。 6 需求需求是作为批量问题的数学模型的输入来考虑的。 静态需求是指它的值不随时间变化，它是静态的或者甚至是定值，而动 态需求是指它的值是随着时间变化的。无论是静态需求还是动态需求，如果 需求的值是已知的，则称之为确定性需求。相反，如果需求的值不是确切已 知的，并且需求的值的出现是基于一些概率因素上的，则称之为不确定性需 求。 当需求是独立需求的情况下，一个项目的需求并不与其他项目的批量有 关。这种需求是单级批量问题中的典型情况。 在多级批量问题条件下，各个项目间存在这前继与后继之间的相互约束 关系，由于一级的需求要取决于其后继的需求，所以成为不独立约束。 动态不独立需求的批量问题要比静态或是独立需求的批量问题要复杂。 不确定性需求要确定性需求要复杂一些。 7 调整结构调整结构是另一种直接影响问题复杂度的重要因素。生产 调整费用或调整时间在问题的模型中经常用二进制变量表示。在对不同的产 品进行生产调度时，会出现生产调整费用和调整时间。 哈尔滨理工人学工学硕士学位论文 有两类调整结果：简单调整结构和复杂调整结构。如果一个时段内的调 整时间和调整费用是顺序无关，这种调整结构就是简单调整结构。反之，就 是复杂调整结构。 有三种复杂调整结构： 第一种，如果当生产过程从前一个时段过渡到当前时段时，不需要多余 的调整，而降低了调整费用和时间，那么这种结构就叫c a r r y o v e r 结构。 第二种复杂调整结构，是由一组项目间的设计和制造流程的类似性而产 生的复杂调整结构，叫做f a m i l y m a j o rs e t u p 。在同族中的各个项目生产变化 中依然需要调整费用或调整时间，只是相对较少些。 如果项目的调整费用和时间取决于生产顺序，这种顺序相关调整结构就 是第三种调整结构。这种调整结构在建模和问题的解决上都比较繁复。 8 盘存缺货盘存短耗是另一种影响批量问题建模和复杂度的批量问题 性质。库存积压和销售损失同时存在也是可能的，所以经常在目标函数中引 入缺货成本。 相对于不考虑缺货的批量问题，考虑缺货的批量问题更加复杂。 2 1 2多级多项目批量问题数学模型 多级多项目批量问题模型假设有k 个项目在t 个时段内m 个生产线上 被制造，产品结构树中位于下一层项目的输出为上一层项目的输入，下层项 目叫做上层项目的前继，上层项目叫做下层项目的后继，其中存在至少一个 项目为其它项目的前继。一个典型的多级多项目批量问题数学模型如公式 ( 2 1 ) 所示。 z = 三z b k + 气毛+ 玩厶)( 2 - 1 ) l 秘“- l 州n + 善? 哗( 2 - 2 囊 匕一善乏二三 l n ，x n 2 0 以上所有i = 1 ，n ，t = l ，t 。 相关符号定义如下： ( 2 3 ) ( 2 4 ) l 为项目i 在t 时段末的库存变量，以为项目i 在t 时段的生产批量。k 哈尔滨理工大学工学硕十学位论文 为项目i 在t 时段是否发生生产调整。为项目i 在t 时段的生产调整费用， c a 为项目i 在t 时段的生产费用，玩为项目i 在t 时段的库存费用。s o ) 为i 项目所有后继。为制造项目一个项目j 所需i 的个数。 式( 2 1 ) 为批量问题的总成本表达式，式( 2 2 ) 为生产批量、库存、后继项 目和外部需求的之间约束关系。式( 2 3 ) 表示生产调整只在该时段有产品生产 时进行。式( 2 4 ) 表示库存和生产批量都为非负值。 2 2批量问题求解算法 目前对批量问题的求解算法可分为五类启发式算法，其中以元启发式算 法应用最广。由于无能力约束和调整时间的多级批量问题为n p 困难问题h 副， 能力约束的多项目批量问题也为n p 困难问题引，考虑到遗传算法的易于编 码、搜索能力强的优点，本文将主要以遗传算法为基础，通过与其他算法相 结合或引入其他算法中的算子，生成适用于多级多项目批量问题的改进算法。 2 2 1遗传算法 遗传算法起源于对生物系统进行计算机模拟研究，是2 0 世纪6 0 年代由 美国m i c h i g a n 大学的h o l l a n d 教授及其学生们创造出了一种基于生物进化机 制的自适应概率优化技术。 2 2 1 1 遗传算法中常用术语遗传算法在求解批量问题时常用到的术语有染 色体、基因、编码、解码、适应度、种群、搜索空间等，下面对其说明。 1 染色体染色体是所求解问题的基本对象，是批量问题的一个解，通 常由一个二进制数组表示，如各个项目在计划期内各个时段的生产调整操作 世 奇o 2 基因基因是染色体上的一个最小的单位，一般为单个参数的编码值。 如以各个项目在各时段的生产调整操作作为染色体时，基因就是一个项目在 某一时段上的生产调整操作状态。 3 编码、解码编码为从一个解根据其编码规则，生成的染色体的过程。 解码就是编码的逆过程。如在染色体中假设的编码方式，编码就是有一个解 到生产调整变量的二进制数组的过程，解码正好相反。 4 适应度适应度是反映染色体个体性能优劣的数量值，表示某一个个 体对于生存环境的适应程度。在新种群生成过程中，染色体的适应度起着重 哈尔滨理工人学工学硕士学位论文 要的作用，种群经常按照染色体的适应度的高低决定它的繁殖机率。适应度 函数的优劣往往左右着一个算法的质量。在对批量问题求解时，适应度函数 一般由一个染色体解码后的解所产生的生产、库存及调整费用等的总成本来 计算。如将所求总成本幂函数作为适应度函数，增加各个解之间总成本的差 距等方法。当然适应度函数也会为新种群的生成带来负面影响，如上面提到 的以总成本的幂函数作为适应度函数的表现形式，使高适应度的染色体得到 较大繁殖概率的同时也加速了早熟，要合理的避免这类现象也是遗传算法研 究中的热点。 5 种群、解空间种群是一代染色体的总和，解空间是由所有解( 包括 可行解和不可行解) 的总和。如何利用数量相对较小的种群来有效的搜索整 个解空间是批量问题算法研究的热点。 2 2 1 2 标准遗传算法流程标准遗传算法是其他改进遗传算法的基础，它的 遗传算子的思想对其后的各种改进算法有重要影响。 图2 1 为标准遗传算法的算法流程。其中各个过程完成的功能如下： 1 群体初始化其主要任务就是生成初代种群。求解批量问题时，初始 种群一般由先验经验或随机生成。初始解的质量往往决定着一个算法的求解 速度和最终解的质量。 2 计算个体适应度对种群中的每个染色体计算其适应度。作为进行遗 传算子操作和生成新种群的依据。 3 选择根据每个染色体的适应度和选择原则进行复制操作。低适应度 的染色体在这个阶段被淘汰，高适应度的染色体被复制保留到下一代种群之 中。 4 交叉算子及变异算子遗传算法的优秀的收敛性主要取决于遗传算子 的交叉和变异操作，交叉算子是遗传算法具有较强的全局搜索能力，变异算 子是遗传算法具有较强的局部搜索能力。交叉是以一定的概率对两个染色体 的部分基因进行交换操作产生新的染色体。根据变异原则和变异概率对染色 体的部分基因实施变异操作，如在对二进制编码的批量问题进行计算时，变 异操作一般是对染色体的某位基因进行去反操作。标准遗传算法的交叉和变 异概率一般是个定值，但对于自适应遗传算法可以采用动态的方式调整交叉 和变异的概率，动态控制进化策略。 哈尔滨理t 大学t 学硕： ：学位论文 图2 1 标准遗传算法流程图 f i g 2 1f l o wc h a r to ft y p i c a lg e n e t i ca l g o r i t h m 有以下算法内容将在第三章和第四章的讨论中被用到。 2 2 2自适应遗传算法 自适应算法是对标准遗传算法的改进形式，其主要思想是对标准遗传算 法中的遗传算子的概率进行动态调节，可以有助于改善早熟问题、锯齿问题 等标准遗传算法的弊病。 自适应遗传算法从以下两方面对标准遗传算法进行改进。 首先，采用自适应交叉概率和自适应变异概率根据染色体适应度、进化 代数对染色体的交叉和变异概率进行动态调节。式( 2 5 ) 是典型的自适应交叉 概率p 。的表达式，式( 2 - 6 ) 自适应变异概率p m 的表达式。 扫。ipc_m。ix姓gen_cur,1b!msgen m a