Управление технологическими процессами


Общая задача составления расписаний



страница7/16
Дата10.05.2018
Размер1.04 Mb.
ТипКонспект
1   2   3   4   5   6   7   8   9   10   ...   16

1.9. Общая задача составления расписаний


Графическое описание задачи

Задачу составления расписания можно представить как некоторую графическую задачу о расположении блоков, соответствующих операциям. Каждая работа i задаётся множеством qi блоков  по одному на каждую операцию. Каждой операции приписано три индекса: i, j, k, где i  номер работы, содержащей эту операцию; j  номер операции внутри работы, j = 1, ..., qi; k  номер машины, на которой операция должна выполнятся.

Рассмотрим пример графического описания задачи типа 5|3|G|Fmax. Длина каждого блока пропорциональна длительности выполнения операции. Расположение работ по строкам приводит к равенству первых индексов всех операций, находящихся в одной строке. Вторые индексы операции одной строки образуют возрастающую последовательность (рис. 8).

Каждое решение есть упорядочение операций – блоков – по строкам, соответствующим машинам, без изменения длин или индексов блоков, при котором совпадают последние индексы операций в каждой строке (рис. 9).



Рис. 8. Графическое описание исходных данных



Рис. 9. Расположение операций по машинам

Однако это расположение не является расписанием, т. к. выполнение операций в указанной последовательности и в указанное время невозможно.

Задача состоит в том, чтобы расположить операции так, чтобы операции, относящиеся к одной работе, не пересекались (рис. 10).

Диаграмма Гантта на рис. 10 представляет одно из возможных расписаний для рассматриваемой задачи.

Рис. 10. Диаграмма Гантта расписания работы системы 5|3|G|Fmax



Задача с двумя машинами

Единственной задачей, для которой решение полностью известно, является задача с двумя машинами (n|2|G|Fmax), при условии, что каждая работа состоит максимум из двух операций. Эта задача есть обобщение конвейерной задачи с двумя машинами и для решения требуется лишь небольшая модификация известного алгоритма.

Решение начинается с разбиения n работ на четыре подмножества:

{A} – подмножество работ, состоящее из единственной операции, выполняемой на машине 1;

{B} – подмножество работ, состоящее из единственной операции, выполняемой на машине 2;

{AB} – подмножество работ, состоящее из двух операций, из которых первая выполняется на машине 1, а вторая – на машине 2;

{BA} – подмножество работ, состоящее из двух операций, из которых первая выполняется на машине 1, а вторая – на машине 2.

После этого работы из подмножества {AB} упорядочиваются в соответствии с алгоритмом, минимизирующим Fmax, и то же самое проделывается с работами из {BA}. Упорядочение работ из {A} и {B} не влияет на максимальную длительность прохождения и может быть произвольным.

Оптимальным является следующий порядок выполнения работ:

а) машина 1 выполняет работы из {AB}, затем из {A}, затем из {BA};

б) машина 2 выполняет работы из {BA}, затем из {B}, затем из {AB}, причём порядок выполнения внутри каждого из подмножеств сохраняется.

Задача с двумя работами

Для решения задачи типа 2|m|G|Fmax можно использовать описанный ранее графический метод для соответствующей конвейерной задачи с двумя работами.

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

Сетевые задачи упорядочения

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

Для описания задач и алгоритмов решения удобно использовать терминологию теории графов.

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

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

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

Вопросы для самопроверки:

1. Какова цель теории расписаний и какие допущения принимаются при постановке задач упорядочения?

2. Какие основные исходные и искомые величины используются в теории расписаний?

3. Какие критерии используются при оценке расписаний?

4. Чем различаются задачи теории расписаний?

5. Какие алгоритмы упорядочения существуют для системы из одной машины?

6. Что представляет собой «задача коммивояжера»?

7. Основные теоремы упорядочения для конвейерных систем?

8. Каковы особенности упорядочения для системы из трех машин?

9. Как представляется расписание для системы из многих машин, выполняющих две работы?

10. В чем состоит общая задача составления расписания?

11. Для какой общей задачи составления расписаний решение полностью известно?

12. В чем особенности сетевых задач упорядочения?


Каталог: general information -> institutes -> engineering institute -> department of quot mechanical engineering quot -> educational-methodical-activity
educational-methodical-activity -> Конспект лекций Омск 2007 удк
educational-methodical-activity -> Математическое моделирование элементов конструкции и технологического процесса механической обработки детали на основе теории графов
educational-methodical-activity -> Конспект лекций ч. 1 Омск
general information -> Тесты для аспирантов (общие вопросы философии науки) Базовый уровень
general information -> Программа вступительного экзамена по специальности


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   10   ...   16


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница