×

Strip packing with precedence constraints and strip packing with release times. (English) Zbl 1171.68050

Summary: 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 \([\frac{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/\varepsilon\), but exponential in \(K\).

MSC:

68W25 Approximation algorithms
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Augustine, J.; Seiden, S., Linear time approximation schemes for vehicle scheduling problems, Theoret. Comput. Sci., 324, 2-3, 147-160 (2004) · Zbl 1091.90015
[2] Baker, B. S.; Brown, D. J.; Katseff, H. P., A 5/4 algorithm for two-dimensional packing., J. Algorithms, 2, 4, 348-368 (1981) · Zbl 0472.68032
[3] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packings in two dimensions., SIAM J. Comput., 9, 4, 846-855 (1980) · Zbl 0447.68080
[4] S. Banerjee, E. Bozorgzadeh, N. Dutt, Physically-aware hw-sw partitioning for reconfigurable architectures with partial dynamic reconfiguration, in: Design Automation Conference, 2005, pp. 335-340; S. Banerjee, E. Bozorgzadeh, N. Dutt, Physically-aware hw-sw partitioning for reconfigurable architectures with partial dynamic reconfiguration, in: Design Automation Conference, 2005, pp. 335-340
[5] Buchsbaum, A. L.; Karloff, H.; Kenyon, C.; Reingold, N.; Thorup, M., Opt versus load in dynamic storage allocation, SIAM J. Comput., 33, 3, 632-646 (2004) · Zbl 1101.68599
[6] Coffman, E. G.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E., Performance bounds for level-oriented two-dimensional packing algorithms., SIAM J. Comput., 9, 4, 808-826 (1980) · Zbl 0447.68079
[7] Csirik, J.; Woeginger, G. J., Shelf algorithms for on-line strip packing, Inform. Process. Lett., 63, 4, 171-175 (1997) · Zbl 1336.68305
[8] de la Vega, W. F.; Lueker, G. S., Bin packing can be solved within \(1 + \epsilon\) in linear time, Combinatorica, 1, 4, 349-355 (1981) · Zbl 0485.68057
[9] de la Vega, W. F.; Zissimopoulos, V., An approximation scheme for strip packing of rectangles with bounded dimensions., Discrete Appl. Math., 82, 1-3, 93-101 (1998) · Zbl 0894.68114
[10] Grotschel, M.; Lovasz, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[11] Jansen, K.; van Stee, R., On strip packing with rotations, (Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing (2005), ACM Press: ACM Press New York, NY, USA), 755-761 · Zbl 1192.68908
[12] Jansen, K.; Zhang, H., Scheduling malleable tasks with precedence constraints, (Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (2005), ACM Press: ACM Press New York, NY, USA), 86-95
[13] Johnson, D. S.; Garey, M. R.; Graham, R. L.; Yao, A. C., Resource constrained scheduling as generalized bin packing, J. Combin. Theory, 21, 3, 257-298 (1976) · Zbl 0384.90053
[14] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[15] N. Karmarkar, R. Karp, An efficient approximation scheme for the one dimensional bin-packing problem, in: Proceedings of the 23rd Sympos. Foundations Computer Sci., FOCS, Tucson, AZ, 1982, pp. 312-320; N. Karmarkar, R. Karp, An efficient approximation scheme for the one dimensional bin-packing problem, in: Proceedings of the 23rd Sympos. Foundations Computer Sci., FOCS, Tucson, AZ, 1982, pp. 312-320
[16] Kenyon, C.; Rémila, E., A near-optimal solution to a two-dimensional cutting stock problem, Math. Oper. Res., 25, 4, 645-656 (2000) · Zbl 0977.90043
[17] Lepère, R.; Trystram, D.; Woeginger, G. J., Approximation algorithms for scheduling malleable tasks under precedence constraints, (Proceedings of the 9th Annual European Symposium on Algorithms (2001), Springer-Verlag: Springer-Verlag London, UK), 146-157 · Zbl 1006.68502
[18] Martel, C., Preemptive scheduling with release times, deadlines, and due times, J. Assoc. Comput. Mach., 29, 3, 812-829 (1982) · Zbl 0485.68033
[19] Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, INFORMS J. Comput., 15, 3, 310-319 (2003) · Zbl 1238.90116
[20] Mounie, G.; Rapine, C.; Trystram, D., Efficient approximation algorithms for scheduling malleable tasks, (Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (1999), ACM Press: ACM Press New York, NY, USA), 23-32
[21] Queyranne, M., Bounds for assembly line balancing heuristics, Oper. Res., 33, 6, 1353-1359 (1985) · Zbl 0579.90054
[22] Schiermeyer, I., Reverse-fit: A 2-optimal algorithm for packing rectangles, (Proceedings of the Second Annual European Symposium on Algorithms (1994), Springer-Verlag: Springer-Verlag London, UK), 290-299
[23] Steiger, C.; Walder, H.; Platzner, M., Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks, IEEE Trans. Comput., 53, 11, 1393-1407 (2004)
[24] Steinberg, A., A strip-packing algorithm with absolute performance bound 2, SIAM J. Comput., 26, 2, 401-409 (1997) · Zbl 0874.68140
[25] Xilinx. http://www.xilinx.com; Xilinx. http://www.xilinx.com
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.