Premium
An FPTAS for a supply scheduling problem with non‐monotone cost functions
Author(s) -
Ng Chi To,
Kovalyov Mikhail Yakovlevich,
Cheng Tai Chiu Edwin
Publication year - 2008
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20276
Subject(s) - monotone polygon , mathematical optimization , mathematics , scheduling (production processes) , polynomial time approximation scheme , scheme (mathematics) , holding cost , computer science , approximation algorithm , mathematical analysis , geometry
Chauhan et al. Oper Res Lett 33 (2005), 249–254 presented a fully polynomial time approximation scheme (FPTAS) for a supply scheduling problem, which is to minimize a total cost associated with the sizes of deliveries from several providers to one manufacturer. The cost functions are assumed non‐decreasing and their arguments are assumed continuously divisible. In this note, we give a motivation for considering the case of non‐monotone cost functions with continuously divisible or discrete arguments. For this more general case, we suggest a modification of the FPTAS in [Chauhan et al., Oper Res Lett 33 (2005), 249–254]. We also suggest a different FPTAS to handle concave cost functions. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008