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

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>