Back to search

University of British Columbia

Optimization with explorable uncertainty

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tabatabaee, Seyed Ali
Contributors dc:contributor
  • Evans, William

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/91837

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Tabatabaee, Seyed Ali. Optimization with explorable uncertainty. doctoral thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/91837