A greedy algorithm for capacitated lot-sizing problems

被引：3
作者：
Girlich, E
Höding, M
Zaporozhets, A
Chubanov, S
机构：
[1] Univ Magdeburg, Dept Math, IMO, D-39106 Magdeburg, Germany
[2] Belarusian State Univ, Dept Econ, Minsk 220050, BELARUS
来源：
OPTIMIZATION | 2003年 / 52卷 / 02期
关键词：
lot-sizing problem; greedy algorithm; polymatroid;
D O I：
10.1080/0233193031000079801
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O(n) time.
引用
收藏
页码：241 / 249
页数：9
相关论文
共 7 条
[1]   COMPUTATIONAL-COMPLEXITY OF THE CAPACITATED LOT SIZE PROBLEM [J].
BITRAN, GR ;
YANASSE, HH .
MANAGEMENT SCIENCE, 1982, 28 (10) :1174-1186
[2]  
Dorit S. H, 1994, MATH OPER RES, V19, P390
[3]  
Edmonds J., 1970, Combinatorial Structures and Their Applications, P69, DOI DOI 10.1007/3-540-36478
[4]   A SIMPLE FORWARD ALGORITHM TO SOLVE GENERAL DYNAMIC LOT SIZING MODELS WITH N PERIODS IN 0(N LOG N) OR 0(N) TIME [J].
FEDERGRUEN, A ;
TZUR, M .
MANAGEMENT SCIENCE, 1991, 37 (08) :909-925
[5]  
Fujishige S., 1991, ANN DISCRETE MATH, V47
[6]  
Kovalev M. M, 1987, MATROIDS DISCRETE OP
[7]   An O(T-3) algorithm for the economic lot-sizing problem with constant capacities [J].
vanHoesel, CPM ;
Wagelmans, APM .
MANAGEMENT SCIENCE, 1996, 42 (01) :142-150
1