Оптимизация загрузки станков

← →
Petr V. Abramov (not at home) (2006-11-26 13:47) [0]

Есть наверняка стандартная задача, прошу помочь найти ее формальную постановку. Итак:
Есть N станков и M видов товаров (M > N), каждый из которых может быть произведен на любом станке, производительность одинаковая. Поступают заказы на производство, на несколько дней вперед. Перевод станка с выпуска одного вида продукции на другой требует времени + сопровождается другими затратами, запуск-остановка станка - еще более дорогостоящая операция (на самом деле "станок" - довольно сложный автомат немалых размеров и производительности).
Продукция поступает на склад, откуда может быть либо продана, либо поступить на дальнейшую обработку (на других станках).
Необходимо: оптимизировать (уменьшить) количество переходов продукции в рамках станка + уменьшить время ожидания заказа клиентом.
Сильно подозреваю, что задача не мне первому пришла в голову :), поэтому наверняка есть ее формальная постановка. помогите найти, кому не сложно.

← →
antonn © (2006-11-26 14:00) [1]

эту задачу изучают в институте "Планирование производства" (см. Производственная программа, Последоватеная/паралельная организация производства)

← →
antonn © (2006-11-26 14:01) [2]

+[1]
просто конспекты я посеял, а советовать по памяти, не зная абсолютно точно, на этом сайте стало "нервонебезопасным" :)

← →
Petr V. Abramov © (2006-11-26 20:49) [3]

да ладно, похожие слова - лучше, чем никаких :)
> на этом сайте стало "нервонебезопасным" :)
да ладно, в случае чего, в RO пойду я :)

← →
Desdechado © (2006-11-26 21:31) [4]

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

← →
Petr V. Abramov © (2006-11-26 21:33) [5]

> у Таха есть.
у кого-кого? :)))

← →
Sergey Masloff (2006-11-26 22:04) [6]

Petr V. Abramov © (26.11.06 21:33) [5]
Хемди А. Таха "введение в исследовыание операций" ISBN 5-8459-0740-3
седьмое издание Вильямс переиздавал в 2005 г. но книжка старая наверняка в библиотеках есть потому что очень распространенная была

← →
Petr V. Abramov © (2006-11-26 22:16) [7]

