Zoveel mogelijk vierkanten in een Rechthoek

[Verwijderd]

Het volgende probleem doet zich voor, te veel afval!

Er is een bedrijfsprocces waar een folie wordt uitgesneden,met een plotter. Dit wordt één voor één gedaan, met het gevolg dat er te veel afval wordt geproduceerd, en dat willen we natuurlijk niet want dat is slecht voor het mileu.

Is er een mooi algoritme te vinden (of tips om deze te maken) om zoveel mogelijk vierkanten (van verschillende formaten) in een rechthoek te krijgen van een vast formaat?

[Stoffel]

Kijk maar eens naar het knapsack probleem, daar moet je wel iets mee kunnen.

[IntToStr]

Ik denk dat een beetje meer uitleg geen kwaad kan, maar een (aangepast) bin packing algoritme wellicht?

[MissingDog]

Kijk hier eens naar...volgens mij precies wat je nodig hebt (trial beschikbaar)

http://www.astrokettle.com/pr2dlp.html

trial link -> http://astrokettle.com/y2d.zip

[ Voor 16% gewijzigd door MissingDog op 16-03-2007 15:42 ]

[Verwijderd]

IntToStr schreef op vrijdag 16 maart 2007 @ 15:37:
Ik denk dat een beetje meer uitleg geen kwaad kan, maar een (aangepast) bin packing algoritme wellicht?

Er moeten uit een rol folie zoveel mogelijk vierkante stukken folie geknipt kunnen worden voor gebruik in een productie proces (het productie proces zelf is verder niet zo boeiend). Omdat dit volgens mij een probleem is wat in veel productie processen voorkomt vroeg ik me af of hier goede algoritmes voor te vinden zijn.

Ik zal in ieder geval gaan google'en op bin packing algoritme, bedankt voor je hulp.

[Verwijderd]

wat altijd erg goed werkt is om alleerst de vierkanten te sorteren op opervlakte en dan met de grootste te beginnen en die aan de buitenkant van de rechthoek te plaatsen. en dan gewoon steeds de daarna kleinere er omheen.

daarnaast kun je dit ook geweldig parelliseeren. je maakt rekent aan het einde van elke verdeling uit hoeveel afval/niet gebruikte ruimte is en probeert gewoon een n-aantal verdelingen. die met de minste afval wint.

onhoud dat er altijd meerdere wegen naar rome zijn en geen enkel weg is perfect.

[Verwijderd]

MissingDog schreef op vrijdag 16 maart 2007 @ 15:40:
Kijk hier eens naar...volgens mij precies wat je nodig hebt (trial beschikbaar)

http://www.astrokettle.com/pr2dlp.html

trial link -> http://astrokettle.com/y2d.zip

Dit is wel precies het principe wat ik bedoel, maar ik wil het zelf uitprogrammeren (in PHP o.i.d.). Dus ik zou graag weten of er algoritmes voor zijn en hoe die dan heten.

[Verwijderd]

Verwijderd schreef op vrijdag 16 maart 2007 @ 15:42:
daarnaast kun je dit ook geweldig parelliseeren. je maakt rekent aan het einde van elke verdeling uit hoeveel afval/niet gebruikte ruimte is en probeert gewoon een n-aantal verdelingen. die met de minste afval wint.

Aan alle mogelijkheden na rekenen volgens het 'brute force' principe, en dan de beste kiezen had ik zelf ook gedacht. Ik vind het echter leuker om hier een doordacht algoritme op los te laten (wat vaak ook snelller is), en ik hoop dus dat die bekend zijn.

[IntToStr]

Verwijderd schreef op vrijdag 16 maart 2007 @ 15:42:
wat altijd erg goed werkt is om alleerst de vierkanten te sorteren op opervlakte en dan met de grootste te beginnen en die aan de buitenkant van de rechthoek te plaatsen. en dan gewoon steeds de daarna kleinere er omheen.

daarnaast kun je dit ook geweldig parelliseeren. je maakt rekent aan het einde van elke verdeling uit hoeveel afval/niet gebruikte ruimte is en probeert gewoon een n-aantal verdelingen. die met de minste afval wint.

onhoud dat er altijd meerdere wegen naar rome zijn en geen enkel weg is perfect.

Aangezien een optimaal bin packing algoritme een NP probleem is zul je benaderingen moeten gebruiken. (Tenzij het probleem zo klein is dat je het alsnog kunt berekenen)

