Scheduling and fixed-parameter tractability
From MaRDI portal
Publication:896271
DOI10.1007/S10107-014-0830-9zbMATH Open1332.68089OpenAlexW2168633992MaRDI QIDQ896271FDOQ896271
Authors: Matthias Mnich, Andreas Wiese 
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
Recommendations
- Scheduling and fixed-parameter tractability
- scientific article; zbMATH DE number 2080869
- Approximability of scheduling with fixed jobs
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Complexity of a class of task scheduling problems
- On the optimality of exact and approximation algorithms for scheduling problems
- Towards tight lower bounds for scheduling problems
- On approximating a scheduling problem
- scientific article; zbMATH DE number 1560337
- Scheduling and constraint propagation
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Integer programming (90C10)
Cites Work
- Title not available (Why is that?)
- An approximation algorithm for the generalized assignment problem
- Title not available (Why is that?)
- Techniques for scheduling with rejection
- Algorithms for Scheduling Independent Tasks
- Color-coding
- Polynomiality for bin packing with a constant number of item types
- Bounds on Multiprocessing Timing Anomalies
- Approximation algorithms for scheduling unrelated parallel machines
- Preemptive scheduling with rejection
- An Application of Bin-Packing to Multiprocessor Scheduling
- Santa Claus schedules jobs on unrelated machines
- Stable assignment with couples: parameterized complexity and local search
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- A framework for the complexity of high-multiplicity scheduling problems
- Bin packing with fixed number of bins revisited
- Parameterizing by the number of numbers
- Approximation schemes for scheduling on parallel machines
- Tighter Bounds for the Multifit Processor Scheduling Algorithm
- Parameterized complexity of a coupled-task scheduling problem
- On the complexity of nonlinear mixed-integer optimization
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- Complexity of integer quasiconvex polynomial optimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- Scheduling and fixed-parameter tractability
- On the parametric complexity of schedules to minimize tardy tasks.
- Algorithms for minimizing weighted flow time
- Approximation schemes for preemptive weighted flow time
- Title not available (Why is that?)
- Weighted geometric set multi-cover via quasi-uniform sampling
- Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines
Cited In (48)
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- A multivariate complexity analysis of the material consumption scheduling problem
- A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
- New algorithms for minimizing the weighted number of tardy jobs on a single machine
- Parameterized resiliency problems
- A characterization of optimal multiprocessor schedules and new dominance rules
- On the parameterized tractability of single machine scheduling with rejection
- On the complexity of scheduling problems with a fixed number of parallel identical machines
- Scheduling a proportionate flow shop of batching machines
- Scheduling meets \(n\)-fold integer programming
- Parameterized complexity of machine scheduling: 15 open problems
- Completing partial schedules for open shop with unit processing times and routing
- Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
- Integer programming in parameterized complexity: three miniatures
- A general scheme for solving a large set of scheduling problems with rejection in FPT time
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- Fixed interval scheduling with third‐party machines
- Structured solutions in scheduling problems
- Improved approximation algorithms for two-stage flowshops scheduling problem
- Parameterized complexity of a coupled-task scheduling problem
- Scheduling and fixed-parameter tractability
- A new perspective on single-machine scheduling problems with late work related criteria
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
- FPT algorithms for a special block-structured integer program with applications in scheduling
- Structural parameters for scheduling with assignment restrictions
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- 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
- Current trends in deterministic scheduling
- Makespan minimization with OR-precedence constraints
- Minimizing the maximum lateness for scheduling with release times and job rejection
- Title not available (Why is that?)
- Serial batching to minimize the weighted number of tardy jobs
- Equitable scheduling on a single machine
- Fixed-parameter approximation schemes for weighted flowtime
- On the optimality of exact and approximation algorithms for scheduling problems
- A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions
- On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
- Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
- Parameterized resiliency problems via integer linear programming
- Title not available (Why is that?)
- On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times
- Combinatorial \(n\)-fold integer programming and applications
- Moderate exponential-time algorithms for scheduling problems
- Combinatorial \(n\)-fold integer programming and applications
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
This page was built for publication: Scheduling and fixed-parameter tractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896271)
