Strip packing with precedence constraints and strip packing with release times

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Strip packing with precedence constraints and strip packing with release times

Full text

Pdf (296 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures table of contents

Cambridge, Massachusetts, USA

SESSION: Processing and scheduling table of contents

Pages: 180 - 189

Year of Publication: 2006

ISBN:1-59593-452-9

Authors

John Augustine	University of California, Irvine, CA
Sudarshan Banerjee	University of California, Irvine, CA
Sandy Irani	University of California, Irvine, CA

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 64, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1148109.1148139 What is a DOI?

ABSTRACT

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 can be used to model scheduling problems in which tasks require a contiguous subset of identical resources that are arranged in a linear topology. The particular variants studied here are motivated by scheduling tasks for dynamically reconfigurable Field-Programmable Gate Arrays (FPGAs) comprised of an array of computing columns. Each column is a computing resource and the array of columns forms the linear topology of resources. We assume that the given FPGA has K columns, where K is a fixed positive integer, and each task occupies a contiguous subset of these columns. For the case in which tasks have precedence constraints, we give an O(log n) approximation, where n is the number of tasks. 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 (1 + ε)- 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<over>K, 1], i.e., the rectangles are at least as wide as a column in the FPGA. Our running time is polynomial in n and 1/ε, but exponential in K.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Xilinx. http://www.xilinx.com.
	2	John E. Augustine , Steven Seiden, Linear time approximation schemes for vehicle scheduling problems, Theoretical Computer Science, v.324 n.2-3, p.147-160, 20 September 2004 [doi>10.1016/j.tcs.2004.05.013]
	3	B. S. Baker, D. J. Brown, and H. P. Katseff. A 5/4 algorithm for two-dimensional packing. J. Algorithms, 2(4):348--368, 1981.
	4	B. S. Baker, E. G. Coffman, and R. L. Rivest. Orthogonal packings in two dimensions. SIAM J. Comput., 9(4):846--855, 1980.
	5	Sudarshan Banerjee , Elaheh Bozorgzadeh , Nikil Dutt, Physically-aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065667]
	6	Adam L. Buchsbaum , Howard Karloff , Claire Kenyon , Nick Reingold , Mikkel Thorup, OPT Versus LOAD in Dynamic Storage Allocation, SIAM Journal on Computing, v.33 n.3, p.632-646, 2004 [doi>10.1137/S0097539703423941]
	7	E. G. Coffman, M. R. Garey, D. S. Johnson, and R. E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput., 9(4):808--826, 1980.
	8	János Csirik , Gerhard J. Woeginger, Shelf algorithms for on-line strip packing, Information Processing Letters, v.63 n.4, p.171-175, Aug. 28, 1997 [doi>10.1016/S0020-0190(97)00120-8 ]
	9	W. F. de la Vega and G. S. Lueker. Bin packing can be solved within 1 + e in linear time. Combinatorica, 1(4):349--355, 1981.
	10	W. Fernandez de la Vega , V. Zissimopoulos, An approximation scheme for strip packing of rectangles with bounded dimensions, Discrete Applied Mathematics, v.82 n.1-3, p.93-101, March 2, 1998 [doi>10.1016/S0166-218X(97)00130-3 ]
	11	M. Grotschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169--197, 1981.
	12	Klaus Jansen , Rob van Stee, On strip packing With rotations, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060702]
	13	Klaus Jansen , Hu Zhang, Scheduling malleable tasks with precedence constraints, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073983]
	14	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	15	N. Karmarkar and R. Karp. An efficient approximation scheme for the one dimensional bin-packing problem. Proceedings of the 23rd Sympos. Foundations Computer Sci. (FOCS), Tucson, AZ, pages 312--320, 1982.
	16	Claire Kenyon , Eric Rémila, A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem, Mathematics of Operations Research, v.25 n.4, p.645-656, November 2000 [doi>10.1287/moor.25.4.645.12118]
	17	Renaud Lepère , Denis Trystram , Gerhard J. Woeginger, Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints, Proceedings of the 9th Annual European Symposium on Algorithms, p.146-157, August 28-31, 2001
	18	D. S. J. M. R. Garey, R. L. Graham and A. C. Yao. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, 21(3):257--298, Nov 1976.
	19	Charles Martel, Preemptive Scheduling with Release Times, Deadlines, and Due Times, Journal of the ACM (JACM), v.29 n.3, p.812-829, July 1982 [doi>10.1145/322326.322337]
	20	Silvano Martello , Michele Monaci , Daniele Vigo, An Exact Approach to the Strip-Packing Problem, INFORMS Journal on Computing, v.15 n.3, p.310-319, July 2003 [doi>10.1287/ijoc.15.3.310.16082]
	21	Gregory Mounie , Christophe Rapine , Dennis Trystram, Efficient approximation algorithms for scheduling malleable tasks, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.23-32, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305622]
	22	M. Queyranne. Bounds for assembly line balancing heuristics. Operations Research, 33(6):1353--1359, 1985.
	23	Ingo Schiermeyer, Reverse-Fit: A 2-Optimal Algorithm for Packing Rectangles, Proceedings of the Second Annual European Symposium on Algorithms, p.290-299, September 26-28, 1994
	24	Christoph Steiger , Herbert Walder , Marco Platzner, Operating Systems for Reconfigurable Embedded Platforms: Online Scheduling of Real-Time Tasks, IEEE Transactions on Computers, v.53 n.11, p.1393-1407, November 2004 [doi>10.1109/TC.2004.99]
	25	A. Steinberg, A Strip-Packing Algorithm with Absolute Performance Bound 2, SIAM Journal on Computing, v.26 n.2, p.401-409, April 1997 [doi>10.1137/S0097539793255801]