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

Назначение сервиса . С помощью онлайн калькулятора можно решить задачу Джонсона для частного варианта ее постановки, когда число станков n=2 . При этом рассчитывается длительность совокупного производственного цикла для найденной оптимальной очередности запуска деталей в обработку. Результаты вычислений оформляются в отчете формата Word (Пример оформления).

ИНСТРУКЦИЯ . Для решения задачи необходимо задать количество деталей (строк).

Количество строк

Вставьте данные из Excel (A - первый столбец,B - второй столбец), нажмите Далее.

Правило Джонсона

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

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

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

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

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

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

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

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

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

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

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

Cтраница 2

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

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

Значительно позднее Кори и Опползер сообщили о других примерах использования метода Джонсона. Они показали, что бутилиден - и этилидендифенилсульфураны реагируют с различными карбонильными соединениями, образуя при этом соответствующие эпоксиды с хорошим выходом / Эти авторы сообщили об отсутствии стереоселективности рассматриваемой реакции, в то время как Джонсон и Граби отмечали стереоселективное образование гронс-эпоксидов.  

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

При больших объемах информации (N 50 и m / N 0 2) и сгруппированных данных применяют метод Джонсона.  

Используя экспериментальные данные по теплоемкости 2-метилбутана и 2-метилпентана, опубликованные в справочной литературе, рассчитана молярная теплоемкость гомологов 2-диметилалканов по предложенной нами формуле и методом Джонсона и Хуанга.  

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

Кеталь удаляет воду, используя ее на расщепление до спирта и ацетона. Однако, согласно некоторым данным , ни метод Джонсона и др. с использованием НС1 вместо НВг, ни последняя методика не годятся для получения н-амиловых эфиров.  

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

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

Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время A i и B i обработки i -й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через X i - время простоя в ожидании i -й детали, то:
A 1
X 1 + X 2 = max(A 1 + A 2 - B 1 , A 1)
X 1 + X 2 + X 3 = max(A 1 + A 2 +A 3 - B 1 - B 2 , A 1 + A 2 - B 1 , A 1)
∑X i = max(∑A i - ∑B i)
Если обозначить через F(t, A k , B k /k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, A k , B k /k = 1..N) = min(A i + F(B i + max(t-A i ,0),A k ,B k =1..N,k≠i))
Если после i -й детали при оптимальном порядке обрабатывается j -я, то:
F(t, A k , B k /k=1..N) = A i + A j + F(t ij , A k , B k /k=1..N; k≠i,j)
где
t ij = B i + max = B i + B j - A i - A j + max
Если max(A i + A j - B i ,A i) < max(A j + A i - B j , A j), то сначала разумнее обрабатывать j -ю деталь.
Можно показать, что указанное условие необходимости перестановки эквивалентно условию:
min(A j , B i) < min(A i , B j)
Соответственно ищем среди всех значений A i и B i наименьшее. Если найденное значение совпадает с некоторым A i , то i -ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi , то последней. Эту процедуру повторяем для всех остальных деталей.

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

Шаг № 2.
Минимальное из значений равно 3 и соответствует B 2: 2-ая деталь обрабатывается последней.

Шаг № 4.
Минимальное из значений равно 5 и соответствует B 4: 4-ая деталь обрабатывается последней.

Шаг № 6.
Минимальное из значений равно 7 и соответствует B 6: 6-ая деталь обрабатывается последней.

В итоге упорядоченная информация принимает вид:

Время простоя второй машины при первичном порядке равно:
max(2 , 2 + 8 - 3 , 2 + 8 + 4 - 3 - 3 , 2 + 8 + 4 + 9 - 3 - 3 - 6 , 2 + 8 + 4 + 9 + 6 - 3 - 3 - 6 - 5 , 2 + 8 + 4 + 9 + 6 + 9 - 3 - 3 - 6 - 5 - 8) = max(2, 7, 8, 11, 12, 13) = 13
Время простоя при оптимальной перестановке равно:
max(2 , 2 + 4 - 3 , 2 + 4 + 6 - 3 - 6 , 2 + 4 + 6 + 9 - 3 - 6 - 8 , 2 + 4 + 6 + 9 + 9 - 3 - 6 - 8 - 7 , 2 + 4 + 6 + 9 + 9 + 8 - 3 - 6 - 8 - 7 - 5) = max(2, 3, 3, 4, 6, 9) = 9

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

Шаг № 2.
Минимальное из значений равно 3 и соответствует B 1: 1-ая деталь обрабатывается последней.

Шаг № 4.
Минимальное из значений равно 4 и соответствует B 6: 6-ая деталь обрабатывается последней.

Доверенности