1. Рассматриваются интервалы времени и , определяется величина .

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

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

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

Рисунок 6.2 – Начальное расписание

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

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

Продолжаем процедуру поиска. Среди не вычеркнутых элементов ищем . После выбора второй детали минимальное время равно 3, и оно соответствует и . Мы можем выбрать любую деталь, поэтому произвольно выбираем , т. е. помещаем на первое место деталь 1. Теперь минимальное время соответствует . Следовательно, деталь 4 ставится на предпоследнее место.

Следующая минимальная величина равна 4 ( и ). Можем назначить 2-е место на первом станке для детали 3 и 3-е место для детали 5.

i	a i	b i	i¢
1
2
3
4
5

Полученная последовательность обработки деталей на двух станка =(1, 3, 5, 4, 2) будет оптимальной.

Эта последовательность представлена диаграммой Ганта на рис.6.3.

Рисунок 6.3 – Оптимальное расписание

Из рис. 6. 3 видно, что время обработки всех деталей равно 28 единиц и суммарное время простоев - 6 единиц.

Замечание. Алгоритм Джонсона применим для последовательности деталей, проходящих последовательную обработку на 3-х станках, в двух нижеследующих случаях:

или .

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

Пример. Пусть операции над деталями задаются сроками выполнения :

i	a i	b i	c i

Условие , например, выполняется. Таким образом, мы имеем:

i	a i	b i	c i	a i + b i	b i + c i

и алгоритм Джонсона позволяет выбрать =(4, 2, 3, 1, 5).

Задания для самостоятельной работы

Найти решение задачи Джонсона для двух последовательных приборов. Длительности обслуживания приборами А и В приведены в таблице.

вариант	Требование время
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B
	t A
	t B

ЗАДАЧА О НАЗНАЧЕНИЯХ

Имеется деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом -ая деталь обрабатывается на первом станке за времени, а на втором — за времени. Каждый станок в каждый момент времени может работать только с одной деталью.

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

Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени S.M. Johnson, который в 1954 г. предложил алгоритм для её решения).

Стоит отметить, что когда число станков больше двух, эта задача становится NP-полной (как доказал Гэри (Garey) в 1976 г.).

Построение алгоритма

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

Рассмотрим порядок подачи деталей на станки, совпадающий с их входным порядком: .

Обозначим через время простоя второго станка непосредственно перед обработкой -ой детали (после обработки -ой детали). Наша цель — минимизировать суммарный простой :

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

Для второй — т.к. она становится готовой к отправке на второй станок в момент времени , а второй станок освобождается в момент времени , то имеем:

Третья деталь становится доступной для второго станка в момент , а станок освобождается в , поэтому:

Таким образом, общий вид для выглядит так:

Посчитаем теперь суммарный простой . Утверждается, что он имеет вид:

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

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

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

Таким образом, чтобы деталь шла до детали , достаточно (хотя и не необходимо), чтобы:

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

Отняв от обеих частей этого неравенства, получим:

или, избавляясь от отрицательных чисел, получаем:

Тем самым, мы получили компаратор : отсортировав детали по нему, мы, согласно приведённым выше выкладкам, придём к оптимальному порядку деталей, в котором нельзя переставить местами никакие две детали, улучшив итоговое время.

Впрочем, можно ещё больше упростить сортировку, если посмотреть на этот компаратор с другой стороны. Фактически он говорит нам о том, что если минимум из четырёх чисел достигается на элементе из массива , то соответствующая деталь должна идти раньше, а если на элементе из массива — то позже. Тем самым мы получаем другую форму алгоритма: отсортировать детали по минимуму из , и если у текущей детали минимум равен , то эту деталь надо обработать первой из оставшихся, иначе — последней из оставшихся.

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

Реализация

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

struct item { int a, b, id; bool operator< (item p) const { return min(a,b) < min(p.a ,p.b ) ; } } ; sort (v.begin () , v.end () ) ; vector< item> a, b; for (int i= 0 ; i< n; ++ i) (v[ i] .a <= v[ i] .b ? a : b) .push_back (v[ i] ) ; a.insert (a.end () , b.rbegin () , b.rend () ) ; int t1= 0 , t2= 0 ; for (int i= 0 ; i< n; ++ i) { t1 + = a[ i] .a ; t2 = max(t2,t1) + a[ i] .b ; }

Здесь все детали хранятся в виде структур , каждая из которых содержит значения и и исходный номер детали.

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

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

Для пояснения алгоритма Джонсона представим матрицу Т как двухстолбцовую  

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

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

Подробная характеристика первых трех вариантов решения задачи дана в главе 11. Напомним, что первый вариант имеет строгое и эффективное решение , называемое по имени его создателя алгоритмом (методом) Джонсона. Второй вариант можно при определенных условиях также свести к решению методом Джонсона, но результат при этом будет не обязательно оптимальным. Строгое решение этой задачи дал Р. Беллман, однако оно трудоемко. Третийвариант самый сложный. Эффективная эвристическая процедура его разрешения известна под названием DS-алгоритм. Этот алгоритм распространяет метод Джонсона на общий случай постановки задачи и обеспечивает околооптимальное решение. Существуют и другие подходы, которые используют теорию очередей и компьютерное моделирование , чтобы решить эту проблему. Но все они трудоемки и сложны и в то же время не гарантируют нахождения оптимальной последовательности.  

Второй пример календарной задачи на оптимизацию заключается в построении графика , наилучшим образом согласующего сроки выпуска продукции на нескольких последовательных стадиях произ-ва (переделах) при различной длительности обработки изделия на каждой из них. Напр., в типографии надо согласовать работу наборного, печатного и переплетного цехов при условии различной трудо-станкоемкости по отдельным цехам разных видов изделий (бланочной продукции, книжной продукции простого или сложного набора, в переплете или без него и т. п.). Задача может решаться при различных критериях оптимизации и различных ограничениях. Так, можно решать задачу на минимальную длительность производств, цикла и, следовательно, минимальную величину среднего остатка изделий в незавершенном произ-ве (заделе) ограничения при этом должны определяться по наличной пропускной способности различных цехов (переделов). Возможна и другая постановка той же задачи, при к-рой критерием оптимизации является наибольшее использование наличной производств, мощности при ограничениях, наложенных на сроки выпуска отдельных видов продукции. Алгоритм для точного решения этой задачи (т. н. задачи Джонсон а) разработан для случаев, когда изделие проходит всего 2 операции, и для приближенного решения при трех операциях. При большем числе операций эти алгоритмы непригодны, что практически их обесценивает, т. к. потребность в решении задачи оптимизации календарного графика возникает гл. обр. в планировании многооперационных процессов (напр., в машиностроении). Е. Боуменом (США) в 1959 и А. Лурье (СССР) в 1960 предложены математически строгие алгоритмы, основанные на общих идеях линейного программирования и позволяющие в принципе решать задачу при любом числе операций. Однако в настоящее время (1965) практически применить эти алгоритмы нельзя они слишком громоздки в расчетном отношении даже для самых мощных из существующих электронных вычислительных машин . Поэтому указанные алгоритмы имеют лишь перспективное значение либо их удастся упростить, либо прогресс вычислительной техники позволит реализовать их на новых машинах.  

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

Постановка задачи в ТР начинается с описания система устройств и множества работ. Для простого процесса обслуживания система обслуживающих устройств(ОУ) описывается их числом, то есть есть 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. Рандомизированные алгоритмы