Title: Scheduling with regular performance measures and optional job rejection on a single machine,
Abstract: We address single machine problems with optional jobs - rejection, studied
recently in Zhang et al. [21] and Cao et al. [2]. In these papers, the authors
focus on minimizing regular performance measures, i.e., functions that are
non-decreasing in the jobs completion time, subject to the constraint that the
total rejection cost cannot exceed a predefined upper bound. They also prove
that the considered problems are ordinary NP-hard and provide
pseudo-polynomial-time Dynamic Programming (DP) solutions. In this paper, we
focus on three of these problems: makespan with release-dates; total completion
times; and total weighted completion, and present enhanced DP solutions
demonstrating both theoretical and practical improvements. Moreover, we provide
extensive numerical studies verifying their efficiency.