Back to search

McMaster University

An FPTAS for Total Weighted Earliness Tardiness Problem with Constant Number of Distinct Due Dates and Polynomially Related Weights

Abstract

dc:description.abstract

<p>We are given a sequence of jobs on a single machine, and each job has a weight, processing time and a due date. A job is early when it finishes before or on its due date and its earliness is the amount of time between its completion time and its due date. A job is tardy when it finishes after its due date and its tardiness is the amount of time between its due date and its completion time. The TWET problem is to find a schedule which minimizes the total weighted earliness and tardiness. We are focusing on the TWET problem with a constant number of distinct due dates and polynomially related weights. This problem has been proven to be NP-hard. In this thesis, we present a dynamic programming algorithm for our TWET problem first and then convert it into an FPTAS by adopting a rounding scheme.</p> <p>There are several important points in our algorithm: we observe the importance of the straddlers and guess them at the beginning through exhaustive enumeration, and insert them back at the very end by solving a linear problem; we know a series of structural properties of the optimal schedule to shrink the state space of the DP; we increase each due date to get a new problem and adopt a rounding scheme of the DP for the new problem to avoid preemption. Finally we move the due dates back to get the final schedule for the original TWET problem without changing the objective value much.</p>

Degree

thesis:*
Department dc:contributor.department
Computer Science
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Huang, Jingjing
Advisor dc:contributor.advisor
  • Karakostas, George

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/7811
8891
4144975

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

Huang, Jingjing. An FPTAS for Total Weighted Earliness Tardiness Problem with Constant Number of Distinct Due Dates and Polynomially Related Weights. 2013. http://hdl.handle.net/11375/12972