Bicriteria scheduling to minimize total late work and maximum tardiness with preemption. (September 2021)

• Record Type: Journal Article
• Authors: Chen, Rubing; Yuan, Jinjiang; Ng, C.T.; Cheng, T.C.E.
• Is Part Of: Computers & industrial engineering. Volume 159(2021)
• Publication Date: 2021-09
• Subjects: Bicriteria scheduling -- Preemption -- Total late work -- Maximum tardiness; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2021.107525
• Languages: English
• ISSNs: 0360-8352

Abstract

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.