A single-item economic lot-sizing problem with a non-uniform resource: Approximation

被引：9

作者：

Chubanov, Sergei ^{[1
,2
]}

Kovalyov, Mikhail Y. ^{[2
,3
]}

Pesch, Erwin ^{[1
]}

机构：

[1] Univ Siegen, Inst Informat Syst, D-57068 Siegen, Germany

[2] Belarusian State Univ, Fac Econ, Minsk, BELARUS

[3] Natl Acad Sci, United Inst Informat Problems, Minsk, BELARUS

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2008年 / 189卷 / 03期

关键词：

lot-sizing; dynamic programming; fully polynomial time approximation scheme;

D O I：

10.1016/j.ejor.2007.02.058

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. Fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：877 / 889

页数：13

共 50 条

[21] Single item lot-sizing with non-decreasing capacities [J].

Pochet, Yves ;

Wolsey, Laurence A. .

MATHEMATICAL PROGRAMMING, 2010, 121 (01) :123-143

[22] Single item lot-sizing with non-decreasing capacities [J].

Yves Pochet ;

Laurence A. Wolsey .

Mathematical Programming, 2010, 121 :123-143

[23] An efficient heuristic procedure for the single-item, discrete lot sizing problem [J].

Canel, C ;

Khumawala, BM ;

Law, JS .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1996, 43 (2-3) :139-148

[24] An O(n log n) algorithm for a single-item capacitated lot-sizing problem with linear costs and no backlogging [J].

Kovalyov, Mikhail Y. ;

Pesch, Erwin .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (13) :3758-3761

[25] General model for single-item lot-sizing with multiple suppliers, quantity discounts, and backordering [J].

Alfares, Hesham K. ;

Turnadi, Rio .

9TH INTERNATIONAL CONFERENCE ON DIGITAL ENTERPRISE TECHNOLOGY - INTELLIGENT MANUFACTURING IN THE KNOWLEDGE ECONOMY ERA, 2016, 56 :199-202

[26] The single-item lot-sizing problem with two production modes, inventory bounds, and periodic carbon emissions capacity [J].

Phouratsamay, Siao-Leu ;

Cheng, T. C. E. .

OPERATIONS RESEARCH LETTERS, 2019, 47 (05) :339-343

[27] Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing [J].

Chu, Feng ;

Chu, Chengbin .

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2007, 4 (02) :233-251

[28] Capacity acquisition for the single-item lot sizing problem under energy constraints [J].

Rapine, Christophe ;

Penz, Bernard ;

Gicquel, Celine ;

Akbalik, Ayse .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2018, 81 :112-122

[29] Metaheuristic optimization for the Single-Item Dynamic Lot Sizing problem with returns and remanufacturing [J].

Parsopoulos, K. E. ;

Konstantaras, I. ;

Skouri, K. .

COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 83 :307-315

[30] An Integrated Single-Item Lot-Sizing Problem in a Two-Stage Industrial Symbiosis Supply Chain with Stochastic Demands [J].

Chamani, Cheshmeh ;

Aghezzaf, El-Houssaine ;

Khatab, Abdelhakim ;

Raa, Birger ;

Singh, Yogang ;

Cottyn, Johannes .

ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: ARTIFICIAL INTELLIGENCE FOR SUSTAINABLE AND RESILIENT PRODUCTION SYSTEMS, APMS 2021, PT II, 2021, 631 :683-693

← 1 2 3 4 5 →