Exact and Heuristic Algorithms for Single-Machine Scheduling with Total Late Work and Job Rejection

This paper investigates the single-machine scheduling problem incorporating rejection cost constraints, intending to minimize total late work. For instances where jobs share a common due date, we establish the NP-hardness of the unweighted case and present an optimal algorithm through problem reduction. Subsequently, we develop a dynamic programming framework for the weighted variant by exploiting the structural properties of the problem. In scenarios involving arbitrary due dates, we propose tailored approaches: branch-and-bound and dynamic programming algorithms are introduced for small-scale unweighted instances, while a genetic algorithm is employed to efficiently address large-scale problems. For the weighted case, we enhance existing frameworks through strategic modifications to expedite computations. Comprehensive numerical experiments are conducted to validate the effectiveness and efficiency of all proposed methodologies.