<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> / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/6641 |
| Date | 02 1900 |
| Creators | Stephenson, Paul A. |
| Contributors | Steiner, George, Business Administration |
| Source Sets | McMaster University |
| Detected Language | English |
| Type | thesis |
Page generated in 0.0079 seconds