Математическая энциклопедия - расписаний теория

ветвь прикладной математики (раздел исследования операций), изучающая математич. постановки и методы решения задач оптимального упорядочения и согласования выполнения нек-рых действий во времени. К Р. т. относятся вопросы, связанные с построением оптимальных расписаний (календарных планов, графиков) выполнения конечных (или повторяющихся) комплексов операций. Область приложения результатов Р. т. включает в себя управление производством, транспортом, строительством, вычислительными системами и др.

Исследуемые в Р. т. задачи часто формулируются как задачи оптимизации процесса обслуживания конечного множества требований в системе, содержащей ограниченные ресурсы. Конечное множество требований отличает модели Р. т. от сходных с ними моделей массового обслуживания теории, где в основном рассматриваются бесконечные потоки требований. В остальном эти теории имеют близкие отправные точки. В Р. т. для каждого требования задается момент его поступления в систему. Находясь в системе, требование должно пройти одну или несколько, в зависимости от условий задачи, стадий обслуживания. Для каждой стадии указываются допустимые наборы ресурсов и длительности обслуживания требования при использовании этих наборов. Оговаривается возможность прерываний процесса обслуживания отдельных требований. Ограничения на очередность обслуживания задаются, как правило, транзитивным, антирефлексивным бинарным отношением. Алгоритмы расчета характеристик больших частично упорядоченных множеств требований составляют основное содержание раздела Р. т., к-рый носит название теории сетевого планирования. Иногда в моделях Р. т. указываются длительности переналадок при переходе от обслуживания одного требования к обслуживанию следующего требования и др. условия.

Следует отметить, что исходя из практич. направленности Р. т. не стремится к унификации терминологии: наряду с термином "требование" употребляются, напр., термины "работа", "операция" и т. д. По той же причине по-разному формально определяется расписание обслуживания требований. В общем случае под расписанием можно понимать однозначное отображение, ставящее в соответствие каждому требованию в каждый момент времени определенный набор ресурсов. В качестве критериев обычно выбираются критерии суммарного и максимального штрафов, имеющие следующий вид:

здесь момент завершения обслуживания требования ав расписании s, N - множество требований, а неубывающие функции, именуемые функциями штрафа. В практич. постановках функции штрафа имеют обычно конкретный экономич. смысл (напр., омертвление оборотных средств, ущерб от потери потребителей и т. д.). Рассматриваются многокритериальные задачи.

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

Основным подходом к решению детерминированных задач Р. т. является общая алгоритмич. схема последовательного анализа вариантов. Именно на этом пути удалось решить наиболее адекватные практике задачи, отработать оптимизационные процедуры планирования работ во времени (к а л е н д а р н о е п л а н и р о в ан и е), реализуемые в автоматизированных системах управления. Вместе стем для ряда детерминированных задач получены быстродействующие решающие правила, доказаны необходимые и достаточные условия их применимости, предложены эффективные приемы, имеющие значение для дискретной оптимизации в целом (см., напр., [1]-[4]). При разработке таких оптимизационных алгоритмов находят применение, в частности, результаты графов теории и математич. программирования. Опубликованные в нач. 70-х гг. 20 в. работы по теории NP -полноты привели к появлению многочисленных исследований сложности задач Р. т. (см., напр., [5]). Результаты этих исследований повысили интерес к алгоритмам приближенного решения и оценке точности таких алгоритмов (см., напр., [6]). Для многих подходов и приемов решения задач дискретной оптимизации Р. т. представляет легко формулируемые практически значимые "пробные камни" примеры.

Лит.:[1] Т а н а е в В. С., Ш к у р б а В. В., Введение в теорию расписаний, М., 1975; [2] К о н в е й Р. В., М а к св е л л В. Л., М и л л е р Л. В., Теория расписаний, пер. с англ., М., 1975; [3] Computer and job-shop scheduling theory, N. Y.-[а. о.]. 1976; [4] G о n z a 1 e z M. J., "А С Т Computing Surveys", 1977, v. 9, № 3, p. 173-204; [5] L e n s t r a J. K., R i n n о о у К a n A. H. G., "Operations Research", 1978, v. 26, № 1, p. 22-35; [6] G a r е у M. R., G r a h a m R. L., J о h n s o n D. S., там же, р. 3-21. Я. Б. Згтдер, В. В. Шкурба.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985