Preemptive scheduling of equal-length jobs in polynomial time

DOI10.1007/S11786-009-0003-ZzbMath1205.90132OpenAlexW2128914352MaRDI QIDQ626963

George B. Mertzios, Walter Unger

Publication date: 19 February 2011

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/9049/1/9049.pdf

zbMATH Keywords

machine schedulingpolynomial algorithmpreemptive schedulingparameterized algorithmequal-length jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
• The complexity of mean flow time scheduling problems with release times
• Preemptive scheduling to minimize mean weighted flow time
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Preemptive scheduling of equal-length jobs to maximize weighted throughput.
• Scheduling equal-length jobs on identical parallel machines
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
• Complexity results for single-machine problems with positive finish-start time-lags
• Preemptive Scheduling of Equal Length Jobs on Two Machines to Minimize Mean Flow Time
• Scheduling identical jobs on uniform parallel machines
• Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines

This page was built for publication: Preemptive scheduling of equal-length jobs in polynomial time