В течение жизни мы регулярно сталкиваемся с расписаниями: транспорт, телевизионные передачи, кино, занятия в школе и институте и прочее. Для решения таких вопросов мы используем интуитивный подход. Однако в таких отраслях как автоматизация объёмного производства требуется оптимизировать общее время работы. Теория расписаний — как направление в исследовании операций началось с работы Г. Ганта в 1910, представившим диаграммы для управления проектами. Термин «теория расписаний» был предложен Р. Белламном в 1956 году. Большинство задач теории расписаний являются NP - трудными, поэтому решение задач больших размерностей требует больших временных затрат. К решению полиномиально неразрешимых задач применяют эвристики — алгоритмы, дающие приближенное решение за приемлемое время. Схемы, объединяющие основные эвристические методы и более эффективно исследующие пространство поиска, называемые метаэвристиками были представлены Ф.Гловером в 1986 году. В данной работе будет представлен метаэвристический алгоритм решения задачи о расписании, представленной сетевым графиком, его реализация и применение.
Алгоритм IASC был запущен на более чем 2-х тысячах задач. Лучшие результаты были получены на задачах с большим числом процессоров и малым числом заданий: c ростом числа заданий растёт ошибка и число итераций, необходимые для достижения оптимального результата, либо определённой планки погрешности вычислений, а с ростом числа процессоров, несмотря на более трудоёмкие вычисления, алгоритм стабильно выдавал лучшие результаты.
Зачастую, обнаружение локального минимума в решении из популяции закрывало все возможности для улучшения — логика мутаций в приведённом алгоритме может сойтись на случай, когда каждую итерацию будут производиться модификации, не приводящие к улучшению результата, и, как следствие, глобальный минимум не будет достигнут.
Простота реализации, универсальность и гибкость иммунных сетей позволяет использовать их для решения большого количества NP- трудных задач. Представленный автором алгоритм IASC является иммунной сетью всего с двумя мутациями, однако погрешности алгоритма являются невысокими. Дальнейшее расширение сети позволит добиться ещё более точных результатов.
