Cтраница 2
В первой модели рассматривается один процессор и система заданий, в которой с каждым заданием связано время обработки и стоимость его пребывания в системе. Мы представим эффективные алгоритмы определения оптимальных расписаний для частного случая, когда ограничения предшествования имеют вид леса. [16]
В силу симметрии нам нужно доказать только необходимость. Вначале заметим, что SK действительно расписание для ( / -, й), так как в нем соблюдаются ограничения предшествования и каждое задание выполняется в течение положенного времени. [17]
G - выходящее дерево, предложен У. Курису [322] предложил алгоритм ( с оценкой временной сложности O ( nlogn)) решения задачи 2 X п Беллмана - Джонсона при наличии ограничений предшествования, определяемых графом G, каждая компонента связности которого - цепь. Здесь ограничения предшествования ( отношение - -) имеют следующий смысл. [18]
G - выходящее дерево, предложен У. Курису [322] предложил алгоритм ( с оценкой временной сложности O ( nlogn)) решения задачи 2 X п Беллмана - Джонсона при наличии ограничений предшествования, определяемых графом G, каждая компонента связности которого - цепь. Здесь ограничения предшествования ( отношение - -) имеют следующий смысл. [19]
Граф, который возникает в таких задачах, трактуется следующим образом ( он называется графом работ или сетевым графиком): его дуги соответствуют выполняемым работам. На очередность выполнения этих работ ( множество которых N задано) наложены некоторые ограничения предшествования, - для каждой работы и указано множество работ Na, которые должны быть завершены до того, как начнется выполнение и. Указание множества предшествующих работ является заданием квазипорядка на множестве N. [20]
Отношение предшествования называется входящим лесом, если каждая вершина в графе предшествования имеет не более одного непосредственного преемника. Аналогично, является выходящим лесом, если каждая вершина в графе предшествования имеет не более одного непосредственного предшественника. В данном параграфе мы рассмотрим эффективные алгоритмы отыскания оптимальных расписаний для задач, в которых ограничения предшествования являются входящими либо выходящими лесами. Вначале рассматривается задача с входящим лесом, а затем для получения алгоритмов составления расписаний в случае выходящего леса используются соображения двойственности. Мы также представим алгоритм для случая, когда задача составления расписания может быть разделена на две или более независимых задачи. [21]
Данная ситуация, бесспорно, выявляет скрытый изъян теории ЛФ-полных задач. Способность различных аспектов задачи сделать эту задачу трудной не всегда пропорциональна длине записи, описывающей тот или иной аспект. В рассмотренном нами случае интуитивно чувствуется, что из-за своей длины числа, записанные в десятичном виде, создают гораздо большие трудности в проведении анализа, чем другие аспекты задачи упорядочения. Например, запись ограничений предшествования требует по крайней мере нескольких символов для каждого ограничения; таким образом, представление ограничений предшествования будет иметь относительно большую длину при меньшем вкладе в сложность задачи. [22]
Данная ситуация, бесспорно, выявляет скрытый изъян теории ЛФ-полных задач. Способность различных аспектов задачи сделать эту задачу трудной не всегда пропорциональна длине записи, описывающей тот или иной аспект. В рассмотренном нами случае интуитивно чувствуется, что из-за своей длины числа, записанные в десятичном виде, создают гораздо большие трудности в проведении анализа, чем другие аспекты задачи упорядочения. Например, запись ограничений предшествования требует по крайней мере нескольких символов для каждого ограничения; таким образом, представление ограничений предшествования будет иметь относительно большую длину при меньшем вкладе в сложность задачи. [23]
Книга представляет собой теоретическое исследование проблем упорядочения, возникающих при организации выполнения работ в вычислительных системах. При этом рассматриваемые модели являются простыми по структуре и содержательными по отношению к большому количеству прикладных проблем. Если говорить кратко, изучаемая общая модель предполагает наличие множества заданий или работ и множества ресурсов, которые используются при обслуживании заданий. Почти во всех случаях модели являются детерминированными в том смысле, что информация, описывающая задания, известна заранее. Эта информация включает времена выполнения заданий, ограничения предшествования при обслуживании заданий, стоимости пребывания в системе и требуемые ресурсы. Рассматриваются основные задачи упорядочения по критериям минимизации длины расписания и минимизации времени пребывания в системе ( взвешенного по стоимостям пребывания заданий в системе), а также упорядочения, связанного с выполнением директивных или крайних сроков. Рассматривается также ряд сопутствующих задач. Представленные результаты включают эффективные оптимальные алгоритмы, эвристические алгоритмы и оценки их характеристик, эффективные перечислительные и приближенные методы, а также математическое обоснование оценок сложности широкого класса задач упорядочения. [24]