11. Генераторы расписаний.

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

Пример матрицы F:

Определение 1. Объект планирования – это тройка элементов k, L, q, в которой k указывает номер работы, L определяет номер прибора и q – повторность выполнения k-й работы -м прибором. В частности, для рассмотренного примера объектами планирования выступают:

3A1; 3C1; 3B1; 3C2.

Объекты планирования соответствуют элементарным операциям. Предметная область планирования представляется в виде смешанного графа, в котором объектами планирования соответствуют вершины графа.

Определение 2. Объекты планирования являются независимыми, если они соответствуют разным приборам и разным работам, т.е. k₁  k₂ и L₁  L₂. В смешанном графе между такими объектами не существует никаких связей.

Определение 3. Между объектами планирования k₁, L₁, q₁ и k₂, L₂, q2 существует взаимосвязь первого рода, если они относятся к одинаковым работам, но разным приборам, т.е. k₁= k₂= k, L₁ L₂.

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

Определение 4. Между объектами планирования k₁, L₁, q₁ и k₂, L₂, q₂ существует взаимосвязь второго рода, если они относятся к разным работам, но одинаковым приборам, т.е. k₁k₂ и L₁= L₂=L.

12. Решающее правило для задачи одного станка

Постановка задачи. Имеется n деталей, для каждой из деталей заданы: время обработки на станке T_j, ; величина штрафа .Штраф устанавливается за единицу времени ожидания j-й детали момента очередности поступления ее на обработку. Необходимо определить такую последовательность запуска деталей на обработку, при которой бы суммарный штраф за время нахождения всех деталей в очереди был бы минимальным.

Пусть – время ожидания j-й детали при использовании -й перестановки. Тогда критерий: .

Выбор производится по всем перестановкам .

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

Тогда оптимальная перестановка: .

Доказательство. Предположим, что – оптимальная перестановка, имеющая значение критерия, равное . Для конструирования перестановки в перестановке поменяем местами i-ю и j-ю детали, т.е. . Аналогично доказательству решающего правила для задачи директора: