This dissertation discusses two independent topics: a resource-constrained shortest-path problem
(RCSP) and a literature review on scheduling problems involving sequence-dependent setup
(SDS) times (costs).
RCSP is often used as a subproblem in column generation because it can be used to
solve many practical problems. This dissertation studies RCSP with multiple resource
constraints on an acyclic graph, because many applications involve this configuration, especially
in column genetation formulations. In particular, this research focuses on a dynamic RCSP
since, as a subproblem in column generation, objective function coefficients are updated using
new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial
solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic
graph with the goal of effectively reoptimizing RCSP in the context of column generation. This
method uses a one-time âÂÂpreliminaryâ phase to transform RCSP into an unconstrained shortest
path problem (SPP) and then solves the resulting SPP after new values of dual variables are used
to update objective function coefficients (i.e., reduced costs) at each iteration. Network
reduction techniques are considered to remove some nodes and/or arcs permanently in the preliminary phase. Specified techniques are explored to reoptimize when only several
coefficients change and for dealing with forbidden and prescribed arcs in the context of a column
generation/branch-and-bound approach. As a benchmark method, a label-setting algorithm is
also proposed. Computational tests are designed to show the effectiveness of the proposed
algorithms and procedures.
This dissertation also gives a literature review related to the class of scheduling
problems that involve SDS times (costs), an important consideration in many practical
applications. It focuses on papers published within the last decade, addressing a variety of
machine configurations - single machine, parallel machine, flow shop, and job shop - reviewing
both optimizing and heuristic solution methods in each category. Since lot-sizing is so
intimately related to scheduling, this dissertation reviews work that integrates these issues in
relationship to each configuration. This dissertation provides a perspective of this line of
research, gives conclusions, and discusses fertile research opportunities posed by this class of
scheduling problems.
since, as a subproblem in column generation, objective function coefficients are updated using
new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial
solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic
graph with the goal of effectively reoptimizing RCSP in the context of column generation. This
method uses a one-time
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/4996 |
| Date | 25 April 2007 |
| Creators | Zhu, Xiaoyan |
| Contributors | Wilhelm, Wilbert E. |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | 990793 bytes, electronic, application/pdf, born digital |
Page generated in 0.002 seconds