Parallel machine scheduling with minimum number of tardy jobs: Approximation and exponential algorithms
作者：
Highlights：
• Minimizing the number of tardy jobs on parallel machines cannot be approximated in polynomial time.
• Sub-exponential time approximation algorithms are proposed for both the unweighted and weighted case.
• When the number of machines is fixed, the problem of minimizing the number of tardy jobs on identical parallel machines is fixed parameter tractable.
摘要
•Minimizing the number of tardy jobs on parallel machines cannot be approximated in polynomial time.•Sub-exponential time approximation algorithms are proposed for both the unweighted and weighted case.•When the number of machines is fixed, the problem of minimizing the number of tardy jobs on identical parallel machines is fixed parameter tractable.
论文关键词：Number of tardy jobs,Identical parallel machines scheduling,Exponential time approximation
论文评审过程：Received 10 April 2020, Revised 25 October 2020, Accepted 8 December 2020, Available online 17 January 2021, Version of Record 17 January 2021.
论文官网地址：https://doi.org/10.1016/j.amc.2020.125888