дай почтать :)
мне решение-то не нужно, мне сама постановка формальная. потому что там еще тонкостей, которые тут не перечилишь (особенно учитывая, что завязывается обратной связью на резервирование готовой продукции), чтоб хоть как-то начать формализовать, а КВАЛИФИЦИРОВАННЫХ решателей задач - их есть, только они все умные очень, каждый по-своему.
P.S.
> Sergey Masloff
в Excel`е сие пр-во не считается :))))

← →
Sergey Masloff (2006-11-26 22:18) [8]

Petr V. Abramov © (26.11.06 22:16) [7]
Попробую найти... У меня была но дома что-то не вижуможет на работе валяется. А так без проблем.

← →
Petr V. Abramov © (2006-11-26 22:35) [9]

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

← →
Petr V. Abramov © (2006-11-26 23:15) [10]

кто чем может, поможите, на случай, если Sergey Masloff книжку не даст... :))))

← →
Юрий Зотов © (2006-11-26 23:40) [11]

> Petr V. Abramov © (26.11.06 23:15) [10]

Петь, если подходить строго, то все оптимизационные задачи решаются одинаково - составляется целевая функция и находится ее минимум (или максимум - смотря, как она составлена).

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

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

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

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

← →
Petr V. Abramov © (2006-11-26 23:58) [12]

> Юрий Зотов © (26.11.06 23:40) [11]
конечно, ты, как и просилось в сабже, формально поставил :)
но вопрос в том, чтобы выбрать тот частный случай, который подойдет (у меня не НИИ высоких исследований).
В том, что этот частный случай кто-то уже формализовал, у меня сомнений нет
с методикаи не спорю, но, в данном случае, явно кто-то уже ходил по граблям, хочется посмотреть отчет о шишках

← →
Юрий Зотов © (2006-11-27 00:30) [13]

Обзываем станки продавцами (это серверы), а заказы - покупателями (это входная очередь). Получаем задачу об универмаге, которая решена в книге Рихтера ("Windows для профессионалов", 3-е издание) и там же есть готовая программа, моделирующая процесс обслуживания. Нужно только прикрутить выходную очередь (склад готовой продукции).

← →
Petr V. Abramov © (2006-11-27 00:42) [14]

> Юрий Зотов © (27.11.06 00:30) [13]
> Получаем задачу об универмаге
не читал Рихтера (к сожалению), но аналогия с универмагом не катит. В качестве элемента есть задача с сортиром из Таденбаума (если правильно фамилию пишу), которую Игорь Шевченко тут приводил в преданьях старины далекой. Остальное - не то. Но явно, если решить, будет удар со стороны классиков :))))

← →
antonn © (2006-11-27 01:07) [15]

Petr V. Abramov ©
может не поможет, но гляньте: http://www.technologics.ru/program/info/text_18126.html?page=5

← →
antonn © (2006-11-27 01:09) [16]

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

← →
Petr V. Abramov © (2006-11-27 01:15) [17]

> antonn © (27.11.06 01:09) [16]
курсовые технарей
это идея, но толькос тз списка лит-ры с конце. а а то я сам технарь, страницку-другую че-нить :) напишу :)
> antonn © (27.11.06 01:07) [15]
завтра гляну, спасибо, пиво :)

← →
antonn © (2006-11-27 01:15) [18]

вот еще неплохой пдф"чик http://www.grsu.by/data/resources/catalog/63778.pdf
:)

← →
Германн © (2006-11-27 01:32) [19]

> Petr V. Abramov © (27.11.06 01:15) [17]
>
> > antonn © (27.11.06 01:09) [16]
> курсовые технарей
> это идея, но толькос тз списка лит-ры с конце. а а то я
> сам технарь, страницку-другую че-нить :) напишу :)
> > antonn © (27.11.06 01:07) [15]
> завтра гляну, спасибо, пиво :)
>

Это правильная идея, имхо. Лучше завтра. :-)

← →
Petr V. Abramov © (2006-11-27 23:12) [20]

похоже, задача перебором хоть на PL/SQL решается (хотелось бы верить :).
оказывается, есть "идеально-оптимальный" план в рамках станка. Правда, оказалось, что и производительность от разных обстоятельств зависит (не от товара :)
Всем, по-любому, спасибо

← →
Юрий Зотов © (2006-11-27 23:19) [21]

> похоже, задача перебором хоть на PL/SQL решается

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

← →
Petr V. Abramov © (2006-11-27 23:24) [22]

> Юрий Зотов © (27.11.06 23:19) [21]
станков в пределах десятка. переходов в "идеально-оптимальном" плане - десяткИ (с учетом вариаций) В принципе за несколько часов начальник справляется, просто это регулярно очень делать надо для достижения эффекта.
Не развеивай мой оптимизм :)))))))

← →
Petr V. Abramov © (2006-11-27 23:26) [23]

понятно, что подход в общем случае не лучший, но на данном заводе его хватит на несколько уровней его развития :)
наверное :)

← →
Sergey13 © (2006-11-28 09:59) [24]

> [23] Petr V. Abramov © (27.11.06 23:26)

Я до рашания этой задачи не дошел в свое время, только прощупывал/приглядывался/выспрашивал предполагаемых пользователей. Создалось впечатление, что она практически не решаема. И если даже решить ее, то тот-же мастер вряд ли сможет воспользоваться ее плодами. Шибко много случайных факторов, учесть которые не представляется возможным, но которые могут поставить крест на самых правильных результатах. Например выход из строя станка, отсутствие сырья, заготовок, инструмента, работника и т.д. и т.п. Поэтому для себя на перспективу мы думали ограничиться просто вычислением коэффициента загрузки по группе обрудования по программе выпуска на период.

← →
PEAKTOP © (2006-11-28 10:25) [25]

> Есть N станков и M видов товаров (M > N), каждый из которых может быть произведен на любом станке ....
Это называется "оперативное управление производством и диспетчеризация".

Из собственной практики внедрения ERP - эта задача теоретически не решается в принципе, потому, что ... если даже решить ее, то тот-же мастер вряд ли сможет воспользоваться ее плодами. Шибко много случайных факторов, учесть которые не представляется возможным, но которые могут поставить крест на самых правильных результатах.

Зато практически решается на ура путем применения Интерактивных диаграмм Гантта (например, они входят в поставку TeeChart v6.0). Интерактивные диаграммы Гантта - я имею в виду то, что этот визуальный объект может не только отображать диаграмму, а и позволяет двигать в ней узлы.
Исходные данные:
1) Отдельное должностное лицо, которое занимается планированием загрузки на смену, назовем его диспетчером.
2) Производственная программа на смену в виде количества операций, операции имеют свою продолжительность во времени.
Решение:
Строится НЕПРАВИЛЬНАЯ диаграмма Ганнта, где все операции стартуют в одно время на одном станке. Диспетчеру остается только "подвигать" по диаграмме "прямоугольники" (оперативные циклы), чтобы все операции были выполнены, при этом желательно на меньшем количестве станков (чтобы мастеру i-го станка сегодня на смену не выходить и зарплату ему не платить). Диспетчер и является этим оптимизатором, который учитывает все тонкости планирования (2-й станок глючит, на 5-м станке работают до обеденного перерыва и т.д.)

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

> но которые могут поставить крест на самых правильных результатах
пересчитать в новых условиях?

> при этом желательно на меньшем количестве станков
здесь немного не так: включить/выключить станок дороже, чем мастеру заплатить.

Кстати, неплохую линку тебе дали
http://www.technologics.ru/program/info/text_18126.html?page=5

Вот они (разработчики) тоже пошли этим же путем - через оперативное планирование. Посмотри скриншоты их ПО, там вот как раз самописная диаграмма Гантта.

Это тебе в SAP системы, в частоности APO (DP + SNP + PP/DS)

Можно на R/3, можно IBN (pmbox.ru)

Внедренцев такого класса в СНГ на R/3 - меньше пальцев на паре рук.

А не из теории ли это массового обслуживания задача?

Юрий Зотов правильно сказал. Это высшая математика раздел Линейное программирование (к софту не имеет никакого отношения)). Насколько помниться, там строиться граф процесса, потом находятся все пути, по путям строится матрица коэфицентов (фактически это система линейных уравнений), потом описываем целевую ф-цию, а дальше чистая математика считаем матрицы. У microsoft даже была программа под DOS которая занималась решением этих матриц. Вроде бы это еще с тех пор когда Билли занимался оптимизацией дорожного движения. Мы на этой программе лабы считали. Но хоть убей не помню как она называлась)) где-то дома валяется...

> а дальше чистая математика считаем матрицы.

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

Но если не ошибаюсь, когда в задачи изменяется сразу несколько критериев оптимизации, то она переходит в разряд задач динамического программирования, а там мат аппарат невероятно сложный и обычно их решают методом моделирования. Т.е. описывают алгоритм и гоняют перебором интуитивно ограничевая параметры системы в предполагаемой области решения...
Можно конечно описать алгоритм функционирования системы на Delphi, C++, но есть уже готовые среды для прогона моделей, например GPSS. Это полноценный язык моделирования систем массового обслуживания. В нем уже есть готовые объекты очереди, устройства обслуживания с описываемыми вероятностными ф-циями, задержки, буферы, вероятностные переходы, и т.д. Т.е. все то, что прийдется описывать самому, если писать это на Delphi или С++. Тут уже встает непростой выбор (в зависимости от сложности задачи и точности полученного результата) что быстрее написать самому или изучить уже созданный язык. GPSS например несложный, есть визуальныя среда бесплатная для студентов, примеры, хелп...
Я просто на GPSS диплом писал, хотя до этого с ним вообще не сталкивался.
Изучал где-то пару недель. На дельфи бы описывал модель гораздо дольше и не факт, что она бы расчитывала правильный результат...
Кроме GPSS есть еще несколько языков моделирования так что выбор есть.

Jeer © (28.11.06 10:58) [29]
а удачных внедрений, подозреваю - еще меньше :)
задача с учетом [20] переформулируется след. образом:
есть N станков, M товаров, и коммерческий директор, который из лучших соображений тасует заказы, как ему хочется :) при этом есть оптимальная последовательность переходов товара для станка, и, что радует - зацикленная, т.е. т0->т1->...->тN->т0. есть среднесрочный план выпуска, исходя из которого можно загрузить станки тривиальным образом. Есть текущие задания для станков.И тут начинает работу коммерческий директор.
Задача: держать план переходов максимально близким к оптимальному (т.е. в идеале не переходить вообще, а если переходить - то по схеме переходов, на максимально близкий товар), пока в результате над ним издевательств он не станет "ну совсем плохим" (опеределить критерии), и начать планировать заново, начиная с тривиального.

P.S.
а как с виду просто шлепать разноцветных лягушек :))))

Оптимизация загрузки станков Найти похожие ветки