Линейный раскрой

Задача

Оптимальным образом осуществить нарезку линейного материала, минимизировав длину обрезков. В качестве исходных данных использовать длину заготовки, ширину разреза и перечень деталей, которые нужно изготовить, с указанием линейного размера и количества. В расчете использовать имеющиеся заготовки различной длины, которые также представлены списком с указанием их длины и количества.

Решение

Задача классическая, поэтому и в сети можно найти множество подробных рассуждений на тему, как её правильно решать с помощью различных математических методов, в том числе с применением MS Excel. Также имеется множество интернет-ресурсов с он-лайн калькуляторами, платными и бесплатными. Тем не менее, я решил предложить свой вариант реализации расчета с использованием платформы My Visual Database (MVDB) в качестве инструмента для создания соответствующей программы. В дальнейшем планирую использовать рассматриваемый метод в составе программы “Производство”, совместив его с системой складского учёта.

Для определения оптимальной раскладки деталей (карты распила) используется алгоритм полного перебора, дополненный условиями оптимизации: отсечения вариантов перебора с заведомо плохим результатом и досрочный выход при получении идеального варианта (нулевой остаток обреза). То есть в цикле перебираются все возможные варианты раскладки деталей до тех пор, пока не будет найден лучший вариант с минимальной величиной обреза или не сработают условия оптимизации.

Затем определяется, сколько раз полученная карта распила может быть использована для изготовления требуемого числа деталей. После чего карта добавляется в результирующий список.

В случае, когда у нас имеется несколько заготовок различной длины, используется стратегия “сохранения ликвидного запаса”, то есть в первую очередь под нож идут короткие заготовки, так как длинные обрезки можно с большей вероятностью использовать при следующем заказе, а мелкие обрезки обычно уходят в утиль. С математической точки зрения такой подход не гарантирует минимальный процент потерь при распиле, но обеспечивает минимизацию закупок материалов для текущего заказа и максимальное использования имеющихся запасов.

Реализация

Для хранения исходных данных и результата используется несколько таблиц БД, а для перебора вариантов данные загружаются в оперативную память. К сожалению, MVDB не поддерживает структуры (Record), поэтому для хранения данных использованы динамические массивы – отдельный массив для каждой величины (при реализации данного алгоритма на других языках он будет немного элегантней).

После инициализации массивов и загрузки в них данных из таблиц БД, организуется два цикла repeat..until. Внешний – для перебора заготовок, внутренний – для подбора вариантов раскладки. В качестве оптимизации во внутреннем цикле использованы проверки:

• если длина обреза равна нулю, то получен идеальный вариант; досрочный выход из цикла
• если длина обреза отрицательна, то нужно перейти к перебору деталей меньшего размера

Однако от слов к делу: ниже находится скрипт с подробными комментариями, реализующий данный алгоритм.

Скрипт

procedure frmCuttingMap_btnCalc_OnClick (Sender: TObject; var Cancel: boolean);
// выполнение расчета
var
  tmpSQL: string; // для хранения текста запроса, удобно для отладки
  tmpQty: integer; // количество деталей
  tmpDetLen: array of integer; // список длин деталей
  tmpDetQty: array of integer; // список количества деталей
  tmpBQty: integer; // количество заготовок
  tmpBIndex: integer; // индекс заготовки, с которой сейчас работает алгоритм
  tmpBlankLen: array of integer; // список длин заготовок
  tmpBlankQty: array of integer; // список количества заготовок
  tmpMap: string; // карта нарезки
  tmpMapQty: integer; // количество использований карты нарезки
  tmpTestQty: array of integer; // список количества деталей для текущего распила
  tmpBestQty: array of integer; // лучший распил
  tmpBestBlankLen: integer; // текущая длина заготовки для записи
  tmpTestBlankLen: integer; // длина текущей заготовки для расчета
  tmpTestScrap: integer; // текущий обрезок
  tmpTestLen: integer; // текущая длина
  tmpBestScrap: integer; // лучший обрезок
  tmpLastIncPos: integer; // последний разряд, который был увеличен
  tmpIncPos: integer;// разряд, который увеличиваем в основном цикле
  tmpDataSet: TDataSet;
  i,j: integer;
  tmpFlag: boolean;
  s: string;
  // модификатор матрицы нарезки
  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,'Поиск решения...',True);
  try
    // сохранить настройки для ширины распила
    CutWidth := Trunc( frmCuttingMap.edtCutWidth.Value );
    IniFile_Write_Int(APP_PARAMS,'CutWidth',CutWidth);
    // инициализация
    SQLExecute('DELETE FROM cuttingMap'); // очистить таблицу результатов
    //
    tmpBQty := SQLExecute('SELECT count(*) FROM blank '); // число заготовок
    SetLength( tmpBlankLen, tmpBQty); // список длин заготовок
    SetLength( tmpBlankQty, tmpBQty); // список количества заготовок
    // данные должны быть упорядочены по возрастанию, чтобы обеспечить стратегию использование коротких обрезков в первую очередь
    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); // список количества деталей
    // начинаем с первого размера заготовки
    tmpBIndex := 0;
    SetLength( tmpTestQty, tmpQty); // список количества деталей для текущего распила
    SetLength( tmpBestQty, tmpQty);
    // данные должны быть упорядочены по убыванию!
    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; // лучший обрезок равен длине заготовки
      // сбрасываем матрицу нарезки
      for i:=0 to tmpQty-1 do
        tmpTestQty[i] := 0;
      //
      tmpIncPos := 0;
      repeat
        Application.ProcessMessages;
        // досрочное завершение
        if ProgressCancel then
          exit;
        if not NextIndex( tmpIncPos ) then // модифицируем матрицу нарезки
          break // если не удалось, то выход из цикла
        else
        begin
          // смотрим, что у нас получилось по длине
          tmpTestLen := 0;
          tmpFlag := False;
          for i :=0 to tmpQty - 1 do
          begin
            tmpTestLen := tmpTestLen + (tmpDetLen[i] + CutWidth)* tmpTestQty[i]; // потом нужно учесть, что последний распил может и не понадобится...
            if tmpTestLen > tmpTestBlankLen then // если длина превысила длину заготовки, дальше можно не считать - плохой вариант
            begin
              tmpFlag := True;
              break;
            end;
          end;
          // если было переполнение, то перейти к следующему варианту
          if tmpFlag then
          begin
            tmpTestQty[tmpLastIncPos] := 0; // сбрасываем счетчик в разряде, который увеличивали последним
            tmpIncPos := tmpLastIncPos + 1; // будем увеличивать счетчик следующего разряда, с меньшим весовым коэффициентом
            continue;
          end;
          tmpTestScrap := tmpTestBlankLen - tmpTestLen; // обрезок
          //
          if tmpTestScrap < tmpBestScrap then // если найден лучший вариант
          begin
            tmpBestScrap := tmpTestScrap;
            for i:=0 to tmpQty - 1 do // запоминаем вариант раскроя
              tmpBestQty[i] := tmpTestQty[i];
          end;
          // идеальный вариант - нулевой обрезок, лучше не бывает
          if tmpBestScrap = 0 then
            break;
          // готовимся к инкременту старшего разряда
          tmpIncPos := 0;
        end;
      until 1=0; // цикл подбора вариантов; выход, если нельзя получить след.матрицу
      // возможен случай когда текущий размер не подходит для расчета
      if tmpBestScrap = tmpTestBlankLen then
      begin // перейти к следующему размеру без записи результата
        inc( tmpBIndex ); // перейти к следующей заготовке
        if tmpBIndex < tmpBQty then
        begin
          continue; // продолжаем...
        end
        else
        begin
          break; // заготовки кончились...
        end;
      end;
      // рисуем карту раскладки
      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;
      // считаем, сколько раз карту можно использовать
      tmpBestBlankLen := tmpTestBlankLen;
      repeat
        inc(tmpMapQty);
        // уменьшаем остатки по деталям
        for i := 0 to tmpQty - 1 do
          tmpDetQty[i] := tmpDetQty[i] - tmpBestQty[i];
        // уменьшаем остатки по заготовкам
        tmpBlankQty[tmpBIndex] := tmpBlankQty[tmpBIndex] - 1;
        // теперь надо определить, можно ли использовать такую раскладку ещё раз
        tmpFlag := false;
        // проверка по остаткам деталей
        for i := 0 to tmpQty - 1 do
          if tmpBestQty[i] > tmpDetQty[i] then
          begin
            tmpFlag := True;
            break;
          end;
        // проверка по остаткам заготовок
        if tmpBlankQty[tmpBIndex] = 0 then
        begin
          tmpFlag := True;
          inc( tmpBIndex ); // перейти к следующей заготовке
        end;
      until tmpFlag;
      // Если что-то удалось подобрать, то
      if tmpBestScrap <> tmpTestBlankLen then
        // сохраняем результат
        SQLExecute('INSERT INTO cuttingMap (blankLength,qty,map,scrap) VALUES ('+IntToStr(tmpBestBlankLen)+','+IntToStr(tmpMapQty)+','+StrToSQL(tmpMap)+','+IntToStr(tmpBestScrap)+')');
      // проверяем, осталось ли что-нибудь на изготовление
      tmpFlag := false;
      for i := 0 to tmpQty - 1 do
        if tmpDetQty[i] > 0 then
        begin
          tmpFlag := True; // да, что-то нашли
          break;
        end;
      // проверяем, есть ли заготовки
      if tmpBIndex = tmpBQty then
        tmpFlag := False;
    until not tmpFlag; // повторять до тех пор, пока есть что-нибудь на изготовление
    // обновить отображение данных
    frmCuttingMap.tgrMap.dbUpdate;
  finally
    Progress();
  end;
  ShowMessage('Раcчет завершен');
