Optimalisatie proces

[Verwijderd]

Op mijn werk kom ik vaak het volgende probleem tegen:

Op de (industriele) markt is de standaard lengte van aluminium extrusie profielen 6 meter lang.

Bij ons moeten die dingen in veel verschillende lengtes gezaagd worden.
Bijv : (om mijn probleem te kunnen verduidelijken)
5 x 2,3 m
10 x 2,6 m
10 x 3,4 m
12 x 1 m
En er zijn veel mogelijkheden om die stukken uit 6 meter te verkrijgen.
Mijn vraag is nu:
Is er iets te programmeren (formule ? / Excel ? enz..) dat mij automatisch het minimum aantal benodigde extrusie profielen van 6 meter geeft, waaruit bovenstaande stukken te zagen zijn ?

Er zijn natuurlijk vele varianten mogelijk, maar het gaat mij hier om de optimalisatie van het minimum benodigde aantal profielen.

[Alarmnummer]

Ik weet niet of je iets van programmeren afweet want dit kan je sowieso oplossen met backtracking (alle mogelijke manieren bij langs gaan) en dan de gene bijhouden die het minste afval opleverd. Als je een beperkte hoeveelheid combinaties hebt dan zal dit proces geen problemen opleveren. Anders is ie namelijk nogal lang aan het rekenen.

Maar een formule ervoor opstellen wordt vrij lastig..

Talen zoals prolog/haskel/clean lenen zich hier goed voor maar het kan ook heel eenvoudig worden gemaakt in c/c++/java/pascal etc etc.

