Синтез расписаний

Важным и обширным множеством приложений, в которых для синтеза целесообразно применять генетические алгоритмы, является планирование производства и распределение ресурсов, включая задачи проектирования технологических процессов производства изделий. Возникающие здесь задачи можно трактовать как задачи синтеза расписаний. Другими примерами приложений генетических методов синтеза могут служить компоновка и размещение оборудования, диспетчирование потоков работ, распределение частот в радиоканалах сетей мобильной связи, проектирование подвески автомобиля и др. [c.205]

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

Если структура хромосомы однородная в том смысле, что все проектные параметры, отображаемые генами, относятся к одной и той же классификационной группе в контексте решаемой задачи, то целесообразен одноточечный кроссовер. Когда гены могут быть сгруппированы по одному признаку (например, по принадлежности к определенным конструктивным блокам) и упорядочены в группах по другому признаку (например, по физическому смыслу), то более эффективным может оказаться многоточечный кроссовер, при котором по одной точке разрыва приходится на каждую группу. Конкретный пример многоточечного кроссовера будет приведен далее при рассмотрении задачи синтеза расписаний для многостадийных процессов. [c.216]

В НСМ используется возможность декомпозиции исходной задачи синтеза на ряд частных задач (подзадач). В исходной задаче требуется найти значения структурных параметров х.еХ, при которых целевая функция F(X) принимает экстремальное значение. При этом предполагается известной модель приложения, позволяющая оценивать значения целевой функции F(X). В к-к подзадаче определяются значения одного или нескольких структурных параметров, составляющих подмножество Х с X. Частные задачи решаются значительно проще общей задачи, обычно это задачи оптимизации малой размерности с локальными целевыми функциями (X ), Х с X. Например, в общей задаче синтеза расписаний частная задача - назначение для очередной работы обслуживающего сервера и определение ее положения во времени. [c.221]

Сокращаются размеры поискового пространства, а следовательно, повышается эффективность поиска, выражаемая как точностью, так и скоростью приближения к искомому результату. Действительно, мощность множества возможных альтернатив в НСМ равна V", где v - число эвристик, п - число генов. В то же время, например, в одностадийной задаче синтеза расписаний, рещаемой обычными генетическими методами, мощность множества альтернатив находится в диапазоне от и до л -с", где с - число серверов. Конечно, набор эвристик в НСМ должен быть разумным, иначе экстремум может оказаться вне пределов сокращенного пространства. [c.223]

Задачам синтеза расписаний (ЗСР) посвящено большое число работ, в том числе и по генетическим алгоритмам синтеза. ЗСР заключается в распределении заданного множества работ во времени и между исполнителями (в пространстве). [c.224]

Многостадийная задача синтеза расписаний, рассматриваемая далее, характеризуется следующими данными [c.226]

Если прогнозируется получение решения с нарушением ограничений, приводящим к незначительным штрафам, то отбор эвристик в задачах синтеза расписаний следует проводить, ориентируясь на значения 2 (табл. 2.2). В противном случае нужно усиливать роль эвристик с временной ориентацией. В задаче N25 прогноз благоприятен, и в набор были включены эвристики Э , и Э . При этом целесообразно для более перспективных эвристик увеличивать вероятности их выбора в операторах мутаций и генерации начального поколения. В экспериментах в случае задачи N25 вероятности выбора эвристик Э,, Э , и взяты в отношениях 2 1 1 4. При этом средний по нескольким вариантам результат применения простого генетического алгоритма оказался Е = 5371. вто время как равновероятное использование всех восьми эвристик дало F = 5536. [c.233]

Повышение эффективности выражается в большей точности (степени приближения к экстремуму) и/или в большей скорости сходимости к приемлемому результату. Так, в задаче синтеза расписаний с помощью НСМ удавалось получать более точные результаты за отрезок времени, оцениваемый 30...40 тыс. обращений к процедуре вычисления целевой функции, чем в альтернативных генетических алгоритмах при в несколько раз большей трудоемкости. [c.241]

Различают расписания статические и динамические. Статическое расписание составляют в окончательном виде до начала его реализации, т.е. заранее должны быть известны совокупности предстоящих работ и средства (ресурсы) для их вьшолнения. Задачи синтеза статических расписаний имеют ряд разновидностей. Большинство из них относится к //Р-трудным задачам дискретного математического программирования, что при размерах задач, имеющих место на практике, исключает возможность применения точных методов оптимизации. Поэтому существующие методы синтеза расписаний являются приближенными, причем они ориентированы на статические расписания. [c.241]

