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 条
  • [31] A new lower bound for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 250 (03) : 754 - 759
  • [32] Reactive GRASP for the strip-packing problem
    Alvarez-Valdes, R.
    Parreno, F.
    Tamarit, J. M.
    COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) : 1065 - 1083
  • [33] A (5/3+ε)-approximation for strip packing
    Harren, Rolf
    Jansen, Klaus
    Praedel, Lars
    van Stee, Rob
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (02): : 248 - 267
  • [34] New upper bounds for online strip packing
    Yu, Guosong
    Mao, Yanling
    Xiao, Jiaoliao
    DISCRETE OPTIMIZATION, 2017, 23 : 20 - 32
  • [35] A note on the Kenyon-Remila strip-packing algorithm
    Sviridenko, Maxim
    INFORMATION PROCESSING LETTERS, 2012, 112 (1-2) : 10 - 12
  • [36] Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
    Henning, Soeren
    Jansen, Klaus
    Rau, Malin
    Schmarje, Lars
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2018, 2018, 10846 : 169 - 180
  • [37] A Tight (3/2+ε)-Approximation for Skewed Strip Packing
    Galvez, Waldo
    Grandoni, Fabrizio
    Ameli, Afrouz Jabal
    Jansen, Klaus
    Khan, Arindam
    Rau, Malin
    ALGORITHMICA, 2023, 85 (10) : 3088 - 3109
  • [38] Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
    Henning, Soeren
    Jansen, Klaus
    Rau, Malin
    Schmarje, Lars
    THEORY OF COMPUTING SYSTEMS, 2020, 64 (01) : 120 - 140
  • [39] Probabilistic analysis of a new class of strip packing algorithms
    N. N. Kuzyurin
    A. I. Pospelov
    Computational Mathematics and Mathematical Physics, 2011, 51 : 1817 - 1822
  • [40] Strip-packing using hybrid genetic approach
    Yeung, LHW
    Tang, WKS
    INTELLIGENT CONTROL SYSTEMS AND SIGNAL PROCESSING 2003, 2003, : 335 - 340