Relevant bibliographies by topics / Strip Packing problem

Academic literature on the topic 'Strip Packing problem'

Author: Grafiati
Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Strip Packing problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Strip Packing problem"

1

Chekanin, Vladislav A., and Alexander V. Chekanin. "Development of the Multimethod Genetic Algorithm for the Strip Packing Problem." Applied Mechanics and Materials 598 (July 2014): 377–81. http://dx.doi.org/10.4028/www.scientific.net/amm.598.377.

Full text
Abstract:
The actual in industry strip packing problem which is NP-hard in strong sense is considered in paper. To the strip packing problem comes down solution of a large number of different practical problems, including problems in logistics, scheduling and planning. The new heuristics intended to pack a given set of rectangular two-dimensional objects in order to minimize of the total length of the filled part of container with an infinity length and fixed width are offered. The proposed multimethod genetic algorithm is investigated on well-known standard benchmarks of two-dimensional strip packing problems.
APA, Harvard, Vancouver, ISO, and other styles
2

Alvarez-Valdes, R., F. Parreño, and J. M. Tamarit. "Reactive GRASP for the strip-packing problem." Computers & Operations Research 35, no. 4 (April 2008): 1065–83. http://dx.doi.org/10.1016/j.cor.2006.07.004.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Zhao, Xusheng, Yunqing Rao, and Jie Fang. "A reinforcement learning algorithm for the 2D-rectangular strip packing problem." Journal of Physics: Conference Series 2181, no. 1 (January 1, 2022): 012002. http://dx.doi.org/10.1088/1742-6596/2181/1/012002.

Full text
Abstract:
Abstract The 2D packing problem is categorized as one branch of the cutting and packing problems, which is widely spread in the manufacturing industries. Over the years many meta­heuristics have been proposed and applied on the packing problem. Recently, the approach combined with machine learning serves as a novel paradigm for solving the combinatorial optimization problem. However, the machine learning approaches have very limited literature reports on the appliance of the packing problem. We propose a reinforcement learning method for the 2D-rectangular strip packing problem. The solution is represented by the sequence of the items and the layout is constructed piece by piece. We use the lowest centroid placement rule for the piece placement, then a Q-learning based sequence optimization is applied. Three groups of conditions are set for the testing, the computational results show the Q-learning approach has good effect on the compaction of the layout.
APA, Harvard, Vancouver, ISO, and other styles
4

BOUGERET, MARIN, PIERRE-FRANCOIS DUTOT, KLAUS JANSEN, CHRISTINA ROBENEK, and DENIS TRYSTRAM. "APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS." Discrete Mathematics, Algorithms and Applications 03, no. 04 (December 2011): 553–86. http://dx.doi.org/10.1142/s1793830911001413.

Full text
Abstract:
We consider two strongly related problems, multiple strip packing and scheduling parallel jobs in platforms. In the first one we are given a list of n rectangles with heights and widths bounded by one and N strips of unit width and infinite height. The objective is to find a nonoverlapping orthogonal packing without rotations of all rectangles into the strips minimizing the maximum height used. In the scheduling problem we consider jobs instead of rectangles, i.e., we are allowed to cut the rectangles vertically and we may have target areas of different size, called platforms. A platform Pℓ is a collection of mℓ processors running at speed sℓ and the objective is to minimize the makespan, i.e., the latest finishing time of a job.
APA, Harvard, Vancouver, ISO, and other styles
5

Côté, Jean-François, Mauro Dell'Amico, and Manuel Iori. "Combinatorial Benders' Cuts for the Strip Packing Problem." Operations Research 62, no. 3 (June 2014): 643–61. http://dx.doi.org/10.1287/opre.2013.1248.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Martello, Silvano, Michele Monaci, and Daniele Vigo. "An Exact Approach to the Strip-Packing Problem." INFORMS Journal on Computing 15, no. 3 (August 2003): 310–19. http://dx.doi.org/10.1287/ijoc.15.3.310.16082.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Chen, Jianli, Wenxing Zhu, and Zheng Peng. "A heuristic algorithm for the strip packing problem." Journal of Heuristics 18, no. 4 (May 30, 2012): 677–97. http://dx.doi.org/10.1007/s10732-012-9203-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Fang, Jie, Yunqing Rao, and Mingliang Shi. "A deep reinforcement learning algorithm for the rectangular strip packing problem." PLOS ONE 18, no. 3 (March 16, 2023): e0282598. http://dx.doi.org/10.1371/journal.pone.0282598.

