Hoe vind je de beste zaagstrategie?

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 10 nov 2021, 00:29

Ik heb je bestand gedownload en zal hier waarschijnlijk komend weekend nog wat testen mee uitvoeren en kijken hoe ver het programma met die voorbeelden komt.
Maar hier eerst nog een 5-tal toelichtingen op de werking van het programma (er zijn alleen al in deze 5 punten nog tal van mogelijkheden voor verdere automatisering).


[1] Rekentijd

Opbouw van het programma:
1. lees de latcatalogus en ordergegevens in (order met N latmaten met voor elke latmaat een gegeven (= bestelde) hoeveelheid)
2. genereer alle magazijnlatverzagingen die alleen latlengtes uit de order leveren, en die bovendien voldoen aan de gegeven afvallimiet per magazijnlat
3. sorteer deze verzagingen op hoeveelheid restafval per magazijnlat
4. doorzoek alle N-tallen verzagingen (te beginnen met de kleinste hoeveelheid restafval)
5. voor elk N-tal mogelijke verzagingen: los het stelsel van N vergelijkingen met N onbekenden op.
6. indien punt 5 een oplossing heeft: evalueer dan de score en houd het minimum bij.

De rekentijd neemt erg snel toe met toenemende N:
- in stap 2: het aantal mogelijke magazijnlatverzagingen (=V) neemt snel toe met N
- in stap 4: het aantal mogelijke verzagingscombinaties = \({V \choose N}\)
- in stap 5: het stelsel oplossen gaat met een tijdsduur in de orde van \(N^2\)

Hou daarom zowel V als N laag:
(1) Kies maximaal N = 5 a 6 lattypen per (deel-)order, en
(2) begin met lage waarden van de hoeveelheid restafval per magazijnlat, en herhaal de berekening met geleidelijk oplopende waarden (mocht het te lang duren: onderbreek het programma dan handmatig; de beste oplossing tot dat moment is altijd al als tekstbestand opgeslagen).


[2] Bestellingen met grote N: optie 1: elimineren van bestelde latmaten

Strategie: probeer 1 of meer order-maten te elimineren, te beginnen met die met het kleinste aantal.
Aan de hand van een voorbeeld:
De order van regel 4 in de Excel-tabel van mijn vorige post bevat 7 latmaten.
Van de maten 147 en 246 zijn slechts 6 exemplaren nodig.
Omdat latmaat 147 een zeer zeldzame bestelling is, proberen we die eerst weg te werken.

Dit kan door in het order bestand de controle waarde onder de 6 (van 147mm) op -1 te zetten:

order.txt

Code: Selecteer alles

0	200	200	0	6	200	0	300	6	0	0	150	0	0	0
0	0	0	0	-1	0	0	0	0	0	0	0	0	0	0
10
Het programma genereert dan een bestand eliminatieverzagingen.txt. Dit is hetzelfde als de magazijnlatverzagingen.txt, maar nu met alle regels met nulwaarden op de positie van de gemarkeerde 6 weggelaten.
Zoek in die tabel dan een regel (of combinatie van regels) waarmee je exact 6 stuks van 147mm kan produceren.
Er zijn er hier veel kandidaten, maar die op regel 42 is het meest ideaal:
(42): 1, 0, 1, 2, 1, 1, 2, 0
dat wil zeggen een verzaging van een magazijnlat in:
1x95 + 0x120 + 1x147 + 2x155 + 1x196 + 1x246 + 2x396
waarbij we 0 restafval hebben.

Hiervan hebben we er 6 nodig, wat oplevert:
6x95 + 0x120 + 6x147 + 12x155 + 6x196 + 6x246 + 12x396
met 0 restafval

Zo hebben we als bonus ook meteen de latten van 246mm compleet (2 vliegen in 1 klap).

Voor de oorspronkelijke order hebben we nu dus nog nodig:
194x95 + 200x120 + 0x147 + 188x155 + 294x196 + 0x246 + 138x396
Dit geeft de volgende order.txt:

Code: Selecteer alles

0	194	200	0	0	188	0	294	0	0	0	138	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
10
met als resultaat:

Code: Selecteer alles

magazijnlatlengte = 1800
zaagbladdikte = 2
max rest = 10
keuze uit 82 mogelijke magazijnlatverzagingen

Verzagingsschema:
    36 x [1, 2, 3, 5, 0]	=   36 x line 5
    16 x [2, 7, 1, 1, 1]	=   16 x line 13
    33 x [1, 0, 2, 3, 2]	=   33 x line 15
    19 x [5, 1, 0, 0, 3]	=   19 x line 16

