MRP_分批计划问题的研究现状与发展(1)

2002年3月第20卷第1期 长沙铁道学院学报JOURNALOFCHANGSHARAILWAYUNIVERSITY No1Mar.2002

文章编号:1000-2499(2002)01-0072-06MRPÒ分批计划问题的研究现状与发展

熊红云,鲁五一,温红艳X(中南大学铁道校区自动化工程研究中心,湖南长沙 410075)

摘 要:生产批量计划问题是MRPÒ(制造资源计划)的一个关键问题,它研究一定计划期内,如何将产品的生产批量和时间在加工项目集上进行分配,并满足一定的性能指标集.该文对MRPÒ生产批量计划问题进行了系统总结,划分了其类型,给出了实际生产中几种典型生产批量计划问题的数学模型及其特点.重点从方法学的角度对有限能力分批计划方法进行了分析和比较,指出了其中存在的问题、解决的途径及进一步的发展趋势.关键词:制造资源计划(MRPÒ);生产批量;能力约束;数学规划中图分类号:T29;F402 文献标识码:A

State-o-fArtinLo-tsizingProblemsofMRPÒXIONGHong-yun,LUWu-yi,WENHong-yan(ResearchCenterforAutomationEngineering,CentralSouthUniversity,Changsha410075,China)

Abstract:Lo-tsizingproblem,whichaddresseshowtodistributethepartbatchesandtimeperiodsoversomeproducingitemsduringthedeterminingtimehorizon,andsubjecttosomeperformanceindexsets,playsakeyroleinimplementingMRPÒ(ManufacturingResourcePlanning).Thispapersummarizesandclassifiesthelo-tsizingproblemofMRPÒ.Byanalyzingandcomparingtheexistingresearchmethodsonlo-tsizingproblems,someusefulidealandmethodologyareproposed.Anditsfuturedevelopingtrendsandresearchdirectionisgivenout.Keywords:manufacturingresourceplanning(MRPÒ);lo-tsizing;capacityconstraining;mathematicalpro-gramming

引 言MRPÒ(ManufacturingResourcePlanning)是目前得到广泛应用的一种生产计划与控制方法,它主要通过有序化的产品结构数据BOM(BillofMaterials)和项目提前期(LeadTime),将最终项目的外部需求(独立需求)逐级扩展到对所有零、部件的需求,然后根据零件的底层码按一定的分批规则确定各项目的最终生产批量.近年来,随着国内外学者对各类批量计划问题研究的不

X收稿日期:2000-06-09作者简介:熊红云(1968-),男,湖南临湘人,中南大学副教授,博士1断深入以及相关学科的发展,涌现出了一些新的生产批量计划理论和方法.本文首先对生产批量计划问题进行表述和分类,对实际生产中经常用到的几种典型模型及其特点进行了分析和总结,并着重从方法学的角度对有限能力分批计划方法(确定性最优化方法、近似/启发式方法、拉格朗日松弛方法、以及随机优化方法等)进行比较,指出其中存在的问题及解决的途径和发展趋势,以指导沿此方向的进一步研究工作.

1 生产批量计划问题的表述及分类1.1 生产批量计划问题的表述总的来说,生产批量计划问题就是在一定计划周期内,将产品的生产批量和时间在加工项目(零部件)集上进行分配,以满足一定的性能指标集.从数学规划的角度来看,生产批量计划问题都可归结为一类混合整数规划问题,表达为在等式或不等式的约束下,对目标函数的优化.典型的生产批量计划问题包括要完成的项目集合,及项目之间的相互需求关系,即物料需求表BOM;项目加工要用到的机床或其它资源,以及机床或资源的可用生产能力;计划的目的是安排不同项目在各个计划周期内的加工批量,使在满足约束条件下,整个计划期内项目总的调整费用和库存费用以及生产加工费用之和为最小.1.2 生产批量计划问题的基本类型早在1913年,Harris就提出了静态环境下定常需求的著名的经济订货批量公式EOQ(Eco-nomicOrderQuantity).1958年,Wanger和Whitin对这一理论进行了开创性的发展,提出了动态环境下需求可变的动态批量计划模型DOQ(DynamicOrderQuantity).在此基础上,人们对生产批量计划的研究逐渐扩展和深入,并开始考虑多项目(Mult-iitem)、多级产品结构(Mult-istage)和有限能力(Capacited)等更复杂的情况,从而形成了生产批量计划的各类问题,具体如表1.表1 生产批量计划问题的基本类型分类原则生产分批计划问题类型需求信息的确定性程度确定性(Deterministic);随机性(Stochastic)外部需求形式静态需求(Static);动态需求(Dynamic)计划期长度有限时期(Limitedhorizon);无限时期(Unlimitedhorizon)项目数量单一项目(Single-item);多项目(Mult-iitem)服务策略和相关成本允许缺货(Backlogallowed);不允许缺货(Backlognotallowed)资源约束情况有限能力(Capactiated);无限能力(Uncapacitated)调整时间是否占用能力考虑调整时间(Setuptime);忽略调整时间(Nosetuptime)生产阶段单一生产阶段(Single-stage);多级生产阶段(Mult-istage)

此外,根据优化目标的不同还可将生产分批计划问题分为:通常情况下目标是在一定时期内生产总费用最小;有些目标值是满足一定的服务水平,如平均周期最小;另外还有一些模型的目标是优化能力的均衡利用率.1.3 几种典型的生产批量计划问题实际生产中一种批量计划问题可能同时包含上述多种基本类型.动态环境下,最简单的问题就是无能力约束的单项目生产分批计划问题ULSP(SingleItemUncapacitdeLotSizingProblem,

73第1期 熊红云等:MRPÒ分批计划问题的研究现状与发展 ULSP)[1].如果在ULSP的基础上加入能力约束,即构成了有能力约束的单件生产批量计划问题.对于多项目生产计划问题,如果项目之间相互不存在需求联系,则为多项目单级生产计划问题CLSP(Mult-iSingle-levelCapacitatedDynamicLo-tsizingProblem),CLSP问题一般考虑能力上的耦合,否则就变成N个ULSP问题.当项目之间存在相关需求时,就构成多级生产计划问题.多级生产阶段根据其产品结构(BOM)还可分为:串行生产结构、组装产品结构以及一般产品结构,分别如图1(a)、(b)、(c)所示.根据能力约束情况,多级生产计划问题又分为多级无能力分批计划问题MLULSP(Mult-ilev-elUncapacitatedLo-tsizingProblem)和有能力约束的多级生产分批计划问题MLCLSP(Mult-iLevelCapacitatedLo-tSizingProblem).

图1 多级产品结构MLCLSP代表了分批计划问题的一般模型,也是目前研究的重点.通常MLCLSP问题可用混合整数规划模型来表示.已知N种不同的项目在给定的计划期T(PlanningHorizon)内各周期t(PlanningPeriods)的外部需求量(独立需求)dit,i=1,2,,,N,t=1,2,,,T,满足假设条件:1)产品的需求必须得到满足,即不允许缺货;2)资源的能力必须得到满足;3)库存费用根据项目在周期末的库存量决定;4)调整时间占用资源能力;5)项目的生产费用系数以及调整、库存费用系数与加工周期无关.则MLCLSP问题的数学模型如下:

MLCLSP:minETt=1ENi=1(hiIit+siYit)(1) s.t:Ii,t-1+Xit-EjIS(i)rijXjt-Iit=dit i=1,2,,,N;t=1,2,,,T(2)

ENi=1(aikXit+bikYit)[Capkt k=1,2,,,R;t=1,2,,,T(3)

Xit-BYit[0 i=1,2,,,N;t=1,2,,,T(4)

Iit,Xit\0 i=1,2,,,N;t=1,2,,,T(5)

YitI{0,1} i=1,2,,,N;t=1,2,,,T(6)

Ii0,IiT=0 i=1,2,,,N(7)

其中已知量:R)))资源数;N)))独立需求项目总数;T)))周期总数;rij)))项目j对项目i的需求系数;S(i))))项目i的紧邻后续节点集;B)))为一大的正数;si)))项目i的调整费用;hi)))项目i在周期t的外部需求量;Capkt)))资源k在周期t的可用生产能力.决策变量为:Xit)))项目i在周期t的加工批量;Iit)))项目i在周期t结束时的库存量;Yit)))项目i在周期t的生产调整变量,YitI{0,1}.

74 长沙铁道学院学报 2002年