This dissertation, which consists of four parts, is to (i) present a mixed integer
programming model for the strategic design of an assembly system in the international
business environment established by the North American Free Trade Agreement
(NAFTA) with the focus on modeling the material flow network with assembly
operations, (ii) compare different decomposition schemes and acceleration techniques to
devise an effective branch-and-price solution approach, (iii) introduce a generalization of
Dantzig-Wolf Decomposition (DWD), and (iv) propose a combination of dual-ascent
and primal drop heuristics.
The model deals with a broad set of design issues (bill-of-materials restrictions,
international financial considerations, and material flows through the entire supply chain)
using effective modeling devices. The first part especially focuses on modeling material
flows in such an assembly system.
The second part is to study several schemes for applying DWD to the productionassembly-
distribution system design problem (PADSDP). Each scheme exploits
selected embedded structures. The research objective is to enhance the rate of DWD convergence in application to PADSDP through formulating a rationale for
decomposition by analyzing potential schemes, adopting acceleration techniques, and
assessing the impacts of schemes and techniques computationally. Test results provide
insights that may be relevant to other applications of DWD.
The third part proposes a generalization of column generation, reformulating the
master problem with fewer variables at the expense of adding more constraints; the subproblem
structure does not change. It shows both analytically and computationally that
the reformulation promotes faster convergence to an optimal solution in application to a
linear program and to the relaxation of an integer program at each node in the branchand-
bound tree. Further, it shows that this reformulation subsumes and generalizes prior
approaches that have been shown to improve the rate of convergence in special cases.
The last part proposes two dual-ascent algorithms and uses each in combination
with a primal drop heuristic to solve the uncapacitated PADSDP, which is formulated as
a mixed integer program. Computational results indicate that one combined heuristic
finds solutions within 0.15% of optimality in most cases and within reasonable time, an
efficacy suiting it well for actual large-scale applications.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2529 |
| Date | 15 May 2009 |
| Creators | Liang, Dong |
| Contributors | Wilhelm, Wilbert E. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.0023 seconds