Skip navigation

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

Kelleler, Hans and Strusevich, Vitaly a. (2006) A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. Theoretical Computer Science, 369. pp. 230-238. ISSN 0304-3975 (doi:10.1016/j.tcs.2006.08.030)

Full text not available from this repository.

Abstract

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

Item Type: Article
Additional Information: [1] Accepted: 25 August 2006. [2] First published online: 1 September 2006. [3] Published in print: 15 December 2006.
Uncontrolled Keywords: single machine scheduling, weighted total tardiness, dynamic programming, FPTAS
Subjects: Q Science > QA Mathematics > QA76 Computer software
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Related URLs:
Last Modified: 14 Oct 2016 09:02
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/1007

Actions (login required)

View Item View Item