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