In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box B. The goal is to pack all the items in B such that the height of the packing is minimized. We consider the ...
详细信息
In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box B. The goal is to pack all the items in B such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of B and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any epsilon > 0, achieves an approximation of T-infinity + epsilon approximate to 1.69103 + epsilon, where T-infinity is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance I and the strip packing solutions for the corresponding instance obtained from I by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the T-infinity + epsilon approximation for 2D bin packing due to Caprara. In particular, we show how his result follows from a simple modification of the asymptotic approximation scheme for 2D strip packing due to Kenyon and Remila.
In this paper, we study an online multi-dimensional bin packing problem where all items are hypercubes. Hypercubes of different size arrive one by one, and we are asked to pack each of them without knowledge of the ne...
详细信息
In this paper, we study an online multi-dimensional bin packing problem where all items are hypercubes. Hypercubes of different size arrive one by one, and we are asked to pack each of them without knowledge of the next pieces so that the number of bins used is minimized. Based on the techniques from one dimensional bin packing and specifically the algorithm Super harmonic by Seiden (J ACM 49:640-671, 2002), we extend the framework for online bin packing problems developed by Seiden to the hypercube packing problem. To the best of our knowledge, this is the first paper to apply a version of Super harmonic (and not of the Improved harmonic algorithm) for online square packing, although the Super harmonic has been already known before. Note that the best previous result was obtained by Epstein and van Stee (Acta Inform 41(9):595-606, 2005b) using an instance of Improved harmonic. In this paper we show that Super harmonic is more powerful than Improve harmonic for online hypercube packing, and then we obtain better upper bounds on asymptotic competitive ratios. More precisely, we get an upper bound of 2.1187 for square packing and an upper bound of 2.6161 for cube packing, which improve upon the previous upper bounds 2.24437 and 2.9421 (Epstein and van Stee in Acta Inform 41(9):595-606, 2005b) for the two problems, respectively.
High impedance faults (HIFs) are easy to occur in collective feeders in wind farms and may cause the cascading of wind generators tripping. This kind of faults is difficult to be detected by traditional relay or fuse ...
详细信息
High impedance faults (HIFs) are easy to occur in collective feeders in wind farms and may cause the cascading of wind generators tripping. This kind of faults is difficult to be detected by traditional relay or fuse due to the limited fault current values and the situation is worse in wind farms. The mostly adopted HIF detection algorithms are based on the 3rd harmonic characteristic of the fault zero-sequence currents, whereas these 3rd harmonics are very easy to be polluted by wind power back-to-back converters. To solve this problem, the typical HIF arc flash based on Mayr's arc model is first built, and the typical fault waveforms of HIF in wind farm are presented. Then the characteristics of high impedance faults are analysed to distinguish the occurrence of HIF from other harmonic interference. After that, the performance of the traditional harmonic based HIF detection algorithm is discussed, and a novel detection algorithm is presented to prevent harmonic interference influence in wind farms.
暂无评论