# Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack

Kellerer, Hans and Strusevich, Vitaly A. (2010) *Minimizing total weighted earliness-tardiness on a single machine around a small common due date: an FPTAS using quadratic knapsack.* International Journal of Foundations of Computer Science (IJFCS) , 21 (3). pp. 357-383. ISSN 0129-0541 (print) 1793-6373 (online) (doi:10.1142/S0129054110007301)

## Abstract

We design a fully polynomial-time approximation scheme (FPTAS) for a single machine scheduling problem to minimize the total weighted earliness and tardiness with respect to a common restrictive due date. Notice that for this problem no constant-ratio approximation algorithm has been known so far. Our approach is based on adopting an FPTAS for a special version of the knapsack problem to minimize a convex quadratic non-separable function. For the continuous relaxation of such a knapsack problem we give an algorithm of a quadratic time complexity. The running time of the resulting FPTAS is strongly polynomial.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | quadratic knapsack, single machine scheduling, earliness-tardiness, FPTAS |

Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 08 Jan 2013 14:01 |

URI: | http://gala.gre.ac.uk/id/eprint/5654 |

### Actions (login required)

View Item |