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)- 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
- Makespan minimization with OR-precedence constraints
- Combinatorial \(n\)-fold integer programming and applications
- Scheduling meets \(n\)-fold integer programming
- A general scheme for solving a large set of scheduling problems with rejection in FPT time
- 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
- 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
- Serial batching to minimize the weighted number of tardy jobs
- On the optimality of exact and approximation algorithms for scheduling problems
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
- On the parameterized tractability of single machine scheduling with rejection
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- Parameterized complexity of machine scheduling: 15 open problems
- On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan
- Minimizing the maximum lateness for scheduling with release times and job rejection
- 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
- Scheduling a proportionate flow shop of batching machines
- Parameterized resiliency problems via integer linear programming
- Parameterized complexity of a coupled-task scheduling problem
- Integer programming in parameterized complexity: three miniatures
- Equitable scheduling on a single machine
- Scheduling and fixed-parameter tractability
- Fixed interval scheduling with third‐party machines
- Structured solutions in scheduling problems
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- A multivariate complexity analysis of the material consumption scheduling problem
- scientific article; zbMATH DE number 7764095 (Why is no real title available?)
- A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions
- On the complexity of scheduling problems with a fixed number of parallel identical machines
- An exact exponential branch-and-merge algorithm for the single machine total tardiness 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
- Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
- Current trends in deterministic scheduling
- Fixed-parameter approximation schemes for weighted flowtime
- FPT algorithms for a special block-structured integer program with applications in scheduling
- Completing partial schedules for open shop with unit processing times and routing
- scientific article; zbMATH DE number 2166451 (Why is no real title available?)
- Improved approximation algorithms for two-stage flowshops scheduling problem
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)
