Оперативно-производственное планирование на предметно-замкнутом участке (стр. 2 из 3)

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

Расписание рассматривается как совокупность

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

Если

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

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

Пример. На рис.1 приведен график расписания

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

Рис.1. График расписания обслуживания требований 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 – трудные задачи).

Исходные данные для решения задачи:

1. Количество рассматриваемых видов деталей M. Виды деталей нумеруются числами

.

2. Количество групп однотипного оборудования I. Группы оборудования нумеруются числами

.

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

Для каждого вида деталей m (

) задаются:

· количество операций в ТМ –

, номера операций в ТМ обозначаются через ;

· продолжительность обработки одной детали на операции

(при обработке деталей m), ;

· номер группы оборудования –

, на котором выполняется операция .

4. План выпуска деталей различных видов – вектор

.

5. Стоимость

прол¨живания деталей вида в единицу времени.

Пусть отрезок планирования разбит на S частей, которые для простоты будем называть сутками и нумеровать числами

. Для каждых суток должны быть заданы следующие величины:

6. Продолжительность суток

.

7. Фонд времени групп оборудования i в сутки

.

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

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