Автоматика и телемеханика, № 7, 2014
© 2014 г. О. ГОЛАМИ (gholami_iran@yahoo.com), (Департамент компьютерной техники, Отделение Ноур, Центр Махмудабада, Исламский Университет Азада, г. Махмудабад, Иран), Ю.Н. СОТСКОВ, д-р физ.-мат. наук (sotskov@newman.bas-net.by), (Объединенный институт проблем информатики НАН Беларуси, Минск)
НЕЙРОСЕТЕВОЙ АЛГОРИТМ ДЛЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ ПОСЛЕДОВАТЕЛЬНЫМИ И ПАРАЛЛЕЛЬНЫМИ ПРИБОРАМИ
Рассматривается задача ||Стах оптимального по быстродействию обслуживания заданного множества требований последовательными и параллельными приборами. Задача ||Стах является обобщением классической задачи 7||Стах на случай, когда в обслуживающей системе имеются не только последовательные, но и параллельные (одинаковые) приборы. Предлагается двухэтапный алгоритм эвристического решения задачи ||Стах. На первом этапе решается задача 7||Стах, т.е. предполагается, что в обслуживающей системе нет параллельных приборов. На втором этапе операции распределяются по параллельным приборам. На обоих этапах разработанного алгоритма используются нейросетевые модели принятия решений. Эффективность нейросетевого алгоритма решения задачи 7||Стах и задачи ||Стах оценивалась на 20 тестовых примерах, которые были получены из 20 известных задач 7||Стах в результате включения в обслуживающую систему случайного количества копий последовательных приборов.
1. Введение
В задачах оперативно-календарного планирования (ОКП), возникающих в промышленности, компьютерных технологиях, логистике и при планировании сервиса, требуется оптимально обслуживать заданное множество требований (т.е. выполнять заданное множество операций) последовательными приборами без прерывания операций и при соблюдении временных и ресурсных ограничений. Временные ограничения указывают на то, что одни операции должны быть закончены раньше, чем начаты некоторые другие операции. Ресурсные ограничения задают недопустимость одновременного выполнения двух и более операций по обслуживанию требований одним и тем же прибором. Для такой обслуживающей системы требуется построить оптимальное по быстродействию расписание, т.е. определить, когда должна начаться каждая из заданных (непрерываемых) операций, чтобы соблюдались временные и ресурсные ограничения, а длина полученного расписания (т.е. общее время Cmax обслуживания заданных требований) была минимальной.
В англоязычной литературе [1-4] сформулированную задачу принято называть задачей job-shop (по-русски: цех работ). В общепринятой трехпозици-онной классификации задач теории расписаний [3] такая задача обозначается
как 3||Стах. В данной статье рассматривается задача ¥3||Стах, которая является обобщением задачи 3||Стах на случай, когда в обслуживающей системе имеются не только последовательные, но и параллельные (в данном случае одинаковые) приборы. Обе задачи 3||Стах и ¥3||Стах являются КР-трудны-ми в сильном смысле [1-5]. КР-трудность задачи означает, что для нее в настоящее время не известен полиномиальный алгоритм решения и, более того, маловероятно, что полиномиальный алгоритм (на детерминированной машине Тьюринга) для КР-трудной задачи когда-либо будет разработан. На практике для решения КР-трудных задач большой размерности приходится применять эвристические алгоритмы, не гарантирующие получение точного решения КР-трудной задачи.
Для эвристического решения задачи ¥3 ||Стах в данной статье предлагается двухэтапный алгоритм. На первом этапе решается задача 3||Стах, т.е. предполагается, что в обслуживающей системе нет параллельных приборов. На втором этапе соответствующие операции распределяются по параллельным приборам, что позволяет во многих случаях уменьшить общее время Стах обслуживания заданного множества требований. На обоих этапах разработанного алгоритма используются нейросетевые модели принятия решений.
В следующем разделе приведены постановки задач 3||Стах и ¥3||Стах. Из обзора литературы (раздел 3) следует, что для решения задачи ¥3||Стах двухэтапный алгоритм (с последующим введением параллельных приборов) ранее не использовался. В разделе 4 описаны искусственные нейронные сети, которые использовались для принятия решений. В разделе 5 описана сетевая модель задачи 3 ||Стах в виде взвешенного смешанного (дизъюнктивного) графа. В разделе 6 описан планировщик расписания на основе обучения искусственной нейронной сети и стратегии разрешения конфликтов операций в сетевой модели задачи 3 ||Стах. В разделе 7 представлены результаты вычислительного эксперимента, проведенного на тестовых задачах 3||Стах и ¥3||Стах для сравнения разработанного нейросетевого алгоритма с эвристическими алгоритмами, основанными на различных правилах приоритета операций.
2. Постановки задач Л || Стах и Р Л1| Стах
Используя терминологию теории расписаний [4], задачи ¥3 ||Стах и 3||Стах можно сформулировать следующим образом.
Множество п требований ^ = (31,..., 3п} необходимо обслужить приборами из множества М = (М1,..., Мт} согласно заданным технологическим маршрутам. Множество приборов М разбито на w подмножеств:
М = М^ ...у Мш, Мк = 0, к €{1,...,м},
где для любых индексов к = и € (1,..., ад} выполняется равенство Мк П Ми= = 0. Каждое подмножество Мк состоит из Wk одинаковых приборов типа к €
Пронумеруем приборы множеств Мк СМ следующим образом:
М = {М1,...,МШ1} ,
(1) = {МЕи-1 ш„+1, ■МЕи-1 • • •, МЕи=1 4 , 2 < к <
Здесь ^^=1 = т. Обслуживание требования £ ^ включает выполнение линеино упорядоченного множества = < , • • •, ^¿П^ Г операции, определяющих технологический маршрут обслуживания требования
Операция ф"^, j £ {1,...,пг}, обозначает обслуживание требования на стадии j £ {1,..., пг} прибором типа ^(у) £ {1,..., эд} в течение заданного времени > 0. В допустимом расписании прерывания любой операции
£ Уг не допускаются. Операция г,?) может быть выполнена любым прибором типа ^(у). Ни один прибор Мг £ М не может выполнять более одной операции в одно и то же время (ресурсное ограничение).
Выполнение операции не может быть начато раньше завершения
операции У1) (временное ограничение), т.е. неравенство
(2) ^"Г1)) < *(")
должно выполняться для любого требования ^ £ ^ и любой стадии У £{2, ...,пг} обслуживания этого требования. Здесь 5(0"(ч)) обозначает время начала операции ф"^, а с^"" 1)) - время окончания операции У "-"1 1). Время с(7г) завершения обслуживания требования £ ^ равно времени окончания последней операции по обслуживанию этого требования: с(7г) = )). Поскольку прерывания операций запрещены, то равенство = «(ф"^) + р" должно выполняться для любой операции
У"" £ Уг, £ ^.
Для решения задачи ||Стах требуется найти такое назначение операций = Ум(г")=к на приборы множества , к £ {1,... , ад}, и для каждой
операции £ и^=1 определить такие моменты времени с(0"(ч)) ^ 0
завершения ее выполнения прибором, на который эта операция назначена, чтобы полученное в результате расписание
^ = (С(дй1д)), с(у^(21,2) ),..., С(д"(гдг1)), )))
имело наименьшую продолжительность (длину), т.е. целевая функция Стах(£) = тах{с(7г) : £ принимала минимальное значение среди всех расписаний, допустимых для задачи ||Стах.
Если в рассматриваемой обслуживающей системе имеется только один прибор каждого типа к £ {1,... , эд}:
(3) |М1| = ••• = |М | = 1
(в этом случае M = {Mi,..., Mw}), то нет необходимости искать оптимальное назначение операций множества Qk на приборы множества Mk: назначения всех операций множества Q = IJW=i Qk на приборы множества M заданы в технологических маршрутах обслуживания требований J. Таким образом, если условие (3) выполняется, то задача FJ||Cmax превращается в классическую задачу J||C max.
На практике в задачах ОКП инъективное отображение IJW=i Qk — M, которое имеет место для задачи J ||Cmax, негативно влияет на ритмичность и устойчивость производственного процесса, поскольку поломка любого обслуживающего прибора Mr € M в момент времени t вызывает останов всего производства, если этот прибор используется в момент времени t.
Напомним [4], что регулярным критерием принято называть минимизацию неубывающей целевой функции F(c(J1), c(J2),..., c(Jn)). Критерий Cmax(S), очевидно, является регулярным. Допустимое расписание называется активным [4], если ни одна операция Q € (JW=1 Qk не может быть начата раньше без того, что другая операция начнется позже, или без изменения порядка выполнения операций каким-либо прибором из множества M. Для любого регулярного критерия хотя бы одно оптимальное расписание является активным [3, 4].
3. Обзор алгоритмов построения расписаний для обслуживающей системы с последовательными и параллельными приборами
Один из путей эвристического решения задачи FJ||Cmax основан на декомпозиции задачи FJ ||Cmax на подзадачи J ||Cmax [6], каждая из которых менее сложна по сравнению с исходной задачей FJ||Cmax, поскольку для решения подзадачи J||Cmax не требуется искать оптимальное назначение операций на параллельные приборы. В [6] сначала решается задача о назначениях операций на соответствующие приборы с использованием некоторых правил приоритета (предпочтения) операций, назначенных на один прибор. Затем решаются полученные задачи J ||Cmax с помощью различных эвристических алгоритмов типа алгоритма смещения узкого места (shifting bottleneck algorithm) или алгоритма локального поиска с запретами (tabu search algorithm).
В [7] рассматривалась задача ОКП с ограничениями готовности приборов в связи с их профилактическим ремонтом. Задача FJ||Cmax составления расписания рассматривалась как с фиксированными интервалами готовности приборов к обслуживанию, так и с нефиксированными интервалами их готовности. В [7] для эвристического решения рассматриваемой задачи предлагалось использовать алгоритм поиска в отфильтрованном пучке возможных вариантов (filtered beam search). Авторами [7] предложена модифицированная схема ветвления процесса решения задачи FJ||Cmax, которая обеспечивает естественное объединение ограничений на доступность приборов и заданных ресурсных ограничений.
В [8] предложена математическая модель и на ее основе разработаны эвристические алгоритмы для решения задачи сос
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.