arXiv Open Access 2016

A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time Objective

Martin Skutella

Lihat Sumber

Abstrak

We present a $\sqrt{e}/(\sqrt{e}-1)$-approximation algorithm for the nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on a single machine subject to release dates and precedence constraints. The previously best known approximation algorithm dates back to 1997; its performance guarantee can be made arbitrarily close to the Euler constant $e$.

Topik & Kata Kunci

cs.DM math.OC

Penulis (1)

Martin Skutella

Format Sitasi

APA MLA BibTeX

Skutella, M. (2016). A 2.542-Approximation for Precedence Constrained Single Machine Scheduling with Release Dates and Total Weighted Completion Time Objective. https://arxiv.org/abs/1603.04690

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2016
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