An AFPTAS for variable sized bin packing with general activation costs
作者：
Highlights：
• AFPTAS for general cost variable size bin packing.
• AFPTAS for due date scheduling with general activation cost on related machines.
• Series of reductions leading to a non-standard application of the shifting technique.
• Shifting gives almost independent subproblems whose solutions are combined via DP.
• Oracle based formulation of an AFPTAS for bin packing with general utilization cost.
摘要
•AFPTAS for general cost variable size bin packing.•AFPTAS for due date scheduling with general activation cost on related machines.•Series of reductions leading to a non-standard application of the shifting technique.•Shifting gives almost independent subproblems whose solutions are combined via DP.•Oracle based formulation of an AFPTAS for bin packing with general utilization cost.
论文关键词：Bin packing,Asymptotic approximation schemes,Scheduling
论文评审过程：Received 11 August 2014, Revised 25 November 2015, Accepted 23 July 2016, Available online 26 September 2016, Version of Record 14 November 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.07.007
