Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Тема 1. Модели упорядочения.
Характеризуются следующими особенностями. Например, имеется множество различных деталей с определенными технологическими маршрутами, а также несколько единиц оборудования (фрезерный, токарный, шлифовальный станки), на которых эти детали обрабатываются, т.к. одновременно обрабатывать более одной детали невозможно, у некоторых станков может образоваться очередь, т.е. деталей, ждущих обработки. Время обработки каждой детали известно. Определить такую очередность обработки деталей на каждом станке, при котором минимизируется некоторый критерий оптимальности, например, суммарная продолжительность завершения комплекса работ. Такая задача называется задачей календарного планирования или составления расписания, а выбор очередности запуска деталей в обработку – упорядочением. В качестве примера рассмотрим упрощенный вариант этой задачи, для которой разработан удобный алгоритм. Пусть имеется несколько изделий, каждая из которых должна быть обработана на 2-х машинах (станках). Известны время обработки и последовательность обработки каждого изделия на каждой машине. Требуется выбрать такой порядок обработки изделий, при котором суммарное время обработки будет минимальным. Основные ограничения: а) время перехода от одной машины к другой незначительно и им можно пренебречь; б) каждое изделие обрабатывается в определенном технологическом порядке; в) каждое обслуживание должно быть завершено прежде, чем начнется следующее. Обозначим - время обработки j-го изделия на 1-й машине, - на 2-й машине. Пример:
Построение модели. Пусть - время простоя 2-й машины между концом выполнения работы по обработке -го изделия на 2-й машине и началом обработки -го изделия на той же самой машине. Тогда суммарное время обработки изделий составит: Так как сумма известна, то надлежит минимизировать (в нашем случае ). Построение алгоритма. Для нахождения оптимальной последовательности порядка обслуживания “m” требований на 2-х пунктах обслуживания наибольшую известность получил «алгоритм Джонсона». Включает следующие этапы: а) поиск наименьшего элемента: Рассмотрим все и и среди них выберем минимальное, т.е. . В нашем случае это . б) перестановка изделий: Если выбранная величина находится в 1-й строке (относится к 1-й машине), то соответствующее изделие помещается на обслуживание в первую возможную очередь. Если – во 2-й строке (относится ко 2-й машине) – то в последнюю очередь. в) исключение из рассматриваемого выбранного изделия: Выбранному изделию присваивается новый номер в очереди, который в дальнейшем считается занятым. Из последующего рассмотрения оно исключается. Далее осуществляется переход к этапу а). После определения оптимального порядка обработки изделий на машинах графически определяется время простоя и работы 2-й машины, которое является минимальным из всех возможных.
Тmin=23+4+1=34
Задачи (для самостоятельного решения). Определить оптимальный порядок обработки изделий:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-21; просмотров: 197; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.63.136 (0.011 с.) |