动态批量与预测时阈

第1章　理论基础 1.1　WW模型与预测时阈 美国Management Science（《管理科学》）杂志在创刊50周年之际（2004年），评选出50年*具影响力的10篇文章（Hopp，2004），其中一篇为Wagner和Whitin在1958年发表的“Dynamic version of the economic lot size model”（经济批量模型的动态形式）。在这一开创性的文章中，研究了企业单产品生产计划中的动态批量问题：企业的目标是优化生产决策使 个周期总成本*小，这就是著名的WW（Wagner-Whitin）模型。文章有两个*主要的贡献：①提出了零库存性质，在零库存性质的基础上设计了 时间的前向动态规划算法；②利用前向动态规划算法解决了预测时阈（forecast horizon）问题（文中用计划时阈（planning horizon）的概念）。 Wagner于2004年专门撰写了关于这篇开创性文章的评论（Wagner，2004），介绍了构建WW模型的背景、过程、理论与实践价值以及未来拓展的方向。在Wagner和Whitin所处的20世纪50年代，采用平方根公式的经济订货批量（economic order quantity，EOQ）模型被普遍采用以解决成本和需求非时变（稳定）的订货批量问题。平方根公式能够较好地平衡订货批量问题中的库存成本和启动成本。Wagner和Whitin充分肯定了经济订货批量模型以及平方根公式的重要价值。然而，当放松成本和需求参数非时变这一假设后，即成本和需求参数时变情形下，再利用平方根公式（计算平均需求和成本）求得的近似解与*优解误差较大。在此背景下，Wagner和Whitin放松了经济订货批量问题的假设，构建了经济批量模型的动态形式，即动态批量（dynamic lot size，DLS）模型。 在WW模型构建中定义的符号如表1-1所示。 企业的目标是在 周期之内达到生产启动成本、变动生产成本、库存成本之和*小。目标函数表示为 （1-1） 约束条件为 （1-2） （1-3） （1-4） 约束条件（1-2）表示产品的库存平衡；约束条件（1-3）表示生产数量和库存数量大于等于零；约束条件（1-4）表示期初和期末两种产品的库存均为零。 在WW模型中目标函数呈现的是一种简化形式，在单位生产成本非时变的情形下，由于 个周期的需求全部满足， ，又因为为常数，即个周期变动生产成本之和为常数，所以目标函数（1-1）中变动成本项可以去掉，目标函数可以简写为 。 以上描述的动态批量问题的*优解中存在如下结构性质。 定理1-1　在的*优解中，对于任意周期t，有如下性质成立：。 定理1-1是著名的零库存性质，即若任意周期 的生产数量大于零，则前一期期末库存为零；若前一期期末的库存不为零，则当期生产数量为零。根据此定理，又可得到以下推论。 推论1-1　在的*优解中，对于任意周期t，有 或 成立。 推论1-1说明任意周期t的生产数量要么为零，要么等于未来整数周期的需求之和。 下面给出生产点和再生点的定义。 定义1-1　给定的*优解，若，则周期 定义为再生点。 定义1-2　给定的*优解，若 ，则周期 定义为生产点。 由零库存性质可得，若周期为生产点，则周期为再生点。 根据定理1-1和推论1-1能够设计出时间复杂度为 的前向动态规划算法。令 为 的*优成本，表示*后一个生产点是 时 的*优成本，根据以上定义可得 （1-5） 而 （1-6） 令 为 中*优的*后一个生产点。Wagner和Whitin（1958a）阐述了如下预测时阈结果。 定理1-2　在的*优解中，若，则周期为预测时阈，周期为决策时阈。 此定理说明在单位生产成本非时变的情形下，当*优的*后一个生产点恰好是结束周期时，结束周期 即预测时阈，周期 即决策时阈，也就是第期的*优决策都不受周期 之后数据信息的影响。 然而，WW模型有诸多很强的假设条件，如单位生产成本是非时变的、不允许需求延迟、不允许需求损失、不考虑生产能力和仓储能力约束、企业的需求是外生的、没有考虑多产品生产情形等。由于WW模型有很强的假设条件，不完全符合企业现实的生产情况，因此后续大量学者通过不断放松WW模型中的假设使其更加接近现实情况。放松假设的过程中，学者研究动态批量问题的侧重点不尽相同，如定价订货联合决策的动态批量问题、多决策主体的动态批量问题等。然而，预测时阈也伴随着动态批量拓展问题的研究得到了深入研究。另外，预测时阈思想还被拓展到多个研究领域。 在一些复杂约束下的动态批量问题中，如需求时间窗的动态批量问题、制造和再制造的动态批量问题等，预测时阈的求解十分困难，因此这类动态批量问题的研究主要聚焦于*优解结构性质的证明与算法设计，并没有探讨预测时阈。在以下的内容中针对动态批量问题的拓展研究和预测时阈问题的拓展研究分别加以阐述，其中动态批量问题的拓展研究中所涉及的文献均未分析预测时阈。 1.2　动态批量拓展研究 以下归纳的6类动态批量拓展研究是近年来企业生产运营过程中遇到的主要问题，也是企业亟须解决的主要问题。正是因为企业有真实存在的难题需要解决，所以以下6类拓展问题也是近20年来动态批量问题研究的热点，高频次地出现在国际主流期刊上。 1.2.1　*小批量约束的动态批量研究 由于在企业生产或采购活动中存在高额的启动成本，为了实现规模经济效应，规定*小批量生产和采购的方式是企业常用的方式之一。与生产能力上限约束相对应，*小生产批量约束是生产能力下限约束。Anderson和Cheah（1993）分别研究了生产能力约束和*小生产批量双重约束下的单产品和多产品动态批量决策问题，分别设计了启发式算法求解多产品情形的*优动态批量和动态规划算法求解单产品情形的*优动态批量。Constantino （1998）利用有效不等式的方法求解了多产品和单产品在*小生产批量约束下的动态批量问题。在无采购能力约束和有采购能力约束两种情形下，Okhrin和Richter（2011a，2011b）进一步研究了Anderson和Cheah（1993）提出的单产品*小采购批量约束的动态批量问题，在证明*优解性质的基础上设计了多项式时间的动态规划算法。在生产和库存成本为凹函数的情形下，Hellion等（2012，2013，2014）考虑了有生产能力和*小生产批量约束下的单产品动态批量决策问题并设计了多项式时间的动态规划算法。在Constantino（1998）的研究基础上，Park和Klabjan（2015）利用有效不等式方法求解了单产品在*小生产批量约束下的动态批量问题。Goerler和Vo?（2016）考虑了有缺陷产品返工和*小批量约束的动态批量决策问题。运用数值实验验证了混合整数规划算法求解此问题的效率。另外，Lee（2004）以及Porras和Dekker（2006）分别从不同角度研究了单产品与多产品在*优批量约束下的动态批量决策问题。 1.2.2　需求时间窗约束的动态批量研究 在经典的动态批量模型中有一个基本的假设，即企业面临的某一周期的需求是一个加总的需求，但是没有考虑需求的宽限期。在企业的实际运作中，客户的需求往往存在一个宽限期，即需求带有时间窗，满足在时间窗内的需求不产生库存和延迟成本，时间窗不同的需求不能加总。Lee等（2001）*早研究了单位生产成本非时变下需求带时间窗约束的动态批量问题，在需求允许延迟与不允许延迟两种情形下分别设计了多项式时间的动态规划算法。在持有库存与延迟交货没有投机性动机的假设下，Jaruphongsa等（2004a）考虑了需求带时间窗约束的两级动态批量问题，在*优解的基础上设计了多项式时间的动态规划算法求解此问题。在Jaruphongsa等（2004a）研究的基础上，Jaruphongsa等（2004b）又进一步将模型拓展到了存在仓储能力约束的情形。在非时变的单位生产成本下，Wolsey（2006）考虑了无生产能力约束和有非时变生产能力约束下的需求带时间窗约束的动态批量问题，利用定义凸二部图的方法求解了两类问题。Brahimi等（2006）研究了多产品共用有限时变生产能力下的需求带时间窗约束的动态批量问题，设计了启发式算法求解此问题。另外，在时变和非时变的单位生产成本下，指出单产品问题有多项式时间的算法。Hwang和Jaruphongsa（2006）给出了一种求解时变成本下需求带时间窗约束的动态批量问题的新方法。Hwang（2007a，2007b）通过研究改进了Hwang和Jaruphongsa（2006）中问题的算法复杂度。Akbalik和Penz（2011）考虑了一个生产能力约束且需求带时间窗约束的两级动态批量问题，设计了一类启发式算法求解了该问题，并用数值实验验证了算法的效率。更多的需求带时间窗约束的动态批量问题的研究可参见相关文献（Absi et al.，2011；Hwang et al.，2010；Hwang and Jaruphongsa，2008；Jaruphongsa and Lee，2008）。 1.2.3　生产启动成本具有学习效应的动态批量研究 生产启动的学习效应是指生产启动成本随着生产启动次数的增加而降低的现象，出现这种现象源于工人在生产启动上的学习和生产启动方法的改进。Chand（1989）指出部分企业和行业小批量生产能获得更多的收益，而工人的学习效应可以提高生产过程的质量与柔性、降低生产启动成本，促使企业小批量生产成为可能。Malik和Wang（1993）在单位生产成本时变的条件下研究了生产启动具有学习效应的动态批量问题，在*优解性质的基础上设计了高效动态规划算法求解该问题。Rachamadugu和Schriber（1995）设计了启发式算法求解生产启动成本具有学习效应的动态批量问题。Teyarachakul等（2008）在需求非时变的假设下考虑了生产启动具有学习和遗忘双重效应的动态批量问题。Teyarachakul等（2011）拓展了Teyarachakul等（2008）的研究，进一步考虑了时变需求下的生产启动具有学习和遗忘双重效应的动态批量问题。Chiu（1997）、Chiu等（2003）、Chiu和Chen（2005）也从不同角度研究了生产启动具有学习和遗忘双重效应的动态批量问题。另外，更多的生产启动具有学习效应的动态批量问题的研究可参见相关文献（Tsai，2011；Cohen et al.，2006；Jaber and Bonney，2003；Hoesel and Wagelmans，2000）。 1.2.4　再制造情形下的动态批量研究 对产品进行回收和再制造，能够有效地降低资源消耗和环境污染，提高资源利用率，在低碳经济这一背景下，企业开始重视产品使用后的回收、库存与再制造等问题。因为回收产品的再制造是制造型企业实现企业行为与环境相融的重要手段，因此再制造问题也开始受到学术界的重视（Gungor and Gupta，1999；Laan and Salomon，1997）。Richter和Sombrutzki（2000）研究了三类再制造动态批量模型：不考虑产品回收再制造模型、考虑产品回收再制造模型、考虑制造和回收产品再制造协同模型。在回收旧产品数量无限大的假设下指出了零库存性质在三类模型中都是成立的，依据零库存性质设计了前向动态规划算法。Richter和Weber（2001）又探讨了Richter和Sombrutzki（2000）中的三类模型成本和需求参数非时变的特殊情形。Golany等（2001）考虑了一个综合不可用回收产品处理过程、可用回收