Online from: 1972
Subject Area: Electrical & Electronic Engineering
Options: To add Favourites and Table of Contents Alerts please take a Emerald profile
|Title:||An FPTAS for SM-CELS problem with monotone cost functions|
|Author(s):||Jianteng Xu, (School of Management, Harbin Institute of Technology, Harbin, People's Republic of China), Qingpu Zhang, (School of Management, Harbin Institute of Technology, Harbin, People's Republic of China), Qingguo Bai, (School of Operations Research and Management Sciences, Qufu Normal University, Rizhao, People's Republic of China)|
|Citation:||Jianteng Xu, Qingpu Zhang, Qingguo Bai, (2009) "An FPTAS for SM-CELS problem with monotone cost functions", Kybernetes, Vol. 38 Iss: 10, pp.1735 - 1746|
|Keywords:||Cybernetics, Inventory costs, Lot size, Programming, Time series analysis|
|Article type:||Research paper|
|DOI:||10.1108/03684920910994105 (Permanent URL)|
|Publisher:||Emerald Group Publishing Limited|
|Acknowledgements:||This paper is supported by National Science Foundation of China under Grant 70672063 and the Research Fund for the Doctoral Program of Higher Education 20060213025. This paper is also supported by National Center of Technology, Policy and Management, Harbin Institute of Technology.|
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.
To purchase this item please login or register.
Complete and print this form to request this document from your librarian