A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
From MaRDI portal
Publication:827589
DOI10.1016/j.dam.2020.11.024zbMath1462.68016OpenAlexW3112184910MaRDI QIDQ827589
Publication date: 13 January 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2020.11.024
Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Two deadline reduction algorithms for scheduling dependent tasks on parallel processors
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
- An efficient algorithm for finding ideal schedules
- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- Parameterized complexity of machine scheduling: 15 open problems
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
- Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
- Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
- Scheduling precedence graphs of bounded height
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling Opposing Forests
- Parameterized Algorithms
This page was built for publication: A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
