A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
From MaRDI portal
Publication:922286
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
single machinepolynomial algorithmdue datespseudopolynomial time boundsum of the weights of the late jobsTime and space bounds
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)
Related Items (41)
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 ⋮ The preemptive resource allocation problem ⋮ Single machine adversarial bilevel scheduling problems ⋮ Algorithms for scheduling deadline-sensitive malleable tasks ⋮ 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
- Unnamed Item
- A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
This page was built for publication: A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