[edit] typo`s (spellen wil niet al te best meer als je de hele dag al bezig bent)

[chem]

toevalligerwijs heeft het bedrijf waar ik voor werk een dergelijke berekeningssysteem gemaakt voor een klant (in dit geval ging het om vlaggen)

dit is best pittig, en is niet iets wat je ff in een uurtje in elkaar schroeft. De formule is vaak zeer complex en alhoewel de uiteindelijk formule niet zo veel tijd kost, is het een tijdrovend karwei...

ik zou er niet aan beginnen

zoek een echte programmeur!

[Verwijderd]

Hoi,

Ik heb een tijdje geleden een jaartje bedrijfswiskunde gestudeerd in Diemen aan de Hogeschool Holland.

Voor een probleem als de jouwe worden bepaalde modules gedoceerd: modelleringstechnieken.

Dit houd in dat jouw probleem wordt omgezet in een wiskundig model. Door dit model middels een programmaatje te analyseren worden diverse oplossingen gevonden.
De voorwaarden die jij hier schetst zijn variabelen die in het model worden opgenomen.

Het is al een tijdje geleden dat ik deze studie heb gedaan en al helemaal dat ik een model heb gemaakt en heb geanalyseerd / opgelost, dus ik kan je helaas niet verder helpen.

Wellicht is het een idee om een student of een docent te benaderen die je verder kan helpen?

Patrick

[Alarmnummer]

Op dinsdag 19 februari 2002 20:51 schreef chem het volgende:
toevalligerwijs heeft het bedrijf waar ik voor werk een dergelijke berekeningssysteem gemaakt voor een klant (in dit geval ging het om vlaggen)

dit is best pittig, en is niet iets wat je ff in een uurtje in elkaar schroeft. De formule is vaak zeer complex en alhoewel de uiteindelijk formule niet zo veel tijd kost, is het een tijdrovend karwei...

ik zou er niet aan beginnen

zoek een echte programmeur!

Volgens mij is het helemaal niet zo gecompliceerd. Korste afstand bepaal opdrachtjes in doolhoven zijn 2e jaars opdrachten. Maar als je niets van programmeren afweet dan kun je het beter aan een programmeur overlaten.

[chem]

Op dinsdag 19 februari 2002 20:54 schreef Alarmnummer het volgende:

[..]

Volgens mij is het helemaal niet zo gecompliceerd. Korste afstand bepaal opdrachtjes in doolhoven zijn 2e jaars opdrachten. Maar als je niets van programmeren afweet dan kun je het beter aan een programmeur overlaten.

tuurlijk, het principe van het vlakverdelen is al behoorlijk uitgemolken, maar als je 't af scratch doet ben je er nodeloos lang mee bezig.

Misschien kan je op zoek gaan naar kant en klare proggels, evt. niet voor jouw doel geschikt, maar bv. voor "hoeveel printjes op een A2" etc., en dan simpelweg de maatvoering aanpassen. Kazig, maar het principe blijft hetzelfde (stickers?)

[Alarmnummer]

Op dinsdag 19 februari 2002 21:01 schreef chem het volgende:

[..]

tuurlijk, het principe van het vlakverdelen is al behoorlijk uitgemolken, maar als je 't af scratch doet ben je er nodeloos lang mee bezig.

Misschien kan je op zoek gaan naar kant en klare proggels, evt. niet voor jouw doel geschikt, maar bv. voor "hoeveel printjes op een A2" etc., en dan simpelweg de maatvoering aanpassen. Kazig, maar het principe blijft hetzelfde (stickers?)

Ik denk als een programmeur met beetje zelf respect hier achter gaat zitten (en dan moeten er niet nog allerlei wensen bijkomen) dat hij het in een middag moet kunnen klaren.

[chem]

Op dinsdag 19 februari 2002 21:05 schreef Alarmnummer het volgende:

[..]

Ik denk als een programmeur met beetje zelf respect hier achter gaat zitten (en dan moeten er niet nog allerlei wensen bijkomen) dat hij het in een middag moet kunnen klaren.

tsja, ik weet niet hoe lang we met de tool zijn bezig geweest wat dat ene aspect betreft: de calculatie bestond uit 11 factoren, die onderling afhankelijk waren en waaronder nog diverse factoren speelde én er moest een admin bij + de mogelijkheid om kortingen aan bepaalde dealers toe te kennen etc. etc.... beetje lastig dus om te zeggen dat het 'zus en zo' lang duurde

ik gok dat het ~ een slappe ochtend + middag kost als je dit in bv. php doet, en een maand of 3 in excell

[RickN]

Op dinsdag 19 februari 2002 20:54 schreef Alarmnummer het volgende:

[..]

Volgens mij is het helemaal niet zo gecompliceerd. Korste afstand bepaal opdrachtjes in doolhoven zijn 2e jaars opdrachten. Maar als je niets van programmeren afweet dan kun je het beter aan een programmeur overlaten.

Ja, maar het probleem wat jij schets is in principe ook maar een korste pad algoritme in een graaf, en daar zijn gewoon snelle algoritmes voor bekend. Ik weet zo niet de precieze complexiteit, maar iig <= O(|V|^2), met V de verzameling knopen in de graaf.

Het optimalisatie probleem dat peioz schets is heel wat anders, is schat dat dit een probleem in NP is en dat er waarschijnlijk geen polynomiale complexiteit algoritme voor is. Backtracken zoals je zeg kan wel en is een lekker simpele oplossing als de verzameling lengtes beperkt is, maar de rekentijd loopt dan gauw uit de hand, waarna je bent aangewezen op heuristische zoekmethoden. Om zo'n methode goed in elkaar te zetten is geen triviale aangelegendheid hoor, trust me, ik heb er een gemaakt voor m'n stage. Duurde 3 maanden en ik was voor het em als stage opdracht ging doen al een hele tijd met het probleem bezig geweest.

[MisterData]

Hmm dit zou een leuke opgave voor GPC zijn geweest

[Alarmnummer]

Op dinsdag 19 februari 2002 21:11 schreef RickN het volgende:

[..]

Ja, maar het probleem wat jij schets is in principe ook maar een korste pad algoritme in een graaf, en daar zijn gewoon snelle algoritmes voor bekend. Ik weet zo niet de precieze complexiteit, maar iig <= O(|V|^2), met V de verzameling knopen in de graaf.

Het optimalisatie probleem dat peioz schets is heel wat anders, is schat dat dit een probleem in NP is en dat er waarschijnlijk geen polynomiale complexiteit algoritme voor is. Backtracken zoals je zeg kan wel en is een lekker simpele oplossing als de verzameling lengtes beperkt is, maar de rekentijd loopt dan gauw uit de hand, waarna je bent aangewezen op heuristische zoekmethoden. Om zo'n methode goed in elkaar te zetten is geen triviale aangelegendheid hoor, trust me, ik heb er een gemaakt voor m'n stage. Duurde 3 maanden en ik was voor het em als stage opdracht ging doen al een hele tijd met het probleem bezig geweest.

Het is inderdaad de vraag hoeveel combinaties er gemaakt kunnen worden. En inderdaad, als je het niet meer via eenvoudig backtracken kan oplossen dan wordt het een stuk gecompliceerder. Maar als het aantal niet te groot is zou je uitstekend gebruik kunnen maken van backtracken. Niet moeilijker doen dan moet.

[Alarmnummer]

[een enorme boeren kinkel methode als er veel combinaties zijn]
Stel dat je 1000 profielen moet maken en door alle combinaties bij langs te gaan is hij te lang bezig. Dan zou je er voor kunnen kiezen om per 10 profielen door te laten rekenen, totaal 100 keer. Hierdoor wordt het aantal combinaties gigantisch gereduceerd. Ik denk niet dat het voor een aluminium bedrijf nuttig is om een wiskundig correct algoritme te maken als er toch altijd wel iets misgaat. (Ben ik zelf wel eens mee op mijn bek gegaan). Je zult natuurlijk altijd wel wat meer verbruiken als een 'correcter' algoritme.. maar of dat kleine beetje nog wat uitmaakt tegen wat er gewoonlijk verloren/beschadigt raakt.

[/een enorme boeren kinkel methode als er veel combinaties zijn]

[Verwijderd]

Op dinsdag 19 februari 2002 21:25 schreef Alarmnummer het volgende:
[een enorme boeren kinkel methode als er veel combinaties zijn]
Stel dat je 1000 profielen moet maken en door alle combinaties bij langs te gaan is hij te lang bezig. Dan zou je er voor kunnen kiezen om per 10 profielen door te laten rekenen, totaal 100 keer. Hierdoor wordt het aantal combinaties gigantisch gereduceerd. Ik denk niet dat het voor een aluminium bedrijf nuttig is om een wiskundig correct algoritme te maken als er toch altijd wel iets misgaat. (Ben ik zelf wel eens mee op mijn bek gegaan). Je zult natuurlijk altijd wel wat meer verbruiken als een 'correcter' algoritme.. maar of dat kleine beetje nog wat uitmaakt tegen wat er gewoonlijk verloren/beschadigt raakt.

[/een enorme boeren kinkel methode als er veel combinaties zijn]

Wat een goede manier is om het aantal combinaties te verminderen is het beperken van het aantal mogelijke lengtes. Waarschijnlijk is het aantal lengtes in de praktijk al erg beperkt. En omdat je bijna altijd meerdere van een bepaalde lengte moet maken kun je ook groepsgewijs backtracken. Het probleem dat je hebt doordat er wel eens wat mis gaat in een bedrijf kun je oplossen door op dat moment je programma de boel opnieuw uit te laten rekenen met de verkeerd gemaakte reststukken.

[RickN]

Wat ook aardig zou kunnen zijn is een database aanleggen van combinaties van lengtes die (bijna) optimaal gebruik maken van zo'n 6 meter lang stuk. Als je dan een verzameling lengtes voorgeschoteld krijgt kun je er eerst die combinaties in de database uitfilteren (omdat je toch bijna niet beter kunt dan dat) en de rest optimaliseren met backtracken ofzo...

[Alarmnummer]

Op dinsdag 19 februari 2002 21:46 schreef borganism het volgende:

[..]

Wat een goede manier is om het aantal combinaties te verminderen is het beperken van het aantal mogelijke lengtes. Waarschijnlijk is het aantal lengtes in de praktijk al erg beperkt. En omdat je bijna altijd meerdere van een bepaalde lengte moet maken kun je ook groepsgewijs backtracken. Het probleem dat je hebt doordat er wel eens wat mis gaat in een bedrijf kun je oplossen door op dat moment je programma de boel opnieuw uit te laten rekenen met de verkeerd gemaakte reststukken.

Ligt er een beetje aan hoe het bedrijf in elkaar zit. Bij veel bedrijven worden er eerst schema`s in elkaar gezet en daarna worden die op dewerkvloer uitgevoerd. Het gebeurt volgens mij niet vaak dat er dan weer een terug koppeling is naar het maken van die schema`s. Maarja.. ligt er maar net een beetje aan hoe het bedrijf in elkaar zit.

en dat met die database is een heel leuk idee maar op een of andere manier moet er wel op een soort patroon gezocht kunnen worden. En dit is volgens mij ook zeker niet eenvoudig.

[Verwijderd]

'k denk dat ik maar eens begin met het zoeken naar gelijksoortige progjes op internet.... Iemand suggesties ?

[Verwijderd]

Goh, doet mij ook denken aan een informatica-opdracht met een kortste-weg probleem. Schrok me dood toen ik die kreeg uitgereikt, had het idee dat het programma enkele jaren zou moeten rekenen, viel uiteindelijk nog reuze mee . Maarja, ik studeer ook niet voor programmeur.

Het lijkt mij ook dat je met een beetje ruwe numbercrunching en zonder al te geniale algortimes ook wel kunt komen, zolang je niet blind elke mogelijke combinatie probeert (zeg min. stuk is 1m, dus alle combinaties uitproberen in 6 stuks, dus ook dingen als 3+3+3+3+3+3=18, goh, dat past niet). Bij overzienbare aantallen profielen zal de rekentijd volgens mij reuze meevallen.
Bij grote aantallen profielen gewoon een subset ervan pakken (1/10e of zo) en die optimaliseren. Tja, zal ook wel afhangen van hoeveel nauwkeurigheid die mensen vragen en hoe lang ze op de resultaten willen wachten.

[Alarmnummer]

Op woensdag 20 februari 2002 23:52 schreef Ublis het volgende:
Het lijkt mij ook dat je met een beetje ruwe numbercrunching en zonder al te geniale algortimes ook wel kunt komen, zolang je niet blind elke mogelijke combinatie probeert (zeg min. stuk is 1m, dus alle combinaties uitproberen in 6 stuks, dus ook dingen als 3+3+3+3+3+3=18, goh, dat past niet). Bij overzienbare aantallen profielen zal de rekentijd volgens mij reuze meevallen.

Dat kan je in je back track procedure wel instellen. Gewoon niet onnodig paden ingaan.

[Killemov]

Als dit (5 x 2,3 m, 10 x 2,6 m, 10 x 3,4 m, 12 x 1 m) de echte lengtes zijn hou je natuurlijk alleen maar 5 x 2,3 m en 12 x 1 m over. Vervolgens pas je een greedy algoritme toe. Je probeert steeds zo lang mogelijke stukken te passen. (2,3 m, 2,3 m, 1 m, rest is dan 40 cm)

[DaRealRenzel]

Toevallig heeft een neef van mij een software bedrijf dat dit reeds standaard in hun pakket hebben, niet alleen zaagoptimalisatie, maar ook reststukadministratie, rekening houdend met zaagsnedes e.d. (dus uit een pijp van 6 meter kun je geen 6 stukken van 1 meter zagen, omdat je de zaagsnede mee moet rekenen..). Kijk ff op www.ispsoftware.nl