SET PARTITIONING AND COLUMN GENERATION HEURISTICS FOR CAPACITATED DYNAMIC LOTSIZING

被引:35
作者
CATTRYSSE, D [1 ]
MAES, J [1 ]
VANWASSENHOVE, LN [1 ]
机构
[1] ERASMUS UNIV,INST ECONOMETR,3000 DR ROTTERDAM,NETHERLANDS
关键词
heuristics; Lotsizing; set partitioning;
D O I
10.1016/0377-2217(90)90296-N
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper discusses set partitioning and column generation heuristics for the multi item single level capacitated dynamic lotsizing problem. Most previous research efforts reported in literature use the single item uncapacitated problem solutions as candidate plans. In this paper a different approach is proposed in which candidate plans are also generated by some well-known multi item capacitated dynamic lotsizing heuristics. The LP relaxation of a set partitioning model is solved and rounded to obtain an integer solution. A number of heuristics are subsequently applied to improve upon this initial solution. Heuristics are also used to convert the possibly fractional solution from the column generation step to a feasible integer one. Our methods are compared with other common sense heuristics. Computational experience shows that our methods perform best for problems with fewer periods than items, but are quite good on average. © 1990.
引用
收藏
页码:38 / 47
页数:10
相关论文
共 20 条
[1]   A CYCLICAL SCHEDULING HEURISTIC FOR LOT SIZING WITH CAPACITY CONSTRAINTS [J].
BAHL, HC ;
RITZMAN, LP .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1984, 22 (05) :791-800
[2]   COLUMN GENERATION BASED HEURISTIC ALGORITHM FOR MULTI-ITEM SCHEDULING [J].
BAHL, HC .
IIE TRANSACTIONS, 1983, 15 (02) :136-141
[3]  
Baker KennethR., 1978, MANAGE SCI, V24, P1710, DOI DOI 10.1287/MNSC.24.16.1710
[4]   STRONG FORMULATIONS FOR MULTI-ITEM CAPACITATED LOT SIZING [J].
BARANY, I ;
VANROY, TJ ;
WOLSEY, LA .
MANAGEMENT SCIENCE, 1984, 30 (10) :1255-1261
[5]  
Dixon P, 1981, J OPERATIONS MANAGEM, V2, P23
[6]   THE DYNAMIC LOT-SIZING PROBLEM FOR MULTIPLE ITEMS UNDER LIMITED CAPACITY [J].
DOGRAMACI, A ;
PANAYIOTOPOULOS, JC ;
ADAM, NR .
AIIE TRANSACTIONS, 1981, 13 (04) :294-303
[7]   OPTIMAL PROGRAMMING OF LOT SIZES, INVENTORY AND LABOR ALLOCATIONS [J].
DZIELINSKI, BP ;
GOMORY, RE .
MANAGEMENT SCIENCE, 1965, 11 (09) :874-890
[8]   SOLVING MULTI-ITEM CAPACITATED LOT-SIZING PROBLEMS USING VARIABLE REDEFINITION [J].
EPPEN, GD ;
MARTIN, RK .
OPERATIONS RESEARCH, 1987, 35 (06) :832-848
[9]  
FLEISCHMANN B, 1987, UNPUB EJOR
[10]  
Florian M., 1980, MANAGE SCI, V26, P12