Курсовая работа: Проектирование модели для определения времени простоя станков на машиностроительном предприятии
Элементы этой матрицы определяются из соотношения
Предположим, что деталь 1 запускается на первом станке первой. Тогда
.
В результате деталь 1 не конфликтует ни с какими другими деталями на нервом станке.
2.
Каждому календарному расписанию 
приписываем
его оценку 
в виде минимально
возможного времени окончания Обработки деталей на последнем станке n в предположении, что на первых п — 1
станках конфликты отсутствуют.
Из
матрицы 
известно возможное время
начала обработки любой детали i на
последнем станке. Оно совпадает с временем 
окончания
ее обработки на предпоследнем станке.
Чтобы не увеличивать длительность обработки деталей, целесообразно на последнем станке обрабатывать детали в очередности их поступления на этот станок
,
где
Оценка 
определяется
следующим образом.
Первоначально сравниваем 
с 
.
Если 
, то время завершения обработки двух
деталей i1 и 
на
последней операции будет равно времени окончания обработки детали i2, т. е.
.
Если 
, то 
.
Далее сравниваем время завершения обработки на последнем станке двух первых деталей i1 и i2 с временам завершения обработки на предпоследнем стачке детали i3.Здесь возможны два случая:
1) если
., то 
;
2)
если 
, то 
, и т.д.
В
результате такого цепного расчета получим минимально возможное время обработки
всех деталей 
для варианта расписания 
предположении, что все
конфликты в нем на первых п — 1 станках устранены. Эту величину и принимаем за
нижнюю границу времени окончания обработки деталей по расписанию 
.
Как
видно из матрицы 
, моменты
завершения обработки деталей на предпоследнем, втором станке упорядочены
следующим образом:
,
т. е. детали на последний станок поступают в очередности 1, 3, 2, 4. Выбираем первые две детали 1 и 3 и определяем момент завершения их обработки на последнем станке.
Так
как 
, то 
.
Включаем в рассмотрение третью по
порядку деталь 2. Поскольку, 
то
минимально возможное время обработки первых трех деталей (1, 3, 2) будет
.
Рассматривая последнюю деталь, видим,
что 
.
Следовательно, 
.
Отсюда получаем
.
Повторим действия I и 2 для остальных вариантов, когда первой на первом станке обрабатывается деталь 2, 3 или 4.
Разрешая конфликт в пользу детали 2, получаем
, 
.
Отдавая предпочтение па первом станке детали 3, получаем расписание и его опенку в виде
, 
.
Разрешаем конфликт в пользу детали 4:
, 
.
3.
Сопоставляем расписания 
, 
и их оценки 
с вершинами дерева,
изображающего процесс ветвления всего множества вариантов расписания на
подмножества (рисунок 1).
Рисунок 1
Из
всех рассмотренных календарных расписаний 
выбираем
такое 
, для которого
.
Поскольку наименьшей оценкой является 
, предпочтение к запуску на
первом станке отдается детали l=1.
Остальные m-1=3 детали продолжают конфликтовать
па первом станке.
Четвертый
шаг. В качестве исходного календарного расписания для дальнейших расчетов берем
матрицу 
, на основе которой будем
определять деталь, подлежащую запуску на нервом станке второй. Для этого
построим календарные расписания в виде матриц 
,
элементы которых находятся по правилу
Разрешая
конфликты для каждой из т—1 оставшейся детали на первом станке, получим нижнюю
границу для каждого расписания 
и выберем из всех расписаний то, для которого
.
Деталь k2 планируется к обработке второй. Выполним эти расчеты для нашего примера.
Разрешая конфликт для детали 2, построим для нее календарное расписание с учетом того, что деталь 1 уже назначена к обработке первой, и найдем его нижнюю границу. Получим
, 
.
Разрешаем конфликт в пользу детали 3:
, 
.
Разрешаем конфликт в пользу детали 4:
, 
.
Сопоставим
полученные расписания и их оценки с вершинами дерева, разливаемыми из вершины 
(рисунок 1).
Так как оценки для всех вариантов одинаковы, безразлично, какой из деталей отдать предпочтение. Пусть деталь 2 планируется к запуску на первом станке второй.
Пятый шаг. Аналогичным образом определим деталь, запускаемую на первом станке третьей.
Разрешаем конфликт относительно детали 3:
, 
.
Разрешаем конфликт относительно детали 4:
, 
.
Сопоставляем
полученные расписания и их оценки с вершинами дерева, развиваемыми из вершины 
(рисунок 1). Так как
оценки, связанные с запуском на первом станке трех первых детален в очередности
1, 2, 3 или 1, 2, 4, одинаковы, безразлично, какой из них отдать предпочтение.
Пусть выбрана первая из них, k3=3, тогда последовательность
обработки деталей на первом станке будет 1, 2, 3, 4, с нижней границей, равной
38.
Шестой шаг. В результате предыдущих шагов
получено календарное расписание 
и
последовательность запуска партий деталей на первом станке 
.
Далее провернем и последовательно разрешаем конфликты на втором станке.
Детали 1, 2, 3, 4 планируются к обработке в интервалах времени соответственно (2—5), (6—15), (15—18),(17—36).
Следовательно, на втором станке деталь 2 запускается после детали I, а детали 3 и 4 конфликтуют.
Разрешим конфликт относительно детали 3.
Для
этого на базе 
составим
расписание, в котором элементы 
для
данной детали и деталей, не участвующих в конфликте, остаются без изменения, а
элементы 
и 
возрастают на величину
задержки в поступлении детали 4 на второй станок, которая равна в данном случае
разности 
—
== 1. Получим расписание и
оценку нижней границы:
, 
.
Разрешая конфликт в пользу детали 4, задерживаем подачу детали 3 ко второму станку на 36—15=21, в результате чего расписание и его оценка принимают вид
, 
.
Сопоставляя
эти расписания и оценки с вершинами графа, развиваемыми из вершины 
, выбираем расписание 
, предусматривающее
обработку на втором станке третьей по порядку детали 3.
Таким образом, на этом шаге упорядочена
очередность запусков партий на втором станке в виде последовательности деталей
1. 2, 3, 4 с оценкой времени совокупного цикла 
.
Седьмой
шаг. Отправляясь от расписания 
,
проверяем наличие конфликтующих детален на третьем станке.
Детали 1, 2, 3, 4 планируются к обработке в интервалах времени соответственно (5—18), (15—26), (18—26),(37—38).
Конфликтуют три первые детали. Разрешаем конфликт в пользу детали 1:
, 
.
Разрешаем конфликт в пользу детали 2:
, 
.
Разрешаем конфликт в пользу детали 3:
, 
.
Разветвляем
вершину 
дерева решений (рисунок 1)
в соответствии с полученными оценками. Для определения детали, запускаемой па
третьем станке второй, выбираем расписание 
,
имеющее меньшую нижнюю границу.
Рассматривая его, видим, что на третьем станке конфликтуют детали 2 и 3, обрабатываемые в интервалы времени соответственно (15—29) и (18—26).
Разрешим конфликт, отдавая предпочтение детали 2.
Получим расписание и его оценку:
, 
.
Разрешим конфликт в пользу детали 3:
, 
.
Таким образом, безразлично, какой детали
отдать предпочтение. Пусть второй обрабатывается деталь 2. Проверяя расписание 
, устанавливаем отсутствие
конфликтов па третьем станке.
Мы
нашли один из вариантов календарного расписания. Чтобы убедиться в его
оптимальности, рассмотрим дерево ветвлений и проанализируем значения нижних
границ для всех его оборванных ветвей. Поскольку все нижние оценки не меньше
полученной, считаем расписание 
оптимальным.
Начало времени обработки партий деталей
.
Календарный график работы оборудования,
соответствующий расписаниям 
и А..
Цифры над прямоугольниками — номера деталей, внутри прямоугольника — время начала и окончания обработки партии деталей.
2 МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ. МЕТОД ВЕТВЕЙ И ГРАНИЦ
Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.
Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения.
Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация Комбинаторное искусство”), Я. Бернулли (работа “Искусство предположений”), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций.
Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.
Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок.
В 1859 г. У. Гамильтон придумал игру Кругосветное путешествие”, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.
Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.
Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.
Постановка задачи следующая.
