The single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties was discussed. Such problems require a job-dependent setup to take place each time a job is started. It was proved that the problem is strongly NP-hard. A dynamic programming algorithm and a polynomial time approximation scheme were also presented for solving the problem.
- Approximation scheme
- Preemption penalty
- Setup time
ASJC Scopus subject areas
- Computational Theory and Mathematics