Date and Time: Wednesday, May 13, 2020 at 8:30 AM (EDT)

BlueJeans Meeting ID:  291 070 490

Link:  https://bluejeans.com/291070490
Title:  Investigations in Time-Dependent Combinatorial Optimization Problems and Their Applications

Advisor: Dr. Martin Savelsbergh (ISyE, Georgia Tech)

Committee Members:

Dr. Natashia Boland (ISyE, Georgia Tech)

Dr. Alejandro Toriello (ISyE, Georgia Tech)

Dr. Chelsea White (ISyE, Georgia Tech)

Dr. Karen Feigh (Aerospace Engineering, Georgia Tech)

Summary:

We explore three distinct but related combinatorial optimization problems involving time. 

Chapter 2 focuses on a time-indexed integer programming (IP) formulation for solving the Traveling Salesman Problem with Time Windows (TSPTW) exactly.  The linear programming relaxation of this formulation provides a strong lower bound on its optimal value, making it an excellent candidate for use in branch-and-bound type solution algorithms, but the number of variables required to model large instances makes solving it very difficult and time-consuming.  With this challenge in mind, we propose a Lagrangian duality-based variable elimination scheme designed to identify infeasible or provably sub-optimal time points that need not be included in the time-indexed IP model.  Results for several instances from the literature are presented.

Chapter 3 shifts to a more applied setting, examining a scheduling problem currently faced by mission planners at NASA.  One of the many problems that deep space travel (to Mars and beyond) presents is a significant lag time in communications between mission control and spacecraft as they move further away from Earth.  At present, planners at mission control build minute-by-minute daily schedules for astronaut crews and update them in real time when circumstances require it, but with significant communications delays in deep space, astronauts will need increased autonomy, as well as automated assistance, in building and adjusting their own schedules.

We present and discuss a prototype semi-autonomous scheduling system built in collaboration with colleagues from aerospace engineering to assist mission crews with rapid on-board re-planning in off-nominal (i.e. unanticipated) or emergency scenarios.  We demonstrate the system's re-planning capabilities with two distinct case studies.

In Chapter 4, we examine a more general scheduling problem that is in some sense a natural offshoot of the work in Chapter 3.  The problem of interest is that of scheduling jobs with start time-dependent deteriorating processing times on a single machine to minimize makespan (i.e. time to completion) when one or more fixed-length maintenance periods may be scheduled to mitigate deterioration.  In particular, the processing time for a job j with start time t has the linear form p_j(t)=p_j+a_jt, where p_j is a base processing time and a_j>0 is a deterioration rate.  We begin with a discussion of the problem's structure, follow this with two proposed IP formulations (one exact and one approximate), and finish with a computational analysis of several greedy heuristics designed to quickly obtain high-quality solutions.