Scheduling with regular performance measures and optional job rejection on a single machine

We address single machine problems with optional job rejection, and focus on minimizing regular performance measures, ie, functions that are non-decreasing in the jobs, completion times, subject to the constraint that the total rejection cost cannot exceed a predefined upper bound. Our contribution is twofold. First, we consider two problems that, to the best of our knowledge, were not addressed in scheduling theory–total (unweighted) tardiness with a common due date and total weighted tardiness with a common due date. For these problems, we show that they are NP-hard and present pseudo-polynomial-time dynamic programming (DP) solution algorithms. Second, we revisit three problems: makespan with release-dates, total completion time, and total weighted completion time, and present enhanced DP solution algorithms. To all studied problems, we provide extensive numerical studies, verifying their efficiency, subsequently demonstrating both theoretical and practical enhancement.