Организационный смысл алгоритма джонсона заключается в. Задача Джонсона

Алгоритм Джонсона

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся ребра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.

Алгоритм

Дан граф с весовой функцией. Если веса всех ребер в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся ребра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество ребер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов ребер должно удовлетворять следующим свойствам.

· Для всех ребер новый вес.

· Для всех пар вершин путь является кратчайшим путем из вершины в вершину с использованием весовой функции тогда и только тогда, когда -- также кратчайший путь из вершины в вершину с весовой функцией.

Сохранение кратчайших путей

Пусть дан взвешенный ориентированный граф с весовой функцией, и пусть -- произвольная функция, отображающая вершины на действительные числа. Для каждого ребра определим:

Пусть -- произвольный путь из вершины в вершину является кратчайшим путем с весовой функцией тогда и только тогда, когда он является кратчайшим путем с весовой функцией, то есть равенство равносильно равенству Кроме того, граф содержит цикл с отрицательным весом с использованием весовой функции тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции.

Изменение веса

1. Для данного графа создадим новый граф, где, для некоторой новой вершины, а.

2. Расширим весовую функцию таким образом, чтобы для всех вершин выполнялось равенство.

Недостатком этого алгоритма является то, что в общем случае работа алгоритма может занять значительное время. /3/

Алгоритм муравья

Главная идея алгоритма муравья (метода муравьиных колоний) состоит в моделировании поведения колонии муравьев, которые способны находить кратчайший путь от муравейника до источника пищи и приспосабливаться к изменяющимся условиям внешней среды, находя новый кратчайший путь, если старый в силу каких-либо обстоятельств оказывается недоступным. При движении муравей откладывает феромон, отмечая свой путь, и эту информацию используют другие муравьи. Таким образом, взаимодействие между агентами (муравьями) происходит посредством непрямой коммуникации. /22/

Если моделировать перемещение муравьев на некотором графе, ребра которого представляют собой пути возможного перемещения муравьев, то помимо положительной обратной связи (откладывания феромона) необходимо моделировать отрицательную обратную связь, т.е. испарение феромона. Наличие отрицательной обратной связи гарантирует, что муравьи будут искать другие пути от колонии до источника пищи, т.е. найденное локально оптимальное решение не будет единственным. Решением задачи будет наиболее обогащенный феромоном путь на ребрах графа, который является оптимальным.

Муравьиные алгоритмы позволяют получить решения многих дискретных комбинаторных задач не хуже вышеперечисленных алгоритмов. Чрезвычайно хорошие результаты муравьиной оптимизации получаются для распределенных систем, параметры которых изменяются во времени. Особенностью муравьиных алгоритмов является не-конвергентность - даже после многих итераций одновременно исследуется множество разных решений, что позволяет не застревать в локальных оптимумах. /4/

В данной работе для решения задачи коммивояжера был выбран алгоритм муравья.



План:

    Введение
  • 1 Алгоритм
    • 1.1 Сохранение кратчайших путей
    • 1.2 Изменение веса
    • 1.3 Основная процедура
  • 2 Сложность
    • Литература

Введение

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.


1. Алгоритм

Дан граф G = (V ,E ) с весовой функцией . Если веса всех рёбер ω в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер , должно удовлетворять следующим свойствам.


1.1. Сохранение кратчайших путей

Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф с весовой функцией , и пусть - произвольная функция, отображающая вершины на действительные числа. Для каждого ребра определим

Пусть - произвольный путь из вершины v 0 в вершину v k . p является кратчайшим путем с весовой функцией ω тогда и только тогда, когда он является кратчайшим путем с весовой функцией , то есть равенство равносильно равенству . Кроме того, граф G содержит цикл с отрицательным весом с использованием весовой функции ω тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции .


1.2. Изменение веса


1.3. Основная процедура

В алгоритме Джонсона используется алгоритм Беллмана - Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возврашает обычную матрицу D = d i j размером , где , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

Алгоритм Джонсона

Строится граф G " if Bellman_Ford = FALSE then print «Входной граф содержит цикл с отрицательным весом» else for для каждой do присвоить величине h (v ) значение , вычисленное алгоритмом Беллмана - Форда for для каждого ребра do for для каждой вершины do вычисление с помощью алгоритма Дейкстры величин для всех вершин for для каждой вершины do return D

2. Сложность

Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно O (V 2 logV + V E ) . При более простой реализации неубывающей очереди с приоритетами время работы становится равным O (V E logV ) , но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда - Уоршелла.

скачать
Данный реферат составлен на основе статьи из русской Википедии . Синхронизация выполнена 20.07.11 23:27:10
Похожие рефераты:

Общий случай задачи выбора последовательности обработки деталей на двух станках, если детали должны пройти обработку на одном станке, а затем на втором и на станке не может обрабатываться больше одной детали, рассмотрел в 1954 г. С. Джонсон. Метод решения такой задачи называют алгоритмом Джонсона.

Рассмотрим участок с двумя агрегатами. Совокупность деталей должна последовательно пройти обработку на первом агрегате, а потом на втором. Между агрегатами отсутствует склад, поэтому занятость второго агрегата задерживает освобождение первого. Требуется выбрать очередность обработки деталей, обеспечивающую меньшее суммарное время занятости участка. Это время рассчитывается от момента начала обработки первой детали на первом агрегате до окончания обработки последней детали на втором агрегате.

Очевидным является вывод, что выигрыша во времени можно достигнуть только за счет параллельной работы агрегатов. Длительная занятость первого агрегата, пока второй стоит, так же как и занятость второго, когда первый агрегат уже закончил работу, нерациональны. Отсюда ясно, что на первое место в очередности следует поставить деталь с меньшим временем обработки на первом агрегате. Аналогично на последнее место следует поставить деталь, у которой самое короткое время обработки на втором агрегате. Если это правило распространить на всю совокупность деталей, то получим алгоритм Джонсона.

Обобщения алгоритма Джонсона Значительно больший практический интерес представляло бы решение задачи, подобной задаче о двух станках, для произвольного количества m станков, на которых должны последовательно пройти обработку п деталей. Анализируя алгоритм Джонсона для задачи о двух станках, можно извлечь из него рекомендации, применимые и к общему случаю последовательной обработки деталей на п танках при произвольном m. Обобщения алгоритма Джонсона: 1. В обработку сначала запускают детали, требующие минимальное время обработки на первом станке в порядке возрастания этого времени. 2. В обработку запускаются сначала детали, требующие максимальное время обработки на последнем станке в порядке убывания этого времени. 3. В обработку запускаются сначала детали, у которых “узкое место” находится дальше от начала процесса обработки (“узким местом” для данной детали называется станок, на котором обработка этой деталей занимает наибольшее время). 4. Обрабатываются вначале детали, у которых суммарное время обработки на всех станках максимальное в порядке убывания этого времени.

Каждое из вышеописанных обобщений алгоритма Джонсона в определенных условиях имеет свои преимущества и свои недостатки. Каждое из этих правил в определенной степени логично. Применение первого из них способствует скорейшему вовлечению в обработку второго станка. Второе правило позволяет уменьшить конечный простой первого станка. Третье правило способствует наиболее быстрому "проскакиванию" к концу технологической линии тех деталей, для которых обработка на первом станке занимает меньшее время, с тем, чтобы освободить первый станок деталям, для которых он является узким местом. К сожалению, эти правила не совместимы друг с другом: последовательность обработки, найденная с использованием одного из них, не соответствует последовательности, полученной по другим правилам.

Пример решения задачи методом Джонсона Время обработки, мин Станок деталь 1 2 3 4 5 Суммарное время обработки 2 5 10 1 5 8 7 5 1 10 3 5 10 2 3 7 7 4 4 5 9 3 1 10 7 4 8 3 1 4 1 2 9 8 2 8 9 2 6 11 25 29 23 27 30 20 22 36