Full text
Abstract:
As a branch of the two-dimensional (2D) optimal blanking problem, rectangular strip packing is a typical non-deterministic polynomial (NP-hard) problem. The classical packing solution method relies on heuristic and metaheuristic algorithms. Usually, it needs to be designed with manual decisions to guide the solution, resulting in a small solution scale, weak generalization, and low solution efficiency. Inspired by deep learning and reinforcement learning, combined with the characteristics of rectangular piece packing, a novel algorithm based on deep reinforcement learning is proposed in this work to solve the rectangular strip packing problem. The pointer network with an encoder and decoder structure is taken as the basic network for the deep reinforcement learning algorithm. A model-free reinforcement learning algorithm is designed to train network parameters to optimize the packing sequence. This design can not only avoid designing heuristic rules separately for different problems but also use the deep networks with self-learning characteristics to solve different instances more widely. At the same time, a piece positioning algorithm based on the maximum rectangles bottom-left (Maxrects-BL) is designed to determine the placement position of pieces on the plate and calculate model rewards and packing parameters. Finally, instances are used to analyze the optimization effect of the algorithm. The experimental results show that the proposed algorithm can produce three better and five comparable results compared with some classical heuristic algorithms. In addition, the calculation time of the proposed algorithm is less than 1 second in all test instances, which shows a good generalization, solution efficiency, and practical application potential.
APA, Harvard, Vancouver, ISO, and other styles
9

Horn, Matthias, Emir Demirović, and Neil Yorke-Smith. "Parallel Batch Processing for the Coating Problem." Proceedings of the International Conference on Automated Planning and Scheduling 33, no. 1 (July 1, 2023): 171–79. http://dx.doi.org/10.1609/icaps.v33i1.27192.

Full text
Abstract:
We solve a challenging scheduling problem with parallel batch processing and two-dimensional shelf strip packing constraints that arises in the tool coating field. Tools are assembled on so-called planetaries (batches) before they are loaded into coating machines to get coated. The assembling is not trivial and must fulfil specific constraints, which we refer to as shelf strip packing constraints. Further, each tool is associated with a starting time window s.t. tools can only be put on the same planetary if their time window overlap. The objective is to minimise the makespan and the number of required planetaries. Since the problem naturally decomposes into scheduling and packing parts, we tackle the problem with a two-phase logic-based Benders decomposition approach. The master problem assigns items to batches. The first phase solves as subproblem the packing problem by checking if the assignment is feasible, whereas the second phase solves the scheduling subproblem. The approach is compared with a monolithic mixed integer linear programming approach as well as a monolithic constraint programming approach. Experimental evaluation shows that our proposed approach outperforms the state-of-the-art benchmarks by solving more instances to optimality in a shorter time.
APA, Harvard, Vancouver, ISO, and other styles
10

Domović, Daniel, Tomislav Rolich, and Marin Golub. "Evolutionary hyper-heuristic for solving the strip-packing problem." Journal of The Textile Institute 110, no. 8 (January 4, 2019): 1141–51. http://dx.doi.org/10.1080/00405000.2018.1550136.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Strip Packing problem"

1

Ortmann, Frank. "Heuristics for offline rectangular packing problems." Thesis, Stellenbosch : University of Stellenbosch, 2010. http://hdl.handle.net/10019.1/3992.

