An O(n^4) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
From MaRDI portal
Publication:1306357
DOI10.1016/S0167-6377(98)00045-5zbMATH Open0955.90032WikidataQ127960074 ScholiaQ127960074MaRDI QIDQ1306357FDOQ1306357
Publication date: 4 March 2001
Published in: Operations Research Letters (Search for Journal in Brave)
Recommendations
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
- Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs
- Preemptive Scheduling of Two Uniform Machines to Minimize the Number of Late Jobs
- An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
- Single Machine Scheduling to Minimize Total Late Work
Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
- The one-machine sequencing problem
- A branch and bound algorithm for the job-shop scheduling problem
- An Algorithm for Solving the Job-Shop Problem
- Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs
- Minimizing late jobs in the general one machine scheduling problem
- A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
Cited In (22)
- Optimality proof of the Kise-Ibaraki-Mine algorithm
- A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems
- Online production planning to maximize the number of on-time orders
- Preemptive scheduling of equal-length jobs to maximize weighted throughput.
- Approximation algorithms for scheduling real-time jobs with multiple feasible intervals
- A branch and bound to minimize the number of late jobs on a single machine with release time constraints
- Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization
- Time-of-use scheduling problem with equal-length jobs
- On-line scheduling on a single machine: Maximizing the number of early jobs
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
- Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
- Tower-of-sets analysis for the Kise-Ibaraki-Mine algorithm
- Minimizing the weighted number of tardy jobs on a single machine with release dates
- Modeling single machine preemptive scheduling problems for computational efficiency
- Preemptive scheduling of equal-length jobs in polynomial time
- A survey of single machine scheduling to minimize weighted number of tardy jobs
- An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
- Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs
- Throughput maximization for speed scaling with agreeable deadlines
- Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance
- Online scheduling of bounded length jobs to maximize throughput
- Speed scaling problems with memory/cache consideration
Uses Software
This page was built for publication: An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306357)
