Scheduling and fixed-parameter tractability
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Deterministic scheduling theory in operations research (90B35) Integer programming (90C10) Combinatorial optimization (90C27)
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
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- 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 minimizing weighted flow time
- Algorithms for Scheduling Independent Tasks
- 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
- 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?)
- 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
Cited in
(61)- Current trends in deterministic scheduling
- On the optimality of exact and approximation algorithms for scheduling problems
- Parameterized complexity of machine scheduling: 15 open problems
- An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
- On the parameterized tractability of single machine scheduling with rejection
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Makespan minimization with OR-precedence constraints
- On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times
- Moderate exponential-time 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
- Combinatorial \(n\)-fold integer programming and applications
- Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
- Parameterized complexity of a coupled-task scheduling problem
- Improved approximation algorithms for two-stage flowshops scheduling problem
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- Scheduling meets n-fold integer programming
- Parameterized resiliency problems
- 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
- A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions
- scientific article; zbMATH DE number 2166451 (Why is no real title available?)
- Integer programming in parameterized complexity: three miniatures
- Fixed-parameter approximation schemes for weighted flowtime
- Combinatorial \(n\)-fold integer programming and applications
- Parameterized resiliency problems via integer linear programming
- Scheduling and fixed-parameter tractability
- Completing partial schedules for open shop with unit processing times and routing
- Scheduling a proportionate flow shop of batching machines
- Fixed interval scheduling with third‐party machines
- Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
- scientific article; zbMATH DE number 7764095 (Why is no real title available?)
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- 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
- 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
- FPT algorithms for a special block-structured integer program with applications in scheduling
- Minimizing the maximum lateness for scheduling with release times and job rejection
- Serial batching to minimize the weighted number of tardy jobs
- Coupled-task scheduling with time windows, bounded pathwidth and bounded slack is para-NP-complete
- Approximation algorithms for demand-based job scheduling with reconfigurable resources
- Fifty years of research in scheduling -- theory and applications
- Exact and approximate high-multiplicity scheduling on identical machines
- Scheduling kernels via configuration LP
- Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: a parameterized complexity analysis
- Complexity of scheduling few types of jobs on related and unrelated machines
- Approximation algorithm for job scheduling with reconfigurable resources
- A new structural parameter on single machine scheduling with release dates and deadlines
- Moderate exponential-time algorithms for scheduling problems
- Additive approximation schemes for load balancing problems
- Single-machine scheduling to minimize the number of tardy jobs with release dates
- Parameterized hardness results for the \textsc{Restricted Santa Claus Problem}
- Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
- Structured solutions in scheduling problems
- 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
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)
