Календарное планирование работы полиграфического предприятия

В больших полиграфических предприятиях существует несколько линий брошюровки и выпуска книг. План выпуска книг на конкретный период (например, месяц) обычно задан. Задача состоит в том, чтобы определить, на какой линии и в какой последовательности должна изготавливаться та или иная книга [9].

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

Формально рассматриваемая задача может быть представлена как задача теории расписаний. Задачи календарного планирования имеют комбинаторный характер. Обычный подход к решению таких задач состоит в построении математической модели и в разработке для нее оптимизационных алгоритмов. Известно, что большинство задач календарного планирования являются NP-сложными [10]. Отметим, что ближе всего к рассматриваемой в данной работе задаче подходит модель системы независимых машин с общими ресурсами. В [11] показано, что уже при одном ресурсе и трех машинах составление кратчайшего расписания для такой системы является NP-сложной задачей. Это практически исключает надежду на то, что когда- нибудь удастся построить оптимальные алгоритмы для таких моделей. Кроме того, такой подход, как правило, не позволяет учесть особенности конкретного производства.

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

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

Для диспетчера были разработаны человекомашинные процедуры, помогающие ему с лучшим качеством решать задачи выбора [9]. Сложные задачи сравнения многокритериальных объектов были заменены совокупностью более простых задач сравнения объектов, различающихся оценками по двум критериям (см. лекцию 9).