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:	Publisher
Last Modified:	14 Oct 2016 09:02
URI:	http://gala.gre.ac.uk/id/eprint/1007

Actions (login required)

View Item