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

, опубликовавшего алгоритм в 1977 году.

Алгоритм

См. также

Напишите отзыв о статье "Алгоритм Джонсона"

Ссылки

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. - 2-е изд. - М .: Издательский дом «Вильямс» , 2007. - С. 726. - ISBN 5-8459-0857-4 .
• Томас Х. Кормен и др. Алгоритмы: построение и анализ. - 1-е изд. - М .: МЦНМО , 2004. - С. 523. - ISBN 5-900916-37-5 .

Алгоритмы поиска на графах Неинформированные методы Информированные методы Кратчайшие пути Минимальное остовное дерево Другое

Отрывок, характеризующий Алгоритм Джонсона

– Нет, я, кажется, домой поеду…
– Как домой, да вы вечер у нас хотели… И то редко стали бывать. А эта моя… – сказал добродушно граф, указывая на Наташу, – только при вас и весела…
– Да, я забыл… Мне непременно надо домой… Дела… – поспешно сказал Пьер.
– Ну так до свидания, – сказал граф, совсем уходя из комнаты.
– Отчего вы уезжаете? Отчего вы расстроены? Отчего?.. – спросила Пьера Наташа, вызывающе глядя ему в глаза.
«Оттого, что я тебя люблю! – хотел он сказать, но он не сказал этого, до слез покраснел и опустил глаза.
– Оттого, что мне лучше реже бывать у вас… Оттого… нет, просто у меня дела.
– Отчего? нет, скажите, – решительно начала было Наташа и вдруг замолчала. Они оба испуганно и смущенно смотрели друг на друга. Он попытался усмехнуться, но не мог: улыбка его выразила страдание, и он молча поцеловал ее руку и вышел.
Пьер решил сам с собою не бывать больше у Ростовых.

Петя, после полученного им решительного отказа, ушел в свою комнату и там, запершись от всех, горько плакал. Все сделали, как будто ничего не заметили, когда он к чаю пришел молчаливый и мрачный, с заплаканными глазами.
На другой день приехал государь. Несколько человек дворовых Ростовых отпросились пойти поглядеть царя. В это утро Петя долго одевался, причесывался и устроивал воротнички так, как у больших. Он хмурился перед зеркалом, делал жесты, пожимал плечами и, наконец, никому не сказавши, надел фуражку и вышел из дома с заднего крыльца, стараясь не быть замеченным. Петя решился идти прямо к тому месту, где был государь, и прямо объяснить какому нибудь камергеру (Пете казалось, что государя всегда окружают камергеры), что он, граф Ростов, несмотря на свою молодость, желает служить отечеству, что молодость не может быть препятствием для преданности и что он готов… Петя, в то время как он собирался, приготовил много прекрасных слов, которые он скажет камергеру.
Петя рассчитывал на успех своего представления государю именно потому, что он ребенок (Петя думал даже, как все удивятся его молодости), а вместе с тем в устройстве своих воротничков, в прическе и в степенной медлительной походке он хотел представить из себя старого человека. Но чем дальше он шел, чем больше он развлекался все прибывающим и прибывающим у Кремля народом, тем больше он забывал соблюдение степенности и медлительности, свойственных взрослым людям. Подходя к Кремлю, он уже стал заботиться о том, чтобы его не затолкали, и решительно, с угрожающим видом выставил по бокам локти. Но в Троицких воротах, несмотря на всю его решительность, люди, которые, вероятно, не знали, с какой патриотической целью он шел в Кремль, так прижали его к стене, что он должен был покориться и остановиться, пока в ворота с гудящим под сводами звуком проезжали экипажи. Около Пети стояла баба с лакеем, два купца и отставной солдат. Постояв несколько времени в воротах, Петя, не дождавшись того, чтобы все экипажи проехали, прежде других хотел тронуться дальше и начал решительно работать локтями; но баба, стоявшая против него, на которую он первую направил свои локти, сердито крикнула на него:
– Что, барчук, толкаешься, видишь – все стоят. Что ж лезть то!
– Так и все полезут, – сказал лакей и, тоже начав работать локтями, затискал Петю в вонючий угол ворот.
Петя отер руками пот, покрывавший его лицо, и поправил размочившиеся от пота воротнички, которые он так хорошо, как у больших, устроил дома.
Петя чувствовал, что он имеет непрезентабельный вид, и боялся, что ежели таким он представится камергерам, то его не допустят до государя. Но оправиться и перейти в другое место не было никакой возможности от тесноты. Один из проезжавших генералов был знакомый Ростовых. Петя хотел просить его помощи, но счел, что это было бы противно мужеству. Когда все экипажи проехали, толпа хлынула и вынесла и Петю на площадь, которая была вся занята народом. Не только по площади, но на откосах, на крышах, везде был народ. Только что Петя очутился на площади, он явственно услыхал наполнявшие весь Кремль звуки колоколов и радостного народного говора.
Одно время на площади было просторнее, но вдруг все головы открылись, все бросилось еще куда то вперед. Петю сдавили так, что он не мог дышать, и все закричало: «Ура! урра! ура!Петя поднимался на цыпочки, толкался, щипался, но ничего не мог видеть, кроме народа вокруг себя.
На всех лицах было одно общее выражение умиления и восторга. Одна купчиха, стоявшая подле Пети, рыдала, и слезы текли у нее из глаз.
– Отец, ангел, батюшка! – приговаривала она, отирая пальцем слезы.

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий случай задачи выбора последовательности обработки деталей на двух станках, если детали должны пройти обработку на одном станке, а затем на втором и на станке не может обрабатываться больше одной детали, рассмотрел в 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. Это и является новым решением. При решении конкретных задач для трех и более станков рекомендуется проанализировать результаты, полученные по каждому из этих правил, и в качестве окончательного варианта выбрать ту последовательность, которая обеспечивает минимум суммарного времени обработки.

«Эталонной» задачей теории расписаний является проблема составления расписания работы технологической линии, известная в литературе под названием задачи Джонсона, по имени С.М.Джонсона, получившего основные аналитические результаты для простейших ситуаций (вариантов) – частных постановок этой задачи .

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

8.1.1 Постановка детерминированной задачи упорядочения,

построение и исследование математической модели

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

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

Традиционная постановка задачи Джонсона состоит в следующем: требуется выбрать порядок обработки деталей (изделий), сформировать (составить) расписание работы технологической линии, обеспечивающее минимальное суммарное время выполнения всего задания, а именно за минимальное время осуществить обработку группы из т деталей, каждая из которых должна последовательно пройти обработку на каждом из п станков, образующих технологическую линию. Предполагается заданным t ij - время обработки i -ой детали (i = 1,…, m ) на j -ом станке (j =1,…,n ).

Основными ограничениями задачи являются:

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

2) каждая деталь обрабатывается в строго определенном технологическом порядке;

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

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

Рассматриваемая задача – одна из типичных задач оперативно-календарного планирования для машиностроительных предприятий мелкосерийного и единичного производства.

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

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

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

Так, если предположить, что в задаче поиска оптимальной очередности, в случае всего 10 деталей затрачивается всего лишь одна минута, на построение каждого варианта расписания и вычисление соответствующего ему значения функции-критерия (критерия оптимальности). Тогда нетрудно подсчитать, что при использовании метода полного перебора (число вариантов равно 10!, то есть 3 628 800 вариантов) и даже при двадцатичетырехчасовом рабочем дне эту задачу пришлось бы решать... почти семь лет. В случае же 20 деталей (число вариантов равно 20!, то есть 2,433*1018 вариантов) даже с помощью современных, быстродействующих компьютеров такая задача методом полного перебора решалась бы более 77 тысяч лет!

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

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

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

С.Джонсоном (S.Joynson) данная задача была решена для двух и трех станков (операций) и произвольного числа деталей, обрабатываемых строго последовательно на этих станках (то есть каждая деталь сначала проходит обработку на первом станке, затем на втором и на третьем). Уже в случае трех станков решение получается сложным, а распространение этого метода (алгоритма Джонсона) на случай четырех и более станков невозможно.

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

Оставив пока в стороне вопрос об общих приемах сокращения объема перебора вариантов порядка (очередности) запуска, рассмотрим частный вариант постановки задачи Джонсона, когда число станковn =2. В этом частном случае удается установить простые приемы нахождения порядка запуска деталей, обеспечивающего наименьшую продолжительность выполнения задания (наименьшую длительность расписания), то есть минимальное суммарное время обработки группы из m деталей (m =6), каждая из которых должна последовательно пройти обработку на каждом из двух станков (сначала на первом, а затем на втором станках), образующих технологическую линию. Время обработки i -ой детали (i =1,…,m ) на j -ом станке (j =1,2) t ij предполагается заданным, и, как правило, для
. В таблице 8.1 представлены исходные данные рассматриваемого примера.

