A note on an economic lot-sizing problem with perishable inventory and economies of scale costs: Approximation solutions and worst case analysis

被引：7

作者：

Bai Q.-G. ^{[1
]}

Zhang Y.-Z. ^{[1
]}

Dong G.-L. ^{[2
]}

机构：

[1] School of Operations Research and Management Sciences, Qufu Normal University

[2] Haiyang Municipal Public Security Bureau

来源：

International Journal of Automation and Computing | 2010年 / 7卷 / 1期

基金：

中国国家自然科学基金;

关键词：

Approximation algorithm; Backlogging; Economic lot-sizing problem; Economies of scale function; Perishable;

D O I：

10.1007/s11633-010-0132-5

中图分类号：

学科分类号：

摘要：

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. © 2010 Institute of Automation, Chinese Academy of Sciences and Springer-Verlag Berlin Heidelberg.

引用

页码：132 / 136

页数：4

共 7 条

[1]

Hsu V.H., Dynamic economic lot size model with perishable inventory, Management Science, 46, 8, pp. 1159-1169, (2000)

[2]

Hsu V.H., An economic lot size model for perishable products with age-dependent inventory and backorder costs, IIE Transactions, 35, 8, pp. 775-780, (2003)

[3]

Chu L.Y., Hsu V.H., Shen Z.J.M., An economic lot sizing problem with perishable inventory and economic of scale costs: Approximation solutions and worst case analysis, Naval Research Logistics, 52, 6, pp. 536-548, (2005)

[4]

Chan L.M.A., Muriel A., Shen Z.J., Smichi-Levi D., On the effectiveness of zero-inventory-ordering policies for the economic lot sizing model with piecewise linear cost structures, Operations Research, 50, 6, pp. 1058-1067, (2002)

[5]

Yang Z.L., Wang J., Bonsau S., Yang J.B., Fang Q.G., A subjective risk analysis approach of container supply chains, International Journal of Automation and Computing, 2, 1, pp. 85-92, (2005)

[6]

Zhang Q.F., Sun J.Y., Tsang E., Combinations of estimation of distribution algorithms and other techniques, International Journal of Automation and Computing, 4, 3, pp. 273-280, (2007)

[7]

Oliveto P.S., He J., Yao X., Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results, International Journal of Automation and Computing, 4, 3, pp. 281-293, (2007)

← 1 →