Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width

DOI10.1007/978-3-319-44914-2_9zbMATH Open1385.90010DBLPconf/door/BevernBBKTW16arXiv1605.00901OpenAlexW2962877422WikidataQ62039070 ScholiaQ62039070MaRDI QIDQ3133204FDOQ3133204

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)

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.

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

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

zbMATH Keywords

parameterized complexityresource-constrained project schedulingparallel identical machinesshuffle productmakespan minimization

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cited In (23)

• 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
• On recognising words that are squares for the shuffle product
• Scheduling meets \(n\)-fold integer programming
• Parameterized complexity of machine scheduling: 15 open problems
• On the parametric complexity of schedules to minimize tardy tasks.
• The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints
• 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
• Single-machine scheduling with release times, deadlines, setup times, and rejection
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Parameterized complexity of a coupled-task scheduling problem
• On dual based lower bounds for the sequential ordering problem with precedences and due dates
• 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
• Title not available (Why is that?)
• A linear-time parameterized algorithm for computing the width of a DAG
• Serial batching to minimize the weighted number of tardy jobs
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• Equitable scheduling on a single machine
• Title not available (Why is that?)
• Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
• On the fine-grained parameterized complexity of partial scheduling to minimize the makespan

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)