В результате решения задачи по четырем выше указанным рекомендациям получаем такой порядок запуска деталей в обработку: – по первой рекомендации: 7 -1 -3 -6 -2 -4 -8 -5; – по второй рекомендации: 2 -8 -5 -4 -6 -3 -7 -1; – по третьей рекомендации: 2 -8 -5 -7 -3 -1 -6 -4; – по четвертой рекомендации: 8 -5 -2 -4 -1 -3 -7 -6. Примечание. Если по какой-либо рекомендации две, или больше деталей оказываются равноценными, то для определения их приоритетов следует воспользоваться какой-либо другой рекомендацией. Например, по рекомендациям вторая и восьмая детали равноценны, но по первой рекомендации целесообразно в обработку запустить сначала вторую деталь, т. к. время ее обработки на первом станке меньше, чем у восьмой детали.

Для каждой детали найдем сумму мест во всех полученных решениях: первая деталь: (2 + 8 + 6 + 5) = 21; вторая деталь: (5 + 1 + 3) = 10; третья деталь: (3 + 6 + 5 + 6) = 20; четвертая деталь: (6 + 4 + 8 + 4) = 22; пятая деталь: (8 + 3 + 2) = 16; шестая деталь: (4 + 5 + 7 + 8) = 24; седьмая деталь: (1 + 7 + 4 + 7) = 19; восьмая деталь: (7 + 2 + 1) = 12.

Расположим детали в порядке возрастания суммы мест: 2– 8– 5– 7– 3– 1– 3– 6. Это и является новым решением. При решении конкретных задач для трех и более станков рекомендуется проанализировать результаты, полученные по каждому из этих правил, и в качестве окончательного варианта выбрать ту последовательность, которая обеспечивает минимум суммарного времени обработки.

Исходные данные и искомые величины при составлении расписаний. Понятие регулярного критерия.

Постановка задачи в ТР начинается с описания система устройств и множества работ. Для простого процесса обслуживания система обслуживающих устройств(ОУ) описывается их числом, то есть есть m устройств, n работ. F[i] – работа, а i номер работы в расписании. Исходные данные:

ti – длительность выполнения операции, то есть длина интервала времени, требуемого iым устройством для выполнения работы(аргумент)

Регулярные критерии позволяют сравнивать расписания
3. Упорядочение работ для одной машины. Искусственные простои и прерывания. Перестановочные расписания.

Система состоит из 1 обслуживающего устройства. На входе стоят n работ. Время выполнения каждой работы известно. Надо составить расписание, минимизирующее среднее время пребывания работы в системе, под которым будем понимать величину, состоящую из:

Время ожидания

Время обслуживания


3. Минимизация среднего времени пребывания работ в системе n|1.


Соотношение между длительностью прохождения и средним числом работ в системе.


5. Составление расписаний в случае критерия с учетом веса в системе n|1.




Составление расписаний в соответствии с плановым сроком. Теорема Джексона.




7. Расписания с упорядочением работ в виде цепочек, которые не могут разрываться в системах n|1.

Пусть есть n работ, которые объединены в k цепочек. Цепочки разрывать нельзя при составлении расписаний, то есть, если началась выполняться первая работа из цепочки, то должны выполняться остальные работы в цепочке. Надо составить расписание, минимизирующее время пребываний работ.

ti – время выполнения цепочки

Fi – время пребывания в системе цепочки

hj – расстояние между последней работой в цепочке и jой

Fij = Fi – hij

Нужно минимизировать:

Так как hij не зависит от расписания, то сумма по hij тоже не зависит. Чтобы (*) минимизировать надо минимизировать:

В расписании, минимизирующем среднее время пребывания в том случае, когда цепочки сгруппированы и их разрывать нельзя:


8. Составление расписаний в системах n|1 при заданном отношении предшествования (цепочки, которые можно разрывать).


9. Расписания для систем конвейерного типа. Теорема о порядке выполнения на двух первых машинах. Теорема о порядке выполнения на двух первых и двух последних машинах в системе n|m|F|F max .


