An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
From MaRDI portal
Publication:880552
DOI10.1007/s10951-006-7039-6zbMath1154.90495OpenAlexW2061109544MaRDI QIDQ880552
Publication date: 15 May 2007
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-006-7039-6
Related Items (9)
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ An exact algorithm for the preemptive single machine scheduling of equal-length jobs ⋮ Competitive two-agent scheduling with release dates and preemption on a single machine ⋮ Preemptive scheduling of equal-length jobs in polynomial time ⋮ Parallel machine problems with equal processing times: a survey ⋮ Minimizing total tardiness on parallel machines with preemptions ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ Optimal work-conserving scheduler synthesis for real-time sporadic tasks using supervisory control of timed discrete-event systems ⋮ Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness
Cites Work
- Optimal assignment of due-dates for preemptive single-machine scheduling
- Scheduling equal-length jobs on identical parallel machines
- Solution of the single machine total tardiness problem
- Complexity results for single-machine problems with positive finish-start time-lags
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness