On the parameterized complexity of interval scheduling with eligible machine sets

DOI10.1016/J.JCSS.2024.103533MaRDI QIDQ6564614zbMATH OpenFDO

Authors Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Dvir Shabtay

Publication date 1 July 2024

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2024.103533

zbMATH Keywords

\textsf{W[1}-hardness]eligible machine setsfixed-parameter tractabilityinterval schedulingjust-in-time scheduling

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines
• A simplified NP-complete satisfiability problem
• Algorithmic Aspects of Vertex Elimination on Graphs
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Interval scheduling on identical machines
• Interval scheduling on related machines
• Interval scheduling: A survey
• Just-in-time scheduling with controllable processing times on parallel machines
• Maximizing weighted number of just-in-time jobs on unrelated parallel machines
• On the \(k\)-coloring of intervals
• On the approximability of an interval scheduling problem
• On the complexity of k-SAT
• On the parameterized complexity of multiple-interval graph problems
• Optimal interval scheduling with a resource constraint
• Parameterized complexity of machine scheduling: 15 open problems
• Precoloring extension on unit interval graphs
• Precoloring extension. I: Interval graphs
• Scheduling jobs with fixed start and end times
• Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs
• Sequencing with Earliness and Tardiness Penalties: A Review
• Single machine scheduling to minimize the number of early and tardy jobs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The just-in-time scheduling problem in a flow-shop scheduling system
• The maximum k-colorable subgraph problem for chordal graphs
• Which problems have strongly exponential complexity?

Cited in

(5)

• Fair repetitive interval scheduling
• Moderate exponential-time algorithms for scheduling problems
• Single-machine scheduling to minimize the number of tardy jobs with release dates
• Just-in-time scheduling in two-stage flexible flow shops
• Minimizing the number of tardy jobs with uniform processing times on parallel machines

This page was built for publication: On the parameterized complexity of interval scheduling with eligible machine sets

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