Parameterized complexity of machine scheduling: 15 open problems (Q1782183): Difference between revisions

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