Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width

DOI10.1007/978-3-319-44914-2_9MaRDI QIDQ3133204zbMATH OpenOpenAlexDBLPWikidataFDO

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

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 minimizationparallel identical machinesparameterized complexityresource-constrained project schedulingshuffle product

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Abstract: Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,$p_{j}in1,2$|$C_{max}$, the problem of finding a non-preemptive minimum-makespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of $k$ other given words, is W[2]-hard parameterized by $k$, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75-82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.

Recommendations

• scientific article; zbMATH DE number 5605136
• Precedence constrained scheduling: A case in \({\mathbf P}\)
• Scheduling with Precedence Constraints of Low Fractional Dimension
• scientific article; zbMATH DE number 3883928
• Handling precedence constraints in scheduling problems by the sequence pair representation
• Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
• On a parallel machine scheduling problem with precedence constraints
• Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal
• Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width
• A monotone approximation algorithm for scheduling with precedence constraints

Cited in

(31)

• On dual based lower bounds for the sequential ordering problem with precedences and due dates
• Parameterized complexity of machine scheduling: 15 open problems
• On the parametric complexity of schedules to minimize tardy tasks.
• \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
• Single-machine scheduling with release times, deadlines, setup times, and rejection
• Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time
• 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 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
• Scheduling meets n-fold integer programming
• 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
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• On recognising words that are squares for the shuffle product
• scientific article; zbMATH DE number 3883928 (Why is no real title available?)
• scientific article; zbMATH DE number 5605136 (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
• Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
• 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
• Fifty years of research on resource-constrained project scheduling explored from different perspectives
• Improved parameterized algorithms for scheduling with precedence constraints and time windows
• FPT implicit enumeration of active schedules
• Parameterized complexity of a parallel machine scheduling problem
• A new structural parameter on single machine scheduling with release dates and deadlines
• Parameterized algorithms and complexity for scheduling with precedence constraints and time windows
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133204)