Задача - теория - расписание
Cтраница 4
Здесь мы не будем более подробно останавливаться на задаче теории расписаний, поскольку нашей непосредственной целью было лишь описание соответствующей дискретной модели. Разумеется, подобное сведение далеко не исчерпывает всех аспектов проблемы - прежде всего по той причине, что оно приводит к серьезным вычислительным трудностям. Поэтому большую роль в решении задач теории расписаний играют различного рода приближенные и эвристические методы. [46]
Рассматриваются вопросы, связанные с построением алгоритмов решения задач теории расписаний для обслуживающих систем с одним и несколькими параллельными приборами. Детально исследуются задачи с ограничениями предшествования в обслуживании требований. Значительное внимание уделяется вопросам сложности решения задач теории расписаний. [47]
Основные понятия и определения приводятся во введении к книге. Глава 1 носит вспомогательный характер и содержит некоторые необходимые в дальнейшем сведения из комбинаторного анализа, теории графов, теории сложности алгоритмов. В главе 2 рассматривается ряд типичных задач одностадийного обслуживания и описываются эффективные методы их решения. В главе 3 рассматривается класс задач теории расписаний, естественным образом формулируемых в терминах минимизации так называемых приоритето-порождающих функционалов. Глава 4 посвящена установлению ЛФ-трудности ряда задач построения оптимальных расписаний. [48]
 |
Оптимум дискретной функции. [49] |
Рассмотрим подробнее остальные четыре группы методов. Методы третьей группы относятся преимущественно к задачам линейного целочисленного программирования. В большинстве же задач проектирования оптимальных химико-технологических систем как целевая функция, так и функции-ограничения являются нелинейными. Но, как будет показано в дальнейшем, к задаче целочисленного линейного программирования сводятся многие задачи теории расписаний, необходимость решения которых возникает при автоматизированном управлении гибкими производственными системами. [50]
Пакет ДИСПРО [111], в отличие от упомянутых пакетов, предназначенных для решения различных задач ДП, реализует широкий набор современных точных и приближенных методов решения многих классов задач ДП. Пакет работает под управлением ОС ЕС ЭВМ. Он разрабатывается с учетом программной и информационной совместимости с ранее разработанными ПП, функционирующими под управлением ОС ЕС. Реализация такого подхода позволила разработку его МО вести очередями, в результате чего в конечном итоге будет разработано семейство пакетов, которое позволит решать различные задачи ДП, как в общих постановках, так и специального вида ( например, задачи теории расписаний, размещения, оптимального распределения ограниченных ресурсов и др.) - Для решения задач вида (9.2) - (9.5) в пакете ДИСПРО предусмотрена возможность использования нескольких методов, которые характеризуются различной эффективностью в зависимости от того, к задачам какой размерности они применяются. [51]
Страницы: 1 2 3 4