Non-Preemptive Scheduling on Machines with Setup Times

Autor:	Mäcker, Alexander, Malatyali, Manuel, der Heide, Friedhelm Meyer auf, Riechers, Sören
Rok vydání:	2015
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n, m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3/2. Comment: A conference version of this paper has been accepted for publication in the proceedings of the 14th Algorithms and Data Structures Symposium (WADS)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1504.07066 Zobrazit plný text záznamu View this record from Arxiv