Задача Джонсона. Теорема Джонсона. Алгоритм, основанный на теореме Джонсона.


Алгоритм:

1) Выбрать работу с мин длительностью прохождения на устройстве А

2) Выбрать работу с мин длительностью прохождения на устройстве В

3) Если А

4) Вынесенную в итоговое расписание работуиз списка доступных вычеркнуть

5) Повторять 1-4 до тех пор, пока все работы не выйдут из списка доступных(то есть будет готовое расписание)


11. Оптимальные расписания для системы n|m|F|F max .


Но если m>3, то составление расписания сложно. Схемы:

Полный перебор(из-за факториального роста вычислительной сложности не применяется)

Динамическое программирование(путём разбиения сложных задач на более простые подзадачи)

Метод ветвей и границ

Метод ветвей и границ – метод решения задач дискретной оптимизации, основанный на вычислении оценок и ветвлений. Это пошаговая процедура конструирования расписаний:

в любой момент времени есть набор претендентов на оптимальное расписание, из которых постоянно выбираем лучшее, используя оценки.

Иначе говоря, метод ветвей и границ за счет оценок существенно уменьшает полный перебор за счет того, что поиск «лучшего» расписания ведется в группе тех расписаний, которые не хуже остальных. То есть в результате такого перебора найдется расписание, которое не хуже любого другого. В самом плохом случае метод ветвей и границ может привести к полному перебору.


13. Параллельные приборы. Система заданий с древовидной структурой.

Есть система задач, причем:

В этой системе определено отношение предшествования(работа может выполняться только если выполнена предшествующая)

Время выполнения каждой работы одинаково и равно единичке

В определенный момент времени: одни работы готовы(предшественники выполнены) и не готовы(иначе).

Для решения целесообразно использовать уровневую стратегию:

На освободившееся устройство назначается задача, готовая к выполнению и дальше всего находящаяся от корня дерева.

Готовое расписание

Методические указания к лабораторной работе

алгоритм Джонсона

по курсу «ТЕОРИЯ информационныx систем»
для специальностей и направлений подготовки:

Специальности (направления)

Квалификация специалиста

Наименование

Наименование

Информационные системы

Бакалавр информационных систем

Информационные системы и технологии


УДК 774:002:006.354

Составители: О. Е. Александров.

Научный редактор: доц., канд. физ.-мат. наук О. Е. Александров

Алгоритм Джонсона: Методические указания к лабораторной работе / О. Е. Александров Екатеринбург: УГТУ-УПИ, 2010. 17 с.

Изложен алгоритм оптимизации последовательности операций и отыскания минимального времени простоя. Приведены задания для самостоятельного выполнения.

Библиогр. 0 назв. Рис. 3. Табл. 4. Прил. 1.

Подготовлено кафедрой «Информационные системы и технологии».

Методические указания обсуждены на заседании кафедры, протокол №__

Заведующий кафедрой ________________

© Уральский государственный технический университет, 2000


Содержание

Перечень условных обозначений символов, единиц и терминов 4

Введение 4

1. Задача упорядочения. алгоритм Джонсона 4

2. Задания для самостоятельного выполнения 14

Заключение 16

Список использованных источникоВ 17

Перечень условных обозначений символов, единиц и терминов

    суффикс «b» означает число, записанное по основанию 2 - двоичное число;

    суффикс «h» означает число, записанное по основанию 16 - шестнадцатиричное число;

    суффикс «.» означает число, записанное по основанию 10 - десятичное число;

N 1 ..N 2

    диапазон целых чисел от N 1 до N 2 ;

[X 1 ..X 2)

    интервал чисел от X 1 до X 2 , X 1 принадлежит интервалу, X 2 – не принадлежит;

Введение

Системы – сложные устройства со множеством внутренних связей-взаимодействий. Многие системы призваны выполнять некие последовательности операций, например, сборочное производство.

