Reductions between scheduling problems with non-renewable resources and knapsack problems

DOI10.1016/j.tcs.2014.11.007zbMath1315.90015OpenAlexW1976110695MaRDI QIDQ482287

Péter Györgyi, Tamás Kis

Publication date: 22 December 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.007

zbMATH Keywords

scheduling problemsknapsack problemsapproximation preserving reductions

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (9)

A multivariate complexity analysis of the material consumption scheduling problem ⋮ Approximation schemes for parallel machine scheduling with non-renewable resources ⋮ A PTAS for a resource scheduling problem with arbitrary number of parallel machines ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Approximability of total weighted completion time with resource consuming jobs ⋮ Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ An FPTAS of minimizing total weighted completion time on single machine with position constraint ⋮ Approximability of scheduling problems with resource consuming jobs

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for inventory constrained scheduling on a single machine
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• Coordinated scheduling of production and delivery with production window and delivery capacity constraints
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Approximate solution of NP optimization problems
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Completeness in approximation classes
• Partially ordered knapsack and applications to scheduling
• Single-machine scheduling under the job rejection constraint
• Complexity of single machine scheduling subject to nonnegative inventory constraints
• A new heuristic algorithm for the machine scheduling problem with job delivery coordination
• Scheduling subject to nonrenewable-resource constraints
• A new fully polynomial time approximation scheme for the Knapsack problem
• Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the `Tower of Sets' property
• Approximation algorithms for knapsack problems with cardinality constraints
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Project scheduling with inventory constraints
• Scheduling of inventory releasing jobs to satisfy time-varying demand: an analysis of complexity
• Scheduling of inventory releasing jobs to minimize a regular objective function of delivery times
• The Stock Size Problem
• Basic scheduling problems with raw material constraints
• Scheduling under a Non-renewable Resource Constraint
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

This page was built for publication: Reductions between scheduling problems with non-renewable resources and knapsack problems