A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

DOI10.1007/BF02248588zbMath0709.90064OpenAlexW2081954069MaRDI QIDQ922286

Publication date: 1990

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02248588

zbMATH Keywords

single machine polynomial algorithm due dates pseudopolynomial time bound sum of the weights of the late jobs Time and space bounds

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

Throughput maximization in multiprocessor speed-scaling, Minimizing the number of late jobs in a stochastic setting using a chance constraint, Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property, A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recircu\-lation, Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs, A heuristic for parallel machine scheduling with agreeable due dates to minimize the number of late jobs, Tower-of-sets analysis for the Kise-Ibaraki-Mine algorithm, Online real-time preemptive scheduling of jobs with deadlines on multiple machines, Approximation schemes for a class of subset selection problems, Minimizing the weighted number of tardy jobs on a single machine with release dates, Approximation algorithms for scheduling real-time jobs with multiple feasible intervals, Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness, ON ONLINE SCHEDULING JOBS WITH RESTART TO MAXIMIZE THE NUMBER OF JOBS COMPLETED TIME ON A SINGLE MACHINE, A survey of single machine scheduling to minimize weighted number of tardy jobs, Throughput Maximization in Multiprocessor Speed-Scaling, A truthful mechanism for value-based scheduling in cloud computing, Weighted throughput in a single machine preemptive scheduling with continuous controllable processing times, Online Throughput Maximization on Unrelated Machines: Commitment is No Burden, Time-of-use scheduling problem with 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, Throughput maximization for speed scaling with agreeable deadlines, Optimality proof of the Kise-Ibaraki-Mine algorithm, Preemptive scheduling of equal-length jobs to maximize weighted throughput., Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times, Online C-benevolent job scheduling on multiple machines, On-line scheduling on a single machine: Maximizing the number of early jobs, Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance, Single Machine Preemptive Scheduling to Minimize the Weighted Number of Late Jobs with Deadlines and Nested Release/Due Date Intervals, Modeling single machine preemptive scheduling problems for computational efficiency, Using short-term memory to minimize the weighted number of late jobs on a single machine., A note on the single machine scheduling to minimize the number of tardy jobs with deadlines, Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs, A practical dynamic programming based methodology for aircraft maintenance check scheduling optimization, An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems, Nonpreemptive flowshop scheduling with machine dominance, A branch and bound to minimize the number of late jobs on a single machine with release time constraints

Cites Work