Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time.
Mikhail BatsynBoris GoldengorinPanos M. PardalosPavel SukhovPublished in: Optim. Methods Softw. (2014)
Keyphrases
- single machine scheduling problem
- single machine
- processing times
- completion times
- scheduling problem
- release dates
- scheduling jobs
- variable neighborhood search
- release times
- sequence dependent setup times
- combinatorial optimization
- precedence constraints
- lagrangian relaxation
- search procedure
- branch and bound algorithm
- total weighted tardiness
- maximum lateness
- dynamic programming
- setup times
- tabu search
- optimal solution
- simulated annealing
- integer programming
- competitive ratio
- flowshop
- np hard
- scheduling algorithm
- metaheuristic
- online algorithms
- feasible solution
- valid inequalities
- learning effect
- identical parallel machines
- lower bound
- search algorithm