latlengte:      95     120     155     196     396
productie:     196     203     190     295     139
order:         194     200     188     294     138
overschot:       2       3       2       1       1

totale orderlengte = 185870 = 103.1465 magazijnlatten
benodigde lengte   = 187408 = 104 magazijnlatten
benodigd / totaal  = 1.0083
onbruikbare rest = 68 = 0.04% van het gebruikte materiaal
huidige min rest = 68

timer: 31.937000 sec

[3]Bestellingen met grote N: optie 2: splitsen

Splits deze in (deel-)orders van maximaal 5 a 6 lattypen, en los de deelorders op.
Zorg daarbij wel voor een evenwichtige verdeling van de bestelde latmaten (dus niet alle grote bij elkaar, maar zowel kleine als grote maten in elke deelorder).


[4]Bestellingen met kleine N: optie 1: aanvullen met frequent bestelde latmaten

De order van regel 5 in de Excel-tabel van mijn vorige post bevat 1 latmaat: 155mm en daar 500 stuks van:

order.txt

Code: Selecteer alles

0	0	0	0	0	500	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
100
En dit geeft in minsolutionminrest100.txt:

Code: Selecteer alles

magazijnlatlengte = 1800
zaagbladdikte = 2
max rest = 100
keuze uit 1 mogelijke magazijnlatverzagingen

Verzagingsschema:
    46 x [11]	=   46 x line 2

latlengte:     155
productie:     506
order:         500
overschot:       6

totale orderlengte = 78500 = 43.5627 magazijnlatten
benodigde lengte   = 82892 = 46 magazijnlatten
benodigd / totaal  = 1.0559
onbruikbare rest = 3450 = 4.16% van het gebruikte materiaal
huidige min rest = 3450

timer: 0.015000 sec
De eenzijdige productie levert hier dus 3450 mm restafval, behoorlijk wat.
Dit zou je kunnen opvangen door ook latmaten die in het algemeen veelvuldig besteld worden maar niet in de huidige order zitten toe te laten. Zet de controle variabele van de betreffende kolom(men) daarvoor op 1.
Als we ook productie van latlengtes 120, 196, 246 en 311mm willen toestaan, geeft dat

order.txt

Code: Selecteer alles

0	0	0	0	0	500	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	1	1	1	0	0	0	0	0
10
waarmee we dit resultaat krijgen:

Code: Selecteer alles

magazijnlatlengte = 1800
zaagbladdikte = 2
max rest = 10
keuze uit 42 mogelijke magazijnlatverzagingen

Verzagingsschema:
    22 x [7, 6, 0, 0, 0]	=   22 x line 26
    53 x [0, 7, 1, 2, 0]	=   53 x line 36

latlengte:     120     155     196     246     311
productie:     154     503      53     106       0
order:           0     500       0       0       0
overschot:     154       3      53     106       0

totale orderlengte = 78500 = 43.5627 magazijnlatten
benodigde lengte   = 135150 = 75 magazijnlatten
benodigd / totaal  = 1.7217
onbruikbare rest = 609 = 0.45% van het gebruikte materiaal
huidige min rest = 609

timer: 1.359000 sec
Nu 609mm restafval, behoorlijk minder dan die 3450mm hierboven, terwijl we het overschot aan latten in de volgende orders gemakkelijk kunnen wegzetten (in deze order-tabel zelfs alles al direct in de volgende order).


[5]Bestellingen met kleine N: optie 2: samenvoegen

Indien mogelijk kan je die bestellingen ook samenvoegen en ze als 1 opdracht verwerken.

Michielvh
Nieuw lid
Nieuw lid
Berichten: 10
Lid geworden op: 27 okt 2021, 12:27

Re: Hoe vind je de beste zaagstrategie?

Bericht door Michielvh » 10 nov 2021, 18:21

Hallo Arie,

Ik zat er doorheen te lezen en las over rekentijden van enkele seconden. Dit is prima acceptabel hoor. We gaan niet veel moeite doen met orders splitsen als de rekentijd onder de 15 minuten (oid) blijft. Ik zet gewoon een zandlopertje op het scherm, met 'wacht op berekeningen.' mocht dit voorkomen.
Men leert hier wel mee omgaan door zelf enkele logische latlengtes toe te voegen oid. En het magazijn met zaagmateriaal moet ook worden bijgevuld af en toe, en het gezaagde materiaal moet worden uitgenomen. Dat kan prima in die tijd.

Plaats reactie