MichaelCH

На текущий момент основной алгоритм линейного раскроя переписан на FreeBasic, что дало ускорение расчетов в несколько раз, поэтому повторно хочу предложить тестирование: Если есть примеры реальных данных с картой раскроя (или без), прошу выложить на форум.

Ссылку на Demo-версию выложил здесь: http://www.excelworld.ru/forum/3-21304-1

Продается, но т.к. уже получил замечание от модераторов за рекламу, то подробная информация в личке. Демо версию пока не реализовал, если сделаю - выложу бесплатно.

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

Да, третий вариант - это раскрой в два профиля, но я не хочу обсуждать, что крой в два профиля лучше, чем в один, я хотел узнать, что лучше, получить меньше полезного остатка, но один, либо несколько маленьких, но суммарной длиной больше. Forus в 79 сообщении уже ответил на этот вопрос. Хотелось бы знать мнение других участников. smsinfo, Вы хотели устроить тест (дуэль) по раскрою, готов принять Ваш вызов. Можете приложить несколько различных вариантов данных для раскроя и указать свои результаты, либо раскроить уже опубликованные в данной теме тесты? Во избежание разночтений лучше ширину реза и торцевую кромку обнулить, таким образом не будет споров, что различные программы по-разному совмещают резы.

В дополнение к качеству раскроя. Я для себя поставил следующие параметры оптимальности: 1. Использования как можно меньшего количества исходных заготовок (профиля) 2. Сделать как можно большим остаток у последней заготовки, при этом все остальные раскроить с минимальными отходами. Данный способ хорошо реализуется на большом профиле. Во вложении три варианта раскроя при размере профиля 4000. В первом варианте - использование 23 заготовок по 4000 и сохранение полезного остатка 3400 Во втором варианте - 23 заготовки, полезный остаток 2465 + 1387 = 3852 В третьем варианте - 24 заготовки, полезный остаток 2609*2 + 1387*2 = 7992 Вопрос: какой из этих вариантов лучше? Я склоняюсь к мнению, что первый, т.к. раскроить в последствии остаток 3400 легче с меньшими потерями,чем 2465+1387 и тем более 4000+3400 - это лучше, чем 2609+2609+1387+1387. Хотя во 2м и 3м варианте "полезный" остаток больше, чем в первом. LP 0x0 4000.rar

Dan-K, для анализа ваших данных не хватает карт раскроя. Относительно моего алгоритма, сейчас реализовано два метода: Решение задачи о рюкзаке (сумма подмножеств) методом динамического программирования - вариант задачи, когда рюкзаков много. Данный метод показывает относительно хорошую скорость и приемлемое качество раскроя. Второй способ - применение линейного программирования (целочисленный симплекс метод). Данный способ не всегда применим, либо может очень долго считать, но находит оптимальное решение - наименьшее количество заготовок. Во вложении расчет данных от Dan-K с различной длиной заготовок от 4000 до 6500 с шагом 100 с применением обоих методов. Линейное программирование показывает результата лучше. Если есть желание, то можете раскроить данные своей программой при любом размере профиля и сравнить результаты. Для сопоставимости различных программ специально обнулил ширину реза и кромки, т.к. программы по-разному относятся к этим параметрам. CSP.rar

У меня при данных настройках - ширина реза 5 и кромка 10 (по 5 с каждой стороны) получился полезный остаток 1970мм. Возникает вопрос, если Ваше оборудование позволяет раскраивать с шириной реза 5 и торцевой кромке 10, то зачем производить расчет при большем резе и большей кромке, ведь результат должен получится хуже (меньше полезный остаток)? Либо Ваша программа при увеличении реза и кромки может выдавать результат лучше? Но тогда это проблема алгоритма раскроя, реализованного в программе. Специально раскроил Ваши данные с разным размером ширины реза (от 5 до 11) и торцевой кромкой (от 0 до 10 с одной стороны, т.е. от 0 до 20 с двух сторон с шагом 2мм). Ни в одном из результатов при увеличении ширины реза или кромки результат не стал лучше. Все схемы во вложении P.S. Тоже раскраиваю в Excel. LinRaskrLP пример2.rar

