PhD Defense by Christopher Muir

Event Details
  • Date/Time:
    • Wednesday July 6, 2022 - Thursday July 7, 2022
      12:30 pm - 2:30 pm
  • Location: Groseclose 404
  • Phone:
  • URL: TEAMS
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Topics in Packing and Scheduling

Full Summary: No summary paragraph submitted.

Thesis Title: Topics in Packing and Scheduling

 

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 LinkTeams

 

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.

Additional Information

In Campus Calendar
No
Groups

Graduate Studies

Invited Audience
Faculty/Staff, Public, Undergraduate students
Categories
Other/Miscellaneous
Keywords
Phd Defense
Status
  • Created By: Tatianna Richardson
  • Workflow Status: Published
  • Created On: Jun 21, 2022 - 1:34pm
  • Last Updated: Jun 21, 2022 - 1:34pm