Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width

DOI10.1007/978-3-319-44914-2_9zbMath1385.90010arXiv1605.00901OpenAlexW2962877422WikidataQ62039070 ScholiaQ62039070MaRDI QIDQ3133204

Christian Komusiewicz, Nimrod Talmon, Laurent Bulteau, René van Bevern, Gerhard J. Woeginger, Robert Bredereck

Publication date: 13 February 2018

Published in: Discrete Optimization and Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.00901

zbMATH Keywords

makespan minimizationresource-constrained project schedulingshuffle productparameterized complexityparallel identical machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (16)

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 ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Equitable scheduling on a single machine ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ On recognising words that are squares for the shuffle product ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Single-machine scheduling with release times, deadlines, setup times, and rejection ⋮ The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Recognizing binary shuffle squares is \textsf{NP}-hard ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time ⋮ Scheduling meets \(n\)-fold integer programming

This page was built for publication: Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width