Таблица 8.1 - Исходные данные для задачи Джонсона и ее решение

детали, i	Время обработки i -ой детали на j -ом станке,(мин.)		очереди, k

Изобразим графически процесс обработки деталей на двух станках для следующей произвольно выбранной очередности запуска деталей в обработку: А→Б→В→Г→Д→Е (рисунок 8.1) (нумерация деталей и последовательность их обработки совпадают).

Рисунок 8.1 – График процесса обработки группы деталей на двух станках

На рисунке 8.1
- суммарное время обработки группы изт деталей (т =6), то есть длительность совокупного производственного цикла – время, которое пройдет от момента начала обработки первой детали (i =А) на первом станке (j =1) до момента окончания обработки последней детали (i =Е) на втором станке (j =2) рассчитывается по формуле (8.1.1) и в рассматриваемом примере равно 41 мин.

где - время обработкиi -ой детали на втором станке,i = 1,…, m ;

- суммарное время обработки всех деталей на втором станке;

- суммарное время простоя второго станка (оборудования на второй операции);

- время простоя второго станка между окончанием выполнения работы по обработке (i -1)-ой детали на этом станке и началом обработкиi -ой детали на том же самом станке (для детали первой очереди запуска
);

- время обработки деталиk k = 1,…, m ;

- время обработки деталиk -ой очереди запуска на втором станке,k = 1,…, m -1;

Критерием оптимальности в данной постановке задачи и соответственно в экономико-математической модели является минимизация длительности совокупного производственного цикла

Так как суммарное время обработки всех деталей на втором станке, то есть сумма известна и в формуле (8.1.2) для любой очередности запуска деталей является константой, то для того, чтобы обеспечить наименьшее значение длительности совокупного производственного цикла необходимо минимизировать суммарное время простоя оборудования на второй операции (время простоя второго станка):

В нашем примере время простоя второго станка:

Если для решения рассматриваемой задачи использовать метод полного перебора, то при наличии m деталей и двух станков и при условии, что все детали обрабатываются сначала на первом, а затем на втором станке в одинаковом порядке на каждом из них, как было показано выше, существуетm ! возможных вариантов (последовательностей), то есть для нашего примера имеется 6!=720 вариантов.

Известен весьма простой алгоритм для нахождения оптимальной последовательности (порядка) обработки т деталей на двух станках – алгоритм Джонсона.

Указанный алгоритм включает следующие основные шаги:

1) выбирается деталь с наименьшей продолжительностью обработки на одном из станков; в нашем примере на первой итерации это деталь Б ;

2) выбранная деталь помещается в начало очереди, если наименьшая продолжительность обработки соответствует первому станку, или в конец очереди, если – второму станку; в нашем примере деталь Б помещается в конец очереди (k =6);

3) строка(и) таблицы 8.1, соответствующая(ие) выбранной(ым) детали(ям) исключается(ются) из дальнейшего рассмотрения (вычеркивается(ются));

4) выбирается деталь среди оставшихся со следующей наименьшей продолжительностью обработки на одном из станков; в нашем примере на второй итерации это деталь В , на третьей итерации это детальЕ , на четвертой итерации это деталиА иГ , на последней итерации это детальД ;

5) выбранная деталь помещается ближе к началу или к концу очереди по указанному в шаге 2 правилу; в нашем примере на второй итерации деталь В помещается ближе к концу очереди (k =5), перед детальюБ , на третьей итерации детальЕ помещается в начало очереди (k =1), на четвертой итерации детальА k =4), а детальГ помещается в начало очереди (k =2), на последней итерации детальД помещается ближе к концу очереди (k =3);

6) если определена очередность запуска для всех деталей, то решение получено, иначе переходим к шагу 3.

В итоге реализации данного алгоритма можно получить оптимальное расписание работы двух станков (рисунок 8.2). В нашем примере (см. таблицу 8.1) найдена оптимальная очередность запуска деталей в обработку - Е→Г→Д→А→В→Б . В последней графе таблицы 8.1 показан номер очереди запуска (k ) соответствующей детали в обработку на каждом станке технологической линии.

№ операции

Рисунок 8.2 – График оптимального расписания работы двух станков

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

(8.1.5)

Затем рассчитывается длительность совокупного производственного цикла по следующей формуле:

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

Методические указания к лабораторной работе алгоритм Джонсона по курсу «ТЕОРИЯ информационны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. Рандомизированные алгоритмы