A Note on an Economic Lot-sizing Problem with Perishable Inventory and Economies of Scale Costs:Approximation Solutions and Worst Case Analysis  

作　　者：Qing-Guo Bai Yu-Zhong Zhang Guang-Long Dong 

机构地区：[1]School of Operations Research and Management Sciences, Qufu Normal University, Rizhao 276826, PRC [2]Haiyang Municipal Public Security Bureau, Haiyang 265100, PRC

出　　处：《International Journal of Automation and computing》2010年第1期132-136,共5页国际自动化与计算杂志（英文版）

基　　金：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);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.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.

关 键 词：Economic lot-sizing problem BACKLOGGING economies of scale function PERISHABLE approximation algorithm 

分 类 号：O241.82[理学—计算数学] F224.0[理学—数学]