Модели составления расписаний работы многопродуктовых периодических химических производств

Календарное планирование многопродуктовых периодических химических производств (МПХП) рассматривается с позиции теории расписаний, позволяющей не только формализовать многие практические задачи, но и разработать методы и алгоритмы для их решения.

Основные понятия теории расписаний

Теория расписаний (ТР) является одним из разделов исследования операций. Данное направление в науке берет свое начало к первым публикациям Генри Гантта 1903 г., предложившего то, что сегодня называют диаграммами Гантта, которые используются во многих работах по теории расписаний.

Другой показательный пример — изобретение конвейера Генри Фордом, который организовал поточное производство на своем автомобильном заводе по «конвейерному типу». Это способ организации производства каких-либо изделий, при котором:

  • — процесс производства разделяется на отдельные операции (стадии);
  • — одновременно в производстве находится несколько изделий, находящиеся на различных стадиях.

Операции при таком способе производства упорядочены, то есть существует очередность операций и нарушать ее нельзя. Еще одна важная особенность такого производства — выполнение независимых операций параллельно. Конвейерное производство позволило Форду в 1,5 раза сократить время выпуска автомобилей.

Термин «теория расписаний» предложил Р. Веллман в 1956 г. Термин возник на стыке других областей научного познания, фактически являясь одним их разделов исследования операций.

Исследование операций (ИО) — научный метод выработки количественно обоснованных рекомендаций по принятию решений. Важность количественного фактора в ИО и целенаправленность сформулированных рекомендаций позволяют определить ИО как теорию принятия оптимальных решений. ИО способствует превращению искусства принятия решений в математическую дисциплину. Термин «ИО» возник в результате буквального перевода выражения «operation research», введенного в конце 1930-х гг. в качестве условного наименования одного из подразделений британских ВВС, занимавшегося вопросами использования радиолокационных установок в общей системе обороны. Первоначально ИО было связано с решением задач военного содержания, но уже с конца 1940-х гг. оно используется для решения технических, технико-экономических задач, а также задач управления на различных уровнях.

Таким образом, можно дать следующее определение Теории Расписаний.

Теория расписаний — это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т. е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений.

К середине XX в. выделились еще две области знаний, некоторые задачи которых впоследствии стали частью ТР. Это сетевое планирование и теория массового обслуживания.

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

Сетевая модель может содержать некоторые другие характеристики (например, время, стоимость, ресурсы), относящиеся к отдельным работам или комплексу в целом.

В 1958-м г. по заказу Министерства Обороны США для проекта создания ракетной системы «Поларис» была разработана специальная техника анализа и оценки комплексов взаимосвязанных работ. Созданная техника получила название PERT (Project Evaluation and Review Technique — анализ критического пути). Двумя ее основными элементами было — наглядное представление комплекса работ на бумаге в виде так называемого сетевого графика и метод расчета критического пути по этому графику.

Можно привести следующую классификацию задач теории расписаний.

По типу искомого решения:

  • задачи упорядочивания. В этих задачах уже задано распределение работ по исполнителям, а также определены все параметры работ (продолжительность выполнения, время поступления и т. д.). Необходимо составить расписание выполнения работ каждым исполнителем;
  • задачи согласования. Основное внимание в этих задачах уделяется выбору продолжительности выполнения работ, времени поступления и другим параметрам;
  • задачи распределения подразумевают поиск оптимального распределения работ по исполнителям.

По типу целевой функции:

  • — задачи с суммарными критериями оптимизации;
  • — задачи с minmax (минимаксными) критериями оптимизации. Отличие этих задач от задач с суммарными критериями заключается в том, что нужно минимизировать не сумму некоторых значений, а лишь максимальное из них;
  • — многокритериальные задачи оптимизации.

По способу задания входной информации:

  • — детерминированные задачи (off-line). Для таких задач характерно, что все входные данные задачи точно известны, т. е. даны значения всех параметров до начала ее решения;
  • — динамические задачи (on-line). Для данных задач расписания строятся в режиме реального времени, т. е. перед началом решения задачи мы не знаем значения всех параметров. Расписание строится по частям по мере поступления новой информации. При этом в любой момент может быть понадобиться ответ о качестве построенного «частичного» расписания.

По разделу теории расписаний:

  • сетевое планирование, или построение расписания для проекта, Project scheduling (PS);
  • календарное планирование, или построение расписания для приборов, процессов и производств, Machine scheduling (MS).

Подавляющее большинство исследованных задач теории расписаний являются NP-трудными (NP — non-deterministic polynomial). Для их решения используются методы сокращенного перебора (в том числе метод ветвей и границ). Первым подходом является разработка полиномиальных эвристических алгоритмов. Для некоторых эвристических алгоритмов известны оценки погрешности получаемого решения. Такие алгоритмы называются приближенными.

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

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

Часто задачи теории расписаний могут быть сформулированы как задачи целочисленного линейного программирования.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >