带分段仓储能力决策的动态批量优化问题研究
|
摘要
本文考虑一个单一产品仓储能力决策和库存决策的动态批量集成优化问题.在这个模型中,长度为T个周期的计划期被划分成连续的若干段,每段初需制定该段的仓储能力决策,同一段中各期的期末库存水平均受限于该段仓储能力.假设每段仓储能力费用为仓储能力的非减函数,各期的产品订货费用为固定费用,库存保管费用是一个期末库存量的线性函数.利用分解技术和几何技术,本文开发一个计算复杂度为O(T~3)的动态规划算法.计算测试显示,该算法与求解混合整数规划(MIP)的商业软件相比,在计算时间上具有明显的优势.
A single item dynamic lot sizing problem integrated with storage capacity and inventory decisions is considered. Given a T-periods planning horizon being partitioned into a series of sections,storage capacity decisions are made at the beginning of each section, and the ending inventory of each period is limited by the storage capacity of section containing it. Assume that section storage capacity cost is a non-decreasing function, ordering cost is a fixed charge, and holding cost is a linear function. By applying decomposition techniques and geometric techniques, an O(T~3) algorithm is presented. Comparing with commercial MIP solver, the saving in computation times of this algorithm is excellent.
A single item dynamic lot sizing problem integrated with storage capacity and inventory decisions is considered. Given a T-periods planning horizon being partitioned into a series of sections,storage capacity decisions are made at the beginning of each section, and the ending inventory of each period is limited by the storage capacity of section containing it. Assume that section storage capacity cost is a non-decreasing function, ordering cost is a fixed charge, and holding cost is a linear function. By applying decomposition techniques and geometric techniques, an O(T~3) algorithm is presented. Comparing with commercial MIP solver, the saving in computation times of this algorithm is excellent.
引文
[1]Wagner H M,Whitin T M.A dynamic version of the economic lot size model[J].Management Science,1958,5(1):89-96.
[2]Aggarwal A,Park J K.Improved algorithms for economic lot-size problems[J].Operations Research,1993,41(3):549-571.
[3]Federgruen A,Tzur M.A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(nlogn)or O(n)time[J].Management Science,1991,37(8):909-925.
[4]Wagelmans A P M,van Hoesel C P M,Kolen A W J.Economic lot-sizing:An O(nlogn)algorithm that runs in linear time in the Wagner-Whitin case[J].Operations Research,1992,40(1):145-156.
[5]Brahimi N,Dauzere-Peres S,Najid N M,et al.Single item lot sizing problems[J].European Journal of Operational Research,2006,168(1):1-16.
[6]Liu X,Tu Y L.Production planning with limited inventory capacity and allowed stock out[J].International Journal of Production Economics,2008,111(1):180-191.
[7]Love S F.Bounded procurement and inventory models with piecewise concave costs[J].Management Science;1973,20(3):313-318.
[8]Atamturk A,Kiigiikyavuz S.An O(n~2)algorithm for lot sizing with inventory bounds and fixed costs[J].Operations Research Letters,2008,36(3):297-299.
[9]Chu F,Chu C.Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing[J].IEEE Transactions on Automation Science and Engineering,2007,4(2):233-251.
[10]Chu C,Chu F,Zhong J,et al.A polynomial algorithm for a lot-sizing problem with backlogging,outsourcing and limited inventory[J].Computers&Industrial Engineering,2013,64(1):200-210.
[11]戴道明.考虑库存能力约束的批量问题与定价的联合决策[J]·系统工程,2010,28(2):90-94.Dai D M.Joint optimal dynamic pricing and lot sizing problem with inventory capacities[J].Systems Engineering,2010,28(2):90-94.
[12]黄玲,钟金宏,杨善林.考虑延期交货、转包和非减库存能力约束的单产品批量模型[J].系统工程理论与实践,2007,27(9):87-96.Huang L,Zhong J H,Yang S L.Single item lot sizing models with backlogging and outsourcingand non-decreasing inventory capacity[J].Systems Engineering—Theory&Practice,2007,27(9):87-96.
[13]Hwang H C,van den Heuvel W.Improved algorithms for a lot-sizing problem with inventory bounds and backlogging[J].Naval Research Logistics,2012,56(3-4):244-253.
[14]Hwang H C,van den Heuvel W,Wagelmans A P M.The economic Jot-sizing problem with lost sales and bounded inventory[J].IHE Transactions,2013,45(8):912-924.
[15]王能民,张秋爽.库存能力有限的再制造批量决策[J].运筹与管理,2008,17(3):7-15.Wang N M,Zhang Q S.Decision for lot sizing problem with remanufacturing and bounded inventory[J].Opera?tions Research and Management Science,2008,17(3):7-15.
[16]Atamtiirk A,Hochbaum D S.Capacity acquisition,subcontracting,and lot sizing[J].Management Science,2001,47(8):1081—1100.
[17]Bradley J R,Arntzen B C.The simultaneous planning of production,capacity,and inventory in seasonal demand environments[J].Operations Research,1999,47(6):795-806.
[18]Chen H D,Hearn D W,Lee C Y.A dynamic programming algorithm for dynamic lot size models with piecewise linear costs[J].Journal of Global Optimization,1994,4(4):397-413.
[19]Van Hoesel C P M,Wagelmans A P M,Moerman B.Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions[J].European Journal of Operational Research,1994,75(2):312-331.
[20]Mark G,Ou J,Teo C P.Warehouse sizing to minimize inventory and storage costs[J].Naval Research Logistics,2001,48(4):299-312.
[21]Koca E,Yaman H,Selim Akturk M.Lot sizing with piecewise concave production costs[J].INFORMS Journal on Computing,2014,26(4):767-779.
[22]马利军,葛羊亮,薛巍立,等.不确定环境下损失厌恶零售商的提前支付决策[J]·系统工程理论与实践,2015,35(2):315-323.Ma L J,Ge Y L,Xue W L,et al.Analysis of advanced payment strategy for the loss-averse retailer under uncertainties[J].Systems Engineering—Theory&Practice,2015,35(2):315-323.
[23]Gong X,Chao X,Simchi-Levi D.Dynamic inventory control with limited capital and short-term financing[J].Naval Research Logistics,2014,61(3):184-201.
[24]于辉,马云麟.订单转保理融资模式的供应链金融模型[J].系统工程理论与实践,2015,35(7):1733-1743.Yu H,Ma Y L.The supply chain finance model—Based on the order-to-factoring mode[J].Systems Engineering-Theory&Practice,2015,35(7):1733-1743.
[2]Aggarwal A,Park J K.Improved algorithms for economic lot-size problems[J].Operations Research,1993,41(3):549-571.
[3]Federgruen A,Tzur M.A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(nlogn)or O(n)time[J].Management Science,1991,37(8):909-925.
[4]Wagelmans A P M,van Hoesel C P M,Kolen A W J.Economic lot-sizing:An O(nlogn)algorithm that runs in linear time in the Wagner-Whitin case[J].Operations Research,1992,40(1):145-156.
[5]Brahimi N,Dauzere-Peres S,Najid N M,et al.Single item lot sizing problems[J].European Journal of Operational Research,2006,168(1):1-16.
[6]Liu X,Tu Y L.Production planning with limited inventory capacity and allowed stock out[J].International Journal of Production Economics,2008,111(1):180-191.
[7]Love S F.Bounded procurement and inventory models with piecewise concave costs[J].Management Science;1973,20(3):313-318.
[8]Atamturk A,Kiigiikyavuz S.An O(n~2)algorithm for lot sizing with inventory bounds and fixed costs[J].Operations Research Letters,2008,36(3):297-299.
[9]Chu F,Chu C.Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing[J].IEEE Transactions on Automation Science and Engineering,2007,4(2):233-251.
[10]Chu C,Chu F,Zhong J,et al.A polynomial algorithm for a lot-sizing problem with backlogging,outsourcing and limited inventory[J].Computers&Industrial Engineering,2013,64(1):200-210.
[11]戴道明.考虑库存能力约束的批量问题与定价的联合决策[J]·系统工程,2010,28(2):90-94.Dai D M.Joint optimal dynamic pricing and lot sizing problem with inventory capacities[J].Systems Engineering,2010,28(2):90-94.
[12]黄玲,钟金宏,杨善林.考虑延期交货、转包和非减库存能力约束的单产品批量模型[J].系统工程理论与实践,2007,27(9):87-96.Huang L,Zhong J H,Yang S L.Single item lot sizing models with backlogging and outsourcingand non-decreasing inventory capacity[J].Systems Engineering—Theory&Practice,2007,27(9):87-96.
[13]Hwang H C,van den Heuvel W.Improved algorithms for a lot-sizing problem with inventory bounds and backlogging[J].Naval Research Logistics,2012,56(3-4):244-253.
[14]Hwang H C,van den Heuvel W,Wagelmans A P M.The economic Jot-sizing problem with lost sales and bounded inventory[J].IHE Transactions,2013,45(8):912-924.
[15]王能民,张秋爽.库存能力有限的再制造批量决策[J].运筹与管理,2008,17(3):7-15.Wang N M,Zhang Q S.Decision for lot sizing problem with remanufacturing and bounded inventory[J].Opera?tions Research and Management Science,2008,17(3):7-15.
[16]Atamtiirk A,Hochbaum D S.Capacity acquisition,subcontracting,and lot sizing[J].Management Science,2001,47(8):1081—1100.
[17]Bradley J R,Arntzen B C.The simultaneous planning of production,capacity,and inventory in seasonal demand environments[J].Operations Research,1999,47(6):795-806.
[18]Chen H D,Hearn D W,Lee C Y.A dynamic programming algorithm for dynamic lot size models with piecewise linear costs[J].Journal of Global Optimization,1994,4(4):397-413.
[19]Van Hoesel C P M,Wagelmans A P M,Moerman B.Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions[J].European Journal of Operational Research,1994,75(2):312-331.
[20]Mark G,Ou J,Teo C P.Warehouse sizing to minimize inventory and storage costs[J].Naval Research Logistics,2001,48(4):299-312.
[21]Koca E,Yaman H,Selim Akturk M.Lot sizing with piecewise concave production costs[J].INFORMS Journal on Computing,2014,26(4):767-779.
[22]马利军,葛羊亮,薛巍立,等.不确定环境下损失厌恶零售商的提前支付决策[J]·系统工程理论与实践,2015,35(2):315-323.Ma L J,Ge Y L,Xue W L,et al.Analysis of advanced payment strategy for the loss-averse retailer under uncertainties[J].Systems Engineering—Theory&Practice,2015,35(2):315-323.
[23]Gong X,Chao X,Simchi-Levi D.Dynamic inventory control with limited capital and short-term financing[J].Naval Research Logistics,2014,61(3):184-201.
[24]于辉,马云麟.订单转保理融资模式的供应链金融模型[J].系统工程理论与实践,2015,35(7):1733-1743.Yu H,Ma Y L.The supply chain finance model—Based on the order-to-factoring mode[J].Systems Engineering-Theory&Practice,2015,35(7):1733-1743.