Approximating Weighted Completion Time for Order Scheduling with Setup Times

Autor:	Mäcker, Alexander, der Heide, Friedhelm Meyer auf, Pukrop, Simon
Rok vydání:	2019
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	Consider a scheduling problem in which jobs need to be processed on a single machine. Each job has a weight and is composed of several operations belonging to different families. The machine needs to perform a setup between the processing of operations of different families. A job is completed when its latest operation completes and the goal is to minimize the total weighted completion time of all jobs. We study this problem from the perspective of approximability and provide constant factor approximations as well as an inapproximability result. Prior to this work, only the NP-hardness of the unweighted case and the polynomial solvability of a certain special case were known. Comment: This paper was accepted for puplication in the proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1910.08360 Zobrazit plný text záznamu View this record from Arxiv