Bicriteria scheduling to minimize total late work and maximum tardiness with preemption. (September 2021) - Chen, Rubing; Yuan, Jinjiang; Ng, C.T.; Cheng, T.C.E.
Highlights: Single machine preemptive bicriteria scheduling. Minimizing total late work and maximum tardiness. Polynomial and pseudo-polynomial algorithms. Abstract: We consider single-machine bicriteria scheduling of n jobs with preemption to minimize the total late work and maximum tardiness. Given the earliest due date order of the jobs in advance, we present an O ( n ) -time algorithm for the hierarchical scheduling problem and an O ( n log n ) -time algorithm for the constrained scheduling problem. For the Pareto-scheduling problem, when all the processing times and due dates are integral, we construct the trade-off curve in O ( n log nP ) time, where P is the total processing time of the jobs.