On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times.
Abhishek SinghPublished in: Inf. Process. Lett. (2023)
Keyphrases
- single machine
- release times
- setup times
- identical machines
- scheduling problem
- processing times
- number of late jobs
- single machine scheduling problem
- sequence dependent setup times
- scheduling jobs
- release dates
- learning effect
- flowshop
- competitive ratio
- dynamic programming
- response time
- completion times
- special case
- strongly np hard
- resource consumption
- precedence constraints