Эти последовательности содержат сотни и тысячи операций разной длительности и выполняются на ограниченном количестве оборудования. В результате суммарная длительность операций может различаться в зависимости от порядка их выполнения. Возникает проблема отыскания оптимальной (самой короткой) последовательности операций.

Данная лабораторная работа рассматривает один из алгоритмов упорядочения последовательности действий при заданных ограничениях, а именно, алгоритм оиыскания оптимальной последовательности операций.

Ниже изложена простейшая теория и алгоритм Джонсона [ 1 ].

1. Задача упорядочения. алгоритм Джонсона

1.1. Постановка проблемы

Страстные любители зрелищ, мексиканцы охотно принимают ансамбли варьете, разъезжающие по провинциальным городам. И вот директор бродячей труппы «Алькасар» 1 при посещении каждого нового города сталкивается с проблемой, на решение которой он потратил несколько лет 2 .

В самом деле, различные города предоставляют не одни и те же удобства; иногда там имеются превосходные залы, благоустроенные авансцены и кулисы; но, увы, слишком часто они больше годятся для продолжительных представлений, чем для последовательности номеров, составляющих программу труппы «Алькасар».

Отсюда и получается, что хотя номера на сцене идут всегда одно и то же время, но подготовка их (одевание, гримировка) занимает довольно неустойчивое время, изменяясь вместе с удобствами театральных уборных. Однако директор труппы тем не менее желает представить свою программу за минимальное время, что сводится к минимизации общего времени ожидания между последовательными номерами (или, иначе, общего времени присутствия на сцене ведущего).

Чтобы упростить задачу, будем предполагать, что время, необходимое для смены дополнительных декораций, пренебрежимо мало, и будем представлять себе, что начало представления для всех: зрителей, актеров, вспомогательного персонала - одно и то же, т. е. что ни зал, ни сцену нельзя занимать до этого начала.

В городке Орисаба было подсчитано, сколько времени уходит на подготовку каждого номера и его выполнение на сцене (табл. 17.1). Мы видим, что руководитель труппы принял для представления на сцене в этом городе определенный порядок следования номеров.

Таблица 17.1.

программы

Время (в минутах)

Принятая

очередность

подготовка

выполнение

Так как количество номеров равно 8, то имеется 8! = 40 320 различных способов следования номеров в представлении; как выбрать тот, который будет отвечать определенному выше критерию?

Исследуем прежде всего, что произойдет, если мы выберем наугад какой-нибудь порядок следования, например: b, f, с, h, g, a, d, е . Рисунок 17.1, -а это не что иное, как диаграмма Ганта, - позволяет легко подсчитать время простоя. Первая линия диаграммы составлена отрезками, подогнанными, так сказать, впритык, длина которых пропорциональна времени соответствующей подготовки разных номеров, взятых в выбранном порядке.

Тогда вторая линия позволяет сравнительно просто определять начало и окончание номера на сцене, если заметить, что для представления номера на сцене необходимо закончить подготовку к нему и что для перехода к следующему номеру необходимо завершить проведение на сцене данного.

Третья линия изображает собою время простоя, получающееся в результате сравнения предыдущих двух линий.

В выбранном нами примере полное время простоя достигает 31 минуты.

1.2. Описание идеи алгоритма Джонсона

Зато время простоя, которое соответствует очередности е, h, a, g, f, с, d, b (рис. 17.2), составляет лишь 13 мин., из них 12 перед началом представления. Выигрыш довольно значителен; поэтому имеет смысл познакомиться с алгоритмом Джонсона, который позволил получить его:

1) Изучается таблица количеств времени, необходимых для выполнения двух операций (подготовки номера и его проведения на сцене), и наименьшее из них отмечается; в данном случае это 8 минут - время проведения на сцене номера b .

2) Если это значение относится к операции первого типа (подготовка), то принимается решение начинать с соответственной операции; если, наоборот, оно относится к операции второго типа (проведение на сцене), то принимается решение оканчивать соответственной операцией. В данном случае речь идет о проведении номера на сцене; таким образом, номер b будет завершать представление.

