Tight complexity analysis of the relocation problem with arbitrary release dates.
Sergey SevastyanovBertrand M. T. LinHsiao-Lan HuangPublished in: Theor. Comput. Sci. (2011)
Keyphrases
- complexity analysis
- release dates
- lower bound
- single machine scheduling problem
- single machine
- branch and bound algorithm
- precedence constraints
- processing times
- scheduling problem
- upper bound
- theoretical analysis
- parallel machines
- np hard
- branch and bound
- worst case
- lagrangian relaxation
- computational complexity
- lower and upper bounds
- objective function
- dynamic programming
- cost function