This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several proper...This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several properties of the optimal solutions are explored. With the help of these optimality properties, a polynomial time approximation algorithm is developed by a new method. The new method adopts a shift technique to obtain a feasible solution of subproblem and takes the optimal solution of the subproblem as an approximation solution of our problem. The worst case performance for the approximation algorithm is proven to be （4√2 ＋ 5）/7. Finally, an instance illustrates that the bound is tight.展开更多
基金supported by National Natural Science Foundation of China (No. 10671108 and 70971076)Found for the Doctoral Program of Higher Education of Ministry of Education of China (No. 20070446001)+1 种基金Innovation Planning Project of Shandong Province (No. SDYY06034)Foundation of Qufu Normal University (No. XJZ200849)
文摘This paper presents an economic lot-sizing problem with perishable inventory and general economies of scale cost functions. For the case with backlogging allowed, a mathematical model is formulated, and several properties of the optimal solutions are explored. With the help of these optimality properties, a polynomial time approximation algorithm is developed by a new method. The new method adopts a shift technique to obtain a feasible solution of subproblem and takes the optimal solution of the subproblem as an approximation solution of our problem. The worst case performance for the approximation algorithm is proven to be （4√2 ＋ 5）/7. Finally, an instance illustrates that the bound is tight.
