Алгоритм Джонсона решение задачи о двух станках

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

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

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

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

i	ai	bi

Построим диаграмму Ганта обработки деталей в начальный момент времени (рис. 6.2).

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

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

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

i	ai	bi	i¢
2

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

i	ai	bi	i¢
1
2
4

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

i	ai	bi	i¢
1
2
3
4
5

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

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

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

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

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

или .

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

или .

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

i	ai	bi	ci

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

i	ai	bi	ci	ai+ bi	bi+ ci

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

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

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

вариант	Требование время
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB
	tA
	tB

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