Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Задача 1. 10 деталей должны пройти последовательную обработку на двух машинах. Деталь, обработка которой на первой машине закончена, немедленно начинает обрабатываться на второй машине. Время обработки i -ой детали на первой машине ai и второй машине b i приведено в табл. 4.1. Найти такое расписание обработки деталей (работ), при котором суммарная продолжительность работ будет минимальна.
Таблица 4.1- Продолжительность обработки деталей на двух машинах
i | ||||||||||
ai | ||||||||||
bi |
Алгоритм решения.
1. Найти . Если , то работу с соответствующим номером запланировать первой, если , то работу запланировать последней.
2. Пометить столбец с запланированной работой и продолжить составление расписания для остальных работ.
3. Если для неких i, j выполняется равенство ai=aj или b i = bj и i<j, то вначале планируется очередность выполнения i -ой работы, затем – j- ой.
4. Если для неких i, j выполняется равенство ai= bj, то очередность выполнения работ определяется по первой машине.
Решение. Очередность выполнения работы будем обозначать номером в квадратных скобках.
Анализируя табл.4.1, видим, что минимальную продолжительность имеют работы номер 4 и 7 на первой машине и работа №8 на второй машине. Согласно п.4 алгоритма, вначале нужно определить очередность выполнения работ номер 4 и 7.
Согласно п.3 алгоритма, первой планируем выполнение работы №4 (ей присваивается первая очередь), затем – работы №7 (вторая очередь). Отметим это, занеся числа 1 и 2 в соответствующие ячейки второй строки табл. 4.2. Помечаем соответствующие столбцы. Работу №8 планируем последней; занесем число 10 во вторую строку табл. 4.2.
Следующими для планирования очередности являются работы номер 1 и 6, продолжительность выполнения которых на второй машине равна 4. Поскольку число 4 относится ко второй машине, очередность этих работ должна определяться с конца расписания. Согласно п.3, вначале определяем очередность работы №1: она будет выполняться перед последней работой (очередь 9), затем – работы №6 (очередь 8).
Далее последовательно определяем выполнение работ №5 (очередь 7), №9 (очередь 3), №10 (очередь 6), №2 (очередь 4) и №3 (очередь 5).
Таблица 4.2 - Очередность выполнения работ на двух машинах
i | ||||||||||
[i] |
Джонсон показал, что описанный выше алгоритм позволяет решить задачу составления оптимального расписания и для трех машин с продолжительностью выполнения i -ой работы соответственно ai, bi, ci, при условии, что для любого i выполняется одно из двух условий: или . В этом случае задача сводится к задаче двух машин, с продолжительностью работ на них соответственно ai,+ bi и bi +ci.
Задача 2. 7 деталей должны пройти последовательную обработку на трех машинах. Продолжительность обработки приведена в табл. 4.3.
Таблица 4.3 - Продолжительность обработки на трех машинах
i | |||||||
ai | |||||||
bi | |||||||
сi |
Анализ приведенных значений показывает, что условие применимости алгоритма выполняется (все ). Результат решения задачи приведен в табл. 4.4.
Таблица 4.4 - Очередность выполнения работ на трех машинах
i | |||||||
ai +bi | |||||||
bi +сi | |||||||
[i] |
Для иллюстрации расписания работ и определения их суммарной продолжительности используется диаграмма Ганта; порядок ее построения понятен из рис. 4.1, где периоды вынужденного простоя машин выделены штриховкой.
Из диаграммы следует, что время простоя второй машины
время простоя третьей машины ,
Рисунок 4.1-Диаграмма Ганта
а суммарная продолжительность всех работ
.
Варианты заданий
Дата публикования: 2015-02-22; Прочитано: 315 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!