Skip navigation
  • Home
  • Browse
    • Communities
      & Collections
    • Browse Items by:
    • Publication Date
    • Author
    • Title
    • Subject
    • Department
  • Sign on to:
    • My MacSphere
    • Receive email
      updates
    • Edit Profile


McMaster University Home Page
  1. MacSphere
  2. Open Access Dissertations and Theses Community
  3. Open Access Dissertations and Theses
Please use this identifier to cite or link to this item: http://hdl.handle.net/11375/9499
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorKarakostas, Georgeen_US
dc.contributor.authorWang, Jingen_US
dc.date.accessioned2014-06-18T16:47:21Z-
dc.date.available2014-06-18T16:47:21Z-
dc.date.created2011-06-07en_US
dc.date.issued2009en_US
dc.identifier.otheropendissertations/4617en_US
dc.identifier.other5635en_US
dc.identifier.other2050099en_US
dc.identifier.urihttp://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.subjectComputational Engineering and Scienceen_US
dc.subjectComputational Engineeringen_US
dc.subjectComputational Engineeringen_US
dc.titleAn FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Datesen_US
dc.typethesisen_US
dc.contributor.departmentComputational Engineering and Scienceen_US
dc.description.degreeMaster of Applied Science (MASc)en_US
Appears in Collections:Open Access Dissertations and Theses

Files in This Item:
File SizeFormat 
fulltext.pdf
Open Access
2.29 MBAdobe PDFView/Open
Show simple item record Statistics


Items in MacSphere are protected by copyright, with all rights reserved, unless otherwise indicated.

Sherman Centre for Digital Scholarship     McMaster University Libraries
©2022 McMaster University, 1280 Main Street West, Hamilton, Ontario L8S 4L8 | 905-525-9140 | Contact Us | Terms of Use & Privacy Policy | Feedback

Report Accessibility Issue