An approximation algorithm for Demand Strip Packing with moldable jobs

Abstract

In Strip Packing (SP), the aim is to place a set of rectangles, often called jobs, inside a strip with a bounded width D and infinite height with no overlaps whilst minimizing the height needed to fit all jobs. In Demand Strip Packing (DSP), we relax this problem by allowing jobs to be sliced vertically. DSP can more accurately model certain problems such as electricity allocation whilst also allowing for better optimal solutions than SP. In some applications, it may be the case that a specific job could be scheduled in multiple ways. We say that a job is moldable if there are multiple options for its processing time and energy demand. The goal of the problem now becomes to find both the optimal way of scheduling the jobs but also which processing configuration each job should use. Both SP and DSP are NP-hard problems and thus, obtaining optimal solutions to instances of these problems is not computationally feasible. Instead, research is focused on developing approximation algorithms which can find a solution that is “good enough” whilst running in polynomial time. In this thesis, we present an approximation algorithm for DSP with moldable jobs. The algorithm runs in polynomial time with respect to the number of jobs and returns a packing whose peak demand is at most (3/2 + ε) times the optimal peak demand for some ε > 0. This result is very close to the best possible approximation ratio, proven to be 3/2 for DSP. The algorithm as constructed, as well as the approximation ratio, is dependent on an assumption that will be a focus of further study. Key to the design of this algorithm is our approach of transforming an optimal packing in a particular way such that a strong structural result holds. The algorithm then makes heavy use of guessing and linear programming to find a feasible solution within the approximation ratio.