УДК 519.8
ОБОБЩЕНИЕ МЕТОДА ДЖОНСОНА ДЛЯ ЗАДАЧИ О К СТАНКАХ И. Г. Яр-Мухамедов
Кыргызско-Российский Славянский университет
Почти полвека прошло с тех пор, как С. М. Джонсон предложил и обосновал свой метод решения задачи о двух станках. Многие предпринимали попытки найти универсальный метод для решения задачи о К станках, но приемлемых и теоретически обоснованных результатов пока нет. В данной работе рассматриваются возможные подходы к решению этой задачи и в частности, путь, основанный на обобщении алгоритма Джонсона для двух станков.
Содержание задачи о двух станках следующее. Имеется некоторое количество деталей и два станка. Каждая из деталей должна обрабатываться сначала на первом станке, а затем на втором. Времена обработки деталей на каждом из станков заданы. Требуется определить такую последовательность запуска деталей на обработку, чтобы суммарное время обработки всех деталей было минимальным.
При К станках резко соответственно возрастает количество данных и очень резко возрастает возможное количество вариантов запуска деталей в обработку. Алгоритм Джонсона, по крайней мере непосредственно, не может быть применен.
Аналитический подход к решению задачи мы рассматривать не будем, так как за более, чем полувековой период попыток, никому не удалось найти общее аналитическое решение.
Один из подходов может быть основан на построении некоторой упорядочивающей функции f(X) – где X – вектор времен обработки некоторой детали, а f() – функция, задающая ранг или относительную позицию соответствующей детали в очереди. Для этого необходимо сформировать представительную или, лучше, полную задачу, и применить к ней нейросетевые, генетические или иные численные методы, чтобы оценить структуру и параметры функции f().
Второй подход может быть основан на системных представлениях. Его можно назвать декомпозиционным. Исходная сложная задача разбивается на совокупность простых подзадач таким образом, чтобы их решения можно было синтезировать в решение исходной сложной задачи. При этом предполагается, что простые задачи мы уже умеем решать. Сложность метода состоит в выборе метода декомпозиции, который удовлетворял бы упомянутому требованию.
Попробуем применит второй подход к решению задачи о К станках. Для этого рассмотрим свойства метода, предложенного Джонсоном. Алгоритм решения задачи о двух станках [1, 6] предельно прост и включает в свой состав следующие пункты.
1. Запишем данные о временах обработки каждой из деталей в таблицу. В боковинке – номер детали, в столбце А – времена обработки на первом станке, В – на втором.
2. Найдем в таблице деталь с минимальным временем обработки на каком-либо из станков.
3. Если это время соответствует первой машине, переместим строку данных в начало таблицы.
4. Если это время соответствует второй машине, переместим строку в конец таблицы.
5. Исключаем перемещенную строку из дальнейшего рассмотрения.
6. Повторяем шаги для уменьшенного количества станков до тех пор, пока оба конца рассматриваемой части таблицы не сомкнутся где-то в середине.
7. В случае нескольких одинаковых значений времен обработки, для простоты будем брать станок с меньшим номером, а в случае равенства времен обработки одной детали будем отдавать предпочтение времени обработки на первом станке.
Рассмотрим, какие принципы лежат или могли лежать в его основании.
1. До начала обработки перед первым станком есть очередь из n деталей (если через n обозначить общее количество деталей), а перед вторым станком очередь имеет нулевую длину. Отсюда следует, что порядок обработки для первого станка совершенно безразличен (время работы первого станка будет равно суммарным временам обработки всех деталей независимо от порядка). Для второго станка время работы тоже не зависит от порядка, но в общее время обработки всех деталей будет входить и время ожидания для второго станка, если очередь перед ним в какие-то периоды времени будет иметь нулевую длину.
2. Деталь с минимальным временем обработки на первом станке должна быть размещена на первом месте, чтобы минимизировать время ожидания второго станка. Со вторым – на втором и так далее. При этом в силу правил отбора обеспечивается образование и рост очереди перед вторым станком. Очередь гарантирует бесперебойность работы второго станка.
3. Деталь с минимальным временем обработки на втором станке размещается последней в очереди. Детали с малым временем обработки на втором станке вызывают истощение очереди или в последующем переводят второй станок в режим ожидания. Эта часть правил гарантирует минимизацию общего времени ожидания путем максимизации очереди перед вторым станком.
Применим эти же принципы к задаче о К станках. Очевидно, что и в этом случае времена обработки на первом станке никак не влияют на суммарный период обработки всех деталей. Перед первым станком очередь из n деталей. Если рассматривать пару из первого и второго станка, то, по-видимому, второй станок уже критичен к порядку обработки, так как лишь создание очереди перед ним позволит обеспечить непрерывность обработки.
Рассмотрим два последних станка. В этой паре последний станок (по крайней мере в общем случае, при прочих равных условиях и т. п.) более критичен к порядку обработки, чем предпоследний. Перед ним расположены n-1 станков, которые могут ухудшить значение общего критерия (суммарного времени обработки на всех станках), а перед предпоследним цепочка станков на единицу меньше, чем перед последним.
Таким образом, степень критичности возрастает от нуля для первого станка до некоторого максимального значения для К-того. Исходя из этого предположения мы можем сформировать правило декомпозиции исходной задачи о К станках.
1. Выделим самый последний станок и занесем его данные в столбец B (см. алгоритм Джонсона). Времена обработки на К-1 станках для каждой из деталей ссуммируем, разделим на К-1 и поместим в столбец А. Полученная задача о двух станках может быть решена методом Джонсона.
2. Формируем подзадачи следующего уровня декомпозиции, если еще есть, что разделять. Для этого в таблице выделим фрагменты с равными временами обработки. Мы можем предполагать, что изменение порядка внутри этих фрагментов таблицы не ухудшит параметры обработки на последующих станках. Для каждой из подтаблиц применим первый пункт по формированию задачи Джонсона о двух станках.
Предложенный метод декомпозиции показывает неплохие результаты. Однако аналитическая проверка и доказательство его оптимальности (в духе С. Джонсона) не проводились. Численная проверка примеров также затруднена. В частности, при трех станках и трех уровнях трудоемкости обработки мы получаем в полном случае 3 в степени 3 деталей, что равно 27. Из этого количества деталей можно получить 27! перестановок (вариантов запуска деталей в обработку), что значительно превосходит возможности современных компьютеров. Считается что им по силам максимум 16! вариантов решений. Использование неполных примеров не позволяет достоверно доказать, но позволяет опровергнуть, если такой пример попадется, правильность метода.
В заключение следует еще раз отметить, что предложенный вариант метода декомпозиции применим только с случае «прочих равных условий». К сожалению, установленный объем статьи не позволяет изложить их суть и модификации метода при их нарушении.
Список литературы:
1. S. M. Johnson. Optimal two - and three-stage production schedules with setup times included. P-402. Santa Monica, California, the RAND Corporation, 1953. – P. 10.
Основные порталы (построено редакторами)