Задача на минимизацию остатков

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

В компании по производству стальных труб есть набор базовых элементов с длиной 11800см, которые можно разрезать и использовать для сварки.
Поступил заказ на Nое количество труб с разными длинами. Каждая такая труба может состоять из нескольких блоков, но блок должен быть не менее 1100см. Задача определить оптимальное деление базовых элементов, чтобы составить все трубы с минимальным количеством обрезков.

Пример:
Требуется сделать трубы с длинами:
1) 11000
2) 15000
3) 9000

Общая необходимая длина = 11т + 15т +9т =35т
35000 / 11800 = 2.966. Значит, что мне достаточно взять 3 базовых элемента.
В идеальном случае минимальный остаток будет: (3-2.966)*11800 = 400
Вопрос: Какие деления базовых элементов делать и как их разделять по трубам, чтобы максимально приблизится к идеальному остатку?

Если на трубу1 я беру 11000, то остается 800. 800 < 1100, поэтому я не могу брать его в дальнейшее использование и 800 сразу идет в обрезки. Значит такое деление уже не оптимально!

Делаем так:
нб - взяли новый блок
ос - взяли из остатков
1) 9900 (нб) + 1100 (нб) = 11000 (в остатках 1900 и 10700)
2) 10700 (ос) + 4300 (нт) = 15000 (в остатках 1900 и 7500)
3) 7500 (ос) + 1500 (1900 порезали на 1500 и 400) = 9000 (в остатках 400)
То есть мы получили лучшее решение.

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

0

offtopic: 11800 -- это все-таки миллиметры... Ну сами представьте себе трубу длиной 118 метров...

Судя по всему, это задача на многокритериальную оптимизацию. И для начала нужно эти критерии четко определить. Потому что к примеру минимум обрезков - это одно, а минимальная суммарная длина обрезков - уже другое.

Вы же как-то очень постепенно излагаете условия задачи... Сперва у вас есть только базовые трубы, потом вдруг обнаруживается склад с остатками... Есть подозрение, что дальше еще возникнет условие минимизировать сварные операции, потому что они стоят дороже обрезков.

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

1

Из примера непонятно - зачем 1900 резать на 1500 и 400, если можно для 1500 взять новый блок, а 1900 складировать до следующего заказа, избежав при этом потери 400?

0

Сообщение от renat_dmitriev Из примера непонятно - зачем 1900 резать на 1500 и 400, если можно для 1500 взять новый блок, а 1900 складировать до следующего заказа, избежав при этом потери 400?

Все верно, можно. Просто у нас всего 3 трубы и эта была последняя, поэтому я не беру новый блок, чтобы не тратить материал.

Добавлено через 9 минут

Сообщение от vantfiles И для начала нужно эти критерии четко определить

В идеальном случае хотелось бы минимизировать остатки и количество блоков на трубу (сварные операции).

Сообщение от vantfiles Потому что к примеру минимум обрезков - это одно, а минимальная суммарная длина обрезков - уже другое.

Наверное, я говорил про суммарное количество обрезков

0

Kertis138, Тогда задача предельно простая: ищете можно ли использовать ровно 11800, если нет, то отрезаете вплоть до 11800 - 1100, то есть до 10700, а остаток идет на следующую трубу и т.д. до бесконечности. Если какая-то труба последняя, ну значит выхода нет и если обрезка составляет меньше 1100, значит никуда не денешься.

1

Сообщение от renat_dmitriev Тогда задача предельно простая: ищете можно ли использовать ровно 11800, если нет, то отрезаете вплоть до 11800 - 1100, то есть до 10700, а остаток идет на следующую трубу и т.д. до бесконечности. Если какая-то труба последняя, ну значит выхода нет и если обрезка составляет меньше 1100, значит никуда не денешься.

А если больше 11800?
Например, 12000. Я могу либо взять 11800 и оставить 200 в остатках или же взять 2 блока и отрезать 7000 и 5000, а остатки пустить на другие трубы

0

Kertis138, Немного засомневался в написанном выше...Уточняющий вопрос: у вас заказаны трубы на 6200 и 6200, вы бы предпочли их отрезать из одной заготовки и потерять 400, но зато ничего не надо сваривать, либо отрезать 6200 и 4500 от одной трубы, и 1700 от следующей, ничего не теряя(остатки годны для других заказов), но зато будет лишняя сварка.

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

Добавлено через 3 минуты

Сообщение от Kertis138 Например, 12000. Я могу либо взять 11800 и оставить 200 в остатках

В данном случае остатка не будет, 200 придется отрезать от следующей трубы, или точнее говоря взять 10700 от текущей и 1300 от следующей. Но я вас понял, если трубы больше 11800, то да, будет немного по другому.

Вообще трубы больше 11800 можно оставлять на потом. Поскольку их все равно нужно разрезать, то их можно скомбинировать с любой трубой которая меньше 10700, дополнив до 11800, а если будут две такие трубы, то вообще прекрасно.

