Scheduling and fixed-parameter tractability
From MaRDI portal
Publication:896271
DOI10.1007/s10107-014-0830-9zbMath1332.68089OpenAlexW2168633992MaRDI QIDQ896271
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-014-0830-9
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (38)
Parameterized Resiliency Problems via Integer Linear Programming ⋮ New algorithms for minimizing the weighted number of tardy jobs on a single machine ⋮ A characterization of optimal multiprocessor schedules and new dominance rules ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work ⋮ Fixed interval scheduling with third‐party machines ⋮ Equitable scheduling on a single machine ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ A new perspective on single-machine scheduling problems with late work related criteria ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Fixed-Parameter Approximation Schemes for Weighted Flowtime. ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ An exact exponential branch-and-merge algorithm for the single machine total tardiness problem ⋮ Single-machine scheduling with release times, deadlines, setup times, and rejection ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Improved approximation algorithms for two-stage flowshops scheduling problem ⋮ Scheduling a proportionate flow shop of batching machines ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ Unnamed Item ⋮ Makespan minimization with OR-precedence constraints ⋮ Scheduling meets \(n\)-fold integer programming ⋮ Parameterized resiliency problems ⋮ On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times ⋮ Moderate exponential-time algorithms for scheduling problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Stable assignment with couples: parameterized complexity and local search
- Parameterizing by the number of numbers
- Approximation algorithms for scheduling unrelated parallel machines
- Approximation schemes for scheduling on parallel machines
- An approximation algorithm for the generalized assignment problem
- Preemptive scheduling with rejection
- 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
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- Parameterized complexity of a coupled-task scheduling problem
- Complexity of integer quasiconvex polynomial optimization
- A framework for the complexity of high-multiplicity scheduling problems
- On the Complexity of Nonlinear Mixed-Integer Optimization
- Weighted Geometric Set Multi-cover via Quasi-uniform Sampling
- Tighter Bounds for the Multifit Processor Scheduling Algorithm
- Approximation schemes for preemptive weighted flow time
- Algorithms for Scheduling Independent Tasks
- An Application of Bin-Packing to Multiprocessor Scheduling
- Color-coding
- Techniques for scheduling with rejection
- Santa Claus Schedules Jobs on Unrelated Machines
- Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines
- Algorithms for minimizing weighted flow time
- Polynomiality for Bin Packing with a Constant Number of Item Types
- Scheduling and Fixed-Parameter Tractability
- Bounds on Multiprocessing Timing Anomalies
This page was built for publication: Scheduling and fixed-parameter tractability
