A multivariate complexity analysis of the material consumption scheduling problem
From MaRDI portal
Publication:6136081
DOI10.1007/s10951-022-00771-5zbMath1520.90095arXiv2102.13642OpenAlexW3135758461MaRDI QIDQ6136081
Rolf Niedermeier, Andrzej Kaczmarczyk, Péter Györgyi, Robert Bredereck, Matthias Bentert
Publication date: 28 August 2023
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.13642
makespan minimizationparameterized computational complexitynon-renewable resourcesexact algorithmsfine-grained complexity
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Approximability of scheduling problems with resource consuming jobs
- Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
- Fundamentals of parameterized complexity
- Approximation schemes for single machine scheduling with non-renewable resource constraints
- Reductions between scheduling problems with non-renewable resources and knapsack problems
- Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
- Interval scheduling and colorful independent sets
- Scheduling and fixed-parameter tractability
- On single-machine scheduling without intermediate delays
- An application of simultaneous diophantine approximation in combinatorial optimization
- Scheduling subject to nonrenewable-resource constraints
- Polynomial algorithms for single machine scheduling problems with financial constraints
- Approximation schemes for parallel machine scheduling with non-renewable resources
- Parameterized complexity of machine scheduling: 15 open problems
- On the parametric complexity of schedules to minimize tardy tasks.
- \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
- Bin packing with fixed number of bins revisited
- On the parameterized tractability of single machine scheduling with rejection
- New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints
- Minimizing makespan on a single machine with release dates and inventory constraints
- Parameterized multi-scenario single-machine scheduling problems
- Combinatorial \(n\)-fold integer programming and applications
- Scheduling with non-renewable resources: minimizing the sum of completion times
- Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Scheduling meets \(n\)-fold integer programming
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- Parametrized complexity theory.
- Integer Programming with a Fixed Number of Variables
- Basic scheduling problems with raw material constraints
- Minkowski's Convex Body Theorem and Integer Programming
- Scheduling under a Non-renewable Resource Constraint
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Parameterized and Exact Computation
- Parameterized Algorithms
- Equitable scheduling on a single machine
- A multivariate complexity analysis of the material consumption scheduling problem
This page was built for publication: A multivariate complexity analysis of the material consumption scheduling problem