Cтраница 2
Формально рассматриваемая задача может быть представлена как задача теории расписаний. Задачи календарного планирования имеют комбинаторный характер. Обычный подход к решению таких задач состоит в построении математической модели и разработке для нее оптимизационных алгоритмов. Отметим, что ближе всего к рассматриваемой в данной работе задаче подходит модель системы независимых машин с общими ресурсами. В [10] показано, что уже при одном ресурсе и трех машинах составление кратчайшего расписания для такой системы является NP-трудной задачей. Это практически исключает надежду на то, что когда-нибудь удастся построить алгоритмы оптимизации для таких моделей. Кроме того, такой подход, как правило, не позволяет учесть особенности конкретного производства. [16]
В дальнейшем будут рассмотрены некоторые методы решения задач теории расписаний. [17]
В качестве метода решения этой задачи, являющейся задачей теории расписаний, применяют различные эвристические приемы. Суть их сводится к тому, что принимается какой-либо определенный порядок обслуживания требования из имеющихся, который позволяет сформировать расписание. [18]
В этой связи решение задачи синхронизации рассматривается как задача теории расписаний с учетом ограничений на выполнение отдельных операций, допускающих прерывания. [19]
Такое видоизменение задачи уже охватывает очень широкий класс задач теории расписаний с ограниченным ресурсом. [20]
Рассматриваются вопросы, связанные с построением алгоритмов решения задач теории расписаний для обслуживающих систем с одним и несколькими параллельными приборами. Детально исследуются задачи с ограничениями предшествования в обслуживании требований. Значительное внимание уделяется вопросам сложности решения задач теории расписаний. [21]
В четвертой главе устанавливается Л - трудность ряда задач теории расписаний. Для большинства рассматриваемых в этой главе задач доказывается, что они являются ЛФ-трудными в сильном смысле. [22]
Сформулированные здесь задачи оперативного планирования относятся к классу задач теории расписаний. В настоящее время не существует общих методов решения задач такого рода, и каждый конкретный случай требует специального рассмотрения. [23]
Здесь мы не будем более подробно останавливаться на задаче теории расписаний, поскольку нашей непосредственной целью было лишь описание соответствующей дискретной модели. Разумеется, подобное сведение далеко не исчерпывает всех аспектов проблемы - прежде всего по той причине, что оно приводит к серьезным вычислительным трудностям. Поэтому большую роль в решении задач теории расписаний играют различного рода приближенные и эвристические методы. [24]
В зависимости от характера потока заявок различается два вида задач теории расписаний: статические и динамические. [25]
В дапной главе устанавливается Л Р - трудность ряда задач теории расписаний. Доказательство того, что данная задача В является ЛФ-трудной, осуществляется по следующей схеме. [26]
Включает МО для сетевого анализа и МО для решения задач теории расписаний. [27]
В заключение отметим, что для - решения многих задач теории расписаний успешно применяются методы динамического программирования, изложенные в гл. [28]
В настоящее время предложено много разных подходов к приближенному решению задач теории расписаний. Важное место среди подобных методов играют различные способы агрегированного описания. [29]
Предварительно установим справедливость одного утверждения, используемого далее при доказательстве NP-трудности некоторых задач теории расписаний. [30]