Degree Type

Dissertation

Date of Award

2018

Degree Name

Doctor of Philosophy

Department

Industrial and Manufacturing Systems Engineering

Major

Industrial and Manufacturing Systems Engineering

First Advisor

Sarah M. Ryan

Abstract

This dissertation presents an integrated method for solving stochastic mixed-integer programs, develops a lower bounding approach for multistage risk-averse stochastic mixed-integer programs, and proposes an optimization formulation for mixed-model assembly line sequencing (MMALS) problems.

It is well known that a stochastic mixed-integer program is difficult to solve due to its non-convexity and stochastic factors. The scenario decomposition algorithms display computational advantage when dealing with a large number of possible realizations of uncertainties, but each has its own advantages and disadvantages. This dissertation presents a solution method for solving large-scale stochastic mixed-integer programs that integrates two scenario-decomposition algorithms: Progressive Hedging (PH) and Dual Decomposition (DD). In this integrated method, fast progress in early iterations of PH speeds up the convergence of DD to an exact solution.

In many applications, the decision makers are risk-averse and are more concerned with large losses in the worst scenarios than with average performance. The PH algorithm can serve as a time-efficient heuristic for risk-averse stochastic mixed-integer programs with many scenarios, but the scenario reformulation for time consistent multistage risk-averse models does not exist. This dissertation develops a scenario-decomposed version of time consistent multistage risk-averse programs, and proposes a lower bounding approach that can assess the quality of PH solutions and thus identify whether the PH algorithm is able to find near-optimal solutions within a reasonable amount of time.

The existing optimization formulations for MMALS problems do not consider many real-world uncertainty factors such as timely part delivery and material quality. In addition, real-time sequencing decisions are required to deal with inevitable disruptions. This dissertation formulates a multistage stochastic optimization problem with part availability uncertainty. A risk-averse model is further developed to guarantee customers’ satisfaction regarding on-time performance.

Computational studies show that the integration of PH helps DD to reduce the run-time significantly, and the lower bounding approach can obtain convergent and tight lower bounds to help PH evaluate quality of solutions. The PH algorithm and the lower bounding approach also help the proposed MMALS formulation to make real-time sequencing decisions.

DOI

https://doi.org/10.31274/etd-180810-5994

Copyright Owner

Ge Guo

Language

en

File Format

application/pdf

File Size

112 pages

Share

COinS