Full text
Abstract:
Thesis (PhD (Logistics))--University of Stellenbosch, 2010.
ENGLISH ABSTRACT: Packing problems are common in industry and there is a large body of literature on the subject. Two packing problems are considered in this dissertation: the strip packing problem and the bin packing problem. The aim in both problems is to pack a speci ed set of small items, the dimensions of which are all known prior to packing (hence giving rise to an o ine problem), into larger objects, called bins. The strip packing problem requires packing these items into a single bin, one dimension of which is unbounded (the bin is therefore referred to as a strip). In two dimensions the width of the strip is typically speci ed and the aim is to pack all the items into the strip, without overlapping, so that the resulting packing height is a minimum. The bin packing problem, on the other hand, is the problem of packing the items into a speci ed set of bins (all of whose dimensions are bounded) so that the wasted space remaining in the bins (which contain items) is a minimum. The bins may all have the same dimensions (in which case the problem is known as the single bin size bin packing problem), or may have di erent dimensions, in which case the problem is called the multiple bin size bin packing problem (MBSBPP). In two dimensions the wasted space is the sum total of areas of the bins (containing items) not covered by items. Many solution methodologies have been developed for above-mentioned problems, but the scope of the solution methodologies considered in this dissertation is restricted to heuristics. Packing heuristics follow a xed set of rules to pack items in such a manner as to nd good, feasible (but not necessarily optimal) solutions to the strip and bin packing problems within as short a time span as possible. Three types of heuristics are considered in this dissertation: (i) those that pack items into levels (the heights of which are determined by the heights of the tallest items in these levels) in such a manner that all items are packed along the bottom of the level, (ii) those that pack items into levels in such a manner that items may be packed anywhere between the horizontal boundaries that de ne the levels, and (iii) those heuristics that do not restrict the packing of items to levels. These three classes of heuristics are known as level algorithms, pseudolevel algorithms and plane algorithms, respectively. A computational approach is adopted in this dissertation in order to evaluate the performances of 218 new heuristics for the strip packing problem in relation to 34 known heuristics from the literature with respect to a set of 1 170 benchmark problem instances. It is found that the new level-packing heuristics do not yield signi cantly better solutions than the known heuristics, but several of the newly proposed pseudolevel heuristics do yield signi cantly better results than the best of the known pseudolevel heuristics in terms of both packing densities achieved and computation times expended. During the evaluation of the plane algorithms two classes of heuristics were identi ed for packing problems, namely sorting-dependent and sortingindependent algorithms. Two new sorting techniques are proposed for the sorting-independent algorithms and one of them yields the best-performing heuristic overall. A new heuristic approach for the MBSBPP is also proposed, which may be combined with level and pseudolevel algorithms for the strip packing problem in order to nd solutions to the problem very rapidly. The best-performing plane-packing heuristic is modi ed to pack items into the largest bins rst, followed by an attempted repacking of the items in those bins into smaller bins with the aim of further minimising wasted space. It is found that the resulting plane-packing algorithm yields the best results in terms of time and packing density, but that the solution di erences between pseudolevel algorithms are not as marked for the MBSBPP as for the strip packing problem.
AFRIKAANSE OPSOMMING: Inpakkingsprobleme kom algemeen in die industrie voor en daar is 'n aansienlike volume literatuur oor hierdie onderwerp. Twee inpakkingsprobleme word in hierdie proefskrif oorweeg, naamlik die strook-inpakkingsprobleem en die houer-inpakkingsprobleem. In beide probleme is die doel om 'n gespesi seerde versameling klein voorwerpe, waarvan die dimensies almal voordat inpakking plaasvind, bekend is (en die probleem dus 'n sogenaamde a yn-probleem is), in een of meer groter houers te pak. In die strook-inpakkingsprobleem word hierdie voorwerpe in een houer, waarvan een dimensie onbegrens is, ingepak (hierdie houer word dus 'n strook genoem). In twee dimensies word die wydte van die strook gewoonlik gespesi seer en is die doel om al die voorwerpe sonder oorvleueling op s o 'n manier in die strook te pak dat die totale inpakkingshoogte geminineer word. In die houer-inpakkingsprobleem, daarenteen, is die doel om die voorwerpe op s o 'n manier in 'n gespesi seerde aantal houers (waarvan al die dimensies begrens is) te pak dat die vermorste of oorblywende ruimte in die houers (wat wel voorwerpe bevat) 'n minimum is. Die houers mag almal dieselfde dimensies h^e (in welke geval die probleem as die enkelgrootte houer-inpakkingsprobleem bekend staan), of mag verskillende dimensies h^e (in welke geval die probleem as die veelvuldige-grootte houer-inpakkingsprobleem bekend staan, afgekort as VGHIP). In twee dimensies word die vermorste ruimte geneem as die somtotaal van daardie deelareas van die houers (wat wel voorwerpe bevat) waar daar geen voorwerpe geplaas word nie. Verskeie oplossingsmetodologie e is al vir die bogenoemde twee inpakkingsprobleme ontwikkel, maar die bestek van die metodologie e wat in hierdie proefskrif oorweeg word, word beperk tot heuristieke. 'n Inpakkingsheuristiek volg 'n vaste stel re els waarvolgens voorwerpe in houers gepak word om so spoedig moontlik goeie, toelaatbare (maar nie noodwendig optimale) oplossings tot die strook-inpakkingsprobleem en die houer-inpakkingsprobleem te vind. Drie tipes inpakkingsheuristieke word in hierdie proefskrif oorweeg, naamlik (i) heuristieke wat voorwerpe langs die onderste randte van horisontale vlakke in die houers pak (die hoogtes van hierdie vlakke word bepaal deur die hoogtes van die hoogste item in elke vlak), (ii) heuristieke wat voorwerpe op enige plek binne horisontale stroke in die houers pak, en (iii) heuristieke waar inpakking nie volgens horisontale vlakke of stroke beperk word nie. Hierdie drie klasse heuristieke staan onderskeidelik as vlakalgoritmes, pseudo-vlakalgoritmes en platvlakalgoritmes bekend. 'n Berekeningsbenadering word in hierdie proefskrif gevolg deur die werkverrigting van die 218 nuwe heuristieke vir die strook-inpakkingsprobleem met die werkverrigting van 34 bekende heuristieke uit die literatuur te vergelyk, deur al die heuristieke op 1 170 toetsprobleme toe te pas. Daar word bevind dat die nuwe vlakalgoritmes nie 'n noemenswaardige verbetering in oplossingskwaliteit in vergeleke met soortgelyke bestaande algoritmes in die literatuur lewer nie, maar dat verskeie nuwe pseudo-vlakalgoritmes wel noemenswaardige verbeteringe in terme van beide inpakkingsdigthede en oplossingstye in vergeleke met die beste bestaande algoritmes in die literatuur lewer. Assessering van die platvlakalgoritmes het gelei tot die identi kasie van twee deelklasse van algoritmes, naamlik sorteringsafhanklike- en sorteringsonafhanklike algoritmes. Twee nuwe sorteringstegnieke word ook vir die deelklas van sorteringsonafhanklike algoritmes voorgestel, en een van hulle lewer die algeheel beste inpakkingsheursitiek. 'n Nuwe heuristiese benadering word ook vir die VGHIP ontwikkel. Hierdie benadering kan met vlak- of pseudo-vlakalgoritmes vir die strook-inpakkingsprobleem gekombineer word om baie vinnig oplossings vir die VGHIP te vind. Die beste platvlakheuristiek vir die strookinpakkingsprobleem word ook aangepas om voorwerpe eers in die grootste houers te pak, en daarna in kleiner houers te herpak met die doel om vermorste ruimte verder te minimeer. Daar word bevind dat die resulterende platvlakalgoritme die beste resultate in terme van beide inpakkingsdigtheid en oplossingstyd lewer, maar dat oplossingsverskille tussen die pseudovlakalgoritmes nie so opmerklik vir die VGHIP is as wat die geval met die strookinpakkingsprobleem was nie.
APA, Harvard, Vancouver, ISO, and other styles
2

