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(nlogn)-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(nlognP) time, where P is the total processing time of the jobs.
Original language | English |
---|---|
Article number | 107525 |
Journal | Computers and Industrial Engineering |
Volume | 159 |
DOIs | |
Publication status | Published - Sept 2021 |
Keywords
- Bicriteria scheduling
- Maximum tardiness
- Preemption
- Total late work
ASJC Scopus subject areas
- General Computer Science
- General Engineering