Автоматика и телемеханика, № 7, 2014
© 2014 г. М.Я. КОВАЛЕВ, д-р физ.-мат. наук (kovalyov_my@newman.bas-net.by), Ю.Н. СОТСКОВ, д-р физ.-мат. наук (sotskov@newman.bas-net.by), Я.М. ШАФРАНСКИЙ, канд. физ.-мат. наук (shafr-04@yandex.ru) (Объединенный институт проблем информатики Национальной академии наук Беларуси, Минск)
НАУЧНАЯ ШКОЛА АКАДЕМИКА В.С. ТАНАЕВА: РЕЗУЛЬТАТЫ ПО ТЕОРИИ РАСПИСАНИЙ
Приводится краткий обзор результатов по теории расписаний, полученных представителями научной школы академика В.С. Танаева. Результаты структурированы по тематике.
1. Введение
При решении многих практических задач возникает потребность оптимального планирования (упорядочения) тех или иных процессов во времени. Необходимость учета ограничений на используемые ресурсы при планировании таких процессов приводит к математическим задачам, рассматриваемым в теории расписаний. Термин "теория расписаний" впервые появился в статье американского математика Р. Беллмана "Mathematical aspects of scheduling theory" (Математические аспекты теории расписаний), опубликованной в 1956 г. Ранее, в 1954 г., была опубликована статья С.М. Джонсона "Optimal two- and three-stage production schedules with setup times included" (Оптимальные двух- и трехстадийные производственные расписания с включенными временами переналадок). В 1955 г. был опубликован доклад Дж.Р. Джексона "Scheduling a production line to minimize maximum tardiness" (Построение расписания работы производственной линии с целью минимизпции максимального запаздывания), а в 1956 г. - статьи В.Е. Смита "Various optimizers for single stage production" (Различные правила оптимизации для одностадийного производства) и Дж.Р. Джексона "An extension of Johnson's results on job lot scheduling" (Обобщение результатов Джонсона на задачи с различными маршрутами требований). С этих публикаций и началось, как принято считать, системное развитие нового раздела исследования операций, именуемого теорией расписаний, в котором изучаются математические модели и методы решения задач оптимального распределения ограниченных ресурсов между объектами во времени. Нельзя не упомянуть также опубликованную в 1903 г. работу Г. Гантта "A graphical daily balance in manufacture" (Графический ежедневный баланс на производстве), в которой были введены так называемые диаграммы Гантта, широко используемые в теории расписаний.
В теории расписаний используется характерный для исследования операций модельный подход к анализу реальных процессов. Модели теории рас-
4* 99
писаний отражают специфические ситуации, возникающие при календарном планировании различных видов целенаправленной деятельности. Разнообразие моделей теории расписаний, степень их общности и универсальности постоянно расширяются, охватывая все более широкую сферу приложений. По существу, любая целенаправленная деятельность человека, так или иначе, должна быть спланирована во времени. Без расписания невозможна координированная работа отдельного производственного участка и всего предприятия. По заранее согласованному графику идет строительство объектов, ремонт оборудования, движение транспорта.
Задачи теории расписаний формулируются в терминах обслуживания требований приборами. Примерами таких задач являются: определение оптимального порядка обработки деталей на станках, выполнения программ на компьютерах, распределение групп студентов по аудиториям, исполнителей по проектам, транспортных средств по участкам дорог и т.д. Требованию сопоставляется некоторое множество приборов, каждый из которых может или должен обслуживать данное требование. Если каждое требование может быть полностью обслужено любым из этих приборов, то обслуживающая система называется одностадийной, в противном случае система - многостадийная. С каждым требованием связывается одна или несколько числовых величин: длительность обслуживания, момент готовности к обслуживанию, директивный срок, к которому желательно завершить обслуживание, весовой коэффициент, характеризующий относительную важность требования и др. Обслуживание требования прибором может протекать непрерывно либо с прерываниями. Для построения расписания необходимо определить для каждой пары "требование-прибор" интервалы времени, в течение которых этот прибор обслуживает данное требование, и сопоставить каждому такому интервалу определенное количество одного либо нескольких видов дополнительных ресурсов, если таковые используются при обслуживании. При этом должен быть соблюден ряд ограничений. Прибор не может обслуживать более одного требования одновременно, количества назначенных ресурсов не должны превышать имеющиеся объемы, на множестве требований может быть задано отношение строгого порядка, которое нельзя нарушать при обслуживании требований, и т.п. В качестве критерия оптимальности расписания может рассматриваться минимизация момента завершения обслуживания всех требований (максимизация быстродействия), минимизация суммы моментов завершения обслуживания требований, минимизация максимального или суммарного запаздывания завершения обслуживания требований относительно заданных директивных сроков, минимизация максимального смещения моментов завершения обслуживания требований относительно заданных директивных сроков.
Как правило, задача теории расписаний (как и большинство задач дискретной оптимизации) может быть решена путем перебора конечного числа вариантов (расписаний). Однако для реальных задач осуществить такой перебор невозможно из-за огромного числа вариантов. Поэтому представляет интерес разработка эффективных (полиномиальных) алгоритмов, время работы (количество элементарных операций) которых ограничено по-
линомом от размерности задачи (числа требований n, числа приборов m и других параметров). Согласно теории сложности вычислений все алгоритмически разрешимые задачи подразделяются на полиномиально разрешимые, для каждой из которых существует полиномиальный алгоритм решения, и NP-трудные. В соответствии с общепринятой, но до сих пор не доказанной гипотезой ни для одной NP-трудной задачи не существует полиномиального алгоритма решения. Для NP-трудных задач представляет интерес разработка приближенных алгоритмов, обеспечивающих получение решения, относительная погрешность которого (по целевой функции) не превосходит либо некоторой величины, зависящей от параметров задачи (приближенные алгоритмы с гарантированными оценками точности), либо любого задаваемого пользователем числа е > 0 (е-приближенные алгоритмы). Интерес представляет также разработка методов частичного перебора вариантов (методы динамического программирования, ветвей и границ и т.п.), локального поиска и других эвристических методов, а также выявление полиномиально разрешимых специальных случаев NP-трудных задач.
Большинство задач теории расписаний являются NP-трудными. О реальной сложности таких задач свидетельствует история решения известной тестовой задачи с 10 требованиями и 10 приборами, причем каждое требование обслуживается каждым из приборов один раз согласно заданному технологическому маршруту. Исходные данные этого примера были опубликованы в 1963 г., а оптимальное по быстродействию расписание для него (с доказательством оптимальности) удалось найти только в 1989 г., несмотря на многочисленные усилия многих математиков и программистов. Очевидно, что реальные задачи календарного планирования, как правило, имеют значительно большую размерность. Выбор оптимального расписания для большинства задач практической размерности требует огромного объема вычислительной работы, который невозможно выполнить за приемлемое время на современных и перспективных вычислительных машинах.
В Беларуси исследования в области теории расписаний начались в конце 1950-х гг. в Институте математики НАН Беларуси. Первые результаты были получены в начале 1960-х гг. для многостадийных обслуживающих систем, в которых перемещение требований между приборами осуществляется операторами переноса. Авторами этих результатов являются В.С. Айзенштат, А.Ш. Блох, А.С. Метельский, Д.А. Супруненко, В.С. Танаев и Р.И. Тышкевич.
В дальнейшем в НАН Беларуси сформировалась научная школа в области теории расписаний. Основатель школы - академик В.С. Танаев, заслуженный деятель науки Республики Беларусь, соавтор одной из первых монографий по теории расписаний [1], опубликованной в 1975 г. издательством "Наука" (Москва). В 1984 г. в этом же издательстве вышла первая часть фундаментальной монографии по теории расписаний [2], а в 1989 г. - вторая ее часть [3]. В 1994 г. переработанные и существенно дополненные варианты этих двух книг опубликовало на английском языке издательство "Kluwer Academic Publishers" [4, 5]. В том же году вышло учебное пособие по теории расписаний [6]. В 1998, 2004 и 2010 гг. опубликованы монографии по задачам
теории расписаний для систем с групповыми технологиями [7] и с неопределенными параметрами [8, 9].
Далее приводится краткое описание результатов по решению задач теории расписаний, полученных представителями школы В.С. Танаева. Результаты структурированы по тематике. Авторы перечисляются в алфавитном порядке вслед за описанием соответствующих результатов. Обзор некоторых результатов приведен ранее в [10].
2. Одностадийные системы обслуживания
Одностадийные системы обслуживания подразделяются на системы с одним и несколькими параллельными приборами. Приборы могут быть идентичными (если длительности обслуживания каждого требования одинаковы на различных приборах), разной производительности и, в общем случае, различными (длительность обслуживания определяется как прибором, так и требованием).
2.1. Максимальная и суммарная стоимость, запаздывание в обслуживании
Предложены полиномиальные алгоритмы решения задачи минимизации максимальной стоимости обслуживания требований одним прибором при разрешении прерываний, различных моментах готовности требований и заданном на множестве требований отношении строгого порядка, а также при различных моментах готовности требований и запрещении прерываний (В.С. Гордон, В.С. Танаев). Установлены свойства и разработаны полиномиальные а
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.