Pareto‐scheduling with double‐weighted jobs to minimize the weighted number of tardy jobs and total weighted late work
研究单机帕累托调度问题，同时最小化加权延误作业数和加权总延迟工作量，提出伪多项式算法和全多项式时间近似方案，并分析特殊情形复杂度。
Abstract 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.