This paper addresses a dynamic lot sizing problem with bounded inventory and stockout where both no backlogging and backlogging allowed cases are considered. The stockout option means that there is outsourcing in a pe...This paper addresses a dynamic lot sizing problem with bounded inventory and stockout where both no backlogging and backlogging allowed cases are considered. The stockout option means that there is outsourcing in a period only when the inventory level at that period is non-positive. The production capacity is unlimited and production cost functions are linear but with fixed charges. The problem is that of satisfying all demands in the planning horizon at minimal total cost. We show that the no backlogging case can be solved in O（T^2） time with general concave inventory holding and outsourcing cost functions where T is the length of the planning horizon. The complexity can be reduced to O（T） when the inventory holding cost functions are also linear and have some realistic properties, even if the outsourcing cost functions remain general concave functions. When the inventory holding and outsourcing cost functions are linear, the backlogging case can be solved in O（ T^3 logT） time whether the outsourcing level at each period is bounded by the sum of the demand of that period and backlogging level from previous periods, or only by the demand of that period.展开更多
基金Acknowledgments This work is supported by the National Natural Science Foundation of China （No. 71171072, 71301040）. The authors are thankful to two anonymous referees and the editor for their constructive comments, which resulted in the subsequent improvement of this article.
文摘This paper addresses a dynamic lot sizing problem with bounded inventory and stockout where both no backlogging and backlogging allowed cases are considered. The stockout option means that there is outsourcing in a period only when the inventory level at that period is non-positive. The production capacity is unlimited and production cost functions are linear but with fixed charges. The problem is that of satisfying all demands in the planning horizon at minimal total cost. We show that the no backlogging case can be solved in O（T^2） time with general concave inventory holding and outsourcing cost functions where T is the length of the planning horizon. The complexity can be reduced to O（T） when the inventory holding cost functions are also linear and have some realistic properties, even if the outsourcing cost functions remain general concave functions. When the inventory holding and outsourcing cost functions are linear, the backlogging case can be solved in O（ T^3 logT） time whether the outsourcing level at each period is bounded by the sum of the demand of that period and backlogging level from previous periods, or only by the demand of that period.
