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.
Michielvh
Nieuw lid
Nieuw lid
Berichten: 10
Lid geworden op: 27 okt 2021, 12:27

Hoe vind je de beste zaagstrategie?

Bericht door Michielvh » 27 okt 2021, 13:55

Hallo wiskundigen,

Ik ben hier terecht gekomen na een zoektocht over het volgende:
Voor een automatische, nog te programmeren zaagmachine ben ik op zoek naar een methode om een (variërende) klantorder zo efficiënt mogelijk uit een aantal vaste lengtes materiaal te zagen.
De magazijnlengte waaruit de stukken gezaagd worden is een vaste maat : 1800.
De klant kan vervolgens delen bestellen met verschillende lengtes. De klant kan uit 9 soorten vaste lengtes kiezen die in variabele aantallen worden besteld.

Het vraagstuk:
Wat is de beste strategie om een willekeurige order te maken met zo min mogelijk afval en zo min mogelijk 'niet bestelde lengtes' ? Zie onderstaande:

Bijvoorbeeld:
De beschikbare lengtes zijn bijvoorbeeld:

c 120
d 156
e 176
f 196
g 246
h 311
i 351
j 396
k 448

Een (willekeurige) order kan bijvoorbeeld bestaan uit :
203 * c (203 stukken van lengte "c")
114 * d
100 * f
250 * g
18 * h

Meer informatie:
-de lengtes worden uit stukken van ' 1800' gezaagd.
-zaagsnedeverlies is ' 2' per snede.
-uit een restant korter dan ' c' kan niks meer gemaakt worden: dat is dus afval.
-de magazijnlengtes moeten zo volledig mogelijk worden opgezaagd met lengtes uit de order, met minimaal afval/restant.
-de zaag-volgorde mag willekeurig zijn. Je mag dus 3*d +6*c+1*g +... whatever.. zagen tot er 1800 (bijna)op is. Maar ook bijvoorbeeld 7*g. Alleen heb je dan dus 1800-(7*(246+2) =64 per magazijnlengte verlies. (250/7=35* 64 verlies)
-van het laatste overblijvende restant (nadat de order klaar is) mogen een of meerdere lengtes gemaakt worden uit de beschikbare-lengte-lijst, ook als dit niet besteld is.

Hoe langer ik erover denk hoe ingewikkelder het wordt. Ik hoop dat iemand met een wiskundeachtergrond dit puzzeltje eens wil bekijken en hier een werkbare strategie voor kan aanreiken, of me van tips kan voorzien waardoor ik dit slim kan aanpakken en er minder afval gemaakt wordt.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 27 okt 2021, 23:23

Dit is een bin packing probleem, zie bijvoorbeeld
https://en.wikipedia.org/wiki/Bin_packing_problem
waarbij
- we hier in 1 dimensie kijken (lengte)
- naar "offline oplossingen" kunnen kijken (we krijgen eerst de complete order voordat we gaan zagen)
- de bins = de magazijnlatten met lengte 1800 zijn.
Dit probleem is NP-hard, dat wil zeggen alleen met brute kracht op te lossen (= alle mogelijkheden afgaan). Dit laatste is voor iets grotere aantallen al snel niet meer te doen: ook de computer heeft hier veel te veel tijd voor nodig.
Wel zijn er goede benaderingensmethoden.
Ik zou in eerste instantie zo te werk gaan:

1. Probleemvereenvoudiging: verwijder de zaagsnedes:
Om het jezelf eenvoudiger te maken kan je bij elke latlengte 1 zaagsnede optellen.
In jouw geval krijgen we dan deze mogelijke lat-lengtes:
122, 158, 178, 198, 248, 313, 353, 398 en 450
en doe dat ook voor de magazijnlatlengte (dus 1802 als rekenlengte te gebruiken).
Immers: de laatste zaagsnede is alleen nodig als we van een magazijnlat latlengte overhouden.
Voorbeeld:
7*(120+2) + 6*(156+2) = 7*122 + 6*158 = 1802
Deze 13 latjes kunnen we uit de magazijnlat van 1800 krijgen door 13 - 1 = 12 zaagsneden.
(de laatste zaagsnede met lengte 2 hebben we niet nodig)

2. Voer een offline bin packing algoritme uit
(zie https://en.wikipedia.org/wiki/Bin_packi ... algorithms)
Dergelijke algoritmes zijn voor diverse programmeertalen terug te vinden op het web, zie bv het laatste algoritme op deze pagina:
https://www.geeksforgeeks.org/bin-packi ... used-bins/
Over het sorteren hoef je je hier niet druk te maken: de mogelijke latlengtes staan al op volgorde.
In het voorbeeld in jouw post heb je dus alleen deze 2 vectoren nodig:
- v met de latlengtes:
v = [122, 158, 178, 198, 248, 313, 353, 398, 450];
- w met de aantallen in de bestelling:
w = [203, 114, 0, 100, 250, 18, 0, 0, 0];

3. Bekijk alternatieve oplossingen
Bovenstaande algoritmes leveren in de praktijk nog wel redelijk wat restmateriaal.
Mocht je in je magazijn ruimte hebben voor een voorraad gezaagde latten, dan kan je tot aanzienlijk minder restmateriaal komen.
In jouw voorbeeld zijn er 4237 mogelijke manieren om je magazijnlatten te verzagen in de 9 gegeven latlengtes. Hiervan zijn er 44 die NUL restlengte geven, 36 met restlengte 1, 49 met restlengte 2 etc.
(de mogelijkheden met restlengte NUL staan in de Excel-tabel hieronder).
Per order kan je dan eerst uit de voorraad verzaagde latten putten, en wat daarna nog nodig is uit magazijnlatten verzagen via handige combinaties uit onderstaande tabel (of een uitgebreidere versie daarvan).

Het is nu wat laat, ik zal hier morgen verder naar kijken.

PS
Met welke programmeertaal werk je?


Afbeelding

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 » 28 okt 2021, 10:06

Hallo Arie,
Wat interessant! En wat leuk om daar meer over te weten te komen.
Het programma is/wordt in C geschreven en de data die daaruit komt sturen we naar de machine. Gaaf als we dat straks kunnen optimaliseren. Momenteel zagen we het met de hand (per 10 stuks) en dat geeft veel meer afval.
Ik ben ook benieuwd hoe je dit in excel hebt gekregen, want ik heb er ook al wat tijd in gestopt maar kwam er niet uit.

Het is geen probleem om stukken uit een magazijn te halen, ik was al bezig met een (digitaal) magazijn. Ik had bedacht om dan bij een bestelling gewoon artikelen uit dit magazijn te halen en de machine alleen steeds het magazijn tot het voorraadniveau te laten bijvullen op een efficiënte wijze.
In het magazijn kunnen we dan per artikel een minimale voorraad aanhouden om te zorgen dat we niet teveel 'incourante' maten in het magazijn krijgen. Bepaalde maten hebben een voorkeur en sommige maten komen juist zelden voor, dus daar wil je niet een magazijn van vol krijgen omdat dat toevallig goed uitkomt bij het opzagen van een lengte. Maar dat is een kwestie van voorraadniveaus aanpassen.
Bij een grote order worden bepaalde productniveaus gewoon 'onder nul' gezet, waardoor deze dan bijgevuld wordt. Of zoiets.
De machine zal dan vanzelf een afnemende vrijheid krijgen van lengtes om 'uit te kiezen' .

Bedankt zover voor het uitgebreide antwoord, ik ga er naar kijken.

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 » 28 okt 2021, 14:35

Ik heb er een tijdje naar gekeken, de volgende stap is dus het selecteren van de verschillende oplossingen zodat de hoeveelheid producten de aantallen benaderen die ook besteld zijn?
En daarna moet je bepaalde lengtes kunnen uitsluiten om te voorkomen dat je daar een magazijn van vol krijgt als bijproduct..

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 30 okt 2021, 10:27

Die tabel heb ik in een andere programmeeromgeving gemaakt, en het resultaat in Excel geladen.
In Excel is het eenvoudiger om kleuren en andere formateringen aan te brengen waardoor alles wat duidelijker wordt.

Maar het belangrijkste: als je een voorraad kan aanleggen, dan is een oplossing met NUL verlies (behalve het zaagsel = 2 eenheden per snede) mogelijk.
Het probleem verandert dan inderdaad in een zoekprobleem onder de 44 complete verzagingen (zie de tabel die ik hierboven gegeven heb), waarbij we zo min mogelijk magazijnlatten willen verzagen om aan een gegeven order te kunnen voldoen.


Een eerste ruwe benadering

Code: Selecteer alles

score = 87:
     2 x [3, 0, 0, 6, 1, 0, 0, 0, 0]    =    2 x line 4
    40 x [0, 4, 1, 0, 4, 0, 0, 0, 0]    =   40 x line 7
     0 x [0, 1, 7, 0, 0, 0, 0, 1, 0]    =    0 x line 8
    27 x [6, 0, 1, 2, 2, 0, 0, 0, 0]    =   27 x line 14
    18 x [2, 0, 0, 2, 2, 1, 1, 0, 0]    =   18 x line 33
TOTAL:     204     160      67     102     252      18      18       0       0
ORDER:     203     114       0     100     250      18       0       0       0
rest:        1      46      67       2       2       0      18       0       0
totale orderlengte = 130212
benodigde lengte   = 156774
benodigd / totaal  = 1.2040
Hierboven een eerste oplossing voor het probleem in jouw voorbeeld:

De order omvat 5 verschillende latlengtes (122, 158, 198, 248 en 313, d.w.z. de kolommen A, B, D, E en F in de tabel).
Als we 5 volledige verzagingen uit de 44 mogelijke verzagingen kiezen, ontstaat een stelsel van 5 vergelijkingen met 5 onbekenden dat we in principe (maar niet altijd) kunnen oplossen.
Voor regels 4, 7, 8, 14 en 33 uit de Excel-tabel levert dat dit stelsel:

\(\begin{bmatrix}3&0&0&6&2 \\ 0&4&1&0&0 \\ 6&0&0&2&2 \\ 1&4&0&2&2 \\ 0&0&0&0&1\end{bmatrix} \cdot \begin{bmatrix} a\\ b\\ c\\ d\\ e\end{bmatrix} = \begin{bmatrix}203\\114\\100\\250\\18\end{bmatrix}\)

waarin a t/m e de benodigde aantallen zijn van de 5 gekozen verzagingen.
Als we die afronden naar boven en de negatieve waarden op nul stellen krijgen we de aantallen die (ruim) voldoende zijn voor de order. In dit geval 2 verzagingen volgens tabelregel 4, 40 volgens regel 7, 27 volgens 14 en 18 volgens 33.
In totaal hebben we dus 2+40+27+18 = 87 magazijnlatten nodig.
Van alle mogelijke combinaties van 5 uit 44 regels geeft deze oplossing de minimale score (= aantal latten = 87).


We hebben nu een bovengrens voor de minimale score, maar ik verwacht met betere zoekalgoritmes op een lager aantal benodigde magazijnlatten te kunnen komen.



Bijlagen
Mocht je het leuk vinden, hier de C-code van bovenstaande (disclaimer: snel in elkaar gezet om een eerste indruk te krijgen, zeker niet super-net, en al helemaal niet uitgebreid getest):

Code: Selecteer alles

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

const int nLatlengtes=9;         // aantal beschikbare latlengtes
const int nVerzagingen=44;       // aantal volledige verzagingen

const double delta = 0.00000001; // tbv afhandeling afrondingsfouten

double latlengtes[nLatlengtes];  // INPUT gegevens
double verzagingen[nVerzagingen][nLatlengtes];
int order[nLatlengtes];

double M[nLatlengtes][nLatlengtes];
int dimM;
int colPosM[nLatlengtes];        // posities bestelde latlengtes
int vLines[nLatlengtes];         // positie van de huidige combinatie
								 // van lijnen in de verzagingstabel
int minLines[nLatlengtes];       // deze lijnencombinatie voor de minimale oplossing
double solM[nLatlengtes];        // oplossing stelsel
int solup[nLatlengtes];          // naar boven afgeronde oplossing
int minsolup[nLatlengtes];       // minimale oplossing
int minscore=999999999;          // minimale score


//---------------------------------------------------------------------------

// load latlengtes en volledige verzagingen van magazijnlengte 1802
void loadBaseValues(void)
{
FILE *fi=fopen("verzagingen.txt","rt");
int i,j;

for(i=0;i<nLatlengtes;i++)
  fscanf(fi,"%lf",&latlengtes[i]);
for(j=0;j<nVerzagingen;j++)
  for(i=0;i<nLatlengtes;i++)
	fscanf(fi,"%lf",&verzagingen[j][i]);
fclose(fi);
}

// load order
void loadOrder(void)
{
FILE *fi=fopen("order.txt","rt");
for(int i=0;i<nLatlengtes;i++)
  fscanf(fi,"%d",&order[i]);
fclose(fi);
}

//---------------------------------------------------------------------------
// print a line:
void printLine()
{
for(int i=0;i<80;i++) printf("-"); printf("\n");
}


//---------------------------------------------------------------------------
// print found solution info:
void printsolution(void)
{
int i,j;
int result[nLatlengtes];
int score;

printLine();
score=0;
for(i=0;i<dimM;i++)
  score+=solup[i];
printf("score = %d:\n\n",score);
for(i=0;i<dimM;i++){
  printf("  %4d x [%.0lf",solup[i],verzagingen[vLines[i]][0]); //+2 for Excel table
  for(j=1;j<nLatlengtes;j++)
	printf(", %.0lf", verzagingen[vLines[i]][j]);
  printf("]\t= %4d x line %d\n",solup[i],vLines[i]+2); //+2 for Excel table
  }

memset(result,0,sizeof(result));
for(i=0;i<dimM;i++){
  for(j=0;j<nLatlengtes;j++){
	result[j]+=(int)(verzagingen[vLines[i]][j]*(double)solup[i]+0.5);
	}
  }

printf("\nTOTAL:");
for(j=0;j<nLatlengtes;j++) printf("%8d",result[j]);
printf("\n");
printf("ORDER:");
for(j=0;j<nLatlengtes;j++) printf("%8d",order[j]);
printf("\n");
printf("rest: ");
for(j=0;j<nLatlengtes;j++) printf("%8d",result[j]-order[j]);
printf("\n\n");

double orderlengte=0;
for(i=0;i<nLatlengtes;i++){
  orderlengte+=(order[i]*latlengtes[i]);
  }
printf("totale orderlengte = %.0lf\n", orderlengte);
printf("benodigde lengte   = %d\n", score*1802);
printf("benodigd / totaal  = %.4lf\n", (double)(score*1802)/orderlengte);

printLine();
}


//---------------------------------------------------------------------------
// print final found minimal solution info:
void printfinal(void)
{
int i;

// load minimal solution values:
for(i=0;i<dimM;i++){
  solup[i]=minsolup[i];
  vLines[i]=minLines[i];
  }
printsolution();
}


// bepaal de score van de huidige oplossing
// en kijk of dit een nieuw minimum is:
void evaluateSolution(void)
{
int i,j;
int score;

score=0;
for(i=0;i<dimM;i++){
  if(solM[i]>delta){
	solup[i]=(int)ceil(solM[i]-delta);
	score+=solup[i];
	}
  else
	solup[i]=0;
  }

// if(score<90) printsolution();  // print all solutions with score < 90

if(score<minscore){
  minscore=score;        // update minimal score
  //printf("%d\n",score);
  printsolution();
  for(i=0;i<dimM;i++){   // store minimal score parameters
	minsolup[i]=solup[i];
	minLines[i]=vLines[i];
	}
  }
}


//---------------------------------------------------------------------------
// los een stelsel op via Gauss-eliminatie:
//   M[][] * x[] = solM[]
// OUTPUT:
//   ok==1: oplossing zit in solM[]
//   ok==0: het stelsel heeft geen unieke oplossing
int solveMatrix(void)
{
int i,j,k, line;
int ok=1;
double tmp, q;

// load initial solution vector:
for(i=0;i<dimM;i++)
  solM[i]=(double)order[colPosM[i]];

// load matrix:
for(i=0;i<dimM;i++)
  for(j=0;j<dimM;j++)
	M[i][j]=verzagingen[vLines[j]][colPosM[i]];

// Gaussian elimination:
for(line=0;line<dimM && ok==1;line++){
  i=line;
  while(fabs(M[i][line])<delta && i<dimM)
	i++;
  if(i==dimM) // all values zero
	ok=0;
  else if(i>line){ // swap lines i and line
	for(j=0; j<dimM; j++){
	  tmp=M[i][j]; M[i][j]=M[line][j]; M[line][j]=tmp;
	  }
	tmp=solM[i]; solM[i]=solM[line]; solM[line]=tmp;
	}

  if(ok==1){ // then M[line][line] != 0:
	q=M[line][line];
	if(q!=1.0){ // normalize to M[line][line]=1:
	  for(j=line; j<dimM; j++)
		M[line][j]/=q;
	  solM[line]/=q;
	  }

	for(i=line+1; i<dimM; i++){ // sweep forward:
	  if(fabs(M[i][line])>delta){ // if M[i][line] != 0
		q=M[i][line];
		for(int k=line; k<dimM; k++)
		  M[i][k]-=(q*M[line][k]);
		solM[i]-=(q*solM[line]);
		}
	  }
	}
  }

if(ok==1){ // sweep backward:
  for(line=dimM-1; line>0; line--){
	for(i=0;i<line;i++){
	  solM[i]-=(M[i][line]*solM[line]);
	  M[i][line]=0.0;
	  }
	}
  }
return(ok);
}


//---------------------------------------------------------------------------
// maak alle combinaties van (5) verzagingen uit alle (44) gegeven opties
// en kijk of deze een oplossing vormen
void visitCombinations(int d, int start)
{
if(d==dimM){ // next combination has been found:
  if(solveMatrix()==1) // if the matrix is invertible:
	evaluateSolution();
  }
else{
  for(int i=start; i<nVerzagingen; i++){
	vLines[d]=i;
	visitCombinations(d+1,i+1);
	}
  }
}


//---------------------------------------------------------------------------
// zoek een minimale oplossing:
void search(void)
{
int i;

dimM=0;
for(i=0;i<nLatlengtes;i++){ // bepaal de kolommen die we nodig hebben:
  if(order[i]>0){
	colPosM[dimM]=i;
	dimM++;
	}
  }
printLine();
printf("current score minimum:\n");
visitCombinations(0,0);
}


//---------------------------------------------------------------------------
// MAIN PROGRAM: load input, start search, print result
int main(int argc, char* argv[])
{
loadBaseValues();
loadOrder();
search();
printfinal();
return 0;
}

//---------------------------------------------------------------------------

verzagingen.txt:

Code: Selecteer alles

122	158	178	198	248	313	353	398	450
7	6	0	0	0	0	0	0	0
1	5	5	0	0	0	0	0	0
3	0	0	6	1	0	0	0	0
0	0	4	3	2	0	0	0	0
0	2	0	5	2	0	0	0	0
0	4	1	0	4	0	0	0	0
0	1	7	0	0	0	0	1	0
5	0	0	2	0	0	0	2	0
0	1	0	0	0	0	0	3	1
0	1	0	0	3	0	0	0	2
1	6	3	1	0	0	0	0	0
1	7	1	2	0	0	0	0	0
6	0	1	2	2	0	0	0	0
0	1	2	4	2	0	0	0	0
3	1	3	0	3	0	0	0	0
3	4	1	0	0	2	0	0	0
2	0	2	0	2	0	2	0	0
6	2	2	0	0	0	0	1	0
6	3	0	1	0	0	0	1	0
0	2	5	1	0	0	0	1	0
0	3	3	2	0	0	0	1	0
0	4	1	3	0	0	0	1	0
3	5	0	0	1	0	0	1	0
2	0	3	0	0	2	0	1	0
1	0	1	0	0	0	2	2	0
8	0	1	1	0	0	0	0	1
2	0	4	2	0	0	0	0	1
2	2	0	4	0	0	0	0	1
4	1	0	0	0	0	2	0	1
0	0	0	0	1	0	2	1	1
3	2	1	1	3	0	0	0	0
2	0	0	2	2	1	1	0	0
2	1	0	1	2	0	2	0	0
2	1	2	0	1	0	0	2	0
2	2	0	1	1	0	0	2	0
2	1	2	3	0	0	0	0	1
5	2	1	0	1	0	0	0	1
1	0	2	0	1	2	0	0	1
4	0	0	1	0	1	1	0	1
2	1	1	1	0	2	0	1	0
2	2	1	0	0	1	1	1	0
1	1	0	1	1	2	0	0	1
1	2	0	0	1	1	1	0	1
1	1	1	0	2	0	0	1	1

order.txt:

Code: Selecteer alles

203 114 0 100 250 18 0 0 0

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 30 okt 2021, 22:50

Hier een variant van bovenstaande met iets (= bijna geen) onbruikbaar restmateriaal:

Selecteer uit de lijst van alle 4237 mogelijke verzagingen al die verzagingen waarvan de geproduceerde latlengtes allemaal in de order voorkomen (alle eindproducten dus uitsluitend in kolom A, B, D, E of F, geen enkel eindproduct in 1 van de overige kolommen).
Deze lijst kan je eventueel ook nog beperken tot een maximale hoeveelheid onbruikbaar restmateriaal per magazijnlat (bv maximaal 10 eenheden per magazijnlat weggooien).

In ons voorbeeld kom je dan uit op deze tabel:

Afbeelding

Voeren we dit in in het programma dat ik hierboven gaf, dan krijgen we:

Code: Selecteer alles

score = 73:
    10 x [7, 6, 0, 0, 0, 0, 0, 0, 0]    =   10 x line 2
     2 x [3, 0, 0, 6, 1, 0, 0, 0, 0]    =    2 x line 3
    18 x [0, 0, 0, 0, 6, 1, 0, 0, 0]    =   18 x line 5
    28 x [2, 2, 0, 0, 5, 0, 0, 0, 0]    =   28 x line 12
    15 x [5, 0, 0, 6, 0, 0, 0, 0, 0]    =   15 x line 18
TOTAL:     207     116       0     102     250      18       0       0       0
ORDER:     203     114       0     100     250      18       0       0       0
rest:        4       2       0       2       0       0       0       0       0
totale orderlengte = 130212
benodigde lengte   = 131546
benodigd / totaal  = 1.0102
En dit is ook het absolute minimum aantal magazijnlatten dat we voor deze order nodig hebben:
totale orderlengte / magazijnlatlengte = 130212 / 1802 = 72.2597
Hierdoor gaan er slechts een zeer beperkt aantal (= 8 ) geproduceerde restlatten naar het magazijn:
4*122 + 2*158 + 2*198 eenheden

Het nadeel is dat we nu 18*[1] + 28*[2] + 15*[4] = 134 eenheden onbruikbaar restmateriaal hebben geproduceerd.

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 » 01 nov 2021, 12:13

Hallo Arie,

Ik vind het een prachtig resultaat. Vooral de laatste variant is goed bruikbaar! Die kleine restanten worden gewoon zaagsel en het aantal onbestelde latlengtes is hier geminimaliseerd. Heel jammer dat ik niet zo bedreven ben in programmeren, dus ik ben een wat geïntimideerd door de code. Maar ik ga er samen met de programmeur van de machine naar kijken, het is aardig goed te volgen.
Heb je de code voor het maken van de tabel ook in C gemaakt? En zou je die willen delen? Ik wil kijken of ik alvast een tabel kan maken voor metrische maten en imperial maten voor drie soorten latten.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 01 nov 2021, 15:07

OK, de code voor de tabel moet ik dan nog wel omzetten, maar dat zal geen problemen leveren.
Ik zal ook de rest code nog wat vriendelijker maken.
Maar heb nog even geduld, ik verwacht hier morgen pas aan toe te komen.

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 » 01 nov 2021, 15:56

Ik heb er geen vreselijke haast mee hoor, ik vind het al fantastisch dat je zo veel tijd aan besteed! Als je me laat weten waar het heen moet kan ik je wel een kerstpakket sturen als dank ;-) Ik weet niet of je een prive bericht kunt sturen hiermee. Dan kan ik je als het klaar is een filmpje sturen van de werkende machine.
Nu ben ik nog met de tekeningen bezig voor de machine (ontwerp) en zie ik bijvoorbeeld alweer dat de zaag iets dikker is, en zo zijn er altijd wel kleine aanpassingen nodig- een extra maat latje ofzo. Het is dus handig als ik de variabelen nog wat kan veranderen als dat nodig is.

Ik denk dat ik dan uitkom op 6 zaagtabellen totaal. Want twee andere versies hebben weer andere lengtematen. Dus Profiel A, B en C in een aantal metrische en een aantal imperial maten. Deze kunnen we niet door elkaar heen gaan maken omwille van verwarring in de productie: de maten liggen soms dicht bij elkaar en ik wil geen metrische maten naar imperial klanten sturen en vice versa.
Dus als ik die tabellen zelf kan genereren ben ik al een heel eind, dat is al moeilijk genoeg. (voor mij dan tenminste ;-)

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 02 nov 2021, 21:48

Michielvh schreef: ... Ik heb er geen vreselijke haast mee hoor ...

... de zaag iets dikker is, en zo zijn er altijd wel kleine aanpassingen nodig- een extra maat latje ofzo. Het is dus handig als ik de variabelen nog wat kan veranderen als dat nodig is ...

... Ik denk dat ik dan uitkom op 6 zaagtabellen totaal ....
Mooi, dan kan ik er komend weekend nog even rustig naar kijken en het geheel wat flexibeler maken.

Kan je ook een indruk geven van de 6 tabellen en dan met name het aantal maten per tabel en grootte-orde van die maten.

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 » 05 nov 2021, 11:07

Ik heb het even met de klant overlegd, en daar komt weer wat meer informatie uit; er is eigenlijk 1 type (A) dat vooral in standaardmaten geleverd wordt en in grotere hoeveelheden. Dat zou dus best met twee (vaste) tabellen kunnen gaan (metrisch en imperial), vooral omdat bij dit type de bestelaantallen groter zijn.

Andere orders met B en C komen ook veel voor met maar éen, twee of drie bestellengtes en
in kleine aantallen, maar ook met wel 14 verschillende bestellengtes! En waardoor je soms wel een meter of meer restmateriaal overhoudt die je ook niet kunt opzagen met 'andere maten uit de order' omdat die er simpelweg niet opstaan. Ook kunnen stukken van ' profiel B' niet uit "profiel C' gezaagd worden wat de orders soms nog kleiner maakt. Lastige kwestie.
Bij sommige orders kun je dus maar 1 stuk zagen en staat er verder niks bruikbaars op de order voor het reststuk.

Ik denk dat er voor het maken van B en C na (of vóór)het berekenen van de zaaglijst een keuze "maak van rest:" in moet komen waar de operator dan bijvoorbeeld invult: 155,450,500,afval. Zodat je in ieder geval nog 'je favoriete lengtes' zelf als extra kunt bestellen om op voorraad te leggen.

Ik vraag me af: Waar moet ik eigenlijk aan denken als berekeningstijd om een tabel te genereren met brute force? 1 minuut? 5 minuten? 0.5 uur? Dat hangt natuurlijk sterk af van het aantal variabelen. En als je vooraf het aantal variabelen beperkt? Door alleen de orderlengtes en aantallen plus eventueel eigen extra keuzes te maken?


In de bijlage heb ik een excel bestand gezet met de verzamelde data.

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 » 05 nov 2021, 11:55

Kan je ook een indruk geven van de 6 tabellen en dan met name het aantal maten per tabel en grootte-orde van die maten.
[/quote]
orderaantal (elke kolom = 1 order tot de dubbele streep , bijv kolom E: 500x 120 + ... +100 x311)
MM zaagmaat (mm) Profieltype pattern
75 A r x x x x x x x x x x
95 A r x 100 200 x x x 100 x x 150
120 A r 500 200 200 x 200 x x 500 300 150
135 A r x x x x x x x x x x
147 A r x x 6 x x x x x x x
155 A r 200 200 200 500 160 200 600 200 500 500
176 A r x x x x x x x x x x
196 A r 200 200 300 x 100 x x 200 200 500
246 A r 200 200 6 x 250 300 x 200 100 300
311 A r 100 x x x 150 x x 100 x 100
351 A r x x x x x x x x x x
396 A r x x 150 x x x x x x x
446 A r x x x x x x x x x x
496 A r x x x x x x x x x x
626 A r x x x x x x x x x x

INCH zaagmaat (mm) Profieltype pattern orderaantal (elke kolom = 1 order tot de dubbele streep , bijv kolom E: 40x 149 + ... +50 x403)
6 149 A r 40 x
8 200 A r 80 x
10 251 A r 120 x
12 302 A r 120 x
14 353 A r 80 x
16 403 A r 60 x
24 607 A r 50 x
24 607 A r 50 x
16 403 A r 50 x
18 453 A r x x
20 504 A r x x
22 555 A r x x
24 606 A r x x

MM zaagmaat (mm) Profieltype pattern orderaantal (elke kolom = 1 order tot de dubbele streep , bijv kolom E: 2x 896 + ... +2 x 346)
96 B r x 20 x x x 60 x x x x x x x x 15 x x x x x x 10 x x x x x x x x x 40 x x x x x x x x x x x x x x x x
121 B r x x x x x 20 x x 11 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 27 x x x x
156 B r x x 2 x x x 2 x x x x x x x 10 x x x x x x x x x x x x x x x x x 60 x x 20 x 2 x x x x 25 x x x x x x
196 B r x x x x x 10 x x 14 x x 10 x x x x x 6 x x x x x x x x x x x x x 12 40 20 x x x 27 x x x 25 x x x x x x x
246 C r x x x x x x x x x x x x 11 x x x x x x x x x x x 20 x x x x x x x x x x x x x x 14 x x x x x x 10 x 1
311 C r x x x x 3 x x x x x 2 x x x 5 x x 25 x x x x x x x x x x x 2 x 7 x x x x x x x x x x 20 x x x 3 x 1
351 C r x x x x x x x x x 1 x x x x x x x 5 x x x x x x x x x x x x x x x x x x x x x x x x 20 x x x x x x
396 C r x x x x x x x x x x x x 11 x x x x 5 x x x x x x x x x x x x x 3 x x x x x x x x x 30 20 x x x x x x
446 C r x x x x x x x x 6 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 25 x x x x x x
496 C r x x x x x x x x 7 x x x 6 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
896 C r 2 x x x x x 3 x 14 1 x x x x x x 2 x x 15 x x x 20 20 x x x 20 x x x x x 1 x 17 x 2 x x x x x x 30 4 x 34
196 C x x x 5 x 20 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 25 x x x x x 10 2
246 C x x x x x 15 x x x x x x x 14 x 10 x x x x x x x x x x x x x x x x x x x x x 20 x x x x x x x x x x x
296 C 2 x x 3 x 15 x x x x x x x x x x x x x x x x x x x x 25 x x x x x x x x x x x x x x x x x x x x 10 5
346 C 2 x 8 3 x 10 x x x x x x 10 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 13
396 C x 6 x x x 15 x x x x x x x x x 15 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 10 54
446 C x x 10 x 7 5 x x x x x x x x x x x x x x x 20 x x x x x x x x x x x x x x x x x x x x x x x x x x 18
496 C x x x 10 x 4 x x 14 x x x x x x x x x x x x 15 x x x x x x x x x x x x x x x 35 x x x x x x x x x 10 19
546 C x x x x x 10 x 30 x x x x x x x x x x x x x x x x x x x x x x 2 x x x x x x x x x x x x x x x x x x
596 C x x x 3 12 20 x x x x 4 x x x x x x x x x 18 x x x x x x x x x x x x x x x x x x x x x x x x x x x 10
646 C x x 10 3 x 10 x x x 2 x x x x x x x 5 x x x x x x x x x x x x x x x x x x x x x x 20 x x x x x x x x
696 C x x x 5 x x x x x 6 x x 10 x x x x x x x x x x x x x x 2 x x 2 x x x x x x x x x x x x x x x x x x
746 C x 7 x 4 x 14 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 20 x x x x x
796 C x 6 x 30 x x x x x x 5 x 10 x 6 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
846 C x x x 24 x x x x x 2 x x x x x x x x x x x x x x 20 x x x x x x x x x x x x x x x x x x x x x x x x
896 C x x x 42 x x x x x 4 x x 5 x x x x x x x x x x x x x 15 x x x x x x x x x x x x x x x x x x x x x x
946 C x x x 48 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
996 C x x x x x x x x x 2 x x x x x x x x x x x x x x x 15 x x x x x x x x x x x x x x x x x x x 25 x x x
1046 C x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
1096 C x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
1146 C x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
1196 C x x x 20 x x x x x x x x x x x x x x x x x x x x x x 15 x x x x x x x x x x x x x x x x x x x x x x
>1196 C x x x 10 x x x x x 6 x x x x x x x x 2 x x x x x x x x x x x x x x x x x x x x x x x x 32 x x x x x


INCH zaagmaat (mm) Profieltype pattern aantal (elke kolom = 1 order, bijv 10 x 406 + ….+ 5 x 1118) voorraad
4 102 B r x x x x x x 10 10 x x x x x x x x x x x x x x x 12 x x x x x x x x 10 x x x x x x x x x x 10
5 127 B r x x x x x x x x 10 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 12 x x x x 10
6 152 B r x x x x x 58 40 x 10 x x 15 x x x 28 x x x x x 24 x 15 19 34 x 40 x 35 x x x x x x x x 52 x 27 26 20 30
7 178 B r x x x x x x x x x x x x x x x x 10 x x x x x x x x x x x x x x x x x x x x x x x x x x 10
8 203 B r x x 10 x 10 x 30 5 x x 5 10 x x 15 25 x x 25 25 20 x 20 x 28 32 30 10 x 10 x 50 10 x 13 12 x x x 60 x x x 40
10 254 C r x x x x x x x 30 10 x x 10 x x x x 50 x x x x x x x x 5 50 10 25 40 x 50 20 x x x x 36 x 30 x 10 10 50
12 305 C r x x x x x x x 10 x 10 x x x x 40 x 100 20 x x x 10 60 20 x x 20 10 x x x 20 30 x 67 16 x 15 x 25 x x x 50
14 356 C x x x x x 26 x x 8 x 1 8 x x x 30 100 x x x x x x x x x x x 46 56 x x 10 x 25 15 14 x x x x x x 40
16 406 C 20 x x 9 20 x x x x 10 x x x 30 x x 20 x x 25 35 x x x 24 x 40 10 x x x 20 x x 51 14 x 13 x 20 x x x 40
18 457 C x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 30
20 508 C x x x x x x x x x x x x x 40 x x x x x x 35 15 x x x x 20 x x x 34 20 x x 26 8 x 6 x 6 x x 7 30
22 559 C x x x x x x x x x x x x x x 10 x x x x 12 20 x x x x x x x x x 32 x x x x x 15 x x x x x x 10
24 610 C x x x x 20 x x x x x x x x x 20 x x x x x 15 x x x x x x x x 17 28 x x 15 x x 14 x x x x x x 30
26 660 C x x x x x x x x x x x x x x x x x x x x 14 x x x x x x x x x x x x x x x 7 x x x 5 x x 10
28 711 C 10 x x x x x 10 x x 10 x x 40 x 10 x x 20 x x 37 x x x x x x x x x x x x x x x x x x x x x x 10
30 762 C x x x x x x x x x x x x x x x x x x x x 14 x x x x x x x x x x x x x x x x x x x 4 x x 20
32 813 C x x x x x x x x x x x x 50 x x x x x 10 x 31 x x x x x x x x x x x x 12 x x x x x x x x x 10
34 864 C 10 x x x x x 10 x x x x x x x 10 x x x x x 25 x x x x x x x x x x x x x x x x x x x x x x 10
36 914 C x x x x x x x x x x x x 20 x 10 x x 10 x x 21 10 x x x x x x x x x x 9 x x x x x x x 3 x 3 20
38 965 C 10 x x x x x x x x x 10 x 20 x x x x x x x 15 x x x x x x x x x x x x x x x x x x x x x x 0
40 1016 C 5 x x x x x x x 5 x 5 x 30 x 5 x x x 5 20 19 x x x x x x x x x x x x x x x x x x x x x x 10
42 1067 C x x x x x x x x x x x x 10 x x x x x x x 14 x x x x x x x x x x x x x x x x x x x x x x 0
44 1118 C 5 x x x x x x x x 5 x x 10 x x x x x x 9 x x x x x x x x x x x x x x x x x x x x x 5 x 0
46 1168 C x x x x x x x x x x x x 10 x x x x x x x 6 x x x x x x x x x x x x x x x x x x x x x x 0
48 1219 C x 17 30 20 x x x x x x x x x x x 30 x x x x x x x x x x x x x x x x 16 x x x x x x x x x x 20

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 » 05 nov 2021, 12:08

'Kan je ook een indruk geven van de 6 tabellen en dan met name het aantal maten per tabel en grootte-orde van die maten.'

Hallo Arie,
Ik denk bij nader inzien en door de extra informatie dat je alleen van de A profielen vooraf een zaagtabel kan maken, omdat de aantallen groter zijn en het aantal maten vrij constant.
De andere orders (B en C) gaan we maar gewoon als 'reeks' in de machine invoeren per order. Het zou mooi zijn als we een tool hebben voor het optimaliseren van de reeks. Maar soms is er nauwelijks sprake van een reeks door de grote variëteit en de veelal kleine order aantallen. Enfin, kijk maar even wat je ervan vind.

De ordertabellen kon ik niet als Excel in bijlage toevoegen. Het forum stond me dat niet toe. Ik heb ze daarom hier in tekst geplakt, vanuit Excel, waarbij ik alle lege cellen van een 'x' heb voorzien om te voorkomen dat alle lege cellen wegvallen en daardoor de kolommen niet meer kloppen. Je kunt dit in Excel wel weer oppoetsen denk ik.
Ik hoop dat je er wat mee kan..

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Hoe vind je de beste zaagstrategie?

Bericht door arie » 09 nov 2021, 08:57

Je tabellen hierboven zijn niet helemaal goed doorgekomen (mogelijk problemen met lege cellen of lijnaanduiding).
Ik ga daarom eerst uit van onderstaande order-tabel (jouw eerste tabel, getransponeerd).
De bovenste regel geeft alle mogelijke bestelbare latlengtes (de catalogus),
elke regel daaronder is een order = bestelling.
Ik heb ter info (niet noodzakelijk) nog toegevoegd:
- kolom Q = aantal lattypen in de bestelling (Excel: =COUNTIF(A2:O2;">0"))
- REGEL 13 = de sommatie van alle bestelde latten van dat type:

Afbeelding


Hier een C-programma (nog een heel ruwe vorm) dat op zoek gaat naar de optimale verzagingsstrategie:

Code: Selecteer alles

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

const int maxCatlengte=50;          // maximaal aantal leverbare latlengtes
const int maxVerzagingen=100000;    // maximaal aantal verzagingsmogelijkheden van een magazijnlat
const int maxLatlengtes=20;         // maximaal aantal latten in een (deel-)bestelling
const int maxRestCount=2000;        // maximale onbruikbare restgrootte per magazijnlat

const double delta = 0.00000001;    // tbv afhandeling afrondingsfouten

// lat- en zaagmachinegegevens:
int zaagbladdikte;
int magazijnlatlengte;
int CATnLatlengtes;                 // aantal leverbare catalogus latlengtes
int CATlatlengtes[maxCatlengte];    // leverbare latlengtes (volgens catalogus)
int restcount[maxRestCount];        // verzagingsstatistiek

// ordergegevens:
int CATaantal[maxCatlengte];        // order
int CATcontrol[maxCatlengte];       // controle randvoorwaarden
int maxrestmateriaal;               // max onbruikbaar restmateriaal per magazijnlat
bool eliminatie;                    // true <=> elimineer 1 of meer ordercomponenten

// rekenlengtes van latten in de huidige order (= gereduceerde CAT versie):
// NB: gecomprimeerde tabellen: alleen de gegevens van de nu gewenste maten:
int nLatlengtes;                   	// aantal bestelde latlengtes + zaagbladdikte
int latlengtes[maxLatlengtes];     	// bestelde latlengtes + zaagbladdikte
int lataantal[maxLatlengtes];      	// aantal benodigde latten
int ctrl[maxLatlengtes];	        // controle randvoorwaarden

// verzagingstabellen voor huidige order:
int verzagingen[maxVerzagingen][maxLatlengtes+1];
int nverzagingen;

// oplossing gerelateerd:
double M[maxLatlengtes][maxLatlengtes];
int dimM;
int colPosM[maxLatlengtes];        	// posities bestelde + toegestane latlengtes
int vLines[maxLatlengtes];         	// positie van de huidige combinatie
                                        // van lijnen in de verzagingstabel
int minLines[maxLatlengtes];       	// de lijnencombinatie van de minimale oplossing
double solM[maxLatlengtes];        	// oplossing stelsel
int solup[maxLatlengtes];          	// naar boven afgeronde oplossing
int minsolup[maxLatlengtes];       	// minimale oplossing (tot nu toe)
int minscore=999999999;            	// minimale score (tot nu toe)

int solutioncount=0;               	// teller van aantal gevonden oplossingen
int minrestfound;                       // minimum restmateriaal (tot nu) gevonden



//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//
// LAT- EN ORDERGEGEVENS:
//   - invoer
//   - print op scherm
//
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

// haal de catalogus latlengtes op:
void loadverzagingmaten(void)
{
FILE *fi=fopen("verzagingmaten.txt","rt");
int i;

fscanf(fi,"%d",&zaagbladdikte);
fscanf(fi,"%d",&magazijnlatlengte);
magazijnlatlengte+=zaagbladdikte;    // rekenlengte magazijnlat
fscanf(fi,"%d",&CATnLatlengtes);
for(i=0;i<CATnLatlengtes;i++)
  fscanf(fi,"%d",&CATlatlengtes[i]);
fclose(fi);
}

void printverzagingmaten(void)
{
printf("\n");
printf("verzagingmaten:\n");
printf("zaagbladdikte = %d\n", zaagbladdikte);
printf("rekenlengte magazijnlat = %d\n",magazijnlatlengte);
printf("catalogus latmaten:\n\t");
for(int i=0;i<CATnLatlengtes;i++)
  printf("%d\t",CATlatlengtes[i]);
printf("\n");
}

// haal de order gegevens op:
void loadorder(void)
{
FILE *fi=fopen("order.txt","rt");
int i;

eliminatie=false;
for(i=0;i<CATnLatlengtes;i++)
  fscanf(fi,"%d",&CATaantal[i]);
for(int i=0;i<CATnLatlengtes;i++){
  fscanf(fi,"%d",&CATcontrol[i]);
  if(CATcontrol[i]<0) // als dit een negatieve controleparameter is:
	eliminatie=true;  // dan moet deze kolom ge-elimineerd worden
  }
fscanf(fi,"%d",&maxrestmateriaal);
fclose(fi);

// comprimeer order: beperk tot
//   - bestelde latlengtes
//   - eventueel toegestane latlengtes
nLatlengtes=0;
for(i=0;i<CATnLatlengtes;i++){
  if(CATaantal[i]>0 || CATcontrol[i]!=0){
	latlengtes[nLatlengtes]=CATlatlengtes[i]+zaagbladdikte;  // gebruik rekenlengtes
	lataantal[nLatlengtes]=CATaantal[i];
  	ctrl[nLatlengtes]=CATcontrol[i];
	++nLatlengtes;
	}
  }
}

void printorder(void)
{
int i;

printf("\nordergegevens:\n");
printf("order:\t");
for(i=0; i<CATnLatlengtes; i++)
  printf("%d\t",CATaantal[i]);
printf("\nctrl:\t");
for(i=0; i<CATnLatlengtes; i++)
  printf("%d\t",CATcontrol[i]);
printf("\n");
printf("max restmateriaal per magazijnlat = %d\n\n",maxrestmateriaal);

printf("relevante deel van de order:\n");
printf("lengte: \t");
for(i=0; i<nLatlengtes; i++)
  printf("%d\t",latlengtes[i]-zaagbladdikte);
printf("\n");
printf("aantal: \t");
for(i=0; i<nLatlengtes; i++)
  printf("%d\t",lataantal[i]);
printf("\n");
printf("ctrl:   \t");
for(i=0; i<nLatlengtes; i++)
  printf("%d\t",ctrl[i]);
printf("\n\n");
}


//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//
//	 VERZAGINGSTABELLEN
//     - genereer verzagkngstabel en frequentietabel afval (= restcount)
//     - sorteer de verzagingstabel naar hoeveelheid restmateriaal per magazijnlat
//     - schrijf de tabellen naar een bestand
//
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// GENEREER EN SORTEER DE VOLLEDIGE TABEL VAN VERZAGINGEN:
//---------------------------------------------------------------------------

// registratie van de huidige recursieve verzaging:
int currentselection[maxLatlengtes];

// recursieve tabelvulling:
// - lengte = tot nu nog beschikbare latlengte
// - latindex = index van het lattype: (nLatlengtes-1)  t/m  0
void vulverzagingtabel(int lengte, int latindex)
{
int i,imax, rest;

if(latindex==0){
  currentselection[0]=lengte/latlengtes[0];
  if(nverzagingen<maxVerzagingen){  // als er nog ruimte is in de tabel:
	rest=lengte%latlengtes[0];
	if(rest<=maxrestmateriaal){
	  for(i=0; i<nLatlengtes; i++)
		verzagingen[nverzagingen][i]=currentselection[i];
	  verzagingen[nverzagingen][nLatlengtes]=rest; // eenheden restmateriaal
	  ++restcount[rest];
	  nverzagingen++;
	  }
	}
  }
else{
  imax=lengte/latlengtes[latindex];
  for(i=0; i<=imax; i++){
	currentselection[latindex]=i;
	vulverzagingtabel(lengte-i*latlengtes[latindex], latindex-1);
	}
  }
}

// schrijf de frequentietabel van de hoeveelheid zaagafval
void writerestcount(void)
{
int i,totaal;
FILE *fo=fopen("restcount.txt","wt");

totaal=0;
fprintf(fo,"afval\taantal\tcumulatief\n");
for(int i=0; i<=maxrestmateriaal; i++){
  totaal += restcount[i];
  fprintf(fo,"%d\t%d\t%d\n",i,restcount[i],totaal);
  }
fclose(fo);
}

// genereer alle mogelijke verzagingen van magazijnlatten in latlengtes
// van de order:
bool genereerverzagingen(void)
{
memset(restcount,0,sizeof(restcount));
nverzagingen=0;
vulverzagingtabel(magazijnlatlengte, nLatlengtes-1);
printf("totaal aantal mogelijke verzagingen = %d\n", nverzagingen);
writerestcount();
if(nverzagingen > maxVerzagingen){
  printf("tabelruimte te klein...");
  return(false);
  }
return(true);
}

// sorteer de verzagingen op oplopende hoeveelheid restafval:
void sorteerverzagingen(void)
{
int i,j,k, idx, tmp;

idx=0;
for(i=0;i<maxrestmateriaal;i++){
  for(j=idx;j<nverzagingen;j++){
	if(verzagingen[j][nLatlengtes]==i){
	  if(j!=idx){ // swap line j and line idx:
		for(k=0;k<=nLatlengtes;k++){
		  tmp=verzagingen[idx][k];
		  verzagingen[idx][k]=verzagingen[j][k];
		  verzagingen[j][k]=tmp;
		  }
		}
	  idx++;
	  }
	}
  }
}


// schrijf de volledige verzagingstabel naar een tekstbestand:
// - de eerste nLatlengtes kolommen de aantallen geproduceerde latten van elk type
// - dan de kolom met hoeveelheid onbruikbaar restmateriaal
void writeverzagingentabel(void)
{
FILE *fo = fopen("magazijnlatverzagingen.txt","wt");
int i,j;

// print header:
for(j=0;j<nLatlengtes;j++)
  fprintf(fo,"%d\t",latlengtes[j]-zaagbladdikte);
fprintf(fo,"rest\n");
// print verzagingen:
for(i=0;i<nverzagingen;i++){
  for(j=0;j<nLatlengtes;j++)
	fprintf(fo,"%d\t",verzagingen[i][j]);
  fprintf(fo,"%d\n",verzagingen[i][nLatlengtes]);
  }
fclose(fo);
}

// schrijf de eliminatietabel naar een tekstbestand = de verzagingen waarin
// de te elimineren latlengte voorkomt
// - de eerste nLatlengtes kolommen de aantallen geproduceerde latten van elk type
// - dan de kolom met hoeveelheid onbruikbaar restmateriaal
int writeeliminatietabel(void)
{
FILE *fo = fopen("eliminatieverzagingen.txt","wt");
int i,j;
bool ok;
int aantal=0;

// print header:
for(j=0;j<nLatlengtes;j++)
  fprintf(fo,"%d\t",latlengtes[j]-zaagbladdikte);
fprintf(fo,"rest\n");

// print verzagingen:
for(i=0;i<nverzagingen;i++){
  // kijk of deze verzaging bruikbaar is voor eliminatie:
  ok=true;
  for(j=0;j<nLatlengtes && ok; j++)
	if(ctrl[j]<0 && verzagingen[i][j]==0)
	  ok=false;
  // voeg verzaging toe indien deze bruikbaar is:
  if(ok){
	aantal++;
	for(j=0;j<nLatlengtes;j++)
	  fprintf(fo,"%d\t",verzagingen[i][j]);
	fprintf(fo,"%d\n",verzagingen[i][nLatlengtes]);
	}
  }
fclose(fo);
return(aantal);
}


//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//
//  OUTPUT OPLOSSINGEN:
//
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
//  HULPFUNCTIES:
//---------------------------------------------------------------------------

// bereken hoeveelheid restmateriaal (= afval) van een gegeven oplossing:
int calcrest(void)
{
int rest=0;

for(int i=0;i<dimM;i++)
  rest+=solup[i]*verzagingen[vLines[i]][nLatlengtes];
return(rest);
}

//---------------------------------------------------------------------------

// print een lijn:
void printLine()
{
for(int i=0;i<80;i++)
  printf("-");
printf("\n");
}

//---------------------------------------------------------------------------
//  SCREEN OUTPUT SOLUTIONS:
//---------------------------------------------------------------------------

// print de (huidige) oplossing:
void printsolution(void)
{
int i,j;
int result[maxLatlengtes];
int score;
int rest;

printLine();
printf("aantal oplossingen = %d\n",solutioncount);
score=0;
for(i=0;i<dimM;i++)
  score+=solup[i];
printf("score = %d:\n\n",score);
for(i=0;i<dimM;i++){
  if(solup[i]>0){
	printf("  %4d x [%d",solup[i],verzagingen[vLines[i]][0]);
	for(j=1;j<nLatlengtes;j++)
	  printf(", %d", verzagingen[vLines[i]][j]);
	printf("]\t= %4d x line %d\n",solup[i],vLines[i]+2); //+2 for Excel table
	}
  }

memset(result,0,sizeof(result));
for(i=0;i<dimM;i++){
  for(j=0;j<nLatlengtes;j++){
	result[j]+=(int)(verzagingen[vLines[i]][j]*(double)solup[i]+0.5);
	}
  }

printf("\n");
printf("latlengte:");
for(j=0;j<nLatlengtes;j++) printf("%8d",latlengtes[j]-zaagbladdikte);
printf("\n");
printf("productie:");
for(j=0;j<nLatlengtes;j++) printf("%8d",result[j]);
printf("\n");
printf("order:    ");
for(j=0;j<nLatlengtes;j++) printf("%8d",lataantal[j]);
printf("\n");
printf("overschot:");
for(j=0;j<nLatlengtes;j++) printf("%8d",result[j]-lataantal[j]);
printf("\n\n");

int orderlengte=0;
for(i=0;i<nLatlengtes;i++){
  orderlengte+=(lataantal[i]*latlengtes[i]);
  }
printf("totale orderlengte = %d = %.4lf magazijnlatten\n", orderlengte, (double)orderlengte/(double)magazijnlatlengte);
printf("benodigde lengte   = %d = %d magazijnlatten\n", score*magazijnlatlengte, score);
printf("benodigd / totaal  = %.4lf\n", (double)(score*magazijnlatlengte)/(double)orderlengte);

rest=calcrest();
printf("onbruikbare rest = %d = %.2lf\% van het gebruikte materiaal\n",rest, 100.0*(double)rest/((double)score*(double)magazijnlatlengte));
printf("huidige min rest = %d\n", minrestfound);

printf("\nmax rest = %d\n", maxrestmateriaal);
printf("aantal verzagingen = %d\n",nverzagingen);

printLine();
}


//---------------------------------------------------------------------------
//    FILE OUTPUT SOLUTIONS:
//---------------------------------------------------------------------------

// schrijf huidige oplossing naar file:
void writeminsolution(double tijd)
{
int i,j;
int result[maxLatlengtes];
int score;
int rest;
char filename[64];

sprintf(filename,"minsolutionminrest%03d.txt",maxrestmateriaal);
FILE *fo=fopen(filename,"wt");

fprintf(fo,"magazijnlatlengte = %d\n", magazijnlatlengte - zaagbladdikte);
fprintf(fo,"zaagbladdikte = %d\n", zaagbladdikte);
fprintf(fo,"max rest = %d\n", maxrestmateriaal);
fprintf(fo,"keuze uit %d mogelijke magazijnlatverzagingen\n\n",nverzagingen);

score=0;
for(i=0;i<dimM;i++)
  score+=solup[i];

fprintf(fo,"Verzagingsschema:\n");
for(i=0;i<dimM;i++){
  if(solup[i]>0){
	fprintf(fo,"  %4d x [%d",solup[i],verzagingen[vLines[i]][0]);
	for(j=1;j<nLatlengtes;j++)
	  fprintf(fo,", %d", verzagingen[vLines[i]][j]);
	fprintf(fo,"]\t= %4d x line %d\n",solup[i],vLines[i]+2); //+2 for Excel table
	}
  }

memset(result,0,sizeof(result));
for(i=0;i<dimM;i++){
  for(j=0;j<nLatlengtes;j++){
	result[j]+=(int)(verzagingen[vLines[i]][j]*(double)solup[i]+0.5);
	}
  }

fprintf(fo,"\n");
fprintf(fo,"latlengte:");
for(j=0;j<nLatlengtes;j++) fprintf(fo,"%8d",latlengtes[j]-zaagbladdikte);
fprintf(fo,"\n");
fprintf(fo,"productie:");
for(j=0;j<nLatlengtes;j++) fprintf(fo,"%8d",result[j]);
fprintf(fo,"\n");
fprintf(fo,"order:    ");
for(j=0;j<nLatlengtes;j++) fprintf(fo,"%8d",lataantal[j]);
fprintf(fo,"\n");
fprintf(fo,"overschot:");
for(j=0;j<nLatlengtes;j++) fprintf(fo,"%8d",result[j]-lataantal[j]);
fprintf(fo,"\n\n");

int orderlengte=0;
for(i=0;i<nLatlengtes;i++){
  orderlengte+=(lataantal[i]*latlengtes[i]);
  }
fprintf(fo,"totale orderlengte = %d = %.4lf magazijnlatten\n", orderlengte, (double)orderlengte/(double)magazijnlatlengte);
fprintf(fo,"benodigde lengte   = %d = %d magazijnlatten\n", score*magazijnlatlengte, score);
fprintf(fo,"benodigd / totaal  = %.4lf\n", (double)(score*magazijnlatlengte)/(double)orderlengte);

rest=calcrest();
fprintf(fo,"onbruikbare rest = %d = %.2lf\% van het gebruikte materiaal\n",rest, 100.0*(double)rest/((double)score*(double)magazijnlatlengte));
fprintf(fo,"huidige min rest = %d\n\n", minrestfound);

if(tijd>delta)
  fprintf(fo,"timer: %.6lf sec\n",tijd);

fclose(fo);
}

//---------------------------------------------------------------------------

// write final found minimal solution info:
void writefinal(double tijd)
{
int i;

// load minimal solution values:
for(i=0;i<dimM;i++){
  solup[i]=minsolup[i];
  vLines[i]=minLines[i];
  }
writeminsolution(tijd);
}

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//
//    SEARCH SOLUTION:
//
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

// bewaar de gevonden = minimale oplossing
void saveminsolution(void)
{
for(int i=0;i<dimM;i++){   // store minimal score parameters
  minsolup[i]=solup[i];
  minLines[i]=vLines[i];
  }
}

// bepaal de score van de huidige oplossing
// en kijk of dit een nieuw minimum is:
void evaluateSolution(void)
{
int i,j;
int score;
int rest;

// bepaal de huidige score (= aantal benodigde magazijnlatten)
score=0;
for(i=0;i<dimM;i++){
  if(solM[i]>delta){
	solup[i]=(int)ceil(solM[i]-delta);
	score+=solup[i];
	}
  else // stel niet-positieve verzagingen gelijk aan nul:
	solup[i]=0;
  }

// als de score beter of gelijk is aan de huidig beste score:
if(score<=minscore){
  // als de huidige score beter is: dan wordt dit de beste score
  if(score<minscore){
	minscore=score;         	// update minimal score
	solutioncount=1;			// begin met tellen voor deze score
	minrestfound=calcrest();	// bepaal hoeveelheid afval
	writeminsolution(0);
	saveminsolution();
	}
  // als de huidige score gelijk is aan de beste score:
  else{
	solutioncount++;			// weer een oplossing met deze score gevonden
	rest=calcrest();			// bepaal hoeveelheid afval
	if(rest<minrestfound){		// indien deze minder is dan eerder gezien:
	  minrestfound=rest;
	  writeminsolution(0);
	  saveminsolution();        // dan wordt dit de tot nu toe optimale oplossing
	  }
	}
  printsolution();
  }
}

//---------------------------------------------------------------------------
// los een stelsel op via Gauss-eliminatie:
//   M[][] * x[] = solM[]
// OUTPUT:
//   ok==1: oplossing zit in solM[]
//   ok==0: het stelsel heeft geen unieke oplossing
int solveMatrix(void)
{
int i,j,k, line;
int ok=1;
double tmp, q;

// load initial solution vector:
for(i=0;i<dimM;i++)
  solM[i]=(double)lataantal[i];

// load matrix:
for(i=0;i<dimM;i++)
  for(j=0;j<dimM;j++)
	M[i][j]=(double)verzagingen[vLines[j]][i];

// Gaussian elimination:
for(line=0;line<dimM && ok==1;line++){
  i=line;
  while(fabs(M[i][line])<delta && i<dimM)
	i++;
  if(i==dimM) // all values zero
	ok=0;
  else if(i>line){ // swap lines i and line
	for(j=0; j<dimM; j++){
	  tmp=M[i][j]; M[i][j]=M[line][j]; M[line][j]=tmp;
	  }
	tmp=solM[i]; solM[i]=solM[line]; solM[line]=tmp;
	}

  if(ok==1){ // then M[line][line] != 0:
	q=M[line][line];
	if(q!=1.0){ // normalize to M[line][line]=1:
	  for(j=line; j<dimM; j++)
		M[line][j]/=q;
	  solM[line]/=q;
	  }

	for(i=line+1; i<dimM; i++){ // sweep forward:
	  if(fabs(M[i][line])>delta){ // if M[i][line] != 0
		q=M[i][line];
		for(int k=line; k<dimM; k++)
		  M[i][k]-=(q*M[line][k]);
		solM[i]-=(q*solM[line]);
		}
	  }
	}
  }

if(ok==1){ // sweep backward:
  for(line=dimM-1; line>0; line--){
	for(i=0;i<line;i++){
	  solM[i]-=(M[i][line]*solM[line]);
	  M[i][line]=0.0;
	  }
	}
  }

return(ok);
}

//---------------------------------------------------------------------------

// doorloop (recursief) alle verzagingscombinaties, en indien
//   een combinatie een oplossing is voor de order: evalueer deze oplossing
void visitCombinations(int d, int end)
{
if(d==0){ // next combination has been found:
  if(solveMatrix()==1) // if the matrix is invertible:
	evaluateSolution();
  }
else{
  for(int i=d-1; i<end; i++){
	vLines[d-1]=i;
	visitCombinations(d-1, i);
	}
  }
}

//---------------------------------------------------------------------------

// start het zoeken over alle mogelijke combinaties Comb(nverzagingen, dimM) :
void search(void)
{
int i;

dimM=nLatlengtes;
printf("\nMatrix dimensies: %d x %d\n\n", dimM, dimM);
printLine();

visitCombinations(dimM, nverzagingen);
}


//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//
//   MAIN PROGRAM:
//
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

int main(int argc, char* argv[])
{
clock_t t;
t = clock();
double tijd;
int aantal;

loadverzagingmaten();
printverzagingmaten();
loadorder();
printorder();

// initialize zoekvariabelen:
minscore=999999999;            	// minimale score tot nu toe = 'oneindig'
solutioncount=0;               	// teller van aantal gevonden oplossingen
if(genereerverzagingen()){
  sorteerverzagingen();
  writeverzagingentabel();
  if(eliminatie){  // handmatige eliminatie van 1 of meer bestelde latwaarden:
	aantal=writeeliminatietabel();
	printf("waarvan bruikbaar voor eliminatie: %d\n",aantal);
	printf("\nelimineer een waarde...\n\n");
	}
  else  // zoek de oplossing voor deze order:
	search();
  }

if(solutioncount==0 && !eliminatie)
  printf("\nGeen oplossingen gevonden...\n");

t=clock()-t;
tijd=((double)t)/(double)CLOCKS_PER_SEC;
if(!eliminatie)
  writefinal(tijd);  // output van de eindoplossing
printf("TIMER: %.6lf sec\n",tijd);

return 0;
}


INVOER:
De invoer bestaat uit 2 tekstbestanden met heel strikte naam en regels:

[1] verzagingmaten.txt
regel 1: zaagbladdikte
regel 2: magazijnlatlengte
regel 3: aantal latmaten in de catalogus
regel 4: alle latmaten van de catalogus
regel 5 en verder: geen restricties, vrij te gebruiken (bv. met de gegevens van andere catalogi)

[2] order.txt
regel 1: bestelling = order = gewenste aantal per latlengte uit de catalogus
regel 2: extra controlemogelijkheid per latlengte, doorgaans elke waarde op 0 (= nul)
regel 3: maximaal aantal mm restmateriaal (= afval) per verzaagde magazijnlat
regel 4 en verder: geen restricties, vrij te gebruiken (bv. met de gegevens van andere orders uit de tabel)


Voorbeeld:
Voor de eerste order van bovenstaande tabel:

verzagingsmaten.txt:

Code: Selecteer alles

2
1800
15
75	95	120	135	147	155	176	196	246	311	351	396	446	496	626
order.txt:

Code: Selecteer alles

0	0	500	0	0	200	0	200	200	100	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
10

UITVOER:

minsolutionminrestNNN.txt
De gevonden oplossing (voor de ingevoerde maximaal NNN mm restafval)

magazijnlatverzagingen.txt
Alle mogelijke verzagingen van de magazijnlatten naar latlengtes uit de order, en met hooguit de gegeven grenswaarde restafval

restcount.txt
Frequentieverdeling van hoeveelheid restafval per verzaging


Voorbeeld:

minsolutionminrest010.txt

Code: Selecteer alles

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

Verzagingsschema:
    21 x [8, 4, 1, 0, 0]	=   21 x line 2
    27 x [3, 0, 6, 1, 0]	=   27 x line 3
    50 x [3, 2, 0, 2, 2]	=   50 x line 5
    18 x [5, 0, 1, 4, 0]	=   18 x line 11
     3 x [5, 6, 0, 1, 0]	=    3 x line 12

latlengte:     120     155     196     246     311
productie:     504     202     201     202     100
order:         500     200     200     200     100
overschot:       4       2       1       2       0

totale orderlengte = 212900 = 118.1465 magazijnlatten
benodigde lengte   = 214438 = 119 magazijnlatten
benodigd / totaal  = 1.0072
onbruikbare rest = 42 = 0.02% van het gebruikte materiaal
huidige min rest = 42

timer: 2.047000 sec
magazijnlatverzagingen.txt

Code: Selecteer alles

120	155	196	246	311	rest
8	4	1	0	0	0
3	0	6	1	0	0
0	2	0	6	0	0
3	2	0	2	2	0
4	3	3	1	0	1
8	2	1	0	1	1
0	0	0	6	1	1
3	0	0	2	3	1
0	2	5	2	0	2
5	0	1	4	0	2
5	6	0	1	0	2
4	1	3	1	1	2
8	0	1	0	2	2
5	4	0	1	1	3
0	0	5	2	1	3
1	5	2	2	0	3
2	2	0	5	0	4
1	3	2	2	1	4
5	2	0	1	2	4
5	0	6	0	0	4
2	0	0	5	1	5
1	1	2	2	2	5
5	0	0	1	3	5
6	3	3	0	0	5
7	6	0	0	0	6
7	0	1	3	0	6
6	1	3	0	1	6
2	2	5	1	0	6
7	4	0	0	1	7
3	5	2	1	0	7
2	0	5	1	1	7
3	3	2	1	1	8
7	2	0	0	2	8
4	2	0	4	0	8
0	7	1	2	0	9
0	1	2	5	0	9
3	1	2	1	2	9
7	0	0	0	3	9
4	0	0	4	1	9
4	2	5	0	0	10
9	0	1	2	0	10
0	5	1	2	1	10
restcount.txt

Code: Selecteer alles

afval	aantal	cumulatief
0	4	4
1	4	8
2	5	13
3	3	16
4	4	20
5	4	24
6	4	28
7	3	31
8	3	34
9	5	39
10	3	42

Tot gevallen als bovenstaande (tot 5 bestelde lattypen met zo'n 40 a 50 verzagingen) werkt het programma redelijk snel (secondenwerk), daarboven wordt het verstandig de order te splitsen.
Ik kom later vandaag nog terug op de rekentijden, de bijzondere gevallen en de controlemogelijkheden.

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 » 09 nov 2021, 09:43

Wat een prachtig resultaat!
Ik denk dat ik de machine naar je ga vernoemen, Arie. ;-)
Jammer dat de andere tabellen niet goed zijn gekomen, ik bedacht me ineens (te laat) dat ik de tabel natuurlijk ook had kunnen uploaden in wetransfer ofzo en dan de download link delen.
Dus mocht je dat nog nodig hebben voor een test, die staat hier: haa tee tee pee es://we.tl/t-kBTUDVOVpV

Plaats reactie