A survey on how the structure of precedence constraints may change the complexity class of scheduling problems (Q1617290): Difference between revisions

@@ Property / author @@
-Damien Prot
@@ Property / author: Damien Prot / rank @@
-Normal rank
@@ Property / author @@
-Odile Bellenguez-Morineau
@@ Property / author: Odile Bellenguez-Morineau / rank @@
-Normal rank
@@ Property / author @@
+Damien Prot
@@ Property / author: Damien Prot / rank @@
+Normal rank
@@ Property / author @@
+Odile Bellenguez-Morineau
@@ Property / author: Odile Bellenguez-Morineau / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2612049039
@@ Property / OpenAlex ID: W2612049039 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.04833
@@ Property / arXiv ID: 1510.04833 / rank @@
+Normal rank
@@ Property / cites work @@
+On a parallel machine scheduling problem with precedence constraints
+Normal rank
@@ Property / cites work @@
+Single machine precedence constrained scheduling is a Vertex cover problem
+Normal rank
@@ Property / cites work @@
+On the Approximability of Single-Machine Scheduling with Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing 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 @@
+Preemptive scheduling of equal-length jobs to maximize weighted throughput.
+Normal rank
@@ Property / cites work @@
+On preemption redundancy in scheduling unit processing time jobs on two parallel machines
+Normal rank
@@ Property / cites work @@
+Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
+Normal rank
@@ Property / cites work @@
+Fractional dimension of partial orders
@@ Property / cites work: Fractional dimension of partial orders / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity results for single-machine problems with positive finish-start time-lags
+Normal rank
@@ Property / cites work @@
+Q3425131
@@ Property / cites work: Q3425131 / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
+Normal rank
@@ Property / cites work @@
+A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
+Normal rank
@@ Property / cites work @@
+Scheduling identical jobs with chain precedence constraints on two uniform machines
+Normal rank
@@ Property / cites work @@
+The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders
+Normal rank
@@ Property / cites work @@
+Normal-form preemption sequences for an open problem in scheduling theory
+Normal rank
@@ Property / cites work @@
+An efficient algorithm for finding ideal schedules
+Normal rank
@@ Property / cites work @@
+Optimal scheduling for two-processor systems
@@ Property / cites work: Optimal scheduling for two-processor systems / rank @@
+Normal rank
@@ Property / cites work @@
+Ideal preemptive schedules on two processors
@@ Property / cites work: Ideal preemptive schedules on two processors / rank @@
+Normal rank
@@ Property / cites work @@
+Single-Machine Scheduling with Precedence Constraints
+Normal rank
@@ Property / cites work @@
+The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
+Normal rank
@@ Property / cites work @@
+Scheduling identical jobs on uniform parallel machines
+Normal rank
@@ Property / cites work @@
+Scheduling preemptive jobs with precedence constraints on parallel machines
+Normal rank
@@ Property / cites work @@
+Scheduling precedence graphs of bounded height
@@ Property / cites work: Scheduling precedence graphs of bounded height / rank @@
+Normal rank
@@ Property / cites work @@
+Profile Scheduling of Opposing Forests and Level Orders
+Normal rank
@@ Property / cites work @@
+On the parametric complexity of schedules to minimize tardy tasks.
+Normal rank
@@ Property / cites work @@
+Digraph width measures in parameterized algorithmics
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling Opposing Forests
@@ Property / cites work: Scheduling Opposing Forests / rank @@
+Normal rank
@@ Property / cites work @@
+A New Algorithm for Preemptive Scheduling of Trees
+Normal rank
@@ Property / cites work @@
+Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation
+Normal rank
@@ Property / cites work @@
+Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
+Normal rank
@@ Property / cites work @@
+Minimizing total completion time for UET tasks with release time and outtree precedence constraints
+Normal rank
@@ Property / cites work @@
+Minimizing mean flow time for UET tasks
@@ Property / cites work: Minimizing mean flow time for UET tasks / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling chain-structured tasks to minimize makespan and mean flow time
+Normal rank
@@ Property / cites work @@
+Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
+Normal rank
@@ Property / cites work @@
+Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
+Normal rank
@@ Property / cites work @@
+Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Q3959420
@@ Property / cites work: Q3959420 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3995531
@@ Property / cites work: Q3995531 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Scheduling under Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Complexity results for scheduling chains on a single machine
+Normal rank
@@ Property / cites work @@
+Q4124328
@@ Property / cites work: Q4124328 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing Total Tardiness on a Single Machine with Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints
+Normal rank
@@ Property / cites work @@
+Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems
+Normal rank
@@ Property / cites work @@
+Scheduling and Fixed-Parameter Tractability
@@ Property / cites work: Scheduling and Fixed-Parameter Tractability / rank @@
+Normal rank
@@ Property / cites work @@
+Q4918387
@@ Property / cites work: Q4918387 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-Time Algorithms for Scheduling on Parallel Processors
+Normal rank
@@ Property / cites work @@
+Sequencing with Series-Parallel Precedence Constraints
+Normal rank
@@ Property / cites work @@
+Optimal scheduling on parallel machines for a new order class
+Normal rank
@@ Property / cites work @@
+A relation between multiprocessor scheduling and linear programming
+Normal rank
@@ Property / cites work @@
+Optimal preemptive scheduling on a fixed number of identical parallel machines
+Normal rank
@@ Property / cites work @@
+Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
+Normal rank
@@ Property / cites work @@
+Scheduling Interval-Ordered Tasks
@@ Property / cites work: Scheduling Interval-Ordered Tasks / rank @@
+Normal rank
@@ Property / cites work @@
+Scheduling
@@ Property / cites work: Scheduling / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Preemptive scheduling of interval orders is polynomial
+Normal rank
@@ Property / cites work @@
+Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
+Normal rank
@@ Property / cites work @@
+Hardness of Precedence Constrained Scheduling on Identical Machines
+Normal rank
@@ Property / cites work @@
+An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
+Normal rank
@@ Property / cites work @@
+Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
+Normal rank
@@ Property / cites work @@
+Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint
+Normal rank
@@ Property / cites work @@
+Single-machine scheduling with precedence constraints and position-dependent processing times
+Normal rank
@@ Property / cites work @@
+The Design of Approximation Algorithms
@@ Property / cites work: The Design of Approximation Algorithms / rank @@
+Normal rank