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

parameterized complexityresource-constrained project schedulingparallel identical machinesshuffle productmakespan minimization

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

(23)

• On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
• 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
• scientific article; zbMATH DE number 5605136 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3883928 (Why is no real title available?)
• Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines

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)