Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work

We consider the single-machine Pareto-scheduling problem to minimize the weighted number of tardy jobs and total weighted late work simultaneously. The problem is to find the set of all the Pareto-optimal points, that is, the Pareto frontier, and their corresponding Pareto-optimal schedules. We consider the corresponding weighted-sum scheduling problem and primary-secondary scheduling problems, being subproblems of the general Pareto-scheduling problem. The NP-hardness of the general problem follows directly from the NP-hardness of the two constituent single-criterion problems. We present a pseudo-polynomial algorithm and a fully polynomial-time approximation scheme (FPTAS) running in weakly polynomial time to deal with the general problem. When all the jobs have a common due date, we further provide an FPTAS running in strongly polynomial time. We also study some special cases of the general problem where the jobs have equal processing times, a common due date, or a common weight, and analyze their computational complexity status.