Back to search

McMaster University

Single Machine Total Weighted Tardiness With Release Dates

Abstract

dc:description.abstract

<p>The single machine total weighted tardiness with release dates problem is known to be strongly NP-hard. With a new lower bounding scheme and a new upper bounding scheme, we get an efficient branch and bound algorithm. In the paper, we first introduce the history of the problem and its computational complexity. Second, the lower bounding schemes and the upper bounding schemes are described in detail. We also present all the dominance rules used in the branch and bound algorithm to solve the problem.</p> <p>In the dominance rules part, we describe the labeling scheme and suggest a data structure for a dominance rule.</p> <p>Finally, we implement the branch and bound algorithm in C++ for the problem with all the techniques introduced above. We present numerical results produced by the program. Using the same instance generating scheme and the test instances from Dr. Jouglet, our results show that this branch and bound method outperforms the previous approaches specialized for the problem.</p>

Degree

thesis:*
Department dc:contributor.department
Computational Engineering and Science
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jing, Wei
Advisor dc:contributor.advisor
  • Steiner, George

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/4621
5639
2050378

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

Jing, Wei. Single Machine Total Weighted Tardiness With Release Dates. 2009. http://hdl.handle.net/11375/9504