Построение - расписание
Cтраница 2
В данном параграфе рассматривается задача построения расписания обслуживания частично упорядоченного множества требований, имеющих одинаковые длительности обслуживания, параллельными идентичными приборами, при котором не нарушаются директивные сроки. Предполагается, что граф редукции отношения строгого порядка является входящим деревом либо число приборов равно двум. [16]
Параметр Л о введен для параметризации модели построения расписания с целью недопустимости негативных решений. [17]
Как показывает следующая лемма, существует простой алгоритм построения расписания для нарастающего списка. [18]
Иными словами, если алгоритм не приводит к построению расписания s ( случай, когда на некоторой итерации для выбранного требования i выполняется ti 8L, L 1, М), то допустимого расписания не существует. [19]
Определим понятие подцикла, которое в дальнейшем понадобится для построения расписания. [20]
Доказательство достаточности (4.9) и (4.10) дает возможность использовать алгоритм построения расписания, если исходные данные совместны. Воспользовавшись приведенным алгоритмом, задачу построения расписания для простейшего случая задания условий легко решить. [21]
На шаге в ( 9 1, ГЫ) осуществляется построение расписания на интервале с номером в, и требования, назначенные на обслуживание в этом интервале, исключаются из множества N. [22]
Рассмотрим алгоритм расстановки меток, приведенный в § 2.3, который был использован для построения расписания при произвольном частичном упорядочении и двух процессорах. В нем метки расставлялись от уровня к уровню. Как следует из § 2.2, уровневая стратегия строит расписания для деревьев от уровня к уровню. [23]
Теорема 2.1. Пусть граф НЕТ-системы ( -, ) является деревом; тогда уровневая стратегия обеспечивает построение расписания минимальной длины без прерываний. [24]
Если известно значение L, то для построения оптимального расписания можно, очевидно, воспользоваться алгоритмами построения расписаний, допустимых как относительно - -, так и относительно директивных сроков, равных Д L ( см. пп. Каждый из этих алгоритмов обладает той характерной особенностью, что при любом б 5 0 и директивных сроках, равных Д L б, строится одно и то же расписание. Действительно, изменение каждого директивного срока на одну и ту же величину не приводит к изменению списков Я, а, следовательно, и соответствующих Я-распи-саний. [25]
Следует отметить, что алгоритмы реализаций данного пакета имеют тот же порядок сложности, что и алгоритм построения расписания. Отсюда следует, что при алгоритмизации моделей этого пакета объективно необходимо использование некоторого числа эвристических правил, которые в данной задаче применяются для расслоения ресурсных ограничений, связывающих размеры партий, выполняемых на одном ресурсе. Различные эвристические правила определяют различные модификации алгоритмов реализации. [26]
Поскольку для решения задачи о назначениях достаточно выполнить не более О ( ( п М) 3) операций и число решаемых в процессе построения расписания s задач не превышает г т - М п, то оптимальное расписание может быть построено за полиномиально ограниченное время. [27]
В этой книге предпринята попытка в сжатой и вместе с тем доступной для широкого круга читателей форме отразить современное состояние одного из разделов теории расписаний - построения расписаний для детерминированных обслуживающих систем с одним и несколькими параллельными приборами. Одностадийные системы являются не только наиболее изученными в настоящее время, но и позволяют без сколь-нибудь громоздких выкладок продемонстрировать характерные особенности подхода к изучению детерминированных обслуживающих систем и проследить основные направления современного развития теории расписаний. [28]
 |
Порядок назначения заявок на обслуживание. [29] |
Выбирая для каждого / подмножество новых заявок, назначаемых на обслуживание только на / - м интервале, получаем v элементарных систем обслуживания, для которых задача построения расписания сводится к только что рассмотренному случаю одинаковости моментов поступления и одинаковости предельных сроков. [30]
Страницы: 1 2 3 4