ME Seminar Series:A Stochastic Branch and Bound-based Methodology for Sequencing and Scheduling in the Presence of Uncertainty

Oct 8

Monday, October 8, 2012

11:30 am - 1:00 pm
Hudson Hall 125

I will present a novel approach to making sequencing and scheduling decisions in the presence of uncertainty that is based on the stochastic branch and bound algorithm, and illustrate through a computational study how it may be used to find optimal, or close to optimal solutions to the stochastic airport runway scheduling problem, where the objective is to find a sequence of aircraft operations on one or several runways that minimizes the total make-span, given uncertain aircraft availability at the runway. I will show how the proposed enhancements to the general stochastic branch and bound algorithm significantly decrease the runtime without sacrificing solution quality, and explain how, through the introduction of dynamic sample sizes, the algorithm is able to place less emphasis on non-promising branches of the branching tree, resulting in reductions in runtime of up to 30% when the make-span is minimized and up to 70% when minimization of system delay is considered; as well as sequences with 5% to 7% shorter make-spans than the sequences obtained using deterministic sequencing models. Finally, I will postulate how the proposed methodology might be used to make sequencing and scheduling decisions in all aspects of aviation and manufacturing where there is significant uncertainty.


Thompson, Michele