随机批量问题一种新模型及算法.pdfVIP

随机批量问题的一种新模型及算法 姜启源 王全勇 (清华大学应用教学系，北京，100084) 摘要 本文研究髓机需求下，单层多产品、资潭能力受限的批量问题．针对需求和资源 镌力限镧都不确定的桃量问题，基于执行计盈I的策喀提出了一种随机环境下的期望值 模型．鉴于模型的复杂性，采用基于髓机模拟的遗传算法求鼻模型．通过对数值算倒的 数据结果进行方差分析，研究了执行计划的策略对耳标费用的影响．最后．对谤问题的 进一步研究工作进行了展望． 关麓词 随机批量问题，随机环境，髓机模拟，遗传算法 l引言 批量问题是现代生产计划系统(如MRPI)中的重要问题之一。它考虑的是成批生产 中短期或中期生产计划的优化问题。近几十年来，杜会生产生活方式的巨大改变，使得批量 问题的实际背景更加复杂。在某些情形(如产品的需求波动很大)下，确定性批量模型的结果 已经不再适用，迫切需要人们建立随机批量模型，并进行深入研究。 对单产品单台设备独立生产的随机批量问题目前已经研究得相当成熟，见：Bookbinder 与Tann]，Higle口J，Ciarallo等”]。近期的文献大多研究需求随机下的单层多产品能力受限的 Muckstadtu]L“。研究方法主要有两种：(1)采用适当方法(如对目标函数取期望)将随机模型 转化为等价的确定性模型，通过优化算法得出随机问题的生产策略；(2)用确定性模型来近 似随机模型(如对随机因素直接取期望)，然后按确定性模型的算法决定循环生产策略或者 直接采用启发式算法动态地决定下一时段的生产批量． 到目前为止，鉴于随机批量问题的复杂性，绝大部分模型也只考虑了需求的随机性，极 步有同时考虑其它随机因素(如资源能力限制、生产单位产品占用的资源能力等)的。本文将 针对需求和资源能力限制都随机的批量问题，基于执行计划的策略提出一种随机环境下的 期望值模型。采用基于随机模拟的遗传算法对该模型的数值算例进行计算，然后对数据结果 进行方差分析，研究模型中的各种参数和环境因素对目标费用的影响。 2 模型 这里随机环境是指在模型的资源能力约束中，资源能力的随机使得解(生产计划)的可 行域是随机的。相关机会规划‘91一般表示为在不确定环境下极大化事件的机会函数，它给出 一个确定解，但实际中只是要求其尽可能地被执行，模型中没有考虑当解不能执行时如何进 行处理．本文将在建模时就考虑到当解不能执行时的处理方法，从而针对需求和资源能力都 ———]|}骚礓 随机批量问题的一种新模型及算击 277 随机的批量问题建立了随机环境下的期望值模型。 本文以Sox和Muckstadt口1的模型为基础，研究随机需求下、单层多产品、有限生产时 段、资源能力受限的批量问题。模型中用到的符号及其解释如下： Md：执行计划的策略； Xn：所制订计划X中，产品i在时段t的生产量，是决策变量； 贾。：根据Md执行生产计划X，产品i在时段t的实际生产量； y。：根据所制订计划x，资源能力j在时段f的所需量； 以：根据Md执行生产计划x，资源能力j在时段t的实际使用量； 磊：产品i在时段t是否生产的标志，如果宜。0，等于l}否则等于o； D。：产品i在时殷t的需求量，是随机变量；其概率密度函数和概率分布函数分别为 D^(z)和DFao)； U，：资源能力j在时段t的限制，是随机变量；其概率密度函数和概率分布函数分别为 urn(x)和UFnb)； x。产品i的初始库存量； H。尸。：产品i在时段t的单位库存费用和单位缺货惩罚费用； A：生产单位产品i所需的生产资源能力； B。U^：资源能力j在时段t的单位费用和能力限制(可用量)； c．、S，：产品i的生产准备费用和生产准备时间； 丁、Ⅳ、J：计划期总时段数、产品的种类敦和资源能力的种类数； D、x、岩、y、P、u、B为相应的向量表示； 资源能力变量以、yj以及参数s。、^。和u^应使用统一的测量资源能力的单位来表示， 如时间单位小时。对于资源能力的单位费用毋，在实际中总是可以将资源能力按其单位费 用的大小进行排序，因此假设0≤BuBa…毋。，Vf。这里假设多种资源柏力之问可相 互替代，