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

СОДЕРЖАНИЕ

§ 6. Задачи теории расписаний
6.1Предмет теории расписаний
6.2Классификация задач теории расписаний
6.3 Целевые функции в задачах теории расписаний
6.4 Построения расписания в случае одного прибора и конечного числа требований
6.5 Задача о двух станках
6.5 Алгоритм Джонсона
§ 7. Задача о назначениях	.
7.1 Постановка задачи. Некоторые свойства
7.2 Венгерский метод решения задачи о назначениях
§ 8. Метод ветвей и границ
8.1 Общая схема метода
8.2 Задача коммивояжера. Метод ветвей и границ для решения задачи коммивояжера
§ 9. Оптимизация на сетях
9.1 Задачи о кратчайшем и критическом пути
9.2 Задача о максимальном потоке
§ 10. Модели управление запасами
10.1 Основные понятия теории управления запасами
10.2 Факторы, определяющие политику управления запасами
10.3 Экономические параметры моделей управления запасами
10.4 Однопродуктовые модели управления запасами при детерминированном спросе
10.5 Классическая дискретная детерминированная задача управления запасами
10.6 Задача управления производством и запасами в случае сезонного спроса
10.7 Задача продавца газет
§ 11. Модели сетевого планирования и управления проектами
Задания для самостоятельной работы
Список литературы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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