Single Machine Scheduling with Few Deadlines

Abstract We study single-machine scheduling problems with few deadlines. We focus on three classical objectives, namely minimizing the weighted number of tardy jobs, the total weighted completion time, and the total weighted late work. For each of the three problems, we give a pseudo-polynomial-time algorithm for a constant number of different deadlines. These algorithms are complemented with ETH-based, almost tight lower bounds. Furthermore, we study the case in which the number of jobs with nontrivial deadline (i.e. jobs with deadline smaller than the total processing time of all jobs) is taken as a parameter. For this case, the complexities of our three problems differ: Minimizing the weighted number of tardy jobs and minimizing the total weighted late work becomes fixed-parameter tractable, while minimizing the total weighted completion time is W[1]-hard.