ПОИСК Статьи Чертежи Таблицы Синтез расписаний из "Информационная поддержка наукоемких изделий. CALS-технологии " Задачам синтеза расписаний (ЗСР) посвящено большое число работ, в том числе и по генетическим алгоритмам синтеза. ЗСР заключается в распределении заданного множества работ во времени и между исполнителями (в пространстве). [c.224] К ЗСР сводятся многие практические задачи планирования и распределения ресурсов. В частности, ЗСР занимают одно из центральных мест в системах управления и бизнеса. Большую группу прикладньгх задач, аналогичных по подходам к их решению, составляют задачи календарного планирования производственных процессов. Среди них заметное место отводится задачам планирования многостадийных процессов. Отметим, что наиболее трудными для решения обычно оказываются многостадийные ЗСР. [c.224] Требуется составить расписание, при котором минимизируются затраты средств Z. [c.225] Уже в представленном виде задача является Л Р-трудной, но обычно она имеет ряд усложняющих дополнений. Типичные дополнения 1) исполнение работ является многостадийным, т.е. каждая работа должна пройти последовательное обслуживашге на нескольких стадиях, каждая из которых характеризуется своим набором серверов и матриц Р 2) множество работ разделяется на несколько подмножеств однотипных работ, последовательное исполнение разнотипных работ на каком-либо сервере требует его перенастройки с соответствующими затратами времени и средств. [c.225] Результаты решения ЗСР обычно представляют в виде диаграмм Ганта, пример диаграммы приведен на рис. 2.17, где работы А, В а С проходят трехстадийное обслуживание на машинах 1,2 и 3. [c.225] Другой вариант диаграммы - горизонтальные строки рисунка соответствуют работам, а не серверам. [c.226] Практическая важность ЗСР привела к тому, что разработано большое число эвристических методов синтеза. Основой метода синтеза являются правило выбора очередной работы и правило назначения сервера для ее обслуживания. Однако любое правило, являясь удачным в одной ситуации, оказьшается неудачным в другой, причем заранее (т.е. в процессе синтеза) эффективность правила определить не удается. Поэтому любой эвристический метод, опирающийся на априорно заданные правила, может привести к расписанию, далекому от оптимального, причем степень удаленности остается неизвестной. [c.226] Приведем примеры правил выбора работ в ЗСР для многостадийных процессов 1) правило FIFO - предпочтение отдается работе с наименьшим временем окончания ее предыдущего обслуживания (на предыдущей стадии) 2) предпочтение отдается работе с наименьщим предельно допустимым временем окончания ее полного обслуживания. [c.226] Примеры правил выбора серверов 1) выбирается сервер, на котором обслуживание данной работы будет наиболее дещевым 2) выбирается сервер, на котором работа будет обслужена за наи-меньщее время. [c.226] Генетические методы могут быть свободными от привязки к определенному правилу. Например, если гены хромосомы соответствуют работам, а значение гена отражает приоритет работы в ее назначении на обслуживание, то порядок назначения работ может стать близким к оптимальному в той степени, в какой это допускают генетические принципы. Однако выбор сервера в этом варианте алгоритма приходится все-таки осуществлять по некоторому фиксированному правилу. [c.226] Требуется получить расписание, минимизирующее общие затраты, складывающиеся из штрафов, затрат на обслуживание всех работ на всех стадиях и затрат на переналадки всех серверов. [c.227] Задачи синтеза расписаний, сформулированные подобным образом, будем обозначать 088Р. [c.227] Исходная задача декомпозируется, и каждая подзадача рассматривается как состоящая из двух частей. В первой части определяется очередная работа, во второй части эта работа назначается на обслуживание, т.е. для нее выбирается один из серверов. Каждая часть может вьшолняться с помощью некоторых эвристических и/или генетических алгоритмов. [c.227] Правило назначения /-й работы на обслуживание указывает на сервер, на котором обслуживание оказьшается наиболее дешевым, а правило - на сервер, на котором обслуживание /-й работы закончится раньше, чем могло бы закончиться на других серверах. [c.227] Большее разнообразие правил для второй части синтеза порождается учетом предпочтительности назначения однотипных работ на последовательное обслуживание. [c.228] Композиция множеств правил первой и второй частей синтеза порождает множество эвристик. [c.228] В итоге хромосома включает п = генов, значениями генов являются номера эвристик. [c.228] Вернуться к основной статье