3) Строка, относящаяся к только что сделанному распределению, вычеркивается из таблицы времен, и к оставшимся значениям вновь применяются пункты 1), 2), 3).

Таблица 17.2.

Место в последовательности

Номера итераций вычисления

Пример. Если из таблицы 17.1 вычеркнуть строку b , то наименьшее имеющееся время будет равно 10 минутам, оно соответствует номеру d и проведению на сцене; значит, номер d будет завершать номера, еще подлежащие распределению: он будет непосредственно предшествовать номеру b , назначенному ранее.

Вычеркнув из таблицы строки b и d , распределим с (11 минут, сцена), аналогично: f (12 минут, сцена), е (12 минут, подготовка), h (15 минут, подготовка), а (20 минут, подготовка) и, наконец, g (20 минут, сцена).

Таблица 17.2 показывает порядок очередности, полученный в процессе последовательных итераций. Варианты, которые имеют место (е можно распределить на четвертой итерации, а f - на пятой; а - на последней, a g - на предпоследней), ничего не меняют в конечном результате: время простоя - по-прежнему 13 минут.

Несколько дней спустя труппа «Алькасар» оказывается в Веракрусе; устройство зала, снятого директором труппы, позволяет сократить время на подготовку, но в то же время члены труппы, исполняющие номера b и h , изменили время своего пребывания на сцене (табл. 17.3).

Таблица 17.3.

программы

Время (в минутах)

подготовка

выполнение

Применение алгоритма Джонсона дает в результате следующую очередность: d, е, b, h, a, g, f, с, которая, согласно рис. 17.3, дает время простоя в 17 мин.

Но в один прекрасный вечер одна из гримировщиц оказывается больна; нет ни возможности заменить ее, ни времени, чтобы исправить афишу. В этих условиях (табл. 17.4) время простоя увеличивается и достигает 25 мин. По своему обыкновению, директор, узнав, что гримировщица выбывает из коллектива дней на восемь, принимается за задачу минимизации. Тогда он пришел к результату, изображенному на рис. 17.5, с временем простоя в 24 мин., что не очень блестяще, но тем не менее дает некоторое улучшение.

Таблица 17.4.

программы

Время (в минутах)

подготовка

выполнение

Браво, директор «Алькасара»!

1.2. Алгоритм Джонсона

Алгоритм Джонсона, который мы использовали выше, позволяет, таким образом, решать задачу установления очередности работ, выполняемых в два последовательных этапа; в некоторых случаях его даже можно распространить на трехэтапные, но не выше. Тем не менее он, как мы видели, весьма полезен.

Сейчас мы познакомимся с некоторыми случаями его применения к производственным процессам.

На рис. 17.6 схематически изображен процесс обработки, состоящий из расточки (машина А ) и последующей чистовой обработки (машина В ), которой подвергаются n различных деталей, поступающих в произвольном порядке для ремонта.

Время, идущее на каждую операцию, распределено очень неравномерно: обозначим через A i и B i время обработки i-й детали соответственно на машинах A и В .

Задача заключается в том, чтобы минимизировать время простоя машины B , т. е. найти порядок следования

p 1 , p 2 , ..., p i , ..., p n ,

который соответствовал бы наименее продолжительному полному ожиданию в промежутках между чистовой обработкой детали p j и детали p j+ 1 , причем сумма берется по последовательным значениям j .

Обозначим через T полное время, которое пройдет от начала расточки первой детали до конца чистовой обработки последней; пусть Х i есть время простоя между концом выполнения работы p i - 1 на машине В и началом работы p i на той же самой машине. Имеем (рис. 17.7)

и так как
известна, то надлежит минимизировать

Из рис. 17.7 можно еще усмотреть, что Х 1 = А 1 и

Следовательно, будет отыскиваться такое Х 2 , чтобы

Исследуем теперь сумму Х 1 + Х 2 ; имеем

Х 1 + Х 2 = Х 1 + max (A 1 + A 2 – B 1 – X 1 ;0 ) =

