EO

Hoe snijd je kerstkoekjes optimaal uit? (video)

21 december 2020 om 13:48 uur

Wat is de optimale manier om uit een rechthoekig vel koekjesdeeg zoveel mogelijk kerstboomvormige koekjes te snijden? Dat is een voorbeeld van een packing problem (pakkingsprobleem), een notoir moeilijke opgave in de theoretische informatica. Informaticus Tillmann Miltzow (UU), Mikkel Abrahamsen (Københavns Universitet) en Nadja Seiferth (Freie Universität Berlin) leggen uit:


Een paper van de onderzoekers is geaccepteerd op de theoretische informatica-conferentie Foundations of Computer Science.

 

Een pakkingsprobleem is eigenlijk een puzzel waarbij je een set stukken probeert in een bepaalde vorm te plaatsen zonder dat ze elkaar overlappen, of om te bepalen dat er niet genoeg ruimte beschikbaar is om dit te doen. Zulke problemen komen overal in het dagelijks leven voor. Je lost bijvoorbeeld een pakkingsprobleem op als je bepaalt waar in de kamer je je meubels neerzet, als je naaipatronen zo efficiënt mogelijk ordent op een stuk stof, of als je zoveel mogelijk kerstkoekjes uit een lap deeg probeert te snijden.

In veel takken van industrie is het cruciaal om ingewikkelde pakkingsproblemen efficiënt op te lossen. Naast kledingproductie geldt dat bijvoorbeeld ook voor het snijden van leer, glas, hout en plaatwerk, selectief lasersinteren, logistiek (om zoveel mogelijk goederen te verpakken in laadcontainers) en 3D-printen (om zoveel mogelijk te printen onderdelen te ordenen in het printvolume); zie figuur 1.

 

nesting 

Figuur 1. Echte voorbeelden van ‘nesting' (het ordenen van vormen) op een dierenhuid (boven) en een stuk stof (onder), geproduceerd door de software van MIRISYS. 

 

 

Toepassingen

Verschillende toepassingen leiden tot verschillende pakkingsproblemen. Bij het rangschikken van naaipatronen op een rol stof is het belangrijk dat elk patroondeel op de juiste manier geörienteerd is ten opzichte van het weefpatroon of op de stof gedrukte patronen. Dat betekent dat de patroondelen niet mogen worden gedraaid. Bij andere toepassingen, zoals het snijden van leer, glas of plaatwerk, zijn er meestal geen beperkingen, zodat de stukken kunnen worden gedraaid om afval te minimaliseren. Weer andere versies van het probleem ontstaan wanneer de vorm van de stof of de stukken beperkt is.

 

 

Moeilijkheid

Van de meeste versies van pakkingsproblemen was het al bekend dat deze NP-moeilijk zijn. In de publicatie laten de onderzoekees zien dat veel problemen waarschijnlijk nog moeilijker zijn, door te bewijzen dat ze ∃R-compleet zijn. Dat geldt in ieder geval voor het pakken van polygonen in een vierkant met toegestane rotaties. Dat wil zeggen dat deze problemen in wezen net zo moeilijk zijn als de vraag of een systeem van polynomiale vergelijkingen en ongelijkheden een echte oplossing heeft - een probleem dat naar verwachting van de meeste onderzoekers moeilijker zal zijn dan NP-complete problemen, hoewel dit nog steeds een openstaande vraag is. Houd dit in gedachten de volgende keer dat u kerstkoekjes bakt!

 

 

Gerelateerd nieuws

Minder dan een nanometer dik, sterker en veelzijdiger dan staal

Minder dan een nanometer dik, sterker en veelzijdiger dan staal

Wetenschappers zijn erin geslaagd omstabiele nanovellen te produceren met boor- en waterstofatomen. Dit biedt kansen voor de nano-elektronica en kwantuminformatietechnologie.

Visualisatie voegt transparantie toe aan digitale productontwikkeling

Visualisatie voegt transparantie toe aan digitale productontwikkeling

Productontwikkeling wordt steeds veeleisender. Kwaliteitseisen worden steeds hoger en bovendien moeten ontwerpers rekening houden met criteria als duurzaamheid en energie-efficiëntie. Visualisatiesoftware biedt de…

Nederlands team wint FES-fietswedstrijd Cybathlon

Nederlands team wint Cybathlon fietswedstrijd (video's)

Studententeam Pulse Racing van de Vrije Universiteit Amsterdam en dwarslaesie-piloot Sander Koomen hebben de Cybathlon 2020 Global Edition gewonnen binnen de discipline Functionele Elektrische Stimulatie (FES)race.…

Webshop

webshop

 

Gratis nieuwsbrief

EOL

 

Focus op

ABB BV
ABB BV

Machineveiligheid, systemen en componenten

Elobau Benelux BV *
Elobau Benelux BV *

creating sustainable solutions

Pilz Nederland
Pilz Nederland

Voor industriële (veilige) automatiseringsoplossingen

Rotero Holland BV
Rotero Holland BV

Stappenmotor - Servomotor - Elektro Magneet

Download gratis engineering boeken

A gratis boeken downloaden

 

Agenda

12 april 2021, online

Hannover Messe

De Hannover Messe is een van de grootste industriebeurzen.

13 april 2021, online

De Makers van Morgen

Over het versnellen van time-to-market en snel doorvoeren van productinnovaties

14 april 2021, online

Thundercomm / Qualcomm Webinar - 5G IoT

Webinar over 5G IoT oplossingen met de Qualcomm Snapdragon architectuur

Meer agendapunten »