Back to search

McMaster University

New dominance orders for scheduling problems

Abstract

dc:description.abstract

<p>A sequencing problem involves finding a sequence in which to process a set of jobs that minimizes a given cost function. The primary difficulty with such problems is that as the number of jobs increases the number of sequences grows astronomically large, and the problems become intractable. Pairwise job interchange is one of the most commonly used solution techniques for sequencing problems. It compares the cost of sequences that differ only in the interchange of two jobs. In this way the cost function indicates a preference for the ordering of certain pairs of jobs such that if a pair of jobs is not in preference order, then the jobs can be interchanged with no increase in cost. The traditional method of pairwise job interchange assumes that either there are no intermediate jobs (adjacent pairwise interchange ) or that an interchange can be performed no matter what the intermediate jobs are (nonadjacent pairwise interchange ). In this thesis we introduce a generalization that permits the pairwise interchange of a pair of jobs provided that the intermediate jobs belong to a restricted subset of jobs (subset -restricted pairwise interchange ). We use subset-restricted pairwise interchange to derive a dominance order on the jobs. This is a partial ordering of the jobs that consists of pairs whose relative order can be fixed in an optimal sequence. The search space can then be reduced to consist of only those sequences that satisfy the relative job orderings in the dominance order. We apply this technique to certain one- and two-machine sequencing problems, and show that the use of our dominance orders significantly reduces the computation time necessary to solve these problems.</p>

Degree

thesis:*
Department dc:contributor.department
Business Administration
Year dc:date.issued
1999

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Stephenson, Paul A.
Advisor dc:contributor.advisor
  • Steiner, George

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/1948
2953
1353048

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

Stephenson, Paul A.. New dominance orders for scheduling problems. 1999. http://hdl.handle.net/11375/6641