Элементы (основы) теории расписаний

Качество функционирования современного производства во многом определяется решениями, принимаемыми на этапах календарного планирования и оперативного управления. Особенно это актуально в связи с созданием современных автоматизированных производств – гибких производственных систем (ГПС). Системы оперативно – календарного планирования современных производств строятся в том числе и на достижениях так называемой «теории расписаний» [29].

Теория расписаний – это наука, занимающаяся исследованиями детерминированных обслуживающих систем на предмет оптимизации расписаний их функционирования.

Примеры таких систем:

· цех, участок, на станках которых осуществляется обработка деталей;

· ВУЗ, где преподаватели обучают студентов и т.д.

В любом случае имеется конечное множество требований (деталей, преподавателей и т.д.) и конечное множество приборов (станков, групп студентов и т.д.) .

Предполагается, что i – е требование на каждой стадии его обслуживания q (например, на каждой операции технологического процесса) может быть обслужено любым из приборов (но не более, чем одним одновременно). Предполагается также, что каждый прибор одновременно может обслуживать не более одного требования.

В теории расписаний рассматриваются различные системы обслуживания:

· системы поточного типа, в которых каждое требование сначала обслуживается приборами первой группы, затем второй группы и т.д. пока не будет обслужено приборами последней r – ой группы;

· системы с различными порядками (маршрутами) прохождения приборов требованиями и т.д.

В частности, в последних системах с последовательными приборами для каждого требования задается своя, специфическая для этого требования последовательность его обслуживания приборами. Требование i сначала обслуживается прибором , затем и т.д. пока не будет обслужено прибором . Последовательности обслуживания могут быть различными для разных требований и могут содержать повторение приборов [32].

В любом случае, если требование i на стадии q должно или может быть обслужено прибором , то предполагается заданной длительность его обслуживания прибором. Запись , как привило, означает, что по условию задачи требование i на стадии q прибором L не обслуживается.

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

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

Расписание – некоторая совокупность указаний относительно того, какие именно требования какими именно приборами обслуживаются в каждый момент времени.

Расписание рассматривается как совокупность кусочно–постоянных непрерывных слева функций, каждая из которых задана на интервале и принимает значения 0, 1, …, n.

Если (здесь i – номер требования), то в момент времени прибор обслуживает требование . Если , то в момент времени прибор L простаивает.

При задании расписания должны соблюдаться все условия и ограничение, вытекающие из постановки рассматриваемой задачи, т.е. расписание должно быть допустимым [32].

Пример. На рис. 28 приведен график расписания обслуживания требований приборами при различных маршрутах обслуживания требований. Все длительности обслуживания равны «1».

Рис. 28. График расписания обслуживания требований

N = {1, 2, 3, 4} приборами M = {1, 2, 3}

Здесь , т.е. первое требование обслуживается первым и вторым приборами, – второе требование обслуживается третьим и вторым приборами, – третье требование обслуживается вторым, первым, снова вторым и третьим приборами, - четвертое требование обслуживается вторым, третьим и первым приборами. – момент поступления требования 1 в систему, – моменты поступления требований 2 и 3 в систему, – момент поступления требования 4 в систему. – директивный срок завершения обслуживания требования 1, – директивный срок завершения обслуживания требования 2, – директивный срок завершения обслуживания требования 3, – директивный срок завершения обслуживания требования 4.

Прибор 1 во временном интервале обслуживает требование 1, в интервале - требование 3, в интервале - требование 4. Прибор 2 в интервале без простоев обслуживает требования 3, 2, 4, 1, 3 и т.д. Это расписание допустимо, т.е. каждый прибор одновременно обслуживает не более одного требования и i – е требование обслуживается одновременно не более, чем одним прибором.

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

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

При построении расписания с наименьшим суммарным временем обслуживания , при этом .

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

Оптимальное расписание может быть найдено в результате перебора конечного множества возможных вариантов. Основная трудность при этом состоит в том, что число таких вариантов очень велико и растет, по меньшей мере, экспоненциально с ростом размерности задачи. Известны так называемые эвристические алгоритмы формирования расписаний, алгоритмы на основе методов линейного и динамического программирования. Задачи составления расписаний для некоторых сложных систем обслуживания до сих пор не решены (NP – трудные задачи).