= max (A 1 + A 2 – B 1 ;X 1) =

= max (A 1 + A 2 – B 1 ;A 1)=

Аналогично,

Эта формула легко распространяется на n временных промежутков X i для некоторого порядка следования S деталей p i

ее можно записать еще лаконичнее:

Это означает, что берется максимум разностей, получаемых при каждом значении r , по всем r от 1 до n .

Таким образом, можно положить

Пусть теперь имеется порядок (S 1)

(S 1) = (p 1 , p 2 , p 3 , ..., p k- 1 , p k , p k +1 , p k+2 , …, p n )

и порядок (S 2 ), полученный из (S 1) перестановкой k -го и (k +1)-го элементов

(S 2 ) = (p 1 , p 2 , p 3 , ..., p k- 1 , p k+ 1 , p k , p k+2 , …, p n ).

Значения и , получаемые для порядков следования (S 1) и (S 2), одинаковы при всех r, кроме, может быть, r= k и r= k + 1.

    Стало быть, мы имеем

то какой-то из двух порядков следования (S 1) и (S 2) предпочтительнее. Порядок (S 1), в котором k+ 1 следует за k , будет лучше, чем (S 2), в котором k+ 1 предшествует k , если

Поэтому можно записать

Соотношение (1) при этих условиях принимает следующий вид:

Min (A k+ 1 ; B k ) < - min (A k ; B k+ 1)

или иначе

min (A k ; B k+ 1) < min (A k+ 1 ; B k ). (2)

Отсюда следует, что порядок (…, p k , p k+ 1 , …) предпочтительнее порядка (…, p k+ 1 , p k , …), если

min (A k ; B k+ 1) < min (A k+ 1 ; B k ).

Рассмотрим тогда порядок

(S′ ) = (... , p k , p l , ... ),

которого всегда можно достичь перестановками. Менять местами элементы p k и p l не нужно, если

min (A k ; B l) ≤ min (A l ; B k ); (3)

последнее выполняется, если A k не превосходит B l , A l , B k

min (A k ; B k ) ≤ min (A l ; B l).

Следовательно, если в таблице времен можно найти время, не превосходящее всех прочих A l или B l , то искомый порядок должен будет начинаться с p k , если время A k , будучи по-прежнему наименьшим, равно некоторым другим A l или B l , искомый порядок можно будет начинать также с p k .

Соотношение (3) выполняется еще в том случае, когда B l не превосходит A k , A l , B k , что можно также записать в виде

min (A l ; B l) ≤ min (A k ; B k ).

Следовательно, если в таблице времен можно отыскать время B l , не превосходящее всех прочих A k или B k , то искомый порядок должен завершаться элементом p l ; если время B l , будучи по-прежнему наименьшим, равно некоторым другим A k или B k , искомый порядок можно с таким же правом завершать элементом p l .

Легко заметить, что определение порядка следования можно тогда осуществлять по шагам согласно алгоритму Джонсона.

Обобщение на трехэтапные работы. Алгоритм Джонсона применим для последовательности n работ, подлежащих выполнению в таком порядке: А , В и С , в двух нижеследующих случаях:

min A i ≥ max B i или min C i ≥ max B i .

Тогда осуществляется поиск оптимальных сроков по суммам

A i + B i и B i + C i .

Пример. Пусть операции над деталями p 1 , ..., p 5 заданы сроками выполнения

A i , B i , C i ;

условие min A i = 6 ≥ rnax B i = 6, например, выполняется. Таким образом, мы имеем две таблицы:

Расточка

(A i )

Фрезеровка

(B i )

Чистовая обработка

(C i )

A i + B i

B i + C i


и алгоритм Джонсона позволяет выбрать

S = (p 4 , p 2 , p 3 , p 1 , p 5)

S = (p 4 , p 2 , p 1 , p 3 , p 5).

2. Задания для самостоятельного выполнения

2.1. Общие замечания

Задание лабораторной работы выполняется индивидуально. Варианты помеченные звездочкой имеют повышенную сложность и могут выполняться группой до 2-х человек.

