An Investigation of Phase Transitions in Single-Machine Scheduling Problems.
Zhihui WangBryan O'GormanTony T. TranEleanor Gilbert RieffelJeremy FrankMinh DoPublished in: ICAPS (2017)
Keyphrases
- phase transition
- single machine scheduling problem
- constraint satisfaction
- branch and bound algorithm
- single machine
- release times
- hard problems
- processing times
- satisfiability problem
- np complete
- random constraint satisfaction problems
- randomly generated
- random instances
- precedence constraints
- cellular automata
- sat problem
- lagrangian relaxation
- random graphs
- resource consumption
- combinatorial optimization
- np complete problems
- lower bound
- hybrid algorithm
- search procedure
- random sat
- scheduling problem
- constraint propagation
- np hard