Вход | Регистрация
 
1С:Предприятие :: 1С:Предприятие 8 общая

Оптимизатор раскроя хлыстов на заготовки

Оптимизатор раскроя хлыстов на заготовки
Я
   serg999
 
28.05.21 - 11:31
Добрый день.

Задача написать оптимизатор раскроя хлыстов. Вроде тема не новая, даже мат. примеры и модели есть в инете ..  
* https://math.semestr.ru/lp/rask.php
* https://math.semestr.ru/simplex/optimal-cutting.php

На первом этапе, попробовал разложить варианты раскроя с ограничением по длине мин. заготовки и длине хлыста. Тут перебор по ТЗ и вроде прослеживается логика.
https://www.screencast.com/t/1CvLiOMfyZSV

На втором этапе надо отобраться по оптимальным вариантам раскроя. Визуально понятно что выбрать, но как это запрограммировать?
Думал насчёт использования СЛАУ, но как понял из документации "систему надо привести к одинаковой размерности" .. короче засада.
Буду признателен за любые мысли по теме.
 
 Партнерская программа EFSOL Oblako
   Garykom
 
1 - 28.05.21 - 11:34
Видяху купи, это не шутка
   acht
 
2 - 28.05.21 - 11:39
А как же ... микросервис на GO?
   polosov
 
3 - 28.05.21 - 11:46
Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ
   Kassern
 
4 - 28.05.21 - 11:46
   Garykom
 
5 - 28.05.21 - 11:48
(2) да пофиг на чем, OpenCL или CUDA смотря какая видяха
   Garykom
 
6 - 28.05.21 - 11:49
В целом такие задачки требуют хороших определенных знаний
Ну или кому то заказывать кто умеет
Не мне ибо у меня опыта маловато, так баловался с CUDA
   Garykom
 
7 - 28.05.21 - 11:57
(0) Напиши тупой полный перебор сначала линейный
Затем распараллель перебор по фоновым в 1С, запускай их по числу логических процессоров
Если скорости не хватает то переходить на GPU
   RomanYS
 
8 - 28.05.21 - 12:07
(7) для начала нужно хотя бы с критериями оптимальности определиться
>>Полный перебор... GPU...
Допустим GPU будет в тысячу раз быстрее. Полный перебор без GPU, например, тысячу лет - на GPU за год переберёшь.
   Garykom
 
9 - 28.05.21 - 12:14
(8) GPU уже не в тысячу раз быстрее а 3 тысячи и более на нормальных видяхах
   Garykom
 
10 - 28.05.21 - 12:16
(9)+ Но согласен что оптимизировать надо
Хотя в его случае  даже тупой пойдет
   Михаил Козлов
 
11 - 28.05.21 - 13:06
Году в 2098 делал похожее для раскроя металла. Правда, ширина рулона была одинаковая (как я понял, у Вас длина хлыста может быть разной).
По сути, делал как во второй ссылке в (0):
- определение рациональных способов раскроя (их посчитать можно заранее и хранить где-то);
- определение оптимальных интенсивностей использования этих способов раскроя.
В отличие от ссылки в (0) на втором этапе решал не просто задачу линейного программирования (интенсивность использования способа раскроя должна быть целой), а целочисленную методом ветвей и границ с использованием задачи ЛП для отсечения вариантов.
Характерных размеров ширины заготовок было порядка 10 (кровельные элементы). Выход готовых составлял 97-98%.
Расчет был довольно быстрым (меньше минуты). Делал на Паскале, на 1С вычисления будут медленнее.
Для начала можно на 2-ом этапе можно попробовать жадный алгоритм: в первую очередь использовать схемы раскроя с минимальными отходами.
Можно было бы повозиться (правда, сейчас лето). Пришлите на мыло (в профиле) несколько реальных примеров.
   МихаилМ
 
12 - 28.05.21 - 13:18
+(4) https://infostart.ru/public/513444/ того же автора
   toypaul
 
13 - 28.05.21 - 13:23
решение СЛАУ (если это оно) вроде есть в 1С
   H A D G E H O G s
 
14 - 28.05.21 - 13:24
(4) Глянь почту плиз.
   Злопчинский
 
15 - 28.05.21 - 13:39
На мисте как-то было уже аналогичная тема, поройся
   ДедМорроз
 
16 - 28.05.21 - 13:40
Когда задача решается
Забывают другие факторы:
- какие-то элементы могут быть нужны раньше других,и если этого не будет,то оптимальность раскроя просто забьет склад болванками.
- динамичность заказов - в процессе выполнения могут быть добавлены другие заготовки или поменяться срочность.
Поэтому,нужно получать более менее оптимальный результат быстро и оценить возможность применения других критериев.
   d4rkmesa
 
17 - 28.05.21 - 13:47
Ага, или начальник лесоцеха сп***ит, скажет что в сердцевине дупло или грибок. Помню, на моей первой работе начальники воровали вагонами пиломатериал, а собственнику говорили, что выход 50-55% норм.
   Михаил Козлов
 
18 - 28.05.21 - 13:56
(13) СЛАУ не имеет отношение к задаче. Кстати, пробовал решение СЛАУ из платформы: удобно данные заполнять и считает быстро.
Правда на плохо обусловленной задаче (системы Ушакова) сыпется при меньшей размерности (38 против 67 Гаусса-Жордана). Но это для 1С неважно.
   Михаил Козлов
 
19 - 28.05.21 - 14:01
(0) Забыл: если нужна реализация симплекс-метода для задачи ЛП - пришлю.
   Kassern
 
20 - 28.05.21 - 14:10
(14) глянул, отписался
   Злопчинский
 
21 - 28.05.21 - 14:21
   serg999
 
22 - 28.05.21 - 17:35
(3) За книжку спасибо!

(18) Да, я понял, что через СЛАУ не решить задачу. Сейчас тоже осмотрю в сторону симплекс-метода, но у меня есть опасения насчет двух хлыстов. Не пойм как объединить две системы уравнений?

(19) Письмо отправил в почту ...
   Krendel
 
23 - 30.05.21 - 11:57
(17) да могут просто ленится думать, я видел когда просто в стружку уходит
   Михаил Козлов
 
24 - 30.05.21 - 16:48
(22) Выслал.
Какая проблема с двумя типоразмерами хлыстов?
- генерите рациональные раскрои для каждого типоразмера;
- формируете задачу ЛП по массиву сгенерированных раскроев (как во 2-ой ссылке в (0)).
   shotsdv2008
 
25 - 30.05.21 - 22:17
Фигней маетась... Если бы хлысты были все ровненькие, а так там стопятьсот всяких вариантов... Я, всё-таки, имею вышку по этому делу...
   SiAl-chel
 
26 - 31.05.21 - 07:51
(11) В каком, каком году? Там у вас яблони на Марсе то уже цветут?
   Михаил Козлов
 
27 - 31.05.21 - 10:09
(26) Промахнулся: в 1998, конечно.


Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.