Competitive Analysis of Online Lot-Sizing Heuristics with Backlogging under Finite Rolling-Horizon
This paper considers the single-item uncapacitated dynamic lot-sizing problem with backlogging in a finite rolling-horizon environment. By permitting backlogging, which means that the inventories can be negative, the assumption with the first setup in period 1 may be no longer appropriate (1). Instead we develop a simple class of online heuristics with backlogging and use competitive analysis to derive worst-case performance of heuristic. Our analysis shows that the online heuristic with backlogging has a worst-case ratio of at most 2 and this result is best-possible for a finite rolling-horizon.
dynamic lot-sizing problem online algorithm the worst-case ratio
Liu Bin Xin Chunlin Shen Fengwu
School of Economics and Management, Beijing, China Operations Management and Strategic Decision Research Center, Beijing University of Chemical Technology, Beijing, China
国际会议
北京
英文
646-650
2010-11-27（万方平台首次上网日期，不代表论文的发表时间）