Jianteng Xu, Qingpu Zhang and Qingguo Bai
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…
Abstract
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.