Реферат Курсовая Конспект
Детерминированные задачи упорядочивания. - Лекция, раздел Науковедение, Курс лекций по дисциплине: МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ 1) Постановка Задачи: Имеется Несколько Издел...
|
1) Постановка задачи:
Имеется несколько изделий, каждое из которых надо обработать на двух машинах последовательно (сначала на первой, потом на второй). Известны времена обработки каждого изделия на каждой машине.
N изд | ||||||
t 1 j | ||||||
t 2 j |
t 1 j – время обработки j-го изделия на первой машине.
t 2 j – время обработки j-го изделия на второй машине.
2) Формализованное описание задачи:
1) Время перехода детали от первой машины к другой незначительно и его можно не учитывать.
2) Каждое изделие должно быть обработано в определенном порядке: сначала на первой машине, потом – на второй.
3) Каждое обслуживание должно быть завершено прежде, чем начнется следующее, прерываться нельзя.
Изобразим процесс обработки изделия на двух машинах графически
3) Построение математической модели.
Пусть t n j – время простоя второй машины. Тогда суммарное время обработки изделий составит
n n
y = ∑ t 2 j + ∑ t n j = 29 + 12 = 41
j=1 j=1
n n
т.к. ∑ t 2 j - известна, то надлежит минимизировать ∑ t n j
j=1 j=1
4) Наследование математической модели.
Известен простой алгоритм для нахождения оптимальной последовательности порядка обслуживания n изделий на двух пунктах обслуживания (алгоритм Джонсона). При этом каждое из изделий должно пройти обслуживание на первом пункте, а затем на втором.
Если использовать метод прямого перебора при наличие n изделий и двух пунктов (машин) существует n! Возможных вариантов. Для нашего примера 720 вариантов.
Алгоритм Джонсона включает следующие этапы:
а) поиск наименьшего элемента. Ищем в таблице наименьший элемент (равен 2 относится ко второй машине), отмечаем его точкой.
N изд | ||||||
t 1 j | 4 * | |||||
t 2 j | 5 * | 3 * | ||||
Номер цикла |
б) перестановка изделий. Если этот элемент относится к первой машине, то столбец поставить на первое место, если ко второй, то на последнее место. При наличие равных минимальных элементов в обеих строках, то на первое (последнее) место в таблице ставится изделие, которому соответствует меньший элемент второй (первой) строки.
в) Вычеркивание из таблицы столбца, отмеченного точкой и возвращение к n(а). И так далее, пока не будет исчерпаны все детали.
В результате получим следующую таблицу:
N изд N j | ||||||
t 1 j | ||||||
t 2 j |
После определения оптимального порядка обработки деталей графически определяем время простоя работы второй машины.
y min = 29 + 4 + 1 = 34
Алгоритм Джонсона работает только для двух машин, есть частные случаи и для твех машин. В этом случае обработка используется:
а) min {t 1j} ≥ max {t 2j} минимальное время на первой машине не меньше максимума t 2j , тогда следует сложение: t 1j + t 2j и рассмотреть их как для I-ой машины, а III машина в качестве II-ой машины.
б) min {t 3j} ≥ max {t 2j}, то складываем (t 2j + t 3j) и считают это для II машины.
Этот алгоритм можно использовать при разработке задач календарного планирования, причем рассматривать большое количество машин, при этом объединять время произвольно.
Тема VIII: Игровые задачи.
– Конец работы –
Эта тема принадлежит разделу:
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ... МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... Курс лекций по дисциплине...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Детерминированные задачи упорядочивания.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов