An FPTAS for a supply scheduling problem with non-monotone cost functions

Chi To Ng, Mikhail Yakovlevich Kovalyov, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)194-199
Number of pages6
JournalNaval Research Logistics
Volume55
Issue number3
DOIs
Publication statusPublished - 1 Apr 2008

Keywords

  • Approximation scheme
  • Combinatorial optimization
  • FPTAS
  • Supply chain scheduling

ASJC Scopus subject areas

  • Management Science and Operations Research

Cite this