научная статья по теме РАСКРОЙ ДЛИННОМЕРНЫХ ОБЪЕКТОВ С УЧЕТОМ ПОТЕРЬ МАТЕРИАЛА Общие и комплексные проблемы естественных и точных наук

Текст научной статьи на тему «РАСКРОЙ ДЛИННОМЕРНЫХ ОБЪЕКТОВ С УЧЕТОМ ПОТЕРЬ МАТЕРИАЛА»

Естественные и технические науки, № 6, 2006

Технология, машины и оборудование лесозаготовок, лесного хозяйства, деревопереработки и химической переработки биомассы дерева

Технология и машины лесозаготовок и лесного хозяйства

Щепалов С. В.

(Петрозаводский государственный университет)

РАСКРОЙ ДЛИННОМЕРНЫХ ОБЪЕКТОВ С УЧЕТОМ ПОТЕРЬ МАТЕРИАЛА

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

Линейный раскрой это динамический процесс, поиск оптимальной траектории выполняется методом динамического программирования. Длину объекта раскроя примем равной Ь е N, градация длины равна Ае Я , набор деталей, на который кроится объект, имеют длины {аг},г = 1..п. Обозначим через W(F) и Z(F) суммарную длину деталей (управлений), входящих в траекторию процесса F, и доход от данного процесса соответственно. Через A(g) обозначим оптимальную траекторию, такую, что W(A(g)) = g, пусть так же Zg =Z(A(g)). Рассматриваемый дискретный случай (без учета пропила) позволяет применить два множества мощностью L для решения данной задачи за время O(nL). Первое множество обозначим I, 111= L, ^ е [0,п], г = 1..Ь, оно хранит индексы деталей, входящих в траектории, второе — £,| £ |= Ь, его элемент ^г=1 Ь — это доход от реализации траектории, суммарное количество длин деталей которой равняется 1. Если такой траектории не существует, тогда 8г = 0. Процесс поиска оптимальной траектории заключается в постепенном движении от элемента множества S с наименьшим индексом к элементу этого же множества с наибольшим индексом. На 1-м шаге процесса выполняется проверка возможности вставки одной из деталей на удалении 1 ее дальнего края от начала доски. Такое возможно, в случае, когда г = ау ,1 < у < п, или 1-а > 0,1 < у < п . В первом случае деталь будет первой в раскрое, значение ее индекса присваивается элементу I (если I = 0), а значение ее цены — элементу Si. В обоих случаях может произойти ситуация, когда I > 0, это значит, что уже существует траектория, сумма длин ее деталей (управлений) равна 1 Обозначим эти траектории F1 и F2, W(F1)= W(F2) = но траектория F1 существовала ранее, следовательно, она оптимальна, и что бы отказаться от нее в пользу траектории F2 должно выполняться неравенство Z(F1) < Z(F2), доказывающее, что новая траектория более доходна. В случае верности неравенства 1-му элементу множества I присваивается значение индекса новой детали, кроме того, Si=Zi=Z(F2).

Естественные и технические науки, № 6, 2006

Процесс поиска продолжается до тех пор, пока не будет раскроена вся доска. Пусть It — индекс последней детали (управления) в найденной оптимальной траектории, тогда

индексы остальных деталей траектории можно найти по рекуррентной формуле: It i = if -at , f = k..l. Доход от реализации оптимальной траектории равен Zik.

Рассмотрим влияние ширины пропила на построение оптимальной траектории. В таком случае длина выпиливаемой детали увеличивается на ширину пропила b. Это касается всех деталей, за исключением, может быть, последней в раскрое. Оставим без изменения величину градации длины. Рассмотрим процесс раскроя Fi на некотором шаге i. Допустим, что W(Fi) = h, где h е N и {0}, заметим, что на первом шаге W(Fi) = 0 е N и {0}. Допустим, так

же, что не раскроенный участок доски длиннее как минимум на b самой длинной детали. Далее возьмем произвольную деталь aj (управление) и добавим ее в раскрой, тогда W(Fi+1) = W(F) + aj + b , W(FM) е R , однако, рассмотренный нами алгоритм оптимизации

способен решать задачу оптимизации при b е N и {0} . Сведем данную задачу к предыдущей. Представим ширину пропила в виде: b = ö + \b\ö < 1, ö е R +, LbJ = 0.

Допустим, что на шаге j раскроенной оказалась часть доски длины Lj е R. Вышеприведенный алгоритм не может манипулировать вещественными расстояниями, применим ослабление задачи. Ослабление заключается в том, что если ö > 0, тогда длину раскроенной части мы считаем равной Lj + r]j е N, n + ö = 1, где r]j — величина поправки на шаге j. Если длина доски позволяет выпилить еще одну деталь ag (плюс некоторый остаток > ö ), то, принимая во внимание ослабление задачи, получим, что длина выпиленной части будет (Lj + ag + ö) е N . У нас нет права снова ослаблять задачу, т.к. допуск уже существует

Может возникнуть ситуация, когда теоретически доска раскроена, а практически суммарная длина допусков позволяет добавить еще одну или несколько деталей. Поэтому для учета допусков вводится еще одно множество, назовем его множеством допусков Q, L =| Q |=| 11=| S |, Qi е R, i = 1..L . Если для некоторого 1 < i < L Ii > 0, тогда Qi = n > 0,n < A -

допуск, который сделан для приведения длины раскроенной части к целочисленному виду. При вставке новой детали выполняется операция сдвига детали и последующего пропила на величину допуска предыдущего шага. Длина округляется до целого значения вверх и принимается длиной раскроенной части. Если допуск присутствует, то он присваивается соответствующему элементу множества Q. Предыдущий допуск обнуляется.

При чтении оптимального раскроя из множества должен быть известен Ii, такой, что aI -

длина последней детали (управления) в оптимальной траектории, тогда по рекуррентной формуле вычисляется индекс Ij предыдущей детали (управления) траектории: I j = \i - n - b\- aL ,1 < i < L. Если Ij=0 или j<0, то оптимальная траектория прочитана полностью.

СПИСОК ЛИТЕРАТУРЫ

1. Беллман Р. Прикладные задачи динамического программирования. / Р. Беллман, С. Дрейфус. М.: Наука, 1965. 460 с.

2. Кузнецов В. А. Задачи раскроя в целлюлозно-бумажной промышленности. / В. А. Кузнецов. СПб.: СПбЛТА, 2000. 132 с.

3. Cormen T.H., Leiserson R L., Rivest R L. Introduction to algorithms. / T.H. Cormen, R. L. Leiserson, R. L. Rivest. [et al.]. -2nd ed. Massachusetts Institute of Technology, 2001.

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком