Linear сutting

Task

Optimal cutting of linear material, minimizing the length of the trimmings. As initial data, use the length of the workpiece, the width of the cut and the list of parts to be made, indicating the linear size and quantity. In the calculation, use the available blanks of various lengths, which are also presented in a list indicating their length and quantity.

Solution

The task is a classic one, therefore, you can find a lot of detailed discussions on the web on how to solve it correctly using various mathematical methods, including using MS Excel. There are also many online resources with online calculators, paid and free. Nevertheless, I decided to offer my own version of the implementation of the calculation using the My Visual Database (MVDB) platform as a tool for creating the corresponding program. In the future, I plan to use the considered method as part of the “Production” program, combining it with the warehouse accounting system.

To determine the optimal layout of parts (cut maps), a complete enumeration algorithm is used, supplemented by optimization conditions: cutting off enumeration options with a deliberately poor result and early exit when an ideal option is obtained (zero cut residue). That is, in the loop, all possible options for the layout of parts are sorted out until the best option with the minimum cutoff value is found or the optimization conditions are triggered.

Then it is determined how many times the resulting cut map can be used to produce the required number of parts. Then the map is added to the resulting list.

In the case where we have several blanks of different lengths, a strategy of “keep liquid stock” is used, that is, short blanks go under the knife first, since long trims are more likely to be used in the next order, and small trims usually go to junk. From a mathematical point of view, this approach does not guarantee a minimum percentage of losses during sawing, but it ensures the minimization of purchases of materials for the current order and the maximum use of available stocks.

Implementation

To store the initial data and the result, several database tables are used, and to enumerate the options, the data is loaded into RAM. Unfortunately, MVDB does not support structures (Record), so dynamic arrays are used to store data – a separate array for each value (when implementing this algorithm in other languages, it will be a little more elegant).

After the arrays are initialized and data is loaded into them from the database tables, two repeat..until loops are organized. External – for sorting blanks, internal – for selecting layout options. The following checks were used as an optimization in the inner loop:

if the trim length is zero, then an ideal variant is obtained; early exit from the cycle

if the trim length is negative, then you need to go to the enumeration of smaller parts

However, from words to deeds: below is a script with detailed comments that implements this algorithm.

Script

procedure frmCuttingMap_btnCalc_OnClick(Sender: TObject; var Cancel: boolean);
// perform calculation
var
   tmpSQL:string; // to store the request text, handy for debugging
   tmpQty: integer; // number of details
   tmpDetLen: array of integer; // list of part lengths
   tmpDetQty: array of integer; // list of number of parts
   tmpBQty: integer; // number of blanks
   tmpBIndex: integer; // index of the workpiece that the algorithm is currently working with
   tmpBlankLen: array of integers; // list of workpiece lengths
   tmpBlankQty: array of integer; // list of the number of blanks
   tmpmap:string; // slicing map
   tmpMapQty: integer; // number of uses of slice map
   tmpTestQty: array of integer; // list of the number of parts for the current cut
   tmpBestQty: array of integer; // best cut
   tmpBestBlankLen: integer; // current length of the workpiece for writing
   tmpTestBlankLen: integer; // length of the current workpiece for calculation
   tmpTestScrap: integer; // current cut
   tmpTestLen: integer; // current length
   tmpBestScrap: integer; // best cut
   tmpLastIncPos: integer; // last bit that was incremented
   tmpIncPos: integer;// digit to increase in the main loop
   tmpDataSet: TDataSet;
   i,j: integer;
   tmpFlag: boolean;
   s:string
   // slicing matrix modifier
   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,'Searching for a solution...',True);
   try
     // save settings for kerf width
     CutWidth := Trunc( frmCuttingMap.edtCutWidth.Value );
     IniFile_Write_Int(APP_PARAMS,'CutWidth',CutWidth);
     // initialization
     SQLExecute('DELETE FROM cuttingMap'); // clear the results table
     //
     tmpBQty := SQLExecute('SELECT count(*) FROM blank '); // number of blanks
     SetLength( tmpBlankLen, tmpBQty); // list of workpiece lengths
     SetLength( tmpBlankQty, tmpBQty); // list of the number of blanks
     // data should be sorted in ascending order to ensure a strategy of using short cuts first
     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 '); // number of positions
     SetLength(tmpDetLen, tmpQty); // list of part lengths
     SetLength( tmpDetQty, tmpQty); // list of number of parts
     // start from the first workpiece size
     tmpBIndex := 0;
     SetLength( tmpTestQty, tmpQty); // list of the number of parts for the current cut
     SetLength(tmpBestQty, tmpQty);
     // data must be sorted in descending order!
     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; // the best cut is equal to the length of the workpiece
       // reset the slicing matrix
       for i:=0 to tmpQty-1 do
         tmpTestQty[i] := 0;
       //
       tmpIncPos := 0;
       repeat
         Application.ProcessMessages;
         // early termination
         if Progress Cancel then
           exit;
         if not NextIndex( tmpIncPos ) then // modify the slicing matrix
           break // if failed, exit the loop
         else
         begin
           // look at what we got in length
           tmpTestLen := 0;
           tmpFlag := False;
           for i :=0 to tmpQty - 1 do
           begin
             tmpTestLen := tmpTestLen + (tmpDetLen[i] + CutWidth)* tmpTestQty[i]; // then you need to take into account that the last cut may not be needed...
             if tmpTestLen > tmpTestBlankLen then // if the length exceeds the length of the blank, then you can not count further - bad option
             begin
               tmpFlag := True;
               break;
             end;
           end;
           // if there was an overflow, then go to the next option
           if tmpFlag then
           begin
             tmpTestQty[tmpLastIncPos] := 0; // reset the counter in the digit that was last incremented
             tmpIncPos := tmpLastIncPos + 1; // we will increase the counter of the next bit, with a smaller weight coefficient
             continue;
           end;
           tmpTestScrap := tmpTestBlankLen - tmpTestLen; // trim
           //
           if tmpTestScrap < tmpBestScrap then // if best match found
           begin
             tmpBestScrap := tmpTestScrap;
             for i:=0 to tmpQty - 1 do // remember cutting option
               tmpBestQty[i] := tmpTestQty[i];
           end;
           // ideal - zero trim, it doesn't get any better
           if tmpBestScrap = 0 then
             break;
           // prepare for high order increment
           tmpIncPos := 0;
         end;
       until 1=0; // selection cycle; exit if the next matrix cannot be obtained
       // there may be a case when the current size is not suitable for calculation
       if tmpBestScrap = tmpTestBlankLen then
       begin // move to the next size without writing the result
         inc(tmpBIndex); // move to the next workpiece
         if tmpBIndex < tmpBQty then
         begin
           continue; // continue...
         end
         else
         begin
           break; // blanks ran out...
         end;
       end;
      // draw layout map
       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;
       // count how many times the card can be used
       tmpBestBlankLen := tmpTestBlankLen;
       repeat
         inc(tmpMapQty);
         // reduce the residuals by parts
         for i := 0 to tmpQty - 1 do
           tmpDetQty[i] := tmpDetQty[i] - tmpBestQty[i];
         // reduce the balance of blanks
         tmpBlankQty[tmpBIndex] := tmpBlankQty[tmpBIndex] - 1;
         // now we need to determine if this layout can be used again
         tmpFlag := false;
         // check for the rest of the parts
         for i := 0 to tmpQty - 1 do
           if tmpBestQty[i] > tmpDetQty[i] then
           begin
             tmpFlag := True;
             break;
           end;
         // add a check for the rest of the blanks !!!!!
         if tmpBlankQty[tmpBIndex] = 0 then
         begin
           tmpFlag := True;
           inc(tmpBIndex); // move to the next workpiece
         end;
       until tmpFlag;
       // If something was found, then
       if tmpBestScrap <> tmpTestBlankLen then
         // save the result
         SQLExecute('INSERT INTO cuttingMap (blankLength,qty,map,scrap) VALUES ('+IntToStr(tmpBestBlankLen)+','+IntToStr(tmpMapQty)+','+StrToSQL(tmpMap)+','+IntToStr(tmpBestScrap) +')');
       // check if there is anything left to make
       tmpFlag := false;
       for i := 0 to tmpQty - 1 do
         if tmpDetQty[i] > 0 then
         begin
           tmpFlag := True; // yes, found something
           break;
         end;
       // check if there are blanks
       if tmpBIndex = tmpBQty then
         tmpFlag := False;
     until not tmpFlag; // repeat until there is something to make
     // update data display
     frmCuttingMap.tgrMap.dbUpdate;
   finally
     progress();
   end;
   ShowMessage('Calculation completed');