Дерево изделия - представление иерархической структуры изделия Диаграмма взаимодействия (процессов) - диаграмма процессов в языке UML, отражающая поведенческий аспект моделируемой системы. В число диаграмм взаимодействия входят диаграммы последовательностей и кооперации Диаграмма Ганта - диаграмма распределения работ во времени и по обслуживающим аппаратам в задачах управления проектами и синтеза расписаний Диаграмма деятельности - диаграмма в языке UML, представляющая собой граф, каждой верщине которого соответствует некоторое элементарное действие, а дуги изображают последовательность выполнения действий [c.311]

Синтез расписаний - процедура составления расписания, представляющего собой распределение заданного множества работ во времени и распределение имеющихся ресурсов между работами [c.314]

Некоторые компоненты СМО характеризуются более чем одним входным и (или) выходным потоками заявок. Правила выбора одного из возможных направлений движения заявок входят в соответствующие модели компонентов. В одних случаях такие правила относятся к исходным данным (например, выбор направления по вероятности), но в некоторых случаях желательно найти оптимальное управление потоками в узлах разветвления. Тогда задача моделирования становится более сложной задачей синтеза, характерными примерами являются маршрутизация заявок или синтез расписаний и планов. [c.127]

В отдельную группу задач структурного синтеза выделяют планирование процессов и распределение ресурсов. В нее входят синтез технологических процессов в различных отраслях промьппленности, проектирование вычислительных процессов для многопроцессорных систем и сетей, синтез логистических процессов (например, планирование перевозок грузов при наличии мно-жества заказов и ограниченном числе транспортных средств), а также планирование работ при управлении проектами. Эти задачи объединяет общность ряда свойств и подходов к решению, как задач синтеза расписаний. [c.178]

Указанные особенности обусловливают сложность решения задач синтеза расписаний, являющихся задачами дискретной оптимизации. [c.178]

Синтез расписаний. Задачи синтеза расписаний требуется решать во многих приложениях, например при планировании различных производственных процессов, распределении ресурсов, выборе числа и типов процессоров для многопроцессорных специализированных комплексов и т. п. [c.195]

Каждая эвристика при применении для синтеза расписаний метода НСМ включает два правила одно для выбора очередной работы, другое для выбора машины, обслуживающей эту работу. [c.195]

Так, при структурном синтезе специализированных ЭВМ и микропроцессорных систем возникают трудности решения ряда специфичных проблем, связанных с согласованием структур и алгоритмов функционирования ЭВМ и систем с характеристиками решаемых задач. Результатами структурного синтеза ЭВМ являются номенклатура входящих в состав ЭВМ блоков, число блоков каждого типа, топология информационных и управляющих взаимосвязей между блоками, а также расписание функционирования каждого блока при организации вычислительного процесса. [c.268]

При одномерном синтезе решаются задачи упорядочения элементов структуры в одномерных пространствах (например, задачи составления расписаний, синтеза процессов, представляемых в виде упорядоченной последовательности элементов). [c.72]

Практическая важность ЗСР привела к тому, что разработано большое число эвристических методов синтеза. Основой метода синтеза являются правило выбора очередной работы и правило назначения сервера для ее обслуживания. Однако любое правило, являясь удачным в одной ситуации, оказьшается неудачным в другой, причем заранее (т.е. в процессе синтеза) эффективность правила определить не удается. Поэтому любой эвристический метод, опирающийся на априорно заданные правила, может привести к расписанию, далекому от оптимального, причем степень удаленности остается неизвестной. [c.226]

Однако статические расписания оказываются далекими от оптимальных, если в процессе их исполнения возникают отклонения от использованных при расчете исходных данных. Поэтому целесообразно применять расписания, способные адаптироваться к изменяющимся условиям. Такие расписания будем называть динамическими или адаптируемыми. Синтез динамических расписаний, или, точнее, адаптация расписаний к изменяющимся условиям, представляет собой слабо исследованную проблему. [c.242]

Рассмотрим возможный подход к решению задачи синтеза динамических расписаний [64]. Эта задача решается, если возникают заметные отклонения реальных значений параметров процесса от значений, априорно принятых при расчете исходного расписания, т.е. расписания, рассчитанного до начала реализации процесса. [c.242]

Преодолеть этот недостаток можно, если использовать идею представления в хромосоме информации о синтезируемом объекте в неявной форме. Гены в этом случае не представляют сами структурные параметры, а указывают на способ определения этих параметров. Например, при синтезе расписаний гены должны представлять не номера работ или обслуживающих агшаратов, а правила генерации очередного варианта расписания. Эта идея неявного описания параметров реализована в методе, названном методом комбинирования эвристик (НСМ - Heuristi s ombination Method) [63]. [c.221]

Задачи синтеза расписаний, сформулированные подобным образом, будем обозначать 088Р. [c.227]

Для иллюстрации преимуществ локально-генетического подхода сравнивались результаты решения задач с помощью генетических алгоритмов простого однопопуляционного (ОГА), многопопуляционного (МГА) и локально-генетического алгоритма (ЛГА). Сопоставление ОГА и ЛГА на задаче синтеза расписаний N21 при ограничении числа вычислений целевой функции Р в проводимых экспериментах значением 10 000 дало значения Р, приведенные в табл. 2.1, где N - размер популяции. Отметим, что в этой задаче синтеза расписаний Р есть цена расписания, которая минимизируется. [c.232]

Эксперименты на задаче синтеза расписаний N105 показали, что ЛГА по эффективности не уступает МГА. Исследование МГА проводилось с помощью программы параллельного генетического поиска GALOPPS. Использовалось восемь параллельных популятщй с размером N , популяции обменивались своими представителями после каждых пяти смен поколений. В каждом варианте расчета бьшо выполнено 24 цикла по пять смен поколений. Значение целевой функции Р, усредненное по ряду вариантов расчета с различными размерами популяции (от 27 до 60), оказалось равным 22 050. [c.232]

Как показали результаты численных экспериментов, в случае синтеза расписаний этот алгоритм можно использовать в задачах с нежесткими ограничениями, причем при выборе штрафы за нарушение ограничений в Р. учитываться не должны. [c.234]

В некоторых задачах, имеющих то или иное секционирование, возможны дополнительные схемы позиционирования. Примерами таких задач могут служить многостадийные задачи синтеза расписаний. Для них используют также локально-генетический алгоритм LGA3, реализующий распределенный регулярный способ позиционирования. [c.236]

Пояснить все три способа позиционирования можно с помощью рис. 2.18, на котором хромосома для многостадийных задач синтеза расписаний представлена в виде матрицы С. Ее элемент Q, есть ген, относящийся к /-му шагу синтеза на -й стадии. В LGA2 одновременной мутации подвергается R генов с последовательными номерами /, что и обусловливает название горизонтальный поиск . В LGA3, наоборот, мутируют гены с последовательными номерами к, т.е. вертикально раеположенные в матрице С. [c.236]

Важно отметить, что регулярный поиск оказывается более эффективным в таких задачах, как синтез расписаний или упаковка грузов в контейнеры. В то же время для задач УКРТ У преимуществ ЬОА2 перед ЬСА1 не зафиксировано, что свидетельствует о слабом влиянии позиции гена или отсутствии такового на вхождение или невхождение гена в хромосомные блоки. [c.237]

Базовым понятием в синтезе расписаний является понятие работы — элементарной планируемой части процесса. Нужно составить план вьшолнения работ, в котором фиксируются объемы работ, распределение ресурсов всех ввдов, моменты (даты) начала и окончания каждой работы, называемые событиями (или вехами), стоимости работ. Ресурсы — обеспечивающие компоненты деятельности, включающие исполнителей, энергию, материалы, оборудование и т. д. [c.178]

Второй подход получил название метод комбинирования эвристик. Этот метод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т. е. проектными параметрами для каждой работы будут номер сервера и порядковый номер в очереди на обслуживание. Пусть N— число работ, М— число серверов. Если гены соответствуют номерам работ, то в первом подходе в хромосоме нужно иметь 2N генов и общее число отличающихся друг от друга хромосом W заметно превьппает наибольшее из чисел Л и М . [c.190]

В других разновидностях задач синтеза расписаний могут быть те или иные усложняющие решение отличия. Примерами отличий могут бьггь 1) много-стадийность — наличие нескольких стадий обслуживания каждой работы [c.195]

Составление расписания операций, т.е. распределение операций по временным тактам и функциональным блокам. При этом определяются типы операционных блоков (комбинационные или последовательностные) и исходные данные для синтеза управляющих блоков. [c.129]

Получение расписаний, близких к оптимальным, возможно с помощью многоэвристичных методов, позволяющих на каждом шаге синтеза использовать ту эвристику из числя возможных кп- [c.209]

Тестовой для синтеза многостадийных расписаний выбрана задача N105 с исходными данными число работ Л = 105, число стадий обслуживания каждой работы q = А, общее число обслуживающих аппаратов (серверов) М= 15. В качестве тестовых использовались также две задачи меньщего размера N21 и N25, отличающиеся otNIOS числом работ, в них соответственно jV равно 21 и25. [c.230]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...