Gomes, Joel Alexandre Roda. "Problema de corte bidimensional : Aplicação a um caso real." Master's thesis, Instituto Superior de Economia e Gestão, 2011. http://hdl.handle.net/10400.5/4540.

Full text
Abstract:
Mestrado em Decisão Económica e Empresarial
O problema de corte guilhotina e empacotamento bidimensional rectangular consiste em alocar múltiplas peças pequenas - itens - numa ou mais placas de tamanho maior -objectos - num padrão que minimize o desperdício de matéria-prima. A motivação para a realização deste projecto é resolver um problema real de uma empresa portuguesa tentando, ao mesmo tempo, propor algo novo. Para isso, desenvolvem-se e apresentam-se duas novas heurísticas, a Guillotinable Bottom-Left First Fit Decreasing Height (BLFFDHG) e a Bottom-Left First Fit Decreasing Height (BLFFDH), baseadas na First Fit Decreasing Height (FFDH) e Bottom-up left-justified (BL), em que, após um nível ter sido preenchido com a abordagem da FFDH, e antes de se abrir um novo nível para o próximo rectângulo, o nível actual é exaustivamente examinado, usando a heurística BL, de modo a tentar alocar itens no espaço que sobra entre dois níveis consecutivos. A diferença entre as novas heurísticas reside no facto de uma impor o corte guilhotina. Em ambas nenhuma das peças pode ser rodada ou sobreposta. Só depois de explorado o nível actual é aberto um novo. Os resultados são comparados com heurísticas da literatura, num conjunto de instâncias reais, em corte de roupeiros, e da literatura. As heurísticas propostas são comparadas entre si em termos de tempos de execução e é determinada a complexidade empírica da programação. Os resultados obtidos indicam que os algoritmos BLFFDHG e BLFFDH proporcionam quase sempre melhores soluções que os algoritmos que lhe deram origem e são bastante competitivos em relação às outras heurísticas usadas nos testes. Em termos de tempo de execução, a BLFFDHG revelou-se mais rápida que a BLFFDH, e a complexidade empírica da programação é, para ambas, 0(n3).
The guillotine cutting problem with two-dimensional rectangular packaging consists of allocating small items in one or more bins - objects - with a pattern that minimize the waste of raw materials. The motivation for this project is to solve a real problem of a Portuguese company and, at the same time, try to propose something new. To this aim, two new heuristics are it developed and presented, the Guillotinable Bottom-Left First Fit Decreasing Height (BLFFDHG) and Bottom-Left First Fit Decreasing Height (BLFFDH), based on First Fit Decreasing Height (FFDH) and Bottom-up left-justified (BL), in which, after a level has been filled with the approach of FFDH, and before opening a new level to the next item, the current level is thoroughly examined, using the BL heuristic, so trying to allocate items in the space left between two consecutive levels. The difference between the new heuristics is that one ensures a pattern that is guillotine cuttable, but in none of them the items can be rotated or overlapped. Only after exploring the current level a new one is open. The results are compared, in terms of solution, with heuristics presented in the literature, using a set of real based instances from a wardrobe cutting and literature instances. The proposed heuristics are compared in terms of execution times and its empirically complexity of programming is estimated. The results indicate that the algorithms BLFFDHG and BLFFDH usually provide better solutions than the algorithms FFDH and BL and are quite competitive when compared with other heuristics used in the tests. In terms of execution time, the BLFFDHG proved to be faster than BLFFDH and empirically they both have a complexity of 0(n3).
APA, Harvard, Vancouver, ISO, and other styles
3

