Back to search

McMaster University

An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates

Abstract

dc:description.abstract

<p>This thesis provides a Fully Polynomial Time Approximation Scheme (FPTAS) for the minimum total weighted tardiness (TWT) problem with a constant number ofdistinct due dates.</p> <p>Given a sequence ofjobs on a single machine, each with a weight, processing time, and a due date, the tardiness of a job is the amount of time that its completion time goes beyond its due date. The TWT problem is to find a schedule of the given jobs such that the total weighted tardiness is minimized. This problem is NP-hard even when the number of distinct due dates is fixed. In this thesis, we present a dynamic programming algorithm for the TWT problem with a constant number of distinct due dates first and then adopt a rounding scheme to obtain an FPTAS.</p> <p>Three major points that we make in this algoritlun are: we observe a series of structural properties of optimal schedules so that we shrink the state space of the DP; we make use of preemption (i.e. allowing the processing of a job to be interrupted and restarted later) for the design of the DP; the rounding scheme that we adopt guarantees that a factor 1+ ℇ of the optimal solution is generated and the algorithm runs within a polynomial time of the problem size.</p>

Degree

thesis:*
Department dc:contributor.department
Computational Engineering and Science
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Jing
Advisor dc:contributor.advisor
  • Karakostas, George

Subjects

dc:subject × 2

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/4617
5635
2050099

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Wang, Jing. An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates. 2009. http://hdl.handle.net/11375/9499