A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem.
Adam KurpiszSamuli LeppänenMonaldo MastrolilliPublished in: ESA (2015)
Keyphrases
- single machine scheduling problem
- min sum
- lower bound
- branch and bound algorithm
- semidefinite
- upper bound
- lagrangian relaxation
- np hard
- branch and bound
- precedence constraints
- lower and upper bounds
- semidefinite programming
- optimal solution
- worst case
- objective function
- sufficient conditions
- column generation
- convex relaxation
- single machine
- processing times
- scheduling problem
- interior point methods
- pairwise