end;

Code language: Delphi (delphi)

В строке 48 и 213 использована процедура отображения индикатора прогресса выполнения, подробно описанная в статье “Во имя прогресса”.

В 66 строке использована константа MAX_QTY = 1000000; чтобы по заготовкам, которые можно купить, не было завершения внешнего цикла по причине нехватки их количества.

Структура данных

Интерфейс

Для редактирования исходных данных используются таблицы с включенным режимом редактирования данных (AllowCreate = True, AllowEdut = True, AllowDelete = True).

Для управления данными предназначены кнопки, расположенные на панели инструментов:

• Очистить входные данные
• Выполнить расчет
• Сформировать документ
• Сформировать PDF

Также на панели инструментов расположено поле, в котором можно указать ширину разреза. Для фрезы ширина может иметь значение 2-3 мм, а при резке лазером ширина разреза составляет всего 0.1 мм. Это означает, что на практике при расчетах можно указать нулевое значение.

Результат

Для вывода результат понадобился отчет с тремя источниками данных. Для формирования отчета служит скрипт, использующий процедуру Report_Open() , входящую в состав библиотечных процедур программы “ClearApp”. В этом же скрипте рассчитывается эффективность полученной раскладки (процент потерь).

procedure UserApp_LinearCalc_Report( AReportMode: integer );
// отчет линейного раскроя
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;
    // Коэффициент использования
    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);
    // Коэффициент использования
    tmpStrParamName[i] := 'CutWidth';
    tmpStrParam[i] := IntToStr(CutWidth)+' мм.';
    inc(i);

    // вызвать универсальную функцию открытия отчета
    tmpFileName := Report_Open( tmpDataSets, tmpDSNames, tmpStrParam, tmpStrParamName, tmpReportMode, tmpReportFileName );
    // чистим...
    Report_FreeDataSets( tmpDataSets );

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

Итоги

Несмотря на то, что проект My Visual Database перестал развиваться более года назад, он все ещё пригоден для создания удобных и эффективных средств автоматизации бизнес-процессов.