Standaard mogelijkheden zijn idd alles sorteren en telkens de grootste pakken, of juist de kleinste, of zelfs een random vierkant... Komt allemaal op ongeveer de zelfde orde uit meestal. Er zijn nog wel wat interessante algoritmes, maar die schieten het doel hier waarschijnlijk iets voorbij

[Wacky]

Tip: zorg er voor dat de oplossing niet meer kost (tijd om te berekenen) dan het probleem nu kost (afvalmateriaal)

[Janoz]

Verwijderd schreef op vrijdag 16 maart 2007 @ 15:47:
[...]


Aan alle mogelijkheden na rekenen volgens het 'brute force' principe, en dan de beste kiezen had ik zelf ook gedacht. Ik vind het echter leuker om hier een doordacht algoritme op los te laten (wat vaak ook snelller is), en ik hoop dus dat die bekend zijn.

De essentie van een NPC probleem is dat deze niet op te lossen zijn op een andere manier dan brute force. Slimmere algoritmen kunnen wel een goede benadering geven. Maar goed. Dis is ook al in de 2e of 3e reactie gemeld. Ik raad je aan om eens bij wikipedia het binpacking en knapsack probleem door te lezen.

[Verwijderd]

Ik zal me zeker verder verdiepen in binpacking en het knapsack probleem. Dat algoritmen een benadering geven, en daardoor eigenlijk altijd nog brute force nodig is vind ik helemaal geen probleem. Brute force gebruiken is ook helemaal niet erg, maar een algoritme ervoor inzetten zou ik ook graag doen.

Dus mocht je nog een goed algoritme kennen (ook al streeft het zijn doel misschien iets voorbij), ik wil het graag weten. Tot zover in ieder geval al bedankt voor de goede aanwijzingen.

[IntToStr]

Bij deze een inhoudsopgave van een paper (meer survey) die ik moest schrijven over bin packing:

code:

Abstract    3
Introduction    3
    The bin packing problem 4
    Online vs offline   4
Classical bin packing   4
    Next fit    5
    First fit   6
    Best fit    7
    Worst fit   8
    Sum-of-squares  9
Multi dimensional bin packing   11
Discrete bin packing    11
Variable-sized bin packing  13
Bin covering    14
Summary 14
References  15

Succes

[DaCoTa]

Verwijderd schreef op vrijdag 16 maart 2007 @ 15:59:
Ik zal me zeker verder verdiepen in binpacking en het knapsack probleem. Dat algoritmen een benadering geven, en daardoor eigenlijk altijd nog brute force nodig is vind ik helemaal geen probleem. Brute force gebruiken is ook helemaal niet erg, maar een algoritme ervoor inzetten zou ik ook graag doen.

De grap met brute force is dat het voor grotere problemen niet meer praktisch is, omdat het teveel rekenkracht kost. In die gevallen MOET je dus een benadering gebruiken.

[Verwijderd]

dit inderdaad een NP probleem. daarom ook mijn idee om gewoon zeg 10.000 verschillende indelingen te creeren en dan de oplissing pakken welke de minste afval geeft. een moderne computer zou enkele honderden indelingen per seconden kunnen bedenken dus binnen een kwartiertje heb je al een aanzienelijke hoeveelheid mogelijkheden. ik weet niet hoeveel tijd er is maar 15m is best weinig.

ik denk dat je in dit probleem de beste oplossing krijgt door van groot naar klein in te delen omdat juist vaak in die kleine vierkanten het verschil zit en daar dus het meeste afval wordt gecreeerd.

[Soultaker]

Vergeet het knapsack probleem; dit is gewoon (2D) bin packing.

Verder is het handig om je specifieke situatie wat nauwkeuriger te omschrijven, op twee punten. Ten eerste: heb je keuze tussen welke vierkanten je gaat uitsnijden (bijvoorbeeld: in plaats van 3 van 2x2, kun je ook 2 van 3x3 doen) of staat precies vast welke vierkanten je moet produceren? Is het een kwestie van alle vierkanten uit een enkele rol halen, of worden er meerdere rollen gebruikt? Helpt het om een deel van de rol over te houden?

Ten tweede, kun je wat meer details geven over de gebruikte afmetingen? Is het bijvoorbeeld zo dat je een rol hebt van een meter en vierkanten die je in centimeters specificeert, of gaat over millimeters? Hoe groot zijn die vierkanten gemiddeld, en hoe groot is je rechtroek ongeveer?

Aangezien dit een moeilijk probleem is, zijn dit soort praktische gegevens nuttig om te bepalen welke aanpak praktisch is.

[ Voor 13% gewijzigd door Soultaker op 16-03-2007 20:03 ]