A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
From MaRDI portal
Publication:1617290
DOI10.1007/S10951-017-0519-ZzbMath1406.90006arXiv1510.04833OpenAlexW2612049039MaRDI QIDQ1617290
Damien Prot, Odile Bellenguez-Morineau
Publication date: 7 November 2018
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1510.04833
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (13)
A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows ⋮ A hybrid algorithm for the vehicle routing problem with and/or precedence constraints and time windows ⋮ Literature reviews in operations research: a new taxonomy and a meta review ⋮ 0-1 mathematical programming models for flexible process planning ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ A metric approach for scheduling problems with minimizing the maximum penalty ⋮ Ideal schedules in parallel machine settings ⋮ Machine scheduling with soft precedence constraints ⋮ The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints ⋮ A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time ⋮ Open-shop scheduling for unit jobs under precedence constraints ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time ⋮ Improved formulations and new valid inequalities for a hybrid flow shop problem with time-varying resources and chaining time-lag
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Single-machine scheduling with precedence constraints and position-dependent processing times
- Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
- An efficient algorithm for finding ideal schedules
- Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation
- An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness
- On a parallel machine scheduling problem with precedence constraints
- Preemptive scheduling of interval orders is polynomial
- Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
- Single machine precedence constrained scheduling is a Vertex cover problem
- Complexity results for scheduling chains on a single machine
- A relation between multiprocessor scheduling and linear programming
- Optimal scheduling on parallel machines for a new order class
- Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
- Ideal preemptive schedules on two processors
- Preemptive scheduling of equal-length jobs to maximize weighted throughput.
- Normal-form preemption sequences for an open problem in scheduling theory
- Fractional dimension of partial orders
- A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- Scheduling preemptive jobs with precedence constraints on parallel machines
- 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
- Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
- Complexity results for single-machine problems with positive finish-start time-lags
- Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems
- Scheduling identical jobs with chain precedence constraints on two uniform machines
- Minimizing total completion time for UET tasks with release time and outtree precedence constraints
- Digraph width measures in parameterized algorithmics
- Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint
- Optimal preemptive scheduling on a fixed number of identical parallel machines
- Optimal scheduling for two-processor systems
- Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On the Approximability of Single-Machine Scheduling with Precedence Constraints
- Minimizing mean flow time for UET tasks
- The Design of Approximation Algorithms
- Hardness of Precedence Constrained Scheduling on Identical Machines
- Scheduling identical jobs on uniform parallel machines
- Scheduling precedence graphs of bounded height
- Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
- Profile Scheduling of Opposing Forests and Level Orders
- Graph minors. II. Algorithmic aspects of tree-width
- Scheduling Interval-Ordered Tasks
- Sequencing with Series-Parallel Precedence Constraints
- A New Algorithm for Preemptive Scheduling of Trees
- Linear-Time Algorithms for Scheduling on Parallel Processors
- Minimizing Total Tardiness on a Single Machine with Precedence Constraints
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Complexity of Scheduling under Precedence Constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling Opposing Forests
- The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders
- Single-Machine Scheduling with Precedence Constraints
- Scheduling and Fixed-Parameter Tractability
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
- Scheduling
- On preemption redundancy in scheduling unit processing time jobs on two parallel machines
This page was built for publication: A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
