An O( n^2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

DOI10.1007/S10951-006-7039-6zbMATH Open1154.90495OpenAlexW2061109544MaRDI QIDQ880552FDOQ880552

N. E. Zubov

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

Recommendations

• An exact algorithm for the preemptive single machine scheduling of equal-length jobs
• Preemptive Scheduling of Equal Length Jobs on Two Machines to Minimize Mean Flow Time
• An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine
• Preemptive scheduling of equal-length jobs in polynomial time
• Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness
• Preemptive scheduling of two uniform parallel machines to minimize total tardiness
• Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan
• Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

zbMATH Keywords

Preemptive schedulingSingle machineTotal tardinessEqual-length jobsRelease date

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Title not available (Why is that?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling equal-length jobs on identical parallel machines
• Title not available (Why is that?)
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Title not available (Why is that?)
• Title not available (Why is that?)
• Solution of the single machine total tardiness problem
• Complexity results for single-machine problems with positive finish-start time-lags
• Optimal assignment of due-dates for preemptive single-machine scheduling
• Title not available (Why is that?)

Cited In (10)

• Minimizing total tardiness on parallel machines with preemptions
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness
• Modeling single machine preemptive scheduling problems for computational efficiency
• Preemptive scheduling of equal-length jobs in polynomial time
• Parallel machine problems with equal processing times: a survey
• Optimal work-conserving scheduler synthesis for real-time sporadic tasks using supervisory control of timed discrete-event systems
• 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 on Two Machines to Minimize Mean Flow Time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q880552)