Cтраница 1
Задачи теории расписаний относятся к классу комбинаторных задач. Точное решение таких задач предполагает использование методов математического программирования - линейного, целочисленного и динамического. Трудоемкость этих методов ограничивает возможность HI применения для оперативного планирования работ, в связи с чем приходится использовать эвристические методы планирования. При этом область поиска наилучшего распределения или плана искусственно сужается до узкого класса решений, в пределах которого отыскивается неплохое распределение или план. Эвристический подход позволяет при умеренном объеме вычислений получать решения, которые, возможно, далеки от оптимальных, но значительно лучше произвольных. [1]
Специфика задач теории расписаний хорошо отражается моделями линейного или нелинейного математического программирования. [2]
В задачах теории расписаний х) осмотры представляются в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат. [3]
В задачах теории расписаний) осмотры представляются в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат. [4]
Дискретный характер задач теории расписаний накладывает заметный отпечаток на методологию их решения и определяет специфику используемого математического аппарата. [5]
Для многих задач теории расписания очень простые решающие правила могут быть получены непосредственно. Рассмотрим, например, так называемую задачу одного станка. [6]
При доказательстве W-трудности задач теории расписаний, рассматриваемых в этом параграфе, в качестве эталонной используется задача о разбиении. [7]
Для решения МР-трудных задач теории расписаний разработано много эвристических процедур и приближенных методов. [8]
Известно несколько формулировок задачи теории расписаний в виде целочисленных задач линейного программирования. [9]
Предлагаемая книга посвящена задачам теории расписаний - важной области прикладной математики, имеющей многочисленные и разнообразные применения. Она содержит достаточно полное и одновре - менно компактное изложение результатов решения основных задач, таких, как минимизация конечного и среднего времени завершения работ одним и несколькими исполнителями с учетом различных условий. [10]
С учетом некоторых характерных особенностей задачи теории расписаний могут быть условно разделены на три группы: задачи согласования ( задачи сетевого планирования и управления); задачи распределения ( задача балансирования сборочной линии, задача о назначениях и др.); задачи упорядочения. [11]
Многие задачи распределения ресурсов, включая задачи теории расписаний, могут быть сформулированы следующим образом. Имеется / производственно-технологических способов использования однородного ресурса в течение Т периодов времени. [12]
Наиболее распространены и разработаны среди З.у. задачи теории расписаний. К ним относятся также методы ситуационного управления и некоторые другие. [13]
Разновидность задач упорядочения и координации - задачи теории расписаний, представляющие совокупность моделей календарного планирования и разработанных для их решения методов дискретного программирования. [14]
В этом параграфе при доказательстве ЛФ-трудности задач теории расписаний в качестве эталонной используется задача о 3-разбиении, состоящая в следующем. [15]