Dan-K, раскроил Ваши данные своей программой (для этого не пришлось делать "несколько сотен оптимизаций подряд"). Имеется 58 деталей, общей длиной 87580мм, для раскроя необходимо минимум 15 хлыстов по 6000 итого 90000мм. При кромке 20мм (по 10 с каждой стороны) уйдет 15*20 = 300мм, и при резе 11мм - 58*11 = 638 мм. Итого максимально возможный полезный остаток: 90000 - 87580 - 300 - 638 = 1482 У меня получилось сохранить 1428, выброшено 1482 - 1428 = 54 мм (54/90000 = 0,06%) или с учетом резов и кромки (90000-87580-1428)/90000 = 1,1% Схемы во вложении. У Вас сохранено 732 мм, т.е выброшено 1482 - 732 = 750 мм (750/90000 = 0,833%) или с учетом резов и кромки (90000-87580-732)/90000 = 1,876% Согласитесь, что остаток 1428 это лучше, чем 732. С удовольствием поучаствовал бы в производственном процессе и помогу с оптимизацией раскроя, к реальному производству не имею никакого отношения, я программист. В 82 сообщении Forus ответил, какова цель тестов - сравнить алгоритмы программ при равных условиях. Если в реальном производстве не производится торцовка, а она задается для минимизации ошибки резчика либо, когда концы профиля необходимо подровнять, то это не имеет отношение к тестам. LinRaskrLP пример.rar

Эффективность раскроя можно оценить следующими показателями: использования меньшего количества заготовок (профиля) и максимизация полезного остатка, остальные показатели - переналадка оборудования, оптимизация складских остатков очень индивидуальна. Да и "полезный остаток" имеет разную ценность, например, три отрезка по 1500 существенно хуже, чем один на 4500. Если за счет увеличения кромки Вы добиваетесь снижения рассчитываемого процента отхода, при этом не получается уменьшить заготовки или увеличить полезный остаток, то это просто самообман. Некоторые программы позволяют совмещать последний рез и кромку, за счет этого получать дополнительный выигрыш в долях процента.

Dan-K, как Вы (или программа) вычисляет потери? Если учитывать, что в шестиметровый профиль умещается 4-5 отрезков, то это 4 реза по 10мм + 18мм кромка. Итого 58 мм, а это уже почти 1% от 6 метров, но никак не 0,9%, а еще ведь остаются неделовые обрезки. Либо у Вас в 0,9% учитывалось только неделовые отходы (без учета реза пилы и кромки)? Кроме того, оборудование ведь не может перенастраивать ширину реза. Для более наглядного анализа качества раскроя хотелось бы видеть исходные данные, которые Вы раскраивали и саму карту раскроя. Обратите внимание на раскрой из 88 сообщения. Если не учитывать технологические отходы (кромка и рез ~ 1%), то на выброс ушло в 1 и 2м тесте 13,2 см (т.к. полезный остаток не удается сформировать), в 3 и 4м тесте выбрасывается только 4 мм из 144 метров, в 5м тесте - на выброс ушло 7см из 324 метров профиля, в 6м тесте выбрасывается 2см, остальное удалось сохранить в виде делового остатка, потери измеряются сотыми долей процента.

Сделал расчет по объединенным заказам (примерно 300-400 окон). В результате получилось 1834 детали общей длиной 2737,154 метра Думаю, что данный набор покажет эффективность алгоритмов различных программ линейного раскроя. Т.к. программы по разному подходят к ширине реза и кромки, то для сопоставимости добавил к размеру деталей ширину реза, а из длины хлыста убрал кромку. Таким образом, ширина реза - 0, кромка - 0, размер хлыста - 5975 (6000-25). Минимально для раскроя необходимо 2737154 / 5975 = 458,101 хлыста, т.е. 459 целых хлыста. Задача минимум - получить раскрой, используя 459 хлыстов, задача максимум - максимизировать остаток от последнего хлыста (при этом потери будут не более 0,899/459 = 0,2%). Количество заготовок достаточно большое и они имеют большую дисперсию, поэтому получить раскрой в 459 заготовок возможно. К реальной ситуации данная задача не относится, т.к. на практике заказ разбивается на партии и производится раскрой каждой партии отдельно. Интересно посмотреть, как специализированные программы решают данный тест. Набор исходных данных и схема раскроя, которую смог найти - во вложении. Пример.rar

Сделал раскрой имеющихся данных при разных размерах профиля от 3000 до 6500 с шагом 500 с теми же условиями (ширина реза - 10, торцевая кромка - 10), итого получилось 48 (6 * 8) тестов. Результаты во вложении. Если у кого-нибудь хватит терпения, то протестируйте свои программы. Будет интересно сравнить эффективность алгоритмов раскроя не только на 6000, но и на других размерах профиля. Тесты.rar

Удалось улучшить решение в 1м и 2м тесте: используется вместо 31 заготовки - 30 При этом не технологические потери во всех тестах минимальны. LinRaskr тест 1-6 вар3.rar

Не удержался и перезапустил раскрой на более сложном пересчете (расчет вместо 5-10 секунд производился не более 30-40 секунд в самом сложном 5м варианте). Результаты улучшились и обогнали WinCalc Схемы раскроя: https://yadi.sk/i/T3fuPINaiwUvz Полезный остаток: Тест 1: 5344 Тест 2: 10688 Тест 3: 3808 Тест 4: 3808 Тест 5: 3874 Тест 6: 3924