Advisor:

Dr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Thesis Committee:

Dr. Santanu Dey, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Mohit Singh, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Siva Theja Maguluri, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Luke Marshall, Microsoft Research

Date and Time: Wednesday, July 6th, 2022, 12:30 pm EDT

Location: Groseclose 404

Meeting Link: Teams

Abstract: 

Packing and scheduling models include some of the most fundamental problems in operations research and computer science.  These broad classes include a wide range of models with applications including logistics, production planning, wireless network design, circuit design, and cloud computing, to name a few.  In this thesis we study three such models: dynamic node packing, interval scheduling with economies of scale, and temporal bin packing with half-capacity jobs; each extends on a well-known problem in packing and scheduling.  While the problems are generally distinct, this research was broadly inspired by applications to cloud computing.  Specifically, this thesis is motivated by problems cloud service providers face when servicing requests for virtual machines.

In Chapter 2, we propose a dynamic version of the node packing problem.  In this model, instead of being given the edges upfront, we model them as Bernoulli random variables.  At each step, the decision maker selects an available node and then observes edges adjacent to this node.  The goal is a policy that maximizes the expected value of the resulting packing.  We model the problem as a Markov decision problem and conduct a polyhedral study of the problem's achievable probabilities polytope.  We develop a variety of valid inequalities based on paths, cycles, and cliques.

In Chapter 3, we study interval scheduling problems exhibiting economies of scale.  An instance is given by a set of interval jobs and a cost function.  Specifically, we focus on the max-weight function and non-negative, non-decreasing concave functions of total schedule weight.  The goal is a partition of the jobs minimizing the total cost with the constraint that jobs within the same schedule cannot overlap.  We propose a set covering formulation and a column generation algorithm to solve its linear relaxation, providing efficient pricing algorithms for the studied cases. To obtain integer solutions, we extend the column generation approach using branch-and-price.

In Chapter 4, we study a different model with interval jobs.  In this problem, interval jobs are partitioned into bins such that at most two jobs in a bin overlap at once.  The decision maker is tasked with minimizing the time-average number of bins required to pack all jobs.  We call this problem temporal bin packing with half-capacity jobs; it is a special case of the general temporal bin packing problem with bounded parallelism.  We study the worst-case performance of a well-known static lower bound, and, motivated by this analysis, we introduce a novel lower bound and integer programming formulation based on formulating the problem as a series of matching problems.  We provide theoretical guarantees on the relative strengths of the static bound, the matching-based bound, and various linear programming bounds.