Strip packing with precedence constraints and strip packing with release times

被引:11
|
作者
Augustine, John [1 ]
Banerjee, Sudarshan [2 ]
Irani, Sandy [3 ]
机构
[1] Tata Res Dev & Design Ctr, Pune 411013, Maharashtra, India
[2] Univ Calif Irvine, Ctr Embedded Comp Syst, Irvine, CA USA
[3] Univ Calif Irvine, Donald Bren Sch Informat & Comp Sci, Irvine, CA USA
关键词
Strip packing; Approximation algorithms; Precedence constraints; Linear programming; Field programmable gate array; LINEAR-TIME; ALGORITHM; DIMENSIONS; BOUNDS;
D O I
10.1016/j.tcs.2009.05.024
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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/epsilon, but exponential in K. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码:3792 / 3803
页数:12
相关论文
共 50 条
  • [1] Heuristics for the strip packing problem with unloading constraints
    da Silveira, Jefferson L. M.
    Miyazawa, Flavio K.
    Xavier, Eduardo C.
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (04) : 991 - 1003
  • [2] Approximate strip packing: Revisited
    Han, Xin
    Iwama, Kazuo
    Ye, Deshi
    Zhang, Guochuan
    INFORMATION AND COMPUTATION, 2016, 249 : 110 - 120
  • [3] A note on online strip packing
    Ye, Deshi
    Han, Xin
    Zhang, Guochuan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (04) : 417 - 423
  • [4] Two-dimensional strip packing with unloading constraints
    da Silveira, Jefferson L. M.
    Xavier, Eduardo C.
    Miyazawa, Flavio K.
    DISCRETE APPLIED MATHEMATICS, 2014, 164 : 512 - 521
  • [5] Online multiple-strip packing
    Ye, Deshi
    Han, Xin
    Zhang, Guochuan
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (03) : 233 - 239
  • [6] Procedures for the bin packing problem with precedence constraints
    Pereira, Jordi
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 250 (03) : 794 - 806
  • [7] Parameterized complexity of Strip Packing and Minimum Volume Packing
    Ashok, Pradeesha
    Kolay, Sudeshna
    Meesum, S. M.
    Saurabh, Saket
    THEORETICAL COMPUTER SCIENCE, 2017, 661 : 56 - 64
  • [8] A note on online strip packing
    Deshi Ye
    Xin Han
    Guochuan Zhang
    Journal of Combinatorial Optimization, 2009, 17 : 417 - 423
  • [9] Hardness and Tight Approximations of Demand Strip Packing
    Jansen, Klaus
    Rau, Malin
    Tutas, Malte
    PROCEEDINGS OF THE 36TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2024, 2024, : 479 - 489
  • [10] On-Line Multiple-Strip Packing
    Ye, Deshi
    Han, Xin
    Zhang, Guochuan
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2009, 5573 : 155 - +