http://npc-news.ru/

Модели и методы теории расписаний

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

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

Теория расписаний представлена набором типовых задач и методов их решения. Рассмотрим далее некоторые задачи, которые могут быть полезны при моделировании потоков работ и построении систем управления ими [5,6,7].

2.1.1. Расписания для одного ресурса. Рассмотрим по­становку следующей простой задачи. Пусть имеются п незави­симых операций (работ), каждая из которых характеризуется временем U (г = 1,2     п) выполнения в системе. Необходи­мо найти оптимальный порядок прохождения всех работ через систему, минимизирующий среднее время обслуживания одной операции:

прохождения работ через систему. Однако для данной задачи найдено простое решение: оптимальный порядок выполнения работ имеет место при выполнении условия t\ ^ t^ ^ . •. ^ tn. Таким образом, решением задачи служит упорядочение работ по их длительности. Для этой цели можно использовать любой известный алгоритм сортировки, сложность которого и будет определять сложность задачи.

Если заданы дополнительно приоритеты pi (г = 1,2, …,п) работ (чем приоритетней работа, тем больше величина то оптимальное решение задачи соответствует упорядочению работ по принципу


Комментарии закрыты.