Parallel greedy algorithms for packing unequal circles into a strip or a rectangle

Autor:	Timo Kubach, Andreas Bortfeldt, Hermann Gehring
Rok vydání:	2009
Předmět:	Combinatorics Discrete mathematics Strip packing problem Knapsack problem Master/slave Rectangle Management Science and Operations Research Greedy algorithm Variable length Finite set Fixed width Mathematics
Zdroj:	Central European Journal of Operations Research. 17:461-477
ISSN:	1613-9178 1435-246X
Popis:	Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3c17dc3c161005beaadf49e0329bfa02 https://doi.org/10.1007/s10100-009-0103-5 Zobrazit plný text záznamu Plný text ve formátu PDF