Please use this identifier to cite or link to this item:
http://hdl.handle.net/11375/9499
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Karakostas, George | en_US |
dc.contributor.author | Wang, Jing | en_US |
dc.date.accessioned | 2014-06-18T16:47:21Z | - |
dc.date.available | 2014-06-18T16:47:21Z | - |
dc.date.created | 2011-06-07 | en_US |
dc.date.issued | 2009 | en_US |
dc.identifier.other | opendissertations/4617 | en_US |
dc.identifier.other | 5635 | en_US |
dc.identifier.other | 2050099 | en_US |
dc.identifier.uri | http://hdl.handle.net/11375/9499 | - |
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> | en_US |
dc.subject | Computational Engineering and Science | en_US |
dc.subject | Computational Engineering | en_US |
dc.subject | Computational Engineering | en_US |
dc.title | An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates | en_US |
dc.type | thesis | en_US |
dc.contributor.department | Computational Engineering and Science | en_US |
dc.description.degree | Master of Applied Science (MASc) | en_US |
Appears in Collections: | Open Access Dissertations and Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
fulltext.pdf | 2.29 MB | Adobe PDF | View/Open |
Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.