Scheduling with job release dates, delivery times and preemption penalties

✍ Scribed by Zhaohui Liu; T.C.Edwin Cheng

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 73 KB
• Volume: 82
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00251-4

✦ Synopsis

We consider in this paper the single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties, where each time a job is started, whether initially or after preemption, a job-dependent setup must take place. First, we prove that the problem is strongly NP-hard. Then, we present a dynamic programming algorithm and a polynomial time approximation scheme.