Методические указания
Особенностями рассматриваемого процесса, на которые должен обратить свое внимание студент при выполнении заданий являются:
-влияние очередности заказов на характеристики процесса; -из-за запрета перехода бригады 2 на следующий заказ до тех пор, пока не закончит свои работы бригада 1, могут возникнуть простои бригады 2;
- простои бригады 2 не влияют на общую продолжительность процесса, которая может быть даже меньше, чем у варианта процесса без такого простоя.
Подобную задачу моделирования последовательных работ решил в 1906 году Генри Гантт. Он предложил определять продолжительность с помощью построения диаграммы, которую впоследствии и назвали диаграммой Гантта.
Пример построения диаграммы Гантта и определения заданных величин.
Таблица 2 - Исходные данные
Заказы |
Длительность выполнения работы 1, мес |
Длительность выполнения работы 2, мес |
Заказ 1 |
3 |
5 |
Заказ 2 |
4 |
2 |
Заказ 3 |
5 |
3 |
Заказ 4 |
1 |
2 |
Заказ 5 |
2 |
1 |
Определим продолжительность Т выполнения всех заказов и количество простоев бригады, выполняющей работу 2 с помощью диаграммы Гантта.
Месяц |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
З
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Заказ 2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Заказ 3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Заказ 4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Заказ 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
аказ
1
|
Работа 1 |
|
Работа 2 |
Как видим из диаграммы, общая продолжительность выполнения всех работ Т составит 18 месяцев, а продолжительность простоев бригад ТП - 2 месяца. Далее необходимо изменить очерёдность выполнения заказов, используя эвристическое правило. Т.е. правило, которое человек вывел сам, основываясь на собственных наблюдениях. Не всегда эвристическое правило даёт нам оптимальный вариант решения.
С помощью алгоритма Джонсона можно определить гарантированно оптимальную очерёдность по критерию minТ.
Алгоритм Джонсона:
1. Необходимо найти в таблице (матрице) Т min.
2. Если Т min находится в первом столбце, то номер строки необходимо поместить в начало очереди, если во втором – то в конец.
3. Строку с Т min из таблицы исключить.
4. Перейти к пункту 1.
Используя алгоритм Джонсона для данной задачи, получим следующую очерёдность выполнения заказов:
4 |
1 |
3 |
2 |
5 |
При построении диаграммы Гантта с использованием данной очерёдности, мы гарантированно получим оптимальный вариант по критерию minТ. Однако и метод Джонсона имеет недостатки, т.к. он работает только с двумя последовательными процессами и лишь в том случае, когда операции выполняются одной бригадой.