Randomized and deterministic local search for SAT and scheduling problems.
Jun GuPublished in: Randomization Methods in Algorithm Design (1997)
Keyphrases
- scheduling problem
- satisfiability testing
- job shop scheduling problem
- stochastic local search
- tabu search
- search algorithm
- tie breaking
- satisfiability problem
- randomized algorithms
- propositional satisfiability
- graph coloring problems
- max sat
- single machine
- propositional logic
- job shop scheduling
- np hard
- memetic algorithm
- processing times
- search procedures
- sat problem
- sat solvers
- random sat instances
- search strategies
- search space
- randomized algorithm
- flowshop
- genetic algorithm
- job shop
- simulated annealing
- sat solving
- boolean satisfiability
- sequencing problems
- optimal solution
- parallel machines
- global search
- phase transition
- greedy heuristics
- constraint programming
- sat instances
- search procedure
- randomly generated
- np complete
- hill climbing
- benchmark problems
- combinatorial optimization
- orders of magnitude
- list scheduling
- lower bound