Impact of precedence constraints on complexity of scheduling problems: a survey.
Damien ProtOdile Bellenguez-MorineauPublished in: CoRR (2015)
Keyphrases
- precedence constraints
- scheduling problem
- precedence relations
- single machine
- sequence dependent setup times
- branch and bound algorithm
- setup times
- vertex cover
- release dates
- parallel machines
- flowshop
- processing times
- approximation algorithms
- series parallel
- single machine scheduling problem
- maximum lateness
- parallel processors
- np hard
- tabu search
- worst case
- unit length
- space complexity
- partially ordered sets
- search algorithm
- total tardiness
- makespan minimization
- computational complexity
- partially ordered
- job shop
- identical machines
- job shop scheduling problem
- parallel algorithm
- upper bound
- dynamic programming
- special case
- optimal solution