Блог пользователя blazerer

Автор blazerer, 13 лет назад, По-русски

Обычно не очень положительно отношусь к подобного рода штукам в эфире, но тут, мне показалось, что может кому-то быть интересным.

Надо как-то решить следующую задачу:
Даны: основные прямоугольные листы размера a на b в количестве равном n, m заказов, также прямоугольников, характеризующихся своими габаритами, и количеством, в котором они должны быть исполнены. Мы должны размещать листы заказов на основном листе. Все листы заказов по своей максимальной характеристике размера меньше максимальной для основного листа и вообще любой заказ помещается на основной лист.
Требуется: расположить листы заказов на основном листе следующим образом:
1) Чтобы минимизировать количество используемых основных листов (чтобы их было меньше n для начала).
2) Чтобы количество различных конфигураций заполнения основных листов тоже было "достаточно близким к минимуму".
3) Допускается небольшое перевыполнение плана, когда какого-то конкретного заказа напечатано чуть больше, чем надо.
Задача не требует идеальных решений, да и их существования сомнительно для меня. Количество заказов достаточно мало (исчисляется количеством пальцев на паре рук), а размеры не больше максимального количества миллиметров в формате А3, первые два условия не перечислены в порядке предпочтительности. В наличие каких-то глобальных оптимумов, как я уже сказал, я слабо верю. Думал над жадностью, дп, переборами, ничего толкового пока в голову не пришло, что было бы можно назвать "нормальным" решением .
Было бы интересно услышать ваши мысли по этому поводу :)
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
По-моему, такое называется задачами раскроя. Петрозаводский университет имеет экспертизу в этом вопросе, свои разработки они неоднократно внедряли на производстве.

Забавно, только сегодня я случайно попал на завод по производству стеклопакетов для пластиковых окон. У них решается подобная задача, когда надо из больших листов стекла нарезать куски под конкретные окна.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    С такой проблемой столкнулся друг на типографии :) Уже спасибо за информацию.
    Жеесть .. тут оказывается люди целые диссертации на подобные темы пишут ...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    У нас на швейной фабрике итальянцы (они фабрику выкупили)  за подобную программу для швейных станков заплатили баснословную сумму. Сколько не спрашивал - не говорят: либо не знают, либо не хотят отвечать.
    Причём программа защищена на нескольких уровнях - вплоть до ключа на LPT-порту.
    Так что эта задачка - очень и очень хороший стимул финансово подняться.
    Если у кого-то есть идеи - ищите сразу с кем заключать контракт. (это без шуток и на полном серьёзе)
13 лет назад, # |
Rev. 8   Проголосовать: нравится +8 Проголосовать: не нравится

In english your problem is called Cutting Stock Problem,

For general Information check http://en.wikipedia.org/wiki/Cutting_stock_problem.

Most existing solutions use some heuristics or genetic  algorithms.

For example,see http://sourceforge.net/projects/cuttingproblem

Another interesting way  is to use some  prolog extensions which allow to solve optimization problems.

(The main idea of them is that you describe you problem in prolog and add optimization parameters )

Google  something like  "optimization problems weak constraints ".

For example,this solver may help:

http://www.dlvsystem.com/dlvsystem/html/DLV_User_Manual.html#AEN452

But it is still under development and it's syntax is not perfect.

I hope some of this will be helpful.