end;Code language: Delphi (delphi)

Lines 48 and 213 use the procedure for displaying a progress bar, which is detailed in the “In the name of progress” article.

Line 66 uses the constant MAX_QTY = 1000000; so that for the blanks that can be bought, there is no completion of the outer cycle due to a lack of their quantity.

Data structure

Interface

Tables with enabled data editing mode are used to edit source data (AllowCreate = True, AllowEdut = True, AllowDelete = True).

The buttons on the toolbar are intended for data management:

• Clear input
• Run a calculation
• Generate Document
• Generate PDF

Also on the toolbar there is a field in which you can specify the width of the cut. For a cutter, the width can be 2-3 mm, and when cutting with a laser, the cut width is only 0.1 mm. This means that, in practice, a zero value can be specified in the calculations.

Result

To display the result, a report with three data sources was needed. To generate a report, a script is used that uses the Report_Open() procedure, which is part of the library procedures of the “ClearApp” program. The same script calculates the efficiency of the resulting layout (percentage of losses).

procedure UserApp_LinearCalc_Report( AReportMode: integer );
// linear nesting report
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 ); // details, calculation and quantity by size
     SetLength( tmpDSNames,3 );
     //
     SetLength(tmpStrParam, 2); // parameters: usage percentage
     SetLength( tmpStrParamName, 2 );
     // details
     tmpSQL := ' SELECT * FROM piece ';
     SQLQuery( tmpSQL, tmpDataSets[0] );
     tmpDSNames[0] := 'Piece';
     // result
     tmpSQL := ' SELECT * FROM cuttingMap ';
     SQLQuery( tmpSQL, tmpDataSets[1] );
     tmpDSNames[1] := 'CuttingMap';
     // summary result
     tmpSQL := 'SELECT blankLength, sum(qty) as qty FROM cuttingMap GROUP BY blankLength';
     SQLQuery( tmpSQL, tmpDataSets[2] );
     tmpDSNames[2] := 'blankSummary';
     // options
     i := 0;
     // Usage factor
     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);
     // Usage factor
     tmpStrParamName[i] := 'CutWidth';
     tmpStrParam[i] := IntToStr(CutWidth)+'mm.';
     inc(i);

     // call the universal report opening function
     tmpFileName := Report_Open( tmpDataSets, tmpDSNames, tmpStrParam, tmpStrParamName, tmpReportMode, tmpReportFileName );
     // clean...
     Report_FreeDataSets( tmpDataSets );

     if AReportMode = RM_PDF then
       OpenFile(tmpFileName);
end;Code language: Delphi (delphi)

Results

Despite the fact that the My Visual Database project ceased development more than a year ago, it is still suitable for creating convenient and effective business process automation tools.