Rodrigues, Marcos Okamura. "Modelos matemáticos para o problema de empacotamento em faixas de peças irregulares." Universidade de São Paulo, 2015. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-25062015-111716/.

Full text
Abstract:
O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças.
The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.
APA, Harvard, Vancouver, ISO, and other styles
4

Júnior, Álvaro Luiz Neuenfeldt. "The Two-Dimensional Rectangular Strip Packing Problem." Doctoral thesis, 2017. https://repositorio-aberto.up.pt/handle/10216/109367.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Júnior, Álvaro Luiz Neuenfeldt. "The Two-Dimensional Rectangular Strip Packing Problem." Tese, 2017. https://repositorio-aberto.up.pt/handle/10216/109367.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Lonkar, Aditya Abhay. "Algorithms for Geometric Packing and Covering Problems." Thesis, 2023. https://etd.iisc.ac.in/handle/2005/6206.

Full text
Abstract:
We study two fundamental problems related to geometric packing and covering, and design algorithms with improved worst-case performance guarantees for them. These problems have numerous applications in resource allocation, logistics, packing, and sensor networks. First, we study the Strip Packing problem (SP), where we are given a vertical half-strip \left[0,W\right]\times\left[0,\infty\right) and a set of n axis-aligned rectangles of width at most W . The goal is to find a non-overlapping packing of all rectangles into the strip such that the height of the packing is minimized. A well-studied and frequently used practical constraint is to allow only those packings that are guillotine separable, i.e., every rectangle in the packing can be obtained by recursively applying a sequence of edge-to-edge axis-parallel cuts (guillotine cuts) that do not intersect any item of the solution. In this thesis, we study approximation algorithms for the Guillotine Strip Packing problem (GSP), i.e., the Strip Packing problem where we require additionally that the packing needs to be guillotine separable. This problem generalizes the classical Bin Packing problem and makespan minimization on identical machines, and thus it is already strongly NP-Hard. Moreover, it is NP-Hard to obtain a polynomial-time \left(3/2\ -\ \epsilon\right)-approximation algorithm for GSP for any \epsilon>\ 0 (exactly as Strip Packing). We provide a matching polynomial time \left(3/2+\epsilon\right)-approximation algorithm for GSP. Furthermore, we present a pseudo-polynomial time \left(3/2+\epsilon\right)-approximation algorithm for GSP. This is surprising as it is NP-Hard to obtain a \left(5/4\ -\ \epsilon\right)-approximation algorithm for (general) Strip Packing in pseudo-polynomial time. Thus, our results essentially settle the approximability of GSP for both the polynomial and the pseudo-polynomial settings. In the context of covering, we study the geometric versions of Set Cover and the related dual Hitting Set problem, and present online and dynamic algorithms for them. In the online version of Set Cover (resp. Hitting Set), m sets (resp. n points) are given and n points (resp. m sets) ar- rive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal as before is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution. For online set cover for axis-parallel squares of arbitrary sizes, we present a tight O\left(\log{n}\right)-competitive algorithm, improving upon the O\left(\log{n}\log{m}\right) general case guarantee. In the same setting for hitting set, we provide a tight O(\log\funcapply N)\ -competitive algorithm, assuming that all points have integral coordinates in \left[0,N\right)^2. No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems). For both dynamic set cover and hitting set with d dimensional hyperrectangles, we obtain \left(\log{m}\right)^{O\left(d\right)}-approximation algorithms with \left(\log{m}\right)^{O\left(d\right)} worst-case update time. This partially answers an open question posed by Chan et al. [SODA’22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.
APA, Harvard, Vancouver, ISO, and other styles
7

Srinidhi, S. "Heuristic Methods For Job Scheduling In A Heat Treatment Shop To Maximize Kiln Utilization." Thesis, 2007. https://etd.iisc.ac.in/handle/2005/541.

Full text
Abstract:
Scheduling in the context of manufacturing systems has become increasingly impor- tant in order for organizations to achieve success in dynamic and competitive scenarios. Scheduling can be described as allocation of available jobs over resources to meet the performance criteria defined in a domain. Our research work fo cuses on scheduling a given set of three-dimensional cylindrical items, each characterized by width wj , height hj, and depth dj , onto parallel non-identical rectangular heat treatment kilns, such that the capacities of the kilns is optimally used. The problem is strongly NP-hard as it generalizes the (one-dimensional) Bin Packing Problem (1BP), in which a set of n positive values wj has to be partitioned into the minimum number of subsets so that the total value in each subset does not exceed the bin capacity W. The problem has been formulated as a variant of the 3D-BPP by following the MILP approach, and we propose a weight optimization heuristic that produces solutions comparable to that of the LP problem, in addition to reducing the computational complexity. Finally, we also propose a Decomposition Algorithm (DA) and validate the perfor- mance effectiveness of our heuristic. The numerical analyses provides useful insights that influence the shop-floor decision making process.
APA, Harvard, Vancouver, ISO, and other styles
8

Srinidhi, S. "Heuristic Methods For Job Scheduling In A Heat Treatment Shop To Maximize Kiln Utilization." Thesis, 2007. http://hdl.handle.net/2005/541.

Full text
Abstract:
Scheduling in the context of manufacturing systems has become increasingly impor- tant in order for organizations to achieve success in dynamic and competitive scenarios. Scheduling can be described as allocation of available jobs over resources to meet the performance criteria defined in a domain. Our research work fo cuses on scheduling a given set of three-dimensional cylindrical items, each characterized by width wj , height hj, and depth dj , onto parallel non-identical rectangular heat treatment kilns, such that the capacities of the kilns is optimally used. The problem is strongly NP-hard as it generalizes the (one-dimensional) Bin Packing Problem (1BP), in which a set of n positive values wj has to be partitioned into the minimum number of subsets so that the total value in each subset does not exceed the bin capacity W. The problem has been formulated as a variant of the 3D-BPP by following the MILP approach, and we propose a weight optimization heuristic that produces solutions comparable to that of the LP problem, in addition to reducing the computational complexity. Finally, we also propose a Decomposition Algorithm (DA) and validate the perfor- mance effectiveness of our heuristic. The numerical analyses provides useful insights that influence the shop-floor decision making process.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Strip Packing problem"

1

Sinclair, Upton. The Jungle. New York, N.Y: Signet Classic, 2001.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sinclair, Upton. The jungle. San Diego, CA: ICON Classics, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Sinclair, Upton. The jungle: An authoritative text, contexts and backgrounds, criticism. New York: Norton, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Sinclair, Upton. The jungle. New York: New American Library, 1990.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Sinclair, Upton. The jungle. New York: Modern Library, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Sinclair, Upton. The jungle: The uncensored original edition. Tucson, Ariz: See Sharp Press, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Sinclair, Upton. The jungle. Tucson, AZ: See Sharp Press, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Sinclair, Upton. The Jungle. Chatham: Fictionwise, Inc., 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Sinclair, Upton. The jungle. Waterville, Me: Kennebec Large Print, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Sinclair, Upton. The Jungle. Waterville, Me: Thorndike Press, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Strip Packing problem"

1

Iori, Manuel, Silvano Martello, and Michele Monaci. "Metaheuristic Algorithms for the Strip Packing Problem." In Applied Optimization, 159–79. Boston, MA: Springer US, 2003. http://dx.doi.org/10.1007/978-1-4613-0233-9_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Burke, Edmund K., Qiang Guo, and Graham Kendall. "A Hyper-Heuristic Approach to Strip Packing Problems." In Parallel Problem Solving from Nature, PPSN XI, 465–74. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-15844-5_47.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Hawa, Asyl L., Rhyd Lewis, and Jonathan M. Thompson. "Heuristics for the Score-Constrained Strip-Packing Problem." In Combinatorial Optimization and Applications, 449–62. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-04651-4_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Neuenfeldt Júnior, Alvaro, Elsa Silva, A. Miguel Gomes, and José Fernando Oliveira. "The Two-Dimensional Strip Packing Problem: What Matters?" In Operational Research, 151–64. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-71583-4_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Babalik, Ahmet. "Implementation of Bat Algorithm on 2D Strip Packing Problem." In Proceedings in Adaptation, Learning and Optimization, 209–18. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-27000-5_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Vasilyev, Igor, Anton V. Ushakov, Maria V. Barkova, Dong Zhang, Jie Ren, and Juan Chen. "Fast Heuristic Algorithms for the Multiple Strip Packing Problem." In Communications in Computer and Information Science, 284–97. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-86433-0_20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Zhang, Defu, Yanjuan Liu, Shengda Chen, and Xiaogang Xie. "A Meta-heuristic Algorithm for the Strip Rectangular Packing Problem." In Lecture Notes in Computer Science, 1235–41. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11539902_157.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Thomas, Jaya, and Narendra S. Chaudhari. "Hybrid Approach for 2D Strip Packing Problem Using Genetic Algorithm." In Advances in Computational Intelligence, 566–74. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38679-4_57.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Hoffmann, Kirsten. "New Lower Bounds for the Three-Dimensional Strip Packing Problem." In Operations Research Proceedings 2013, 201–7. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-07001-8_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Buchwald, Torsten, and Guntram Scheithauer. "Upper Bounds for Heuristic Approaches to the Strip Packing Problem." In Operations Research Proceedings, 65–70. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-28697-6_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Strip Packing problem"

1

Domovic, D., and T. Rolich. "Solving strip-packing problem using sequence pair." In 2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO). IEEE, 2015. http://dx.doi.org/10.1109/mipro.2015.7160455.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Miranda, Gara, Jesica de Armas, Carlos Segura, and Coromoto Leon. "Hyperheuristic codification for the multi-objective 2D Guillotine Strip Packing Problem." In 2010 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2010. http://dx.doi.org/10.1109/cec.2010.5585914.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Coelho, Dayanne G., Elizabeth F. Wanner, Sergio R. Souza, Eduardo G. Carrano, and Robin C. Purshouse. "A multiobjective evolutionary algorithm for the 2D Guillotine Strip Packing Problem." In 2012 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2012. http://dx.doi.org/10.1109/cec.2012.6256469.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Abdelhafiez, Ehab A., and Fahd A. Alturki. "A novel shaking optimization algorithm for two-dimensional irregular strip-packing problem." In 2010 2nd International Conference on Mechanical and Electronics Engineering (ICMEE 2010). IEEE, 2010. http://dx.doi.org/10.1109/icmee.2010.5558533.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bekrar, Abdelghani, Imed Kacem, Chengbin Chu, and Cherif Sadfi. "A Branch and Bound Algorithm for solving the 2D Strip Packing Problem." In 2006 International Conference on Service Systems and Service Management. IEEE, 2006. http://dx.doi.org/10.1109/icsssm.2006.320758.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Salto, Carolina, Guillermo Leguizamón, Enrique Alba, and Juan M. Molina. "Hybrid Ant Colony System to Solve a 2-Dimensional Strip Packing Problem." In 2008 8th International Conference on Hybrid Intelligent Systems (HIS). IEEE, 2008. http://dx.doi.org/10.1109/his.2008.133.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Duanbing Chen, Yan Fu, Mingsheng Shang, and Wenqi Huang. "A Quasi-Human Heuristic Algorithm for the 2D Rectangular Strip Packing Problem." In 2008 International Symposium on Information Science and Engineering (ISISE). IEEE, 2008. http://dx.doi.org/10.1109/isise.2008.10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Anggraeny, Fetty Tri, Nanik Suciati, and Anny Yuniarti. "Extended local search and polygon grouping for 2D irregular strip packing problem." In 2013 International Conference on ICT for Smart Society (ICISS). IEEE, 2013. http://dx.doi.org/10.1109/ictss.2013.6588054.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Matayoshi, Mitsukuni. "The 2D strip packing problem: A new approach with verification by EA." In 2010 IEEE International Conference on Systems, Man and Cybernetics - SMC. IEEE, 2010. http://dx.doi.org/10.1109/icsmc.2010.5641931.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Marat, Mesyagutov,. "Lower Bounds for the 2D Strip Packing Problem: Linear and 1D Contiguous Relaxation." In Information Control Problems in Manufacturing, edited by Bakhtadze, Natalia, Chair Dolgui, Alexandre and Bakhtadze, Natalia. Elsevier, 2009. http://dx.doi.org/10.3182/20090603-3-ru-2001.00337.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Strip Packing problem' for particular source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography