Complexity of Scheduling under Precedence Constraints

Cited in

(only showing first 100 items - show all)

Single machine precedence constrained scheduling is a Vertex cover problem
Optimal and heuristic solution methods for a multiprocessor machine scheduling problem
Scheduling three chains on two parallel machines
A compact labelling scheme for series-parallel graphs
Applications of scheduling theory to formal language theory
An experiment in scheduling and planning of non-structured jobs: Lessons learned from artificial intelligence and operational research toolbox
Complexity results for scheduling chains on a single machine
On the complexity of generalized due date scheduling problems
Four solution techniques for a general one machine scheduling problem. A comparative study
On the complexity of scheduling with large communication delays
Local search procedures for improving feasible solutions to the sequential ordering problem
A comparative study of computational procedures for the resource constrained project scheduling problem
Tree scheduling with communication delays
Analysis of scheduling problems with typed task systems
The three-machine flow-shop problem with arbitrary precedence relations
Three, four, five, six, or the complexity of scheduling with communication delays
Stochastic scheduling and forwards induction
Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
Scheduling loosely connected task graphs.
On the approximability of average completion time scheduling under precedence constraints.
On scheduling cycle shops: Classification, complexity and approximation
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
Pareto optimal matchings of students to courses in the presence of prerequisites
GPU implementation of a cellular genetic algorithm for scheduling dependent tasks of physical system simulation programs
Single-machine scheduling with supporting tasks
Bi-criteria Pareto-scheduling on a single machine with due indices and precedence constraints
Polynomial time approximation algorithms for machine scheduling: Ten open problems
A fast task-to-processor assignment heuristic for real-time multiprocessor DSP applications
Discrete optimization with polynomially detectable boundaries and restricted level sets
An EPTAS for scheduling fork-join graphs with communication delay
Ideal schedules in parallel machine settings
Makespan minimization with OR-precedence constraints
Server cloud scheduling
Time-critical testing and search problems
The worst-case analysis of the Garey-Johnson algorithm
Machine scheduling with soft precedence constraints
Polyhedral results for position-based scheduling of chains on a single machine
Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates
Scheduling with constrained processor allocation for interval orders
Parallel machine problems with equal processing times: a survey
A complete 4-parametric complexity classification of short shop scheduling problems
Revisiting multiple pattern matching algorithms for multi-core architecture
Homogeneously non-idling schedules of unit-time jobs on identical parallel machines
The complexity of machine scheduling for stability with a single disrupted job
The pairwise flowtime network construction problem
Single machine scheduling problems with uncertain parameters and the OWA criterion
Online Linear Optimization for Job Scheduling Under Precedence Constraints
Minimizing lateness for precedence graphs with constant delays on dedicated pipelined processors
Performance of Garey-Johnson algorithm for pipelined typed tasks systems
Vertex cover in graphs with locally few colors
APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS
Hybrid flow-shop with adjustment
Scheduling of machines and automated guided vehicles in FMS using differential evolution
Approximating weighted completion time for order scheduling with setup times
Complete Complexity Classification of Short Shop Scheduling
Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
Profile Scheduling of Opposing Forests and Level Orders
Two level heuristic for the resource constrained scheduling problem
Time complexity of single machine scheduling with stochastic precedence constraints
Open shop problems with unit time operations
Scheduling malleable tasks with precedence constraints
NP-Complete operations research problems and approximation algorithms
On the Complexity of Scheduling to Optimize Average Response Time
Algorithms for single-machine scheduling with stochastic outtree precedence relations to minimize expected weighted flow time or maximum expected lateness
A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles
On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
Simultaneous job input sequencing and vehicle dispatching in a single-vehicle automated guided vehicle system: a heuristic branch-and-bound approach coupled with a discrete events simulation model
scientific article; zbMATH DE number 809154 (Why is no real title available?)
A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
Quasi-PTAS for scheduling with precedences using LP hierarchies
An improved approximation algorithm for scheduling under arborescence precedence constraints
Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
Decision diagrams for solving a job scheduling problem under precedence constraints
Approximation schemes for scheduling jobs with chain precedence constraints
Scheduling partially ordered jobs faster than \(2^n\)
Scheduling \(UET\)-tasks on a star network: complexity and approximation
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
Bounding the running time of algorithms for scheduling and packing problems
On scheduling with the non-idling constraint
Open-shop scheduling for unit jobs under precedence constraints
On scheduling with the non-idling constraint
PARAdeg-processor scheduling for acyclic SWITCH-less program nets
Improving local search heuristics for some scheduling problems. II
Facets of the generalized permutahedron of a poset
Algorithms for the multiperiod workforce scheduling and routing problem with dependent tasks
Equitable scheduling on a single machine
Resource-constrained multi-project scheduling problem: a survey
Server cloud scheduling
Minimizing the total weighted duration of courses in a single machine problem with precedence constraints
Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines
Exact algorithms for a parallel machine scheduling problem with workforce and contiguity constraints
Minimizing total completion time with machine-dependent priority lists
New partitioning techniques and faster algorithms for approximate interval scheduling
Perfect matching under precedence constraints
Fifty years of research on resource-constrained project scheduling explored from different perspectives
Improved parameterized algorithms for scheduling with precedence constraints and time windows
Streaming algorithms for scheduling jobs with priorities
An improved discrete optimisation procedure with comparison to constraint programming
Precedence-constrained shortest path
Scheduling with bully selfish jobs

This page was built for publication: Complexity of Scheduling under Precedence Constraints

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