{"659004":{"#nid":"659004","#data":{"type":"event","title":"PhD Defense by Christopher Muir","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EThesis Title\u003C\/strong\u003E: Topics in Packing and Scheduling\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAdvisor:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EThesis Committee:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Santanu Dey, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Mohit Singh, H. Milton Stewart\u0026nbsp;School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Siva Theja Maguluri,\u0026nbsp;H. Milton Stewart\u0026nbsp;School of Industrial and Systems Engineering, Georgia Tech\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Luke Marshall, Microsoft Research\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EDate and Time\u003C\/strong\u003E: Wednesday, July 6th, 2022, 12:30 pm EDT\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ELocation\u003C\/strong\u003E:\u0026nbsp;Groseclose 404\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EMeeting Link\u003C\/strong\u003E:\u0026nbsp;\u003Ca href=\u0022https:\/\/teams.microsoft.com\/l\/meetup-join\/19%3ameeting_YWRlY2Q5NTgtNTI3Yy00YTVkLWJmNzYtMmRhMTU1YjY4NDA5%40thread.v2\/0?context=%7b%22Tid%22%3a%22482198bb-ae7b-4b25-8b7a-6d7f32faa083%22%2c%22Oid%22%3a%223c50581e-1aaf-4d1e-8ada-7b4cf43bd8f5%22%7d\u0022 title=\u0022https:\/\/teams.microsoft.com\/l\/meetup-join\/19%3ameeting_YWRlY2Q5NTgtNTI3Yy00YTVkLWJmNzYtMmRhMTU1YjY4NDA5%40thread.v2\/0?context=%7b%22Tid%22%3a%22482198bb-ae7b-4b25-8b7a-6d7f32faa083%22%2c%22Oid%22%3a%223c50581e-1aaf-4d1e-8ada-7b4cf43bd8f5%22%7d\u0022\u003ETeams\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPacking and scheduling models include some of the most fundamental problems in operations research and computer science. \u0026nbsp;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.\u0026nbsp;\u0026nbsp;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. \u0026nbsp;While the problems are generally distinct, this research was broadly inspired by applications to cloud computing. \u0026nbsp;Specifically, this thesis is motivated by problems cloud service providers face when servicing requests for virtual machines.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn Chapter 2, we propose a dynamic version of the node packing problem. \u0026nbsp;In this model, instead of being given the edges upfront, we model them as Bernoulli random variables. \u0026nbsp;At each step, the decision maker selects an available node and then observes edges adjacent to this node. \u0026nbsp;The goal is a policy that maximizes the expected value of the resulting packing. \u0026nbsp;We model the problem as a Markov decision problem and conduct a polyhedral study of the problem\u0026#39;s achievable probabilities polytope. \u0026nbsp;We develop a variety of valid inequalities based on paths, cycles, and cliques.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn Chapter 3, we study interval scheduling problems exhibiting economies of scale. \u0026nbsp;An instance is given by a set of interval jobs and a cost function. \u0026nbsp;Specifically, we focus on the max-weight function and non-negative, non-decreasing concave functions of total schedule weight. \u0026nbsp;The goal is a partition of the jobs minimizing the total cost with the constraint that jobs within the same schedule cannot overlap. \u0026nbsp;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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn Chapter 4, we study a different model with interval jobs. \u0026nbsp;In this problem, interval jobs are partitioned into bins such that at most two jobs in a bin overlap at once. \u0026nbsp;The decision maker is tasked with minimizing the time-average number of bins required to pack all jobs. \u0026nbsp;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. \u0026nbsp;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.\u0026nbsp; We provide theoretical guarantees on the relative strengths of the static bound, the matching-based bound, and various linear programming bounds.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Topics in Packing and Scheduling"}],"uid":"27707","created_gmt":"2022-06-21 17:34:12","changed_gmt":"2022-06-21 17:34:12","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-07-06T13:30:00-04:00","event_time_end":"2022-07-07T15:30:00-04:00","event_time_end_last":"2022-07-07T15:30:00-04:00","gmt_time_start":"2022-07-06 17:30:00","gmt_time_end":"2022-07-07 19:30:00","gmt_time_end_last":"2022-07-07 19:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}