An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

被引：0

作者：

Sergei Chubanov

Mikhail Y. Kovalyov

Erwin Pesch

机构：

[1] Belarus State University and the Institute of Information Systems at the University of Siegen,Faculty of Economics

[2] Belarus State University,Faculty of Economics

[3] and United Institute of Informatics Problems,Institute of Information Systems at the University of Siegen

[4] National Academy of Sciences of Belarus,undefined

[5] ,undefined

来源：

Mathematical Programming | 2006年 / 106卷

关键词：

Capacitated economic lot-sizing problem; Dynamic programming; Fully polynomial time approximation scheme;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.

引用

页码：453 / 466

页数：13

共 35 条

[1] An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure
Chubanov, S
Kovalyov, MY
Pesch, E
MATHEMATICAL PROGRAMMING, 2006, 106 (03) : 453 - 466
[2] A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure
Ng, C. T.
Kovalyov, Mikhail Y.
Cheng, T. C. E.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (02) : 621 - 624
[3] An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand
Chubanov, Sergei
Pesch, Erwin
OPERATIONS RESEARCH LETTERS, 2012, 40 (06) : 445 - 449
[4] A single-item economic lot-sizing problem with a non-uniform resource: Approximation
Chubanov, Sergei
Kovalyov, Mikhail Y.
Pesch, Erwin
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 189 (03) : 877 - 889
[5] The single-item lot-sizing problem with immediate lost sales
Aksen, D
Altinkemer, K
Chand, S
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 147 (03) : 558 - 566
[6] A single-Item uncapacitated lot-sizing problem with remanufacturing and outsourcing
Wang, Nengmin
He, Zhengwen
Sun, Jingchun
Xie, Haiyan
Shi, Wei
CEIS 2011, 2011, 15
[7] The single-item green lot-sizing problem with fixed carbon emissions
Absi, Nabil
Dauzere-Peres, Stephane
Kedad-Sidhoum, Safia
Penz, Bernard
Rapine, Christophe
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 248 (03) : 849 - 855
[8] A single-item lot-sizing problem with a by-product and inventory capacities
Suzanne, Elodie
Absi, Nabil
Borodin, Valeria
van den Heuvel, Wilco
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 287 (03) : 844 - 855
[9] Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost
Akbalik, Ayse
Rapine, Christophe
OPERATIONS RESEARCH LETTERS, 2012, 40 (05) : 390 - 397
[10] Capacitated lot-sizing problem with outsourcing
Zhang, Minjiao
OPERATIONS RESEARCH LETTERS, 2015, 43 (05) : 479 - 483

← 1 2 3 4 →