Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines.
Ruiqing SunPublished in: J. Comb. Optim. (2024)
Keyphrases
- approximation schemes
- completion times
- identical parallel machines
- approximation algorithms
- strongly np hard
- processing times
- scheduling problem
- scheduling jobs
- single machine
- release dates
- single machine scheduling problem
- flowshop
- weighted sum
- np hard
- competitive ratio
- special case
- precedence constraints
- setup times
- queue length
- parallel machines
- numerical methods
- fixed number
- resource consumption
- batch processing
- worst case
- steady state
- tabu search