|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Тема создана для обсуждения вопросов, озвученных здесь. 19091036 ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2016, 23:44 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Garya, таких задач в производстве тьма ни один БПМН это не опишет ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2016, 23:47 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
не то что б оптимизировать ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2016, 23:47 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRosGaryaЯ бы это сделал не в BPMN, а в виде WEB-службы, к которой исполнительная ядро, работающее с BPMN, обращается при вызовах из процессов. Причем, над тем, как соблюсти компромисс между быстродействием и универсальностью такой WEB-службы, нужно еще тщательно поразмыслить. Вот смотри Я тут тебе описал два метода как можно задать граф процессов 1. Статический - типа рисуешь процессы вручную 2. Динамический - типа процессыный граф формируется на основе какого то алгоритма Вопрос 1 Как вообще задавать это ограничение - т.е. длительность какого то подграфа в процессном графе (а этих подграфов там может несметное количество разных и клонов) не должно превыщать определеннное число единиц чего то Вопрос 2 - как определить, что в заданном графе вообще есть такие подграфы .... а до методов дойдем еще :)Я понимаю, о чем ты. Когда граф статический, решать оптимизационные задачи на нем проще, используя, в частности, метод ветвей и границ, который работает на статическом графе. Когда граф динамический, количество доступных методов резко сокращается. BPMN ориентирован работает на статических графах. Существует прием, который позволяет превратить динамический граф в статический. Это граф "всех возможных вариантов" - он ведь статический, не так ли? Конечно же, он может быть весьма масштабным. Такой прием нам подходит? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2016, 23:51 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
GaryaСуществует прием, который позволяет превратить динамический граф в статический. Это граф "всех возможных вариантов" - он ведь статический, не так ли? Конечно же, он может быть весьма масштабным. Такой прием нам подходит? ты представляешь размерность этого графа надеюсь :) но все ж ты не ответил как вообще задавать такие ограничения это равносильно что ты напишешь в ИНФИНЕ Критический путь граф АА <= что то? а как этот АА идентифицировать? а как найти такие АА даже в статическом графе? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2016, 23:55 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRos, Критический путь граф АА <= что то? без вопроса :) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2016, 23:56 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRosGarya, таких задач в производстве тьма ни один БПМН это не опишетВерно, BPMN не для описания динамических графов. :) Однако, с его помощью можно описать алгоритм, который работает с динамическим графом. Можно создать наборы сущностей, например, "узлы графа". С помощью BPMN можно соединять узлы ребрами или, напротив, удалять ребра графа. Можно задествовать активити "для всех ребер, с которыми состыкован данный узел выполнить оценнку длительности", причем запустить такое вычисление как параллельное. Можно сделать рекуррентные вызовы подпроцессов, которые запускают оценку по смежным узлам. Таким образом, что вычисления "бешенно распараллелятся". А для того, чтобы отработала главная идея метода ветвей и границ, можно воспользоваться в какой-то структуре, к которой имеют доступ все ветки вычислений, фиксировать наиболее оптимальные текущие полученные результаты. Откатом активити и подпроцессов можно реализовать прерывание "раскрашивания графа", длина которого вышла за пределы текущего наиболее оптимального. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:03 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
GaryaViPRosGarya, таких задач в производстве тьма ни один БПМН это не опишетВерно, BPMN не для описания динамических графов. :) Однако, с его помощью можно описать алгоритм, который работает с динамическим графом. Можно создать наборы сущностей, например, "узлы графа". С помощью BPMN можно соединять узлы ребрами или, напротив, удалять ребра графа. Можно задествовать активити "для всех ребер, с которыми состыкован данный узел выполнить оценнку длительности", причем запустить такое вычисление как параллельное. Можно сделать рекуррентные вызовы подпроцессов, которые запускают оценку по смежным узлам. Таким образом, что вычисления "бешенно распараллелятся". А для того, чтобы отработала главная идея метода ветвей и границ, можно воспользоваться в какой-то структуре, к которой имеют доступ все ветки вычислений, фиксировать наиболее оптимальные текущие полученные результаты. Откатом активити и подпроцессов можно реализовать прерывание "раскрашивания графа", длина которого вышла за пределы текущего наиболее оптимального. Во первых это твои мечты :) Во вторых каждый активити - это минимум поток процессор во третьих - это программирование :) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:06 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ты будешь ждать до окончания времен, даже если можешь этот танец спроектировать на чем нить (думаю они просто упадут) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:08 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
а как задать ограничение, как нить подумай ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:09 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRosViPRos, Критический путь граф АА <= что то? без вопроса :)"Критический путь" и "оптимальный путь" - разные вещи. Тот факт, что у тебя есть "критический" - это не просто хорошо, это суперотлично. :) Если время расчета ограничено, а граф имеет колоссальную размерность (а с граф возможных вариантов наверняка именно так и есть), можно искать не самое оптимальное решение, а близкое к оптимальному, которое укладывается в заданные ограничения. Заданное ограничение, например, предельно допустимое максимальное время выполнения от начала и до конца. Алгоритм будет "раскрашивать" ребра графа возможностей и "отбрасывать" те из них, которые вышли за пределы, во-первых, заданного ограничения, во-вторых, текущего частно-оптимального решения. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:11 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Garya, для этого надо сначала построить очень много графов - это неприемлемо на самом деле вообще надо сначала уточнить - выполнимо ли ограничение вообще в обозримом будущем я ж снял доп мильен ограничений (есть ли ресурс, есть ли мощности,,,) что бы вообще когда нибудь такое ограничение сработало конечно - первым делом надо найти такой граф (что ты отвергаешь, как его идентифицировать :)), вычислить критический путь (и - там могут быть много таких входов с разными сроками межпроцессного хранения) хотя бы в идеальном случае (без учета доругих ограничений). а то может воще не стоит эту задачу рассматривать потом надо рассмотреть все такие граф в иделаьном случае - на совместимость а потом токо можно попробовать что то посчитать (и то надо все время уметь остановится) но самое интересное что все эти задачи легко сводятся к другим - более простым задачам :) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:20 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Задам другой вопрос У тебя есть БД - много там отношений - табличек в одном из них , например в Строке накладной есть два таких свойства Материал и Единица измерения какой(ие) алгоритм(ы) предложишь для поиска максимально подходящего значения одного в зависимости от значения другого ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:23 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRosGaryaпропущено... Верно, BPMN не для описания динамических графов. :) Однако, с его помощью можно описать алгоритм, который работает с динамическим графом. Можно создать наборы сущностей, например, "узлы графа". С помощью BPMN можно соединять узлы ребрами или, напротив, удалять ребра графа. Можно задествовать активити "для всех ребер, с которыми состыкован данный узел выполнить оценнку длительности", причем запустить такое вычисление как параллельное. Можно сделать рекуррентные вызовы подпроцессов, которые запускают оценку по смежным узлам. Таким образом, что вычисления "бешенно распараллелятся". А для того, чтобы отработала главная идея метода ветвей и границ, можно воспользоваться в какой-то структуре, к которой имеют доступ все ветки вычислений, фиксировать наиболее оптимальные текущие полученные результаты. Откатом активити и подпроцессов можно реализовать прерывание "раскрашивания графа", длина которого вышла за пределы текущего наиболее оптимального. Во первых это твои мечты :) Во вторых каждый активити - это минимум поток процессор во третьих - это программирование :)Ты трижды прав. :) Я говорю о том, что BPMN, в том случае, если задействуется как технология распараллеливания вычислений, может распараллелить их в груде таких задач, в которых прежде традиционно распараллеливание не использовалось (ну, например, в том же методе ветвей и границ обычно работает традиционный цикл последовательного перебора). А то, что для каждого из такого вычисления потребуется отдельный поток - это верно. Но с учетом, что компьютеры стремятся к многопроцессорной, многоядерной архитектуре, и при том каждое из ядер может отрабатывать в режиме разделяемого времени множество потоков вычислений, сама технология высокоэффективного распараллеливания вычислений может "рвануть". Компьютеры могут стать и тысяче-процсессными и миллионо-ядерными... Просекаешь, о чем я? А если еще заложить и специальные процессные низкоуровневые инструкции для диспетчеризации потоков вычислений, да завязать их с BPMN-подобными средствами в операционных системах, которые в свою очередь транслируются на любой высокий уровень, мы получаем бесконечно-масштабируемую вычислительную архитектуру с бесконечными возможностями для распараллеливания вычислений. Да, это мечта... Но она ведь и может воплотиться, не так ли? :) А то, что это программирование - ты тоже прав. Только, в отличие от последовательных блок-схем алгоритмов такой подход предлагает новые технологии параллельных алгоритмов с изначально заложенными в алгоритмической нотации правилами диспетчеризации параллельных потоков. Просекаешь себе возможности! Это ж революция на ровном месте! Да каких масштабов... Я когда понял, что идеи, заложенные в BPMN, можно транслировать из сферы управления бизнес-процессами в сферы совершенно другого плана, был сам ошарашен. Мне только удивительно, что ошарашило лишь меня. Либо другие ошарашенные тщательно скрывают, что их тоже ошарашило, и сидят там втихомолку что-то уже реализовывают такого плана... ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:28 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
GaryaЯ когда понял, что идеи, заложенные в BPMN, можно транслировать из сферы управления бизнес-процессами в сферы совершенно другого плана, был сам ошарашен. Мне только удивительно, что ошарашило лишь меня. Либо другие ошарашенные тщательно скрывают, что их тоже ошарашило, и сидят там втихомолку что-то уже реализовывают такого плана... Она ошарашила тебя совей псевдодоступностью и визуализацией :) (уже больше 50 процессов (да и не только, любой граф с больше чем 50-100 узлами) уже не воспринимается мозгами а теперь подумай об издели с 100 000 деталями, от 5-50 операциями на деталь и таких изделий много и 1000ами станков людей материалов и т.д. и плюнь на свой БПМН :) параллельное программирование не нуждается в БПМН (есть много технологий гридкомпьютинг), во всех новых технологиях есть отличные Фреймворки для параллельного программирования, есть просто языки на них заточенные и т.д. у нас есть комп с 800 процессорами - это не панацея ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:38 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRosа как задать ограничение, как нить подумайТак что тут думать? Ограничения для частично-оптимального решения: "Для участка от A до B время выполнения не более 5 часов." Ограничение для ресурса:"Задействуется ресурс не более 1 раза на интервале в 1 минуту" и "ресурс работает с 8 утра до 20:00 только по рабочим дням". Если нужно решить оптимизационные задачи, как распределить ресурс между множеством процессов, то можно "поженить" метод ветвей и границ с методами линейного программирования. В этой книжке есть классные примеры, как это можно сделать. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:40 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
GaryaViPRosа как задать ограничение, как нить подумайТак что тут думать? Ограничения для частично-оптимального решения: "Для участка от A до B время выполнения не более 5 часов." Ограничение для ресурса:"Pадействуется ресурс не более 1 раза на интервале в 1 минуту" и "ресурс работает с 8 утра до 20:00 только по рабочим дням". Если нужно решить оптимизационные задачи, как распределить ресурс между множеством процессов, то можно "поженить" метод ветвей и границ с методами линейного программирования. В этой книжке есть классные примеры, как это можно сделать. Для участка от A до B время выполнения не более 5 часов :) а может там много таких участков? а может какой то участок в другом заводе? это не математическое ограничение у тебя есть модель Процесса Вход - Процесс - Выход - Поток - Вход - Процес .... ты должен составить математическое выражение для ограничения ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:47 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Да ладно, я ж не тебя экзаменую, я тебя давно знаю, захочешь - решишь просто меня бесит это тупое упрямство уделать 1С на его поле :) миллион не разрешенных, востребованных задач особенно на семантическом поле, всякие задачи на морфизмы. сводимость, идентифицируемость и т.д. а они все пытаются луку п. автоматизировать :( ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:50 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
захочешь - решишь любую задачу хоте сказать, а не то о чем говорили ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 00:51 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRos, Я, видимо, как-то невнятно объясняю... Есть описания графов, а есть описания алгоритмов действий. Это немного разные вещи. Классически в программировании алгоритм изображается блок-схемой, чем-то вроде такого: Классический подход для таких алгоритмов базируется на последовательном прохождении операций. BPMN - это тоже, по сути, описание алгоритма действий. Только "заточено" такое описание под описание бизнес-процессов. Однако, роднит его с "вычислительным" алгоритмом одна существенная деталь - и то, и другое ориентировано на возможность его исполнения с применением компьютера. Так вот, по сути "действие", "активити", "элементарая операция" в алгоритме - не так уж важно, что конкретно делает. Важно, что в BPMN появляется возможность: 1) Обработки ошибок 2) Настраиваемой компенсации (отката) действий (например, действие A:=A+B, которое уже выполнилось, можно компенсировать-вернуть посредством действия A:=A-B). 3) Возможность "вызова" под-алгоритмов (подпроцессов), в том числе, рекуррентного. 4) Возможность распараллеливания действий, при этом на схеме весь набор распараллеленных потоков изображается как одно действие. Далее "пучок" распараллеленных потоков, выполняющихся в схожей логике, при необходимости, можно собрать в одной точке, либо дождавшись "одного победителя" (по заданным критериям), либо всех, кто был запущен на параллельное выполнение. 5) Возможность обмена информацией относительно слабо связанных между собой алгоритмов, нацеленных на решение разных задач и работающих в разных собственных ритмах (посредством "слабых" связей и "хореографии") Помимо собственно нотации как таковой в пул идей заложена также технология управления изменениями этого самого алгоритма. Она подразумевает возможность изменения алгоритма непосредственно в процессе его исполнения . То есть, у тебя уже запущены какие-то потоки (например, вычислений). Ты можешь изменить алгоритм, не останавливая их ! На ходу! При этом запущенные "до изменения" потоки "подружатся" с потоками, которые возникнут "после изменения". Где вы такое видели, в каких средах разработки? Вы можете мешать бетон уже построенного дома и придавать ему новую форму, и при этом ранее построенный дом не обрушится! Лично для меня это звучит как фантастика. Во всей это "вкусняшке" я не вижу, однако, одной вещи, которая, возможно, тебя более всего беспокоит - возможности алгоритму динамически генерить самого себя. Это упущение, возможно, будет устранено в последующих редакциях нотации. А может быть и нет... :) Так вот я о чем! Я сравниваю с принципами традиционного описания АЛГОРИТМОВ, а не графов. А про графы - это отдельная песня. Если граф можно формализовать (а для твоих задач, я полагаю, его можно формализовать), то его описание можно сгенерить алгоритмом. А уж в какой нотации будет описан алгоритм, это дело десятое... :) ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 01:17 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
ViPRosЗадам другой вопрос У тебя есть БД - много там отношений - табличек в одном из них , например в Строке накладной есть два таких свойства Материал и Единица измерения какой(ие) алгоритм(ы) предложишь для поиска максимально подходящего значения одного в зависимости от значения другогоМаксимально подходящего по каким критериям? Я подозреваю, о чем ты... Для дискретных производств обычно вводят "минимальный размер партии" - своеобразный квант, неделимый атом... :) Вот до него всё и раскладывается. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 01:22 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Отсюда 19091055 :ViPRosа ведь это просто Пролеживаемость детали :) Срок годности :) Пролеживаемость детали просчитывается на каждой операции исходя из размеров партий. Размер партий все определяет. Запустил партию в работу - всё, пока она не будет обработана, ни на что другое ресурс не отвлекается. Вроде бы, пустяк, о сильно всё упрощает: 1) Размер партии = const 2) Партия атомарна, то есть, всегда обрабатывается целиком. Если эти два условия нарушатся, теоретически, можно найти более оптимальные варианты последовательностей действий. Вот только рассчитать их НЕ на квантовом компьютере, полагаю, даже для простых производств будет нереально. Потому на некоторые допущения приходится идти. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 01:39 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
Garya, Размер партии - это суть оптимизации только его и ищут - оптимального размера партии запуска, а у тебя он константа :) эх ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 02:29 |
|
Оптимизационные задачи на графах
|
|||
---|---|---|---|
#18+
GaryaViPRosЗадам другой вопрос У тебя есть БД - много там отношений - табличек в одном из них , например в Строке накладной есть два таких свойства Материал и Единица измерения какой(ие) алгоритм(ы) предложишь для поиска максимально подходящего значения одного в зависимости от значения другогоМаксимально подходящего по каким критериям? Я подозреваю, о чем ты... Для дискретных производств обычно вводят "минимальный размер партии" - своеобразный квант, неделимый атом... :) Вот до него всё и раскладывается. не это задача в лоб именно если задано значение одного допустим - Бетон, надо искать допустим - Тонна вот как узнать что Тонна подходит больше или воще только Тонна и подходит ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2016, 02:31 |
|
|
start [/forum/topic.php?fid=29&msg=39221960&tid=1525809]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
39ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
66ms |
get tp. blocked users: |
2ms |
others: | 13ms |
total: | 164ms |
0 / 0 |