Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines.
Sami DaviesJanardhan KulkarniThomas RothvossJakub TarnawskiYihao ZhangPublished in: SODA (2021)
Keyphrases
- completion times
- communication delays
- processing times
- scheduling problem
- flowshop
- precedence relations
- single machine
- single machine scheduling problem
- identical parallel machines
- weighted sum
- parallel machines
- np hard
- release dates
- absolute deviation
- precedence constraints
- control theory
- linear program
- shortest processing time
- setup times
- special case
- execution times
- queue length
- tabu search
- linear programming
- multiprocessor systems
- job shop scheduling problem
- job shop
- hybrid algorithm
- resource allocation
- computational complexity