Алгоритм одномерного раскроя #520699

Здравствуйте. Если кто-нибудь сталкивался с задачей оптимального одномерного раскроя, поделитесь, пожалуйста, алгоритмом. Пока что, ничего полезного, кроме уже готовых программ (с закрытым, естественно, кодом) не нашел.

Прошу прощения, а Вы сами-то Вашу ссылку открывали? Или иного решения, кроме как "через книжный магазин", мне найти не удастся?

а разве одномерный раскрой жадный алгоритм не решает?

Попробуйте в гугле поискать. Или заказать копию либо связаться с автором.

а что оптимизировать в одномерном случае то или я не понял?

Даны 10 кусков различной длины. Из этих материалов нужно получить двадцать изделий по своим спецификациям (длине).

Решает, но не оптимально. Количество отходов в случае использования "жадного" алгоритма больше, чем при использовании, допустим, трудоемкого, но результативного метода перебора. В идеале - избавится от отходов. В реале - сократить их.

понял

Нужно будет еще обработку и станки учитывать. Там засады могут быть разные.

+1

Вроде занимался. Попробуйте к нему обратиться.

только думаю надо все же более конкретно выяснить что да как пока нафантазировал так: допустим ежедневно утром мы знаем потребность нарезов на день мы можем 1. от большого куска все нарезать и кусочек останется - его придется выкинуть ибо ничего из него не выйдет 2. отрезать поровну примерно от двух кусков, на сегодня отходов нет, но так до бесконечности делать нельзя

Задача не раскрыта 1) Достаточно все раскроить? 2) Должно остаться максимально количество нетронутых кусков? 3) Должно остаться минимальное количество кусков? 4) Должно быть минимальное количество порезов? 5) Должна быть минимальная длина порезов?

см

Раскрой с учетом вероятности заказа, на которую можно будет использовать остаток без "остатка" - не нужен. Чтобы было понятно, отвечу на вопросы из : 1. Раскроить нужно все заказанные детали. 2. Количество нетронутых кусков не важно. 3. Не совсем понятно. Если речь про отходы - стремление к минимальному количеству отходов - важно. 4,5. Не важно.

повеселило "2. Количество нетронутых кусков не важно. 3. Не совсем понятно." Автор абсолютно не в теме. Рекомендую начать с математики. А по поводу "неважного" количества нетронутых кусков это и вообще говорит о незнании и/или неумении/нежелании понять то, что неучет количества нетронутых кусков приведет к тому, что хранить "тронутые" в определенный момент станет затруднительно. Ну и к проблемам во взаимотношениях с бухгалтерией, складом, а возможно, и с УК. :) Дай угадаю - 1986?

+ Однако угадал :) Такой вот "подарочек" нарешает задач ...

А вообще алгоритм эффективного одномерного раскроя достаточно прост. 1)Имеем инфу о наличии и размерах кусков(как тронутых, так и нетронутых), с учетом размещения - "дальнего"(склады) и "ближнего"(цех). 2)Имеем инфу о размерах выкроек и о том, какова вероятность их использования, усредненная за некоторые периоды и текущая(за самый короткий последний период - типа), в т.ч. с учетом плана производства. 3)при выборе куска, от которого будем отрезать выкройку, определяемся с тем, сможем-ли мы использовать остаток для какой-то выкройки в будущем. С учетом вероятностей и планов производств. 4)При невозможности использования согласно п.3 определем % отхода по разным критериям(к размеру начального куска, к размеру куска по последнему отрезу и т.д.). 5)Если этот % нас не устраивает(нужны заранее выданные критерии), то делаем N попыток по п.3 с другими потенциальными выкройками. 6) + различные критерии оптимизации - по трафику склад-цех, по времени ожидания нового куска и т.д.

Что это за производство было?

Такая постановка верна? Xij = 0 или 1, если i-я деталь из j-того куска. Ограничения: СУММАi(Li*Xij)<=Aj СУММАj(Xij)<=1 Функционал: СУММАi(Li*Xij)-> MAX Если попробовать в лоб схему неявного перебора (ветвей и границ) с оценкой функционала, как решения релаксированой задачи ЛП, боюсь отсечения не будет: ЛП будет выдавать, что все можно выкроить. Если из куска может получаться небольшое число деталей, то можно попробовать предваритьно сгенерить для каждого куска возможные варианты раскроя на детали и потом уже методом ветвей и границ искать оптимальный. Что-то похожее делал в ситуации, когда различных длин деталей было немного (около 10). Получалось прилично: примерно 97-98% выхода. Киньте Ваш адрес на мыло (в профиле), попробую связать с более знающим человеком. Хорошо бы увидеть конкретный пример.

