Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property
From MaRDI portal
Publication:1341403
DOI10.1016/0895-7177(94)90209-7zbMath0810.90070OpenAlexW1986168186MaRDI QIDQ1341403
Publication date: 11 January 1995
Published in: Mathematical and Computer Modelling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0895-7177(94)90209-7
due dateprocessing timerelease dateknapsack-like problemMoore-Hodgson algorithmnested inequality constraintstower of sets
Related Items
Tower-of-sets analysis for the Kise-Ibaraki-Mine algorithm ⋮ Minimizing the weighted number of tardy jobs on a single machine with release dates ⋮ A survey of single machine scheduling to minimize weighted number of tardy jobs ⋮ Branch less, cut more and minimize the number of late equal-length jobs on identical machines ⋮ A study of single-machine scheduling problem to maximize throughput ⋮ Time-of-use scheduling problem with equal-length jobs ⋮ Competitive two-agent scheduling with release dates and preemption on a single machine ⋮ New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem ⋮ Throughput maximization for speed scaling with agreeable deadlines ⋮ Genetic algorithms to minimize the weighted number of late jobs on a single machine. ⋮ Parallel machine problems with equal processing times: a survey ⋮ Optimality proof of the Kise-Ibaraki-Mine algorithm ⋮ Online scheduling of bounded length jobs to maximize throughput ⋮ 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 ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Single machine scheduling with deadlines, release and due dates ⋮ A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints ⋮ A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates ⋮ Single Machine Preemptive Scheduling to Minimize the Weighted Number of Late Jobs with Deadlines and Nested Release/Due Date Intervals ⋮ Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine ⋮ 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 branch and bound to minimize the number of late jobs on a single machine with release time constraints
Cites Work
- Unnamed Item
- A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
- A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times
- 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
