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

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

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

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

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