Strip packing with precedence constraints and strip packing with release times

• Published in: Theoretical computer science 2009-09, Vol.410 (38), p.3792-3803
• Main Authors: Augustine, John, Banerjee, Sudarshan, Irani, Sandy
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Approximation algorithms; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Computer systems performance. Reliability; Designs and configurations; Exact sciences and technology; Field programmable gate array; Linear programming; Mathematics; Miscellaneous; Precedence constraints; Sciences and techniques of general use; Software; Strip packing; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2009.05.024

The 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 ( log n ) 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 [ 1 K , 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 .