Материал: 2501

решений с использованием соответствующих моделей, изучается в рамках

теории расписаний [1].

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

Методы теории расписаний применяются в различных отраслях экономики, в том числе в сфере работы автомобильного транспорта при выполнен перевозок грузов.

3. Ч слом, представляющим со ой длительность операции.

Маш ной называется устройство, способное выполнить все, что

Постановка задачи в теории расписаний. Постановка задачи в теории расписаний начинается с описания системы машин и множества работ. Для простейшего процесса обслуживания система машин полностью описывается числом.

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

326

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

Предположим, что общая длительность всех операций включает в себя все настройки маш ны, предшествующие выполнению операции, и все переналадки ее после выполнения операции. Подобное

обновления, систематизации, обработки, а с другой – необходимостью координации интересов всех указанных субъектов грузоперевозок [7].

Классификация задач теории расписаний. Задачи теории расписаний различаются числом выполняемых в системе обслуживаний, характером поступления их в систему и порядком участия отдельных ПРУиМ в выполнении конкретного обслуживания. В зависимости от

327

характера поступления требований на обслуживание различают два вида задач: статические и динамические.

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

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

- Задачи с minmax (минимаксными) критериями оптимизации.

Отличие этих задач от задач с суммарными критериями заключается в

328

том, что нужно минимизировать не сумму некоторых значений, а лишь максимальное из них. Например, если в упомянутой задаче необходимо

минимизировать максимальное значение, то мы получим одну из тривиальных задач этого класса;

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

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

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

задачам, введя спец альную функцию штрафа, который нужно минимиз ровать. Тем не менее, принято выделять такие задачи в отдельный класс.

По способу задан я входной информации:

- Детерм н рованные задачи (off-line). Для таких задач характерно, что все входные данные задачи точно известны, т.е. даны значения всех параметров до начала ее решения;

- Динамические задачи (on-line). Для данных задач расписания

- Календарное планирование или построение расписания для приборов, Machine scheduling (MS);

- Составление временных таблиц (Time Tabling);

- Доставка товаров в магазины (Shop-Floor Scheduling);

- Составление расписаний движения транспортных средств (Transport Scheduling), Циклические расписания для транспортных средств (Vehicle Routing);

- Составление расписаний спортивных мероприятий (Sports scheduling) [2].

Для классификации задач теории расписаний может использоваться запись A | B | C | D |, где:

A характеризует процесс поступления работ. Для динамических задач A представляет собой функцию распределения времени между

329

поступлениями. Для статистических задач A соответствует числу одновременно поступивших работ, если по этому поводу ничего специально не оговорено. Если на месте A стоит n, то это означает произвольное, но конечное число работ в статическом случае;

B характеризует число машин в системе. Если на месте B стоит m, то

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

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

1.Минимаксные критерии в задачахДс такими критериями целевая функция представляет собой функцию максимума от значений штрафов

требований. Примеры минимаксных критериев:

- критерий минимизации максимальногоИмомента завершения требований. Задачи с такой целевой функцией называют задачами на

быстродействие; - критерий минимизации максимального временного смещения;

2.Суммарные критерии в задачах с такими критериями целевая функция представляет собой сумму значений штрафов требований. Примеры суммарных критериев:

- критерий минимизации суммарного времени окончания обслуживания требований;

- критерий минимизации суммарного запаздывания требований; - критерий минимизации количества запаздывающих требований.

Иногда бывает удобно оценивать расписание величинами, относящиеся не к работам, а к системе обслуживания. Из этих величин

330