Алгоритм Джонсона решение задачи о двух станках
1. Рассматриваются интервалы времени и , определяется величина . 2. Если эта величина находится в столбце , то -ю деталь помещаем на первый станок в первую очередь. Если эта величина находится в столбце , то -я деталь занимает последнее место на первом станке. 3. Вычеркиваем выбранную деталь, и продолжаем процедуру поиска, повторяя шаги 1 и 2. В случае одинаковых значений выбираем любую деталь. Полученная последовательность обработки деталей будет оптимальной.
Пример. Пусть время обработки пяти деталей на двух машинах задана в таблице:
Построим диаграмму Ганта обработки деталей в начальный момент времени (рис. 6.2).
Рисунок 6.2 – Начальное расписание
По графику видно, что начальный порядок обработки деталей допускает простои второго станка (суммарное время простоев 8 единиц), длина производственного цикла равна 30 единицам времени. По алгоритму Джонсона определим величину . В нашем примере эта величина равна . Таким образом, деталь 2 на первом станке обрабатывается последней.
Продолжаем процедуру поиска. Среди не вычеркнутых элементов ищем . После выбора второй детали минимальное время равно 3, и оно соответствует и . Мы можем выбрать любую деталь, поэтому произвольно выбираем , т. е. помещаем на первое место деталь 1. Теперь минимальное время соответствует . Следовательно, деталь 4 ставится на предпоследнее место.
Следующая минимальная величина равна 4 ( и ). Можем назначить 2-е место на первом станке для детали 3 и 3-е место для детали 5.
Полученная последовательность обработки деталей на двух станка =(1, 3, 5, 4, 2) будет оптимальной. Эта последовательность представлена диаграммой Ганта на рис.6.3.
Рисунок 6.3 – Оптимальное расписание
Из рис. 6. 3 видно, что время обработки всех деталей равно 28 единиц и суммарное время простоев - 6 единиц.
Замечание. Алгоритм Джонсона применим для последовательности деталей, проходящих последовательную обработку на 3-х станках, в двух нижеследующих случаях: или .
Тогда осуществляется поиск оптимальных строк по суммам или .
Пример. Пусть операции над деталями задаются сроками выполнения :
Условие , например, выполняется. Таким образом, мы имеем:
и алгоритм Джонсона позволяет выбрать =(4, 2, 3, 1, 5).
Задания для самостоятельной работы Найти решение задачи Джонсона для двух последовательных приборов. Длительности обслуживания приборами А и В приведены в таблице.
ЗАДАЧА О НАЗНАЧЕНИЯХ
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (3099)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |