{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/9499"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/9499","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates","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>","abstract_html":"&lt;p&gt;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.&lt;/p&gt; &lt;p&gt;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.&lt;/p&gt; &lt;p&gt;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.&lt;/p&gt;","abstract_has_math":false,"creators":["Wang, Jing"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computational Engineering and Science","school":null,"contributors":[],"advisors":["Karakostas, George"],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-11-18T19:33:35Z","subjects":["Computational Engineering and Science","Computational Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/14571"],"render_values":[{"text":"https://doi.org/10.71548/14571","href":"https://doi.org/10.71548/14571","code":true}]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/4617","5635","2050099"],"render_values":[{"text":"opendissertations/4617","href":null,"code":true},{"text":"5635","href":null,"code":true},{"text":"2050099","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11375/9499","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"http://hdl.handle.net/11375/9499","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F9499","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Karakostas, George"]},{"key":"dc:contributor.department","label":"Department","values":["Computational Engineering and Science"]},{"key":"dc:creator","label":"Author","values":["Wang, Jing"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-06-18T16:47:21Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-18T16:47:21Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2011-06-07"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Engineering and Science","Computational Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["opendissertations/4617","5635","2050099"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11375/9499","https://doi.org/10.71548/14571"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["<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>"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Applied Science (MASc)"]},{"key":"dc:title","label":"Title","values":["An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Karakostas, George"],"dc:contributor.department":["Computational Engineering and Science"],"dc:creator":["Wang, Jing"],"dc:date.accessioned":["2014-06-18T16:47:21Z"],"dc:date.available":["2014-06-18T16:47:21Z"],"dc:date.created":["2011-06-07"],"dc:date.issued":["2009"],"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>"],"dc:description.degree":["Master of Applied Science (MASc)"],"dc:identifier.other":["opendissertations/4617","5635","2050099"],"dc:identifier.uri":["http://hdl.handle.net/11375/9499","https://doi.org/10.71548/14571"],"dc:subject":["Computational Engineering and Science","Computational Engineering"],"dc:title":["An FPTAS for the Single Machine Minimum Total Weighted Tardiness Problem With a Fixed Number of Distinct Due Dates"],"dc:type":["thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:33:35Z"}