Improved approximation schemes for early work scheduling on identical parallel machines with common due date.
Weidong LiPublished in: CoRR (2020)
Keyphrases
- identical parallel machines
- approximation schemes
- scheduling problem
- fixed number
- scheduling jobs
- processing times
- approximation algorithms
- release dates
- strongly np hard
- single machine
- parallel machines
- precedence constraints
- single server
- np hard
- competitive ratio
- special case
- resource allocation
- lower bound
- multistage
- dynamic programming