Parameterized complexity of machine scheduling: 15 open problems

DOI10.1016/j.cor.2018.07.020zbMath1458.90333arXiv1709.01670OpenAlexW2751935900MaRDI QIDQ1782183

Matthias Mnich, René van Bevern

Publication date: 18 September 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

parallel machinesmakespanthroughputtotal tardinesstotal completion timenumber of tardy jobsshop scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (33)

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 ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times ⋮ Shop scheduling in manufacturing environments: a review ⋮ Maximizing total early work in a distributed two‐machine flow‐shop ⋮ Equitable scheduling on a single machine ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ A new perspective on single-machine scheduling problems with late work related criteria ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ Unnamed Item ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Scheduling a proportionate flow shop of batching machines ⋮ Domino sequencing: scheduling with state-based sequence-dependent setup times ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ Approximate and robust bounded job start scheduling for Royal Mail delivery offices ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Moderate exponential-time algorithms for scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Polynomial kernels for weighted problems
• High-multiplicity scheduling on one machine with forbidden start and completion times
• Erratum to: ``Minimizing total tardiness on parallel machines with preemptions
• Stable assignment with couples: parameterized complexity and local search
• Lower bounds on kernelization
• Maximizing weighted number of just-in-time jobs on unrelated parallel machines
• The complexity of mean flow time scheduling problems with release times
• Interval scheduling and colorful independent sets
• Scheduling and fixed-parameter tractability
• Minimizing mean flow time with release time constraint
• Single machine precedence constrained scheduling is a Vertex cover problem
• Single machine scheduling with forbidden start times
• Scheduling jobs with fixed start and end times
• Approximation schemes for scheduling on parallel machines
• Approximability of flow shop scheduling
• Makespan minimization in open shops: A polynomial time approximation scheme
• Scheduling unit time open shops to minimize the weighted number of late jobs
• Is a unit-job shop not easier than identical parallel machines?
• On minimizing the weighted number of late jobs in unit execution time open-shops.
• A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• On the parametric complexity of schedules to minimize tardy tasks.
• Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• On the complexity of minimizing the number of late jobs in unit time open shop
• Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
• Structural parameters for scheduling with assignment restrictions
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Parallel machine problems with equal processing times: a survey
• A complete 4-parametric complexity classification of short shop scheduling problems
• Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
• A survey of scheduling problems with setup times or costs
• Parametrized complexity theory.
• The routing open-shop problem on a network: complexity and approximation
• A framework for the complexity of high-multiplicity scheduling problems
• New Races in Parameterized Algorithmics
• Open Problems in Throughput Scheduling
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Complexity results for scheduling tasks with discrete starting times
• Strip Graphs: Recognition and Scheduling
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Open shop problems with unit time operations
• Open Shop Scheduling to Minimize Finish Time
• The Complexity of Flowshop and Jobshop Scheduling
• Computational Complexity of Discrete Optimization Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Short Shop Schedules
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• About the Structure of the Integer Cone and its Application to Bin Packing
• Vector Summation in Banach Space and Polynomial Algorithms for Flow Shops and Open Shops
• Kernelization Lower Bounds by Cross-Composition
• Reducibility among Combinatorial Problems
• Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Parameterized Algorithms
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Completing Partial Schedules for Open Shop with Unit Processing Times and Routing

This page was built for publication: Parameterized complexity of machine scheduling: 15 open problems