TY  - JOUR
AB  - Purpose– The purpose of this paper is to find the best approximation algorithm for solving the more general case of single‐supplier multi‐retailer capacitated economic lot‐sizing (SM‐CELS) problem in deterministic inventory theory, which is the non‐deterministic polynomial (NP)‐hard problem.Design/methodology/approach– Since few theoretical results have been published on polynomial time approximation algorithms for SM‐CELS problems, this paper develops a fully polynomial time approximation scheme (FPTAS) for the problem with monotone production and holding‐backlogging cost functions. First the optimal solution of a rounded problem is presented as the approximate solution and its straightforward dynamic‐programming (DP) algorithm. Then the straightforward DP algorithm is converted into an FPTAS by exploiting combinatorial properties of the recursive function.Findings– An FPTAS is designed for the SM‐CELS problem with monotone cost functions, which is the strongest polynomial time approximation result.Research limitations/implications– The main limitation is that the supplier only manufactures without holding any products when the model is applied.Practical implications– The paper presents the best result for the SM‐CELS problem in deterministic inventory theory.Originality/value– The LP‐rounding technique, an effective approach to design approximation algorithms for NP‐hard problems, is successfully applied to the SM‐CELS problem in this paper.
VL  - 38
IS  - 10
SN  - 0368-492X
DO  - 10.1108/03684920910994105
UR  - https://doi.org/10.1108/03684920910994105
AU  - Xu Jianteng
AU  - Zhang Qingpu
AU  - Bai Qingguo
ED  - Mian‐yun Chen
ED  - Yi Lin
ED  - Hejing Xiong
PY  - 2009
Y1  - 2009/01/01
TI  - An FPTAS for SM‐CELS problem with monotone cost functions
T2  - Kybernetes
PB  - Emerald Group Publishing Limited
SP  - 1735
EP  - 1746
Y2  - 2024/04/25
ER  -