1

на первом месте минимизация остатков. Чем меньше, тем лучше. 14 труб за час - очень много. Их может быть больше 150

Добавлено через 1 минуту
Есть один из вариантов от проектировщиков. Но я не смог понять, какие остатки получились, и какая логика была при делении.
То есть они на каждую трубу брали 2 куска

Нужная длина - Сегмент 1 - Сегмент 2
18600 9700 8900
18600 9700 8900
18600 11700 6900
18600 11700 6900
18600 11700 6900
18600 11700 6900
18600 9700 8900
18600 9700 8900
18600 11700 6900
18600 11700 6900
18600 11700 6900
18600 11700 6900
18600 9700 8900
18600 9700 8900
18600 9700 8900
18600 11700 6900
18600 11700 6900

0

Kertis138, Если на первом месте оптимизация остатков, то как я написал, безостаточный алгоритм вполне прост - если нельзя использовать все 11800, то отрезаем не больше 10700, а 1100 используем для следующих деталей. Здесь нет разницы больше или меньше 11800 длина трубы. Так что вопрос только в оптимизации числа разрезов и здесь нужно подумать и поанализировать.

1

renat_dmitriev, "...то отрезаете вплоть до 11800 - 1100, то есть до 10700, а остаток идет на следующую трубу..."

Не все так просто...
Допустим у нас нет остатков, только исходные трубы 11800 -- и поступает заказ на одну трубу длиной 11100
Из условий видно, что нам придется отрезать по куску от двух исходных труб, но:
(10700 + 400) -- не получается, довесок не может быть короче 1100

А вот дальше встает вопрос критерия - как резать эти два куска, потому что длина первого куска L1 должна быть в диапазоне:

1100 < L1 < 10000

и соответственно длина второго куска L2 = 11100 - L1

Что выгоднее -- (10000 + 1100) или (5550 + 5550 ) ?.. или проще отрезать так -- (6000 + 5100) ?

Добавлено через 1 час 0 минут
В общем, тут получается три варианта - 1) заказы до 10700, 2) заказы от 10700 до 12900, 3) свыше 12900

Чисто интуитивно - нельзя отрезать кусок больше 9600 -- то есть больше, чем 11800 - 2*1100 -- но объяснить не могу...

1

vantfiles, Мне кажется вы абсолютно правы, и куски в интервале от длина_заготовки - 2200 и возможно длина_заготовки + 2200 лучше не отрезать, а взять другой кусок. Соответственно куски от 9600 до 14000 нельзя использовать в начале и нельзя оставлять на конец, на них нужно расходовать уже отрезанные трубы, чтобы не попадать в этот интервал. Но по хорошему надо запустить тесты с перебором для 12 рандомных позиций и все станет ясно.

Добавлено через 36 минут
Да, все верно, кажется все встало на свои место. Сформулировать можно так:

ДЗ - длина заготовки
МБ - минимальный блок
СПО - сумма длин предыдущих обрезков
ДК - длина очередного куска

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

ABS(ДЗ + СПО - ДК) не равен 0, но меньше МБ, потому что в этом случае придется делать лишний разрез. В этой ситуации нужно брать другой кусок, а потенциально опасные куски от ДЗ - МБ до ДЗ + МБ (не включительно) не оставлять на конец, а дополнять ими уже отрезанные

Пример:
Пусть у нас 3 куска 8200 15000 и 17000

1. Отрезаем 8200, обрезка 3600 (первый кусок закончен)
2. 3600 используем для второго куска, еще для второго куска нужно 11400
3. 11400 отрезать не можем, поэтому отрезаем 10300, обрезка 1500
4. Отрезаем 1100 от новой заготовки, обрезки 1500 и 10700
5. Используем обрезки для третьего куска, еще для третьего куска нужно 4800
6. Отрезаем 4800, обрезка 7000. Дело сделано.

Итого получаем 4 отрезания и 4 сварки(по 2 на второй и третий кусок)
Соответственно на втором куске у нас не выполняется условие, получив одну обрезку, он вернул 2.
Пробуем поменять местами 2й и 3й кусок

1. Отрезаем 8200, обрезка 3600 (первый кусок закончен)
2. 3600 используем для второго куска, еще для второго куска нужно 13400
3. Используем целую заготовку(11800), еще для второго куска нужно 1600
4. Отрезаем 1600 от новой заготовки, обрезка 10200, второй кусок закончен
5. Используем 10200 для третьего куска, еще нужно 4800
6. Отрезаем 4800, обрезка 7000. Дело сделано.

Итого: 3 отрезания и 3 сварки (2 на второй кусок, 1 на третий)

Что и требовалось доказать... =)

Естественно, если есть кусок, чья длина равна длине обрезки, то использовать нужно его по принципу чем меньше обрезок после куска тем лучше.

1