Single machine scheduling with the total weighted late work and rejection cost
研究了单机调度中总加权延迟工作与总拒绝成本的帕累托调度和受限调度问题，证明了帕累托调度是NP难的并给出了FPTAS，同时证明了受限调度不存在FPTAS并开发了松弛FPTAS。
Abstract We study a single machine scheduling problem with the total weighted late work and the total rejection cost. The late work of a job is the part of this job executed after its due date, and the rejection cost of a job is the fee of rejecting to process it. We consider a Pareto scheduling and two restricted scheduling problems. The Pareto scheduling problem aims to find all non‐dominated values of the total weighted late work and the total rejection cost. The restricted scheduling problems are dedicated to minimizing the total weighted late work with the total rejection cost not greater than a given threshold, and minimizing the total rejection cost with the total weighted late work not greater than a given threshold, respectively. For the Pareto scheduling problem, we prove that it is binary NP‐hard by providing a pseudo‐polynomial time algorithm, and give a fully polynomial time approximation scheme (FPTAS). For the restricted scheduling problems, we prove that there are no FPTASes unless , which answers an open problem. Moreover, we develop relaxed FPTASes for these two restricted scheduling problems.