Расписаний Теория

84

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

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

Иногда в моделях Р. Т. Указываются длительности переналадок при переходе от обслуживания одного требования к обслуживанию следующего требования и др. Условия. Следует отметить, что исходя из практич. Направленности Р. Т. Не стремится к унификации терминологии. Наряду с термином "требование" употребляются, напр., термины "работа", "операция" и т. Д. По той же причине по-разному формально определяется расписание обслуживания требований. В общем случае под расписанием можно понимать однозначное отображение, ставящее в соответствие каждому требованию в каждый момент времени определенный набор ресурсов. В качестве критериев обычно выбираются критерии суммарного и максимального штрафов, имеющие следующий вид. здесь - момент завершения обслуживания требования ав расписании 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. Я. Б. Згтдер, В. В. Шкурба.

Значения в других словарях
Раскроя Задача

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

Распада Разрыва Метод

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

Распознавание Образов

- раздел математич. Кибернетики, разрабатывающий принципы и методы классификации, а также идентификации предметов, явлений, процессов, сигналов, ситуаций - всех тех объектов, к-рые могут быть описаны конечным набором нек-рых признаков или свойств, характеризующих объект. Описание объекта представляет собой n-мерный вектор, где п - число признаков, используемых для характеристики объекта, причем i-я координата этого вектора равна значению i-ro признака, i=l, . , п. В описании объекта допусти..

Распределение

- то же, что обобщенная функция. ..

Дополнительный поиск Расписаний Теория Расписаний Теория

Добавить комментарий
Комментарии
Комментариев пока нет

На нашем сайте Вы найдете значение "Расписаний Теория" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Расписаний Теория, различные варианты толкований, скрытый смысл.

Первая буква "Р". Общая длина 17 символа