Title: Non-preemptive Scheduling with Setup Times: A PTAS
Abstract: Consider the following scheduling problem: a set of jobs is to be processed without preemption on m identical machines. The jobs are partitioned into classes. Before jobs from a class can be processed on a machine, a setup is required, whose duration depends on the class. The objective is to schedule all jobs while minimizing the completion time of the last job, also known as the makespan. We present and analyze three polynomial algorithms for this problem. The first algorithm follows a next-fit strategy and has approximation ratio 3. The second is a very efficient algorithm with approximation ratio arbitrarily close to 2. The last algorithm is a polynomial time approximation scheme.
Publication Year: 2016
Publication Date: 2016-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 6
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot