A FULLY POLYNOMIAL-APPROXIMATION SCHEME FOR SINGLE-PRODUCT SCHEDULING IN A FINITE-CAPACITY FACILITY

被引:17
作者
GAVISH, B
JOHNSON, RE
机构
[1] Vanderbilt Univ, , TN
关键词
D O I
10.1287/opre.38.1.70
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper considers a version of the economic lot sizing problem for a single product produced in a facility of finite capacity over a finite time horizon with specifiable start and end conditions. A set of algorithms is presented that will approximate the optimal production schedule to a given allowable error (ε). Algorithms with computation time bounds of O(1/ε2) are presented which allow for setups of finite length, setups with or without direct cash flow, quite general cost and demand functions, and a wide variety of production policy constraints. The procedures make no a priori assumptions about the form of the optimal solution. Numerical results are included.
引用
收藏
页码:70 / 83
页数:14
相关论文
共 26 条
[1]   COMPUTATIONAL-COMPLEXITY OF THE CAPACITATED LOT SIZE PROBLEM [J].
BITRAN, GR ;
YANASSE, HH .
MANAGEMENT SCIENCE, 1982, 28 (10) :1174-1186
[2]   APPROXIMATION FORMULATIONS FOR THE SINGLE-PRODUCT CAPACITATED LOT SIZE PROBLEM [J].
BITRAN, GR ;
MATSUO, H .
OPERATIONS RESEARCH, 1986, 34 (01) :63-74
[3]   APPROXIMATION METHODS FOR THE UNCAPACITATED DYNAMIC LOT SIZE PROBLEM [J].
BITRAN, GR ;
MAGNANTI, TL ;
YANASSE, HH .
MANAGEMENT SCIENCE, 1984, 30 (09) :1121-1140
[4]   PLANNING HORIZONS FOR DYNAMIC LOT SIZE MODEL WITH BACKLOGGING [J].
BLACKBURN, JD ;
KUNREUTHER, H .
MANAGEMENT SCIENCE SERIES A-THEORY, 1974, 21 (03) :251-255
[5]   ECONOMIC LOT SCHEDULING PROBLEM (ELSP) - REVIEW AND EXTENSIONS [J].
ELMAGHRABY, SE .
MANAGEMENT SCIENCE, 1978, 24 (06) :587-598
[6]   EXTENSIONS OF PLANNING HORIZON THEOREM IN DYNAMIC LOT SIZE MODEL [J].
EPPEN, GD ;
GOULD, FJ ;
PASHIGIAN, BP .
MANAGEMENT SCIENCE SERIES A-THEORY, 1969, 15 (05) :268-277
[7]   SOLVING MULTI-ITEM CAPACITATED LOT-SIZING PROBLEMS USING VARIABLE REDEFINITION [J].
EPPEN, GD ;
MARTIN, RK .
OPERATIONS RESEARCH, 1987, 35 (06) :832-848
[8]   WORST-CASE ANALYSIS OF HEURISTIC ALGORITHMS [J].
FISHER, ML .
MANAGEMENT SCIENCE, 1980, 26 (01) :1-17
[9]   DETERMINISTIC PRODUCTION PLANNING WITH CONCAVE COSTS AND CAPACITY CONSTRAINTS [J].
FLORIAN, M ;
KLEIN, M .
MANAGEMENT SCIENCE SERIES A-THEORY, 1971, 18 (01) :12-20
[10]   DETERMINISTIC PRODUCTION PLANNING - ALGORITHMS AND COMPLEXITY [J].
FLORIAN, M ;
LENSTRA, JK ;
RINNOOYKAN, AHG .
MANAGEMENT SCIENCE, 1980, 26 (07) :669-679