\(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling

DOI10.1016/0167-6377(95)00031-9zbMath0857.90056OpenAlexW2029604753WikidataQ59567993 ScholiaQ59567993MaRDI QIDQ1919171

Michael R. Fellows, Hans L. Bodlaender

Publication date: 1 August 1996

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(95)00031-9

zbMATH Keywords

multiprocessor schedulingpartial ordersparameterized complexityprecedence constrained \(K\)-processor scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Parallel numerical computation (65Y05)

Related Items (20)

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 general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ The Birth and Early Years of Parameterized Complexity ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Scheduling unit-length jobs with precedence constraints of small height ⋮ Scheduling and fixed-parameter tractability ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A model for minimizing active processor time ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ On the computational hardness based on linear fpt-reductions ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ Threshold dominating sets and an improved characterization of \(W[2\)] ⋮ Scheduling meets \(n\)-fold integer programming

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The parameterized complexity of sequence alignment and consensus
• On the parameterized complexity of short computation and factorization
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Domino Treewidth
• Erratum “Optimal Sequencing of Two Equivalent Processors”
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling