Strip packing with precedence constraints and strip packing with release times

• DOI: 10.1016/j.tcs.2009.05.024
• Publication Date: 2009-05-29T13:15:40Z
• Authors: John Augustine; Sudarshan Banerjee; Sandy Irani
• Keywords: Field programmable gate array; 0211 other engineering and technologies; 02 engineering and technology; 0102 computer and information sciences; 01 natural sciences; Approximation algorithms; Theoretical Computer Science; Strip packing; Linear programming; Precedence constraints; Computer Science(all)

AbstractThe strip packing problem seeks to tightly pack a set of n rectangles into a strip of fixed width and arbitrary height. The rectangles model tasks and the height models time. This paper examines two variants of strip packing: when the rectangles to be placed have precedence constraints and when the rectangles have release times. Strip packing is used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. The variants studied here are motivated by scheduling tasks for dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs) comprised of a linear arrangement of K homogeneous computing resources, where K is a fixed positive integer, and each task occupies a contiguous subset of these resources. For the case in which tasks have precedence constraints, we give an O(logn) approximation algorithm. We then consider the special case in which all the rectangles have uniform height, and reduce it to the resource constrained scheduling studied by Garey, Graham, Johnson and Yao, thereby extending their asymptotic results to our special case problem. We also give an absolute 3-approximation for this special case problem. For strip packing with release times, we provide an asymptotic polynomial time approximation scheme. We make the standard assumption that the rectangles have height at most 1. In addition, we also require widths to be in [1K,1]. For the FPGA application, this would imply that the rectangles are at least as wide as a column. Our running time is polynomial in n and 1/ϵ, but exponential in K.