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

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

Еще более перспективными оказались разработанные в самое последнее время общие схемы последовательного конструирования, анализа и отсеивания вариантов, берущие свое начало от вычислительных схем динамического программирования, но не требующие выполнения принципа оптимальности.

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

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

Методы моделирования

Моделирование является наиболее универсальным средством решения задач оптимизации.

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

Применение таких подходов к задачам календарного планирования приводит нас к возможности использования при построении графиков некоторых правил предпочтения.

В последние годы широкое распространение получили методы моделирования с использованием статистических испытаний—методов Монте-Карло. Применение методов Монте-Карло в задачах календарного планирования приводит к так называемым рандомизированным правилам предпочтения.

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

1.3. 5 Персональный компьютер и решение задач календарного планирования

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

Не следует вместе с тем думать, что реализация задач календарного планирования на ПК под силу только математикам. В настоящее время быстрыми темпами идет процесс все большего и большего приспособления ПК к потребителю, причем, ПК, предназначенные для решения планово-экономических задач, будут предъявлять к своим потребителям куда меньшие требования, чем сегодняшние ПК для научных расчетов.

Этот процесс во многом связан с разработкой специальных универсальных алгоритмических языков и средств автоматизации программирования. Как известно, программирование можно рассматривать как процесс записи алгоритма решения задачи в специальных символах, отражающих машинные операции, которые могут быть реализованы данной ПК. Стремление избавиться от необходимости ориентироваться при записи алгоритма на конкретную машину и привело к созданию некоторых специальных алгоритмических языков, весьма простых и удобных для практического использования и доступных для изучения. Умение программировать объективно перестает быть привилегией математика и постепенно входит в круг обязательных знаний каждого грамотного человека.