PhD Thesis Defence - Seyed Ali Tabatabaee

Name: Seyed Ali Tabatabaee

Date: Tuesday, 22 July 2025

Time: 11:00 am to 2:00 pm

Location: ICCS 202

Zoom Link: To be confirmed

Thesis Title: Optimization with Explorable Uncertainty

Abstract:

Many real-world problems involve elements (e.g., clients, jobs, etc.) with uncertain properties. Acquiring more accurate properties of these elements is often costly but sometimes necessary for high-quality solutions. The goal is to find such solutions through cost-effective strategies for obtaining more accurate information. The described model is often referred to as explorable uncertainty. This thesis studies optimization problems from the domains of facility location and job scheduling in the explorable uncertainty model. First, we study center problems with moving entities of bounded speed in Euclidean space, where the movement of the entities is unpredictable and processing must be done in real-time. Center problems involve determining the location of a facility to serve a set of entities while optimizing a specified objective function. In particular, we investigate computing the 1-center, centroid, center of mass, and 1-median for a set of moving entities. Next, motivated by the connections observed between these problems and perpetual scheduling problems, we shift our focus to study the latter in more depth. Perpetual scheduling problems involve jobs that require recurring processing. The goal is to process these jobs while optimizing a specified objective function. More specifically, we investigate two prominent examples of perpetual scheduling problems, namely the bamboo trimming problem and the windows scheduling problem, in settings that have not been considered before. Finally, we study these two scheduling problems in the model of explorable uncertainty, where jobs’ processing requirements can be reduced by taking some actions. We provide novel algorithms for the problems considered throughout this thesis. Our results contribute to a better understanding of the various forms of explorable uncertainty and the additional intricacy introduced to optimization problems when considered in this model.