A Faster FPTAS for a Supply Chain Scheduling Problem to Minimize Holding Costs with Outsourcing

作者：Liu Shang Chia; Wu Chin Chia^*

来源：Asia Pacific Journal of Operational Research, 2016, 33(5): 1650039.

DOI：10.1142/S0217595916500391

• Supply chain scheduling
• outsourcing
• inventory control
• FPTAS
• approximation algorithm
• shortest path problem

This paper addresses a scheduling problem in a flexible supply chain where the jobs can be either processed in house, or outsourced to a third-party supplier with the goal of minimizing the sum of holding and delivery costs subject to an upper bound on the outsourcing cost. The problem with identical job processing times has been proved as binary NP-hard one and a fully polynomial time approximation scheme (FPTAS) that runs in O(n(8)/epsilon(2)) time has also been given. The aim of this paper is to derive a more effective FPTAS running in O(n(4) log n log max{n, 1/epsilon}/epsilon(2)) time for this problem.

• 出版日期2016-10