Scheduling and fixed-parameter tractability
From MaRDI portal
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)
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
Cites work
- scientific article; zbMATH DE number 5764783 (Why is no real title available?)
- scientific article; zbMATH DE number 3550182 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 503190 (Why is no real title available?)
- scientific article; zbMATH DE number 2079378 (Why is no real title available?)
- A framework for the complexity of high-multiplicity scheduling problems
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- Algorithms for Scheduling Independent Tasks
- Algorithms for minimizing weighted flow time
- An Application of Bin-Packing to Multiprocessor Scheduling
- An approximation algorithm for the generalized assignment problem
- Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines
- Approximation algorithms for scheduling unrelated parallel machines
- Approximation schemes for preemptive weighted flow time
- Approximation schemes for scheduling on parallel machines
- Bin packing with fixed number of bins revisited
- Bounds on Multiprocessing Timing Anomalies
- Color-coding
- Complexity of integer quasiconvex polynomial optimization
- On the complexity of nonlinear mixed-integer optimization
- On the parametric complexity of schedules to minimize tardy tasks.
- Parameterized complexity of a coupled-task scheduling problem
- Polynomiality for bin packing with a constant number of item types
- Preemptive scheduling with rejection
- Scheduling and fixed-parameter tractability
- Stable assignment with couples: parameterized complexity and local search
- Techniques for scheduling with rejection
- Tighter Bounds for the Multifit Processor Scheduling Algorithm
- Weighted geometric set multi-cover via quasi-uniform sampling
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
Cited in
(47)- Combinatorial \(n\)-fold integer programming and applications
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- 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
- A characterization of optimal multiprocessor schedules and new dominance rules
- Parameterized resiliency problems
- On the parameterized tractability of single machine scheduling with rejection
- A multivariate complexity analysis of the material consumption scheduling problem
- 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
- 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
- A new perspective on single-machine scheduling problems with late work related criteria
- FPT algorithms for a special block-structured integer program with applications in scheduling
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- Current trends in deterministic scheduling
- 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
- Makespan minimization with OR-precedence constraints
- Minimizing the maximum lateness for scheduling with release times and job rejection
- scientific article; zbMATH DE number 2166451 (Why is no real title available?)
- Serial batching to minimize the weighted number of tardy jobs
- Equitable scheduling on a single machine
- On the optimality of exact and approximation algorithms for scheduling problems
- Fixed-parameter approximation schemes for weighted flowtime
- 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
- Parameterized resiliency problems via integer linear programming
- On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times
- Moderate exponential-time algorithms for scheduling problems
- Combinatorial \(n\)-fold integer programming and applications
- Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
- scientific article; zbMATH DE number 7764095 (Why is no real title available?)
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)
