Предмет теории расписаний

СОДЕРЖАНИЕ

Задачи теории расписаний

Предмет теории расписаний

Теория расписаний — это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений.

Задачи составления расписаний возникают в частности:

на производстве, когда нужно упорядочить отдельные операции по исполнителям (цеха, станки) и по времени;

на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;

при планировании занятий в учебных заведениях;

при планировании занятости персонала, например, дежурства врачей;

при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;

при планировании проведения спортивных мероприятий;

в компьютерных сетях при планировании очередности передачи пакетов информации и т.д.

В общем случае проблемы формулируются так: Задано некоторое множество работ (требований) с определённым набором характеристик: длительность обработки требования (простейший случай), стоимость обработки требования, момент поступления требования, директивный срок окончания обслуживания требования. Задано некоторое множество машин (приборов) , на которых требования должны обслуживаться в соответствии с некоторым порядком.

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

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

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

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