一种改进的MRP批量决策的优化模型与算法研究

一种改进的MRP批量决策的优化模型与算法研究①陈志祥②，贺铁牛（中山大学管理学院，广州，510275）摘要：制造资源计划MRPII中物料需求计划MRP的决策是一个核心模块。传统的MRP计算方法不能适应市场波动与顾客需求的不同变化带来的影响，本文考虑现实的供应环境与需求特点，建立一种改进的物料需求计划的优化模型。模型引入了价格、订货成本、持有成本等供应信息辅助决策，考虑了可能出现的流动资金和安全库存的约束；并且充分考虑MRP净需求是离散性的特点，使生产过程的批量决策动态响应外部环境的变化。关键词：物料需求计划，批量，优化模型中图分类号：文献标识码：文章编号：0．引言物料需求计划（MaterialRequirementsPlanning,MRP）是上个世纪六十年代初期在美国开始出现的，应用计算机来计算物料需求和制订生产作业计划的一种方法。1975年，美国生产管理专家Orlicky编写了有关MRP的权威性专著，系统提出了初期MRP的思想和完整的工作逻辑，其出发点是根据对成品的需求，自动地计算出构成这些成品的部件、零件，以至原材料的相关需求量；由成品的交货期计算出各部件、零件生产进度日程与外购件的采购日程。在初期MRP的基础上，引入资源计划与保证、安排生产、执行监控与反馈等功能，即形成闭环的MRP系统（Closed-loopMRP）。欧美生产管理专家对传统MRP的研究最早，发现传统MRP系统中存在的问题也是最早。Kadipasaoglu（1995）指出，传统的MRP系统存在很多缺陷和不足，其中造成不稳定性最显著的两点是：（1）传统的MRP系统假设环境是确定的；（2）传统的MRP很少考虑如何供应链之间的合作需要。K.vanDonselaar（2000）论述了造成MRP系统不稳定的三个因素：批量、需求的不确定、产品。Jagannathan（1998）研究了批量与提前期相关的MRP处理方法，在研究中分别应用了混合的0－1规划、动态规划、拉格朗日松弛法建立模型，并用随机产生的参数值验证了结果。Gaafar等（2000）提出了用人工神经网络解决批量问题的方法，但是，由于神经网络主要对知识背景不清楚和推理机制不明确的非结构化问题非常有效，而批量策略可以以成本或库存为目标建立精确的模型，因此用神经网络解决批量问题的方法并没有得到推广。Gutierrez等（2002）研究了有库存限制的动态批量问题，通过建立动态规划模型并引出相关推论，证明了其模型算法的优越性并给出了算例，对传统的静态环境、无约束条件的批量算法作出了较大改进。在MRP批量策略改进研究方面，国内学者也进行了研究.针对传统MRP在市场波动的环境下运行欠佳的问题，蓝伯雄（2004）、谢沁华（2004）等指出，传统MRP在系统设计上存在先天性的缺陷，主要是优化机制、批量和提前期计算、无限能力假设等方面。谢沁华、孙先锦（2004）从MRP系统内部进行分析，认为传统MRP在批量计算上存在缺陷，对采购批量的确定提出用ABC分类法改进，对作业批量的确定提出两种方法：（1）利用数学模型来确定最优作业批量，决策目标是使生产成本最小；（2）采用JIT的拉动式作业来代替MRP的推动式作业，以解决在制品库存过多的问题。梁梁、余玉刚（2005）等人提出了一种MRP进货批量决策模型，该模型充分考虑了MRP的需求是离散性的特点，采取在每个计划期初发问“是否要定货，定多少货”的方式给定货批量作出决策，以达到总费用最小。与其他研究不同的是，本文考虑现实的供应环境与需求特点，建立一种改进的物料需求计划的优化模型，①项目基金资助：国家自然科学基金（70271023，70672078）②作者简介：陈志祥（1966-），男，广西陆川人，中山大学管理学院副教授，博士。研究方向：现代生产管理理论与方法，email:[e-mail],020-84036133为此引入了供应信息辅助决策，考虑了可能出现的流动资金和安全库存的约束；并且充分考虑MRP净需求是离散性的特点。使生产过程的批量决策动态响应外部环境的变化。1问题描述一般而言，在现实环境下，制造企业的生产物料的供应价格在不同期间可能会因市场波动和顾客需求而有所不同，订货成本可能会由于供应商的更换或调整而波动，持有成本也有可能随季节、假日等不断变化；同时，在每个期间的采购和订货费用可能受到流动资金不足的约束，各种物料的库存水平也有可能需要考虑企业安全库存数量的要求。但是传统的MRP批量决策模型没有考虑这些因素，因此得到的订货批量显然不是最佳的。本文考虑现实的供应环境与需求特点，建立一种改进的物料需求计划的优化模型，为此：（1）引入了价格、订货成本、持有成本等供应信息辅助决策，考虑了可能出现的流动资金和安全库存的约束；（2）充分考虑MRP净需求是离散性的特点，在每个时段的期初做出决策：是否需要订货以及订货数量，动态响应外部环境的变化；（3）目标是计划期内的成本最小化。2．模型与算法2．1模型构建本文建立改进后MRP订货批量决策的数学模型如下：（1）模型下标i－物料代号（i＝1，2，…，I）；t－时段代号（t＝1，2，…，T）；m－时段代号；（2）模型参数I－通过BOM表汇总后需要外购的物料总数；T－主生产计划制订的生产周期；Li－物料i的订货提前期；Dit－物料i在时段t的需求量；Sit－物料i在时段t的在途库存；Si0－物料i在i＝1的期初库存（即i＝0期的期末库存）；Oit－物料i在时段t的一次订货费用；Hit－单位物料i在时段t的持有成本；Pit－物料i在时段t的供应价格；Ft－在t时段的流动资金约束；Savit－物料i在时段t的安全库存量；M－一个很大的正数。（3）模型变量（Xit）－是0－1决策变量，表示在第t－L时段期初决定物料i是否订货，即在第t周是否支付订货款；Qit－是连续决策变量，表示在第t－L时段期初决定物料i在第t周订多少货；Invit－物料i在时段t的库存量。（4）目标函数minTC=IiTtititXO11)(+IiTLtititiQP11+IiLtititiSP11+IiTtititHInv11（1）式中，mtiititiLtmLtiiititititiitLtIiDSSTLLtIiDQDSSInvii10110),...,2,1;,...,2,1(),(),...,2,1;,...,2,1(),()(（5）约束条件0≤Qit≤（Xit）M（i＝1，2，…，I；t＝1，2，…，T）（2）（说明：各物料在各期的订货量不能为负数，不能超过最大供应量约束）IiititXO1)(+IiititQP1+IiititSP1+IiTtititHInv11≤Ft（t＝1，2，…，T）（3）（说明：每个时段的各物料总费用不能超过该时段的流动资金约束）iiLtmLtititititiDQDSS110)()(≥0（i＝1，2，…，I；m＝Li＋1，Li＋2，...，T）（4）（说明：各物料的各个时段的期末库存量不能为负数）Savit≤Invit（i＝1，2，…，I；t＝1，2，…，T）（5）（说明：各物料在每个时段的库存量不能低于安全库存量）10)(itX（i＝1，2，…，I；t＝1，2，…，T）（6）（说明：各物料在各时段决策是否订货，是为1，否为0，其结果影响订货费用）（6）模型说明在目标函数中，TtIiititXO11)(代表各物料在各个时段所要支付订货费用的总和；IiTLtititiQP11代表在本周期内订货并收到的物料采购总成本；IiLtititiSP11代表已在上个周期订货、但在本周期内收到的在途库存物料采购总成本；IiTtititHInv11代表各物料在各时段的持有总成本；IiTLmimLtmLtititititiiiiHDQDSS11110)()(代表所有物料在本MPS周期的前L期以后的总持有成本；IiLmimmtititiiHDSS1110)(代表所有物料在本MPS周期的前L期的总持有成本。由于所有物料在本MPS周期的前L期的期末库存量已经在上一个MPS周期里确定下来了，因此现有模型不必有各种物料在本MPS周期的前L期期末库存量大于零的约束。2．2模型求解算法本模型是典型的含0-1决策变量的线性规划问题，为了求解方便，本文所用到的算法首先枚举所有0-1决策变量的状态，把它转化成一般的线性规划问题，然后用字典序的修正单纯形法求解。修正单纯形法比一般的单纯形法效率要高，而字典序的修正单纯形法可以处理系统退化的情形，所以本算法是一个较高效而全面的解法。为了提高计算效率，本算法先把各物料独立计算，然后看是否满足资金约束，如果满足，当前的解就是最优解；否则，加入资金约束，重新建立线性规划模型再计算。由于在一般情况下流动资金约束容易满足，这样效率会得到很大提高。图1MRP批量优化模型程序流程图本模型所用到的C++程序流程具体步骤如下：NNYNNY读入数据枚举0-1决策变量的状态e；found=0化成规范形：minC’xAx=b调用字典序修正单纯形法求解有最优解found=1，更新最优解取e的下一个状态e的状态枚举完毕found=1i=1用第i个物料的数据构造独立的线性规划模型i物料总数满足资金约束输出：最优解结束各物料及各阶段的流动资金约束综合起来构造线性规划模型含资金约束的综合模型输出：找不到可行解结束i=i+1NYYYYNStep1先忽略流动资金约束，为各物料建立线性规划模型；Step2枚举决策变量的一个状态，化为对应的最小值线性规划标准型：minz=C’xAx=bStep3调用字典序修正单纯形法求解；Step4待全部物料求解出来后，检验各阶段是否满足流动资金约束，若满足，转6（可以提高计算效率）；否则，转5；Step5把全部物料的各阶段流动资金约束综合起来，重新建立一个线性规划模型，用Step2,3的方法求解.若有解，转6；否则，转7；Step6输出：最优解，程序结束；Step7输出：没有可行解，程序结束。程序流程如图1所示。3．优化模型与传统的批量模型的比较传统的MRP批量政策的前提假设没有考虑在计划期内的物料价格、订货成本、持有成本波动情况和能力约束前提，因此用优化模型与传统MRP批量政策分别计算时，为了便于对比分析，将物料价格、订货成本、持有成本等参数设置为常数，并且不考虑流动资金的约束。因为传统的MRP批量政策没有考虑多种物料采购之间的成本平衡和资金约束，本文只取一种物料的订货批量进行计算对比。从某厂商的生产数据中，得到某物料的总需求计划如表1所示：表1某物料的总需求计划计划期（周）012345678910总需求554540030552005045该物料在计划期内的价格保持稳定，订货成本是110元/次，持有成本是2元/周，第1周初的库存量为55件，生产周期是1周，该物料的订货提前期是1周。试确定该物料的MRP订货批量以使总的费用最低。由于此处的价格是常数，因而在下文对比讨论中考虑的总费用不加说明的话，均为没有考虑该物料成本的总费用。由于传统的MRP订货批量政策均没有约束条件，为了便于对比，此处对改进后的线性模型不设流动资金约束。（1）优化模型方法按照优化后的线性模型代入数据后求解得到得相应MRP净需求计划如表2所示：表2线性规划优化模型得到的MRP净需求计划计划期合计012345678910总需求554540030552005045订货状态（0-1）1001100100订货量85003075009500各期订货费用110001101100011000净需求0450030000500计划收到的订货08500307500950各期期末库存550400002000450各期库存费用0800004000900订货和库存总费用110800110110400110900650（2