Варианты помеченные звездочкой дают право на освобождение от экзамена (при полном выполнении) или на освобождение от одного вопроса на экзамене (при частичном выполнении). Уровень  полное/частичное выполнение  определяет преподаватель.

Для выполнения лабораторной работы вам необходимо:

    Ознакомиться с теорией главы 1.

    Ознакомиться с приложенной программой-решением задачи Форда-Фалкерсона.

    Выполнить задание к лабораторной работе.

    Написать и сдать отчет.

2.2. Варианты заданий

Вариант 1 (стандартный)

Опираясь на пример решения задачи Джонсона в прилагаемой программе, обобщить это решение на случай трехэтапных операций.

    Классифицировать данную систему в соответствии с теорией систем (курсом лекций).

    Указать для данной системы: множество входов, множество выходов, множество глобальных состояний.

    Записать реакцию системы (либо выходную функцию).

Вариант 2 *

    Разработать и описать комбинированный алгоритм (Фаулкс+Джонсон) по выбору допустимой последовательности операций и оптимизации этой ДОПУСТИМОЙ последовательности по времени.

    Создать автоматизированную систему (программу) вычисления по предложенному алгоритму.

ВНИМАНИЕ!!! Самодельные реализации принимаются только в MathCAD.

1.2. Оформление результатов работы

Вы должны представить письменный отчет (один на группу) по выполненной работе (1020 страниц, не считая листингов программы - листинги рекомендуется не печатать) и работоспособный код программы. Отчет должен быть оформлен в соответствии со стандартом [ 2 ].

Отчет должен состоять из следующих частей:

    титульный лист;

    введение;

    основная часть (может состоять из нескольких глав);

    заключение;

    список использованных источников.

Отчет должен содержать:

    краткий обзор математических алгоритмов сжатия информации, при-вет-ству-ется описание алгоритмов не упомянутых в данных методических указаниях;

    описание проблем, с которыми вы столкнулись при написании программы, и их решений;

    подробное описание вашего кода и наиболее интересных решений, использованных в нем;

    описание результатов сравнения эффективности работы вашего и предоставленного вам готового кода.

Работоспособный код вашей программы представляется в виде исходного файла (файлов) программы на дискете. Распечатывать полный листинг не нужно.

1.4. Прием зачета по результатам работы

Зачет принимается в форме обсуждения отчета о выполнении лабораторной работы и программы с членами группы, представившей отчет. При обсуждении отчета каждый из членов группы должен продемонстрировать:

    Знание основ теории.

    Знание устройства и взаимодействия частей представленного и/или своего кода программы.

    Умение компилировать код и запускать программу.

    Умение модифицировать свой код программы и способность объяснить назначение (функции) отдельных частей кода программы.

    Умение интерпретировать результаты сравнения работы своего и предоставленного вам готового кода.

Заключение

В результате выполнения этой работы:

    Вы сможете лучше понять что такое упорядочение операций.

    Ознакомитесь с примерами методов оптимизации порядка выполнения операций.

    Получите практический навык использования алгоритма L;jycjyf.

    Алгоритм Беллмана-Форда. Алгоритм Флойда. Топологическая сортировка. Сильно... . Потоки в сетях. Метод Форда-Уоршола. Алгоритм Джонсона для разреженных графов. Метаэвристики в примерах...

  1. Алгоритмы построения расписаний для одноприборных систем входящих в состав систем реального времени

    Документ

    Функции становится единственно значимым. В алгоритмах «упаковки» и алгоритмах сочетающих жадные стратегии и стратегии... М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. - М.: Мир, 1982. Костенко В.А., Гурьянов Е.С. Алгоритм построения...

  2. Основная образовательная программа (100)

    Основная образовательная программа

    Задача «Максимальная выполнимость» Вероятностный алгоритм Джонсона . Дерандомизация. Алгоритм Гоеманса-Вильямсона. 3.11. Решение... (r|p)-центроиде. 13. Рандомизированные алгоритмы