Работал я как-то(более 8 лет назад) на фирме, которая производила изделия из листовой нержавейки. Соответственно раскрой, но уже "двумерный". Но там "выкройки" были относительно простые(в основном прямоугольники разных размеров) и задачи делать раскрой прямо в 1С не было. После некоторого времени на обдумывание вопроса и поисков нашли в Инете прогу, Астра-Д(если не ошибся), купили. Прогу  юзали технологи - делали на ней карты раскроя. Но там было среднесерийное производство(сотни и > штук для нескольких десятков однотипных изделий в месяц) и соответственно более или менее жесткий план.

Вот это, насколько я понимаю, и есть наследница той Астры, с котрой когда-то пришлось работать.

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

Ню-ню. Для того, чтобы что-то услышать "по существу", надо, как минимум, дорасти до понимания. Ты - не дорос, Подарочек :)

автор на яндексе забанен!? и в гугле.... я этот использовал -

Тогда мне не понятен весь тот флейм, который был тобой сказан. Для кого, я ж не дорос. Или так - крик души?

Спасибо. Сразу видно пафоса в человеке меньше, чем у Глаза.

Да тебе вообще многое непонятно. Например то, что пост вполне информативен(понятное дело, алгоритм там примерный, но какие данные - таков и алгоритм), для тех, кто умеет читать, а не находить знакомые буквы, ес-но :) Мне вот в отношении тебя сразу всё стало понятно. И выразил я это одним кратким и емким 1986 :) Непонятно только то, как тебя на работе до сих пор держат и как ты с таким подходом - "это неважно, то неважно, всё неважно" - это в учете-то - под УК не загремел до сих пор. Но у тебя всё впереди, с такими знаниями и внимательностью ты так "накроишь" ...

Вы, прошу прощения, корм ищете, а не в проблеме помочь хотите. Если я сказал "неважно", то можете Вы принять это как данность, как первоначальное условие, и не лезть со своими "алгоритмами там примерными"? Как минимум уже 2 человека в этой ветке очень мне помогли в вопросе. Без малейшего пафоса. И в конце концов, какой УК, какой учет? Может я колбасу в магазине нарезаю. Проще надо быть, товарищ Глаз. Проще.

Диагноз, однако. ну раз ты настолько туп, то объясню. Ты не колбасу в магазине нарезаешь, это верно. ты составляешь программу, которая будет выдаваль данные для раскроя некоего материала, который стоит наверняка не сильно дешевле колбасы, а вот кроится будет партиями поболее. Теперь пляшем от твоего "Количество нетронутых кусков не важно." Это приводит к тому, что при определенных условиях программа накроит по одной выкройке из всех доступных кусков и сбросит начатые куски в запас. Следствия: 1)Перегрузка цеховых помещений начатыми и не использованными до конца кусками. Мелочь? Да, в сравнении с другими следствиями. Но и за эту мелочь бьют, особенно если производство более или менее поточное. 2)При определеннной комбинации заказов может сложиться ситуация, когнда начатые куски окажутся недостаточно велики для последующего использования(в плане только большие выкройки) вообще или будут давать огромный %% отходов. Как тебе ситуация, когда с тебя лично взыщут убытки от транспортировки туда-сюда начатых кусков(в цехе они мешаются, т.к. их слишком много), а также от того, что придется закупать материал дополнительно т.к. тот, который есть(те самые начатые куски), не подходит. А "где деньги, Зин" сверх тех, что уже заложены в бюджете на производственную программу. В банке? А там %%. Который у некоторых возникнет ненавязчивое желание слупить с виновных. Что? На тебе нет полной материальной ответственности? Был бы человек - статья найдется :) На крайний случай халатность припаяют. Ну а если не статья, то "коллекторы" с инструментом для терморектального воздействия на особо тупых. Достаточно я сказал, чтобы ты почувствовал весь идиотизм своей бравады или еще нет? Ну а про "какой УК, какой учет?" это ты потом "коллекторам" или, что несколько более мягкий вариант, дяденьке следователю будешь рассказывать :) Не помнишь, сколько там сейчас килорублей нижняя граница применения УК? И свой совет - быть проще, прибереги для себя, может он тебе поможет :) "it's economy, stupid!"

Пункт 3, т.с. на сладкое :) Хорошо, если отходы после раскроя взвешиваются и хранятся, а если нет? Вот тут может найтись "орёл", который поняв, что на раскрое сидит лох, свалит на него свои грешки/недостачи материала. И попробуй потом доказать, что твоя в потерях только часть.

только по длине? тут любой тупой 1Сник может реализовать. одна рекурсивняя функция я двухмерный давно делал на 7.7 и в экселе рисовал. типа оптимальное размещение прямоугольных деталей на поддоне

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

Попробуйте на любой современной машине решить ПРОИЗВОЛЬНУЮ задачу Штейнера, скажем, для 20 точек.

пиши тз и сколько готов заплатить. а так даже в гугле искать неохота по штейнера и его задачки

50 000 руб устроит за 25 точек?