Scheduling problems with late work criterion have been extensively studied under the assumption that all jobs have to be processed. However, since the production capacities are limited, processing all jobs may cause some jobs to miss their due dates. In such a situation, rejecting some jobs with a fee becomes an alternative option for preserving a high-quality service for the accepted jobs. A recent study by Yao-Wen Sang et al. considers the trade-off between the total weighted late work of accepted jobs and the rejection cost of rejected jobs. This research, which combines late work criterion with rejection cost, is encountered in the fields of manufacturing systems, control systems, and agriculture systems. The results are published on the journal of Naval Research Logistics. The abstract of the paper is copied below.

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 P = NP, which answers an open problem. Moreover, we develop relaxed FPTASes for these two restricted scheduling problems.

If you are interested in the research, please read the paper:

Sang, Y. -W., Wang, J. -Q., Sterna, M., & Blazewicz, J. (2024). Single machine scheduling with the total weighted late work and rejection cost. Naval Research Logistics (NRL), 1–15. https://doi.org/10.1002/nav.22222

A full version of this article could be viewed at:

https://doi.org/10.1002/nav.22222