Minimizing the total weighted earliness-tardiness about a non-restrictive common due date with optional job rejection on single and multiple machines

Abstract This research introduces pseudo-polynomial optimal algorithms for various variants of the problem aimed at minimizing both weighted and unweighted total earliness and tardiness for a given set of jobs with a common, non-restrictive due date and optional job rejection. In this context, each job is associated with a rejection cost, allowing for the possibility of rejecting a subset of the jobs. The variants we consider in this paper include non-restricted rejection, an upper bound on the total rejection cost, an upper bound on the total scheduling cost, and a Pareto-optimal solution. Several key innovations are presented: the integration of optional job rejection, the nontrivial adaptation to the environment of multiple machines, the provision of efficient algorithms for both weighted and unweighted scenarios, and the introduction of Pareto-optimal scheduling. These advancements make the proposed algorithms highly applicable to real-world production systems while maintaining pseudo-polynomial complexity, providing both theoretical depth and practical utility.