Tâche
Coupe optimale du matériau linéaire, minimisant la longueur des chutes. Comme données initiales, utilisez la longueur de la pièce, la largeur de la coupe et la liste des pièces à fabriquer, en indiquant la taille et la quantité linéaires. Dans le calcul, utilisez les flans disponibles de différentes longueurs, qui sont également présentés dans une liste indiquant leur longueur et leur quantité.
Solution
La tâche est classique, par conséquent, vous pouvez trouver de nombreuses discussions détaillées sur le Web sur la façon de la résoudre correctement en utilisant diverses méthodes mathématiques, y compris en utilisant MS Excel. Il existe également de nombreuses ressources en ligne avec des calculatrices en ligne, payantes et gratuites. Néanmoins, j’ai décidé de proposer ma propre version de l’implémentation du calcul en utilisant la plateforme My Visual Database (MVDB) comme outil de création du programme correspondant. À l’avenir, je prévois d’utiliser la méthode considérée dans le cadre du programme “Production”, en la combinant avec le système de comptabilité d’entrepôt.
Pour déterminer la disposition optimale des pièces (cartes de coupe), un algorithme d’énumération complet est utilisé, complété par des conditions d’optimisation : coupure des options d’énumération avec un résultat volontairement médiocre et sortie précoce lorsqu’une option idéale est obtenue (zéro résidu de coupe). Autrement dit, dans la boucle, toutes les options possibles pour la disposition des pièces sont triées jusqu’à ce que la meilleure option avec la valeur de coupure minimale soit trouvée ou que les conditions d’optimisation soient déclenchées.
Ensuite, il est déterminé combien de fois la carte de coupe résultante peut être utilisée pour produire le nombre requis de pièces. Ensuite, la carte est ajoutée à la liste résultante.
Dans le cas où nous avons plusieurs flans de longueurs différentes, une stratégie de “garder le stock liquide” est utilisée, c’est-à-dire que les flans courts passent d’abord sous le couteau, car les longues garnitures sont plus susceptibles d’être utilisées dans la commande suivante, et les petites les garnitures vont généralement à la malbouffe. D’un point de vue mathématique, cette approche ne garantit pas un pourcentage minimum de pertes lors du sciage, mais elle assure la minimisation des achats de matières pour la commande en cours et l’utilisation maximale des stocks disponibles.
Mise en œuvre
Pour stocker les données initiales et le résultat, plusieurs tables de base de données sont utilisées, et pour énumérer les options, les données sont chargées dans la RAM. Malheureusement, MVDB ne prend pas en charge les structures (Record), donc des tableaux dynamiques sont utilisés pour stocker des données – un tableau séparé pour chaque valeur (lors de l’implémentation de cet algorithme dans d’autres langages, ce sera un peu plus élégant).
Une fois que les tableaux sont initialisés et que les données y sont chargées à partir des tables de la base de données, deux boucles repeat..until sont organisées. Externe – pour trier les blancs, interne – pour sélectionner les options de mise en page. Les vérifications suivantes ont été utilisées comme optimisation dans la boucle interne :
- si la longueur d’assiette est nulle, alors une variante idéale est obtenue ; sortie anticipée du cycle
- si la longueur de coupe est négative, vous devez passer à l’énumération des pièces plus petites
Cependant, des paroles aux actes : ci-dessous se trouve un script avec des commentaires détaillés qui implémente cet algorithme.
Scénario
procedure frmCuttingMap_btnCalc_OnClick (Sender: TObject; var Cancel: boolean);
// effectuer un calcul
var
tmpSQL: string; // pour stocker le texte de la requête, pratique pour le débogage
tmpQty: integer; // nombre de détails
tmpDetLen: array of integer; // liste des longueurs de pièces
tmpDetQty: array of integer; // liste des quantités de pièces
tmpBQty: integer; // nombre de blancs
tmpBIndex: integer; // l'index de la pièce avec laquelle l'algorithme travaille actuellement
tmpBlankLen: array of integer; // liste des longueurs de pièces
tmpBlankQty: array of integer; // liste des blancs disponibles
tmpMap: string; // schéma de découpage
tmpMapQty: integer; // nombre d'utilisations du schéma de découpage
tmpTestQty: array of integer; // liste du nombre de pièces pour la variante actuelle
tmpBestQty: array of integer; // meilleure coupe
tmpBestBlankLen: integer; // la longueur actuelle du blanc à écrire
tmpTestBlankLen: integer; // longueur de la pièce actuelle pour le calcul
tmpTestScrap: integer; // bilan matériel actuel
tmpTestLen: integer; // longueur actuelle
tmpBestScrap: integer; // meilleur ferraille
tmpLastIncPos: integer; // le dernier position qui a été augmenté
tmpIncPos: integer;// le position que l'on augmente dans la boucle principale
tmpDataSet: TDataSet;
i,j: integer;
tmpFlag: boolean;
s: string;
// modificateur de schéma de découpage
function NextIndex( APos: integer ):boolean;
begin
if APos >= tmpQty then
begin
Result := False;
end
else
begin
Result := True;
tmpTestQty[APos] := tmpTestQty[APos] + 1;
tmpLastIncPos := APos;
if tmpTestQty[APos] > tmpDetQty[APos] then
begin
tmpTestQty[APos] := 0;
Result := NextIndex( APos + 1);
end;
end;
end;
//
begin
Progress(0,0,'A la recherche d'une solution...',True);
try
// enregistrer les paramètres de largeur de coupe
CutWidth := Trunc( frmCuttingMap.edtCutWidth.Value );
IniFile_Write_Int(APP_PARAMS,'CutWidth',CutWidth);
// initialisation
SQLExecute('DELETE FROM cuttingMap'); // tableau de résultat clair
//
tmpBQty := SQLExecute('SELECT count(*) FROM blank '); // nombre de blancs
SetLength( tmpBlankLen, tmpBQty); // liste des longueurs de blancs
SetLength( tmpBlankQty, tmpBQty); // liste des blancs
// les données doivent être triées par ordre croissant pour s'assurer que la stratégie consiste à utiliser les raccourcis en premier
SQLQuery('SELECT * FROM blank ORDER BY length ASC',tmpDataSet);
try
for i := 0 to tmpBQty-1 do
begin
tmpBlankLen[i] := tmpDataSet.FieldByName('length').asInteger;
if tmpDataSet.FieldByName('basic').asInteger = 1 then
tmpBlankQty[i] := MAX_QTY
else
tmpBlankQty[i] := tmpDataSet.FieldByName('qty').asInteger;
tmpDataSet.next;
end;
finally
tmpDataSet.Free;
end;
tmpQty := SQLExecute('SELECT count(*) FROM piece ');
SetLength( tmpDetLen, tmpQty);
SetLength( tmpDetQty, tmpQty);
// commencer par la première taille de la blanc
tmpBIndex := 0;
SetLength( tmpTestQty, tmpQty); // liste du nombre de pièces pour la variante actuelle
SetLength( tmpBestQty, tmpQty);
// les données doivent être triées par ordre décroissant !
SQLQuery('SELECT * FROM piece ORDER BY length DESC',tmpDataSet);
try
for i := 0 to tmpQty-1 do
begin
tmpDetLen[i] := tmpDataSet.FieldByName('length').asInteger;
tmpDetQty[i] := tmpDataSet.FieldByName('qty').asInteger;
tmpDataSet.next;
end;
finally
tmpDataSet.Free;
end;
//
repeat
tmpTestBlankLen := tmpBlankLen[tmpBIndex];
tmpBestScrap := tmpTestBlankLen;
// réinitialiser le schéma de découpage
for i:=0 to tmpQty-1 do
tmpTestQty[i] := 0;
//
tmpIncPos := 0;
repeat
Application.ProcessMessages;
// résiliation anticipée
if ProgressCancel then
exit;
if not NextIndex( tmpIncPos ) then // modification de la matrice de découpage
break // en cas d'échec, sortir de la boucle
else
begin
// regarde ce qu'on a en longueur
tmpTestLen := 0;
tmpFlag := False;
for i :=0 to tmpQty - 1 do
begin
tmpTestLen := tmpTestLen + (tmpDetLen[i] + CutWidth)* tmpTestQty[i]; // alors vous devez considérer que la dernière coupe peut ne pas être nécessaire ...
if tmpTestLen > tmpTestBlankLen then // si la longueur dépasse la longueur de la pièce, vous ne pouvez plus compter - une mauvaise option
begin
tmpFlag := True;
break;
end;
end;
// s'il y a eu un débordement, passez à l'option suivante
if tmpFlag then
begin
tmpTestQty[tmpLastIncPos] := 0; // réinitialiser le compteur dans le chiffre qui a été incrémenté en dernier
tmpIncPos := tmpLastIncPos + 1; // nous augmenterons le compteur du chiffre suivant, avec un coefficient de poids plus petit
continue;
end;
tmpTestScrap := tmpTestBlankLen - tmpTestLen;
//
if tmpTestScrap < tmpBestScrap then // si la meilleure option est trouvée
begin
tmpBestScrap := tmpTestScrap;
for i:=0 to tmpQty - 1 do // rappelez-vous l'option de coupe
tmpBestQty[i] := tmpTestQty[i];
end;
// option idéale - coupe zéro, ça ne s'améliore pas
if tmpBestScrap = 0 then
break;
// se préparer pour l'incrément de commande élevé
tmpIncPos := 0;
end;
until 1=0; // cycle de sélection ; sortir si la prochaine matrice ne peut pas être obtenue
//il peut y avoir un cas où la taille actuelle ne convient pas au calcul
if tmpBestScrap = tmpTestBlankLen then
begin // passer à la dimension suivante sans enregistrer le résultat
inc( tmpBIndex ); // aller à la pièce suivante
if tmpBIndex < tmpBQty then
begin
continue;
end
else
begin
break;
end;
end;
// dessiner une mise en page
tmpMap := '';
for i := 0 to tmpQty - 1 do
for j := 0 to tmpBestQty[i] - 1 do
begin
if tmpMap <> '' then
tmpMap := tmpMap + ': ';
tmpMap := tmpMap + IntToStr( tmpDetLen[ i ] );
end;
//
tmpMapQty := 0;
// compter combien de fois le schéma peut être utilisé
tmpBestBlankLen := tmpTestBlankLen;
repeat
inc(tmpMapQty);
// réduire les restes
for i := 0 to tmpQty - 1 do
tmpDetQty[i] := tmpDetQty[i] - tmpBestQty[i];
// réduire les restes
tmpBlankQty[tmpBIndex] := tmpBlankQty[tmpBIndex] - 1;
// nous devons maintenant déterminer s'il est possible d'utiliser à nouveau cette mise en page
tmpFlag := false;
// vérification des pièces
for i := 0 to tmpQty - 1 do
if tmpBestQty[i] > tmpDetQty[i] then
begin
tmpFlag := True;
break;
end;
// vérifier les restes
if tmpBlankQty[tmpBIndex] = 0 then
begin
tmpFlag := True;
inc( tmpBIndex );
end;
until tmpFlag;
// Si quelque chose a été trouvé, alors
if tmpBestScrap <> tmpTestBlankLen then
// enregistrer le résultat
SQLExecute('INSERT INTO cuttingMap (blankLength,qty,map,scrap) VALUES ('+IntToStr(tmpBestBlankLen)+','+IntToStr(tmpMapQty)+','+StrToSQL(tmpMap)+','+IntToStr(tmpBestScrap)+')');
// vérifier s'il reste quelque chose à faire
tmpFlag := false;
for i := 0 to tmpQty - 1 do
if tmpDetQty[i] > 0 then
begin
tmpFlag := True;
break;
end;
// vérifier s'il y a des blancs
if tmpBIndex = tmpBQty then
tmpFlag := False;
until not tmpFlag; // répéter jusqu'à ce qu'il y ait quelque chose à faire
// mettre à jour l'affichage des données
frmCuttingMap.tgrMap.dbUpdate;
finally
Progress();
end;
ShowMessage('Calcul terminé');
end;
Langage du code : Delphi (delphi)Les lignes 48 et 213 utilisent la procédure d’affichage d’une barre de progression, qui est détaillée dans l’article “Au nom du progrès”.
La ligne 66 utilise la constante MAX_QTY = 1000000 ; de sorte que pour les flans qui peuvent être achetés, il n’y a pas d’achèvement du cycle extérieur en raison d’un manque de leur quantité.
Structure de données
Interface
Les tables avec le mode d’édition de données activé sont utilisées pour modifier les données source (AllowCreate = True, AllowEdut = True, AllowDelete = True).
Les boutons de la barre d’outils sont destinés à la gestion des données :
- Effacer l’entrée
- Exécuter un calcul
- Générer un document
- Générer un PDF
La barre d’outils contient également un champ dans lequel vous pouvez spécifier la largeur de la coupe. Pour un cutter, la largeur peut être de 2 à 3 mm et lors de la découpe au laser, la largeur de coupe n’est que de 0,1 mm. Cela signifie qu’en pratique, une valeur nulle peut être spécifiée dans les calculs.
Résultat
Pour afficher le résultat, un rapport avec trois sources de données était nécessaire. Pour générer un rapport, on utilise un script qui utilise la procédure Report_Open(), qui fait partie des procédures de la bibliothèque du programme “ClearApp”. Le même script calcule l’efficacité de la mise en page résultante (pourcentage de pertes).
procedure UserApp_LinearCalc_Report( AReportMode: integer );
// rapport coupe linéaire
var
tmpDataSets : array of TDataSet;
tmpDSNames: array of string;
tmpStrParam: array of string;
tmpStrParamName: array of string;
tmpReportMode:integer;
tmpReportFileName:string;
tmpSQL: string;
tmpID: string;
i: integer;
tmpFileName: string;
begin
tmpReportMode := AReportMode;
tmpReportFileName := 'LinearCalc.fr3';
SetLength( tmpDataSets,3 );
SetLength( tmpDSNames,3 );
//
SetLength( tmpStrParam, 2 );
SetLength( tmpStrParamName, 2 );
// детали
tmpSQL := ' SELECT * FROM piece ';
SQLQuery( tmpSQL, tmpDataSets[0] );
tmpDSNames[0] := 'Piece';
// результат
tmpSQL := ' SELECT * FROM cuttingMap ';
SQLQuery( tmpSQL, tmpDataSets[1] );
tmpDSNames[1] := 'CuttingMap';
// сводный результат
tmpSQL := 'SELECT blankLength, sum(qty) as qty FROM cuttingMap GROUP BY blankLength';
SQLQuery( tmpSQL, tmpDataSets[2] );
tmpDSNames[2] := 'blankSummary';
// параметры
i := 0;
// pourcentage de perte
tmpStrParamName[i] := 'Percent';
tmpStrParam[i] := FormatFloat('#0.0', ( SQLExecute('SELECT sum( scrap * qty ) FROM cuttingMap') / SQLExecute('SELECT sum( blankLength * qty ) FROM cuttingMap') )*100 )+'%';
inc(i);
// Largeur de coupe
tmpStrParamName[i] := 'CutWidth';
tmpStrParam[i] := IntToStr(CutWidth)+' мм.';
inc(i);
// appeler la fonction d'ouverture de rapport universel
tmpFileName := Report_Open( tmpDataSets, tmpDSNames, tmpStrParam, tmpStrParamName, tmpReportMode, tmpReportFileName );
// nettoyage...
Report_FreeDataSets( tmpDataSets );
if AReportMode = RM_PDF then
OpenFile(tmpFileName);
end;
Langage du code : Delphi (delphi)Résultats
Bien que le projet My Visual Database ait cessé de se développer il y a plus d’un an, il convient toujours à la création d’outils d’automatisation des processus métier pratiques et efficaces.