Методические указания к лабораторной работе алгоритм Джонсона по курсу «теория информационныx систем» для специальностей и направлений подготовки: Специальности (направления) icon

Методические указания к лабораторной работе алгоритм Джонсона по курсу «теория информационныx систем» для специальностей и направлений подготовки: Специальности (направления)


Смотрите также:
Методические указания к лабораторной работе по курсу “Физические основы электроники” для...
Методические указания к выполнению лабораторной работы по курсу «Безопасность жизнедеятельности»...
Методические указания к лабораторной работе №7 по курсам «Основы теории цепей»...
Методические указания к лабораторной работе №109 по физике для студентов всех специальностей...
Методические указания к лабораторной работе по курсу механизация животноводческих ферм...
Методические указания к лабораторной работе по курсу механизация животноводческих ферм...
Методические указания к лабораторной работе по курсу «Технологические основы гап» для студентов...
Методические указания к лабораторной работе по курсу "Компьютерный анализ электронных схем" для...
Методические указания к лабораторной работе по курсу «Промышленные сапр» для студентов дневной...
Методические указания к выполнению лабораторной работы по дисциплине...
Методические указания к лабораторной работе 8 моделирование...
Методические указания к лабораторной работе №43 по физике для студентов всех специальностей...



Загрузка...
скачать


Министерство образования Российской Федерации

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









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

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

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

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

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

Код

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

Код

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

230200

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

62

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

230201

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

65

Инженер









 

УДК 774:002:006.354


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


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


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


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


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


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


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

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



© Содержание, оформление: Александров О.Е., 2010

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

Содержание


Содержание 3

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

Введение 4

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

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

Заключение 17

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



^

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


0111b

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

0ABCh

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

111.

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

N1..N2

  • диапазон целых чисел от N1 до N2;

[X1..X2)

  • интервал чисел от X1 до X2, X1 принадлежит интервалу, X2 – не принадлежит;

Введение


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

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

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

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

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

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


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

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

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

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

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


Таблица 17.1.

Номер

программы


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


Принятая

очередность


подготовка

выполнение

а


20


25


3


b


10


8


8


с


14


11


6


d


12


10


7


е


12


15


1


f


18


12


5


g


25


20


4


h


15


20


2



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




Рис. 17.1.

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

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

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

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

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


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

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



Рис. 17.2.

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

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

Таблица 17.2.

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

Номера

итераций

вычисления




1






















b

2



















d




3
















c







4

(e)










f










5

e










(f)










6




h



















7







a

(g)













8







(a)

g














^ Пример. Если из таблицы 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.

Номер

программы


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


подготовка

выполнение

а


15


25


b


10


12


с


12


11


d


8


10


е


9


15


f


15


12


g


18


20


h


12


16



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

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



Рис. 17.3.



Рис. 17.4.



Рис. 17.5.

Таблица 17.4.

Номер

программы


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


подготовка

выполнение

а


20


25


b


15


12


с


20


11


d


12


10


е


13


15


f


18


12


g


22


20


h


15


26



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

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


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



Рис. 17.6.

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

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



Рис. 17.7.

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

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

p1, p2, ..., pi, ..., pn,

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

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



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



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



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



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

Х1 + Х2 = Х1+ max(A1 + A2  B1  X1;0) =

= max(A1 + A2 – B1;X1) =

= max(A1 + A2 – B1;A1)= 

Аналогично,




и



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



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



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

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



откуда



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

(S1) = (p1, p2, p3, ..., pk-1, pk, pk+1, pk+2, …, pn)

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

(S2) = (p1, p2, p3, ..., pk-1, pk+1, pk, pk+2, …, pn).

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

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



если



  1. Если же



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

(1)

Но



и



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



и



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

— min (Ak+1; Bk) < — min (Ak; Bk+1)

или иначе

min (Ak; Bk+1) < min (Ak+1; Bk). (2)

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

min (Ak; Bk+1) < min (Ak+1; Bk).

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

(S′) = (..., pk, pl, ...),

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

min (Ak; Bl) ≤ min (Al; Bk); (3)

последнее выполняется, если Ak не превосходит Bl, Al, Bk, что можно также записать в виде

min (Ak; Bk) ≤ min (Al; Bl).

Следовательно, если в таблице времен можно найти время, не превосходящее всех прочих Al или Bl, то искомый порядок должен будет начинаться с pk, если время Ak, будучи по-прежнему наименьшим, равно некоторым другим Al или Bl, искомый порядок можно будет начинать также с pk.

Соотношение (3) выполняется еще в том случае, когда Bl не превосходит Ak, Al, Bk, что можно также записать в виде

min (Al; Bl) ≤ min (Ak; Bk).

Следовательно, если в таблице времен можно отыскать время Bl, не превосходящее всех прочих Ak или Bk, то искомый порядок должен завершаться элементом pl; если время Bl, будучи по-прежнему наименьшим, равно некоторым другим Ak или Bk, искомый порядок можно с таким же правом завершать элементом pl.

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

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

min Ai ≥ max Bi или min Ci ≥ max Bi.

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

Ai + Bi и Bi + Ci.



Рис. 17.8.

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

Ai , Bi , Ci;

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





Расточка

(Ai)

Фрезеровка

(Bi)

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

(Ci)

p1

p2

p3

p4

p5

7

11

8

7

6

6

5

3

5

3

4

12

7

8

3







Ai + Bi

Bi + Ci

p1

p2

p3

p4

p5

13

16

11

12

9

10

17

10

13

6




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

S = (p4, p2, p3, p1, p5)

или

S = (p4, p2, p1, p3, p5).
^

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

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


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

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

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

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

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

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

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

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

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


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

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

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

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

Вариант 2*


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

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

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

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


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

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

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

  2. введение;

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

  4. заключение;

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

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

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

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

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

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

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

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


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

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

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

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

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

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

Заключение


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

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

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

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

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

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

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


1 Популярный мюзик-холл на Елисейских полях в Париже. — Прим. ред.

2 Видимо, он решал ее перебором вариантов. Прим. ред.

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

  1. 1Кофман А., Фор Р. Займемся исследованием операций. М.: Мир, 1966. 278 с.

2. СТП УГТУ УПИ 1-96. Общие требования и правила оформления дипломных и курсовых проектов (работ). 1996. 34 с. Группа Т51.






Скачать 206,27 Kb.
оставить комментарий
Дата02.10.2011
Размер206,27 Kb.
ТипМетодические указания, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх