Cтраница 4
Ер, получим расписание обслуживания требований, допустимое относительно заданных сроков. Полученное расписание содержит не более п ( р - 1) ( М - 1) р прерываний. Действительно, при построении расписания для каждого интервала Eh получаем не более М-1 прерываний, а в результате стыковки полученных расписаний добавляется не более n ( p - i) прерываний. [46]
Пусть непосредственное порождение йв с помощью экспертизы Э10 невозможно, но известен регулярный способ ( модель) порождения любой альтернативы из QB. Например, пусть заданы правила построения возможных расписаний авиарейсов; в то же время число всех вариантов расписаний настолько велико, что их совместный анализ эксперту провести не удается. Параметры модели заранее не известны, но могут быть найдены экспертами. [47]
В последней модели мы рассмотрим задачу при наличии более одной машины. Сами машины не обязательно являются одинаковыми. Мы положим значения стоимостей равными единице и покажем, как эту задачу построения расписания свести к транспортной задаче. [48]
В задаче построения расписания минимальной длины на известной вычислительной системе для заданного комплекса информационно и логически связанных задач уже можно рассматривать и статические, и динамические планы решения задач. Задачи планирования и назначения связаны между собой, и часто их разделение носит вынужденный характер либо объясняется принципами построения расписания. Это разделение может иметь место при составлении динамических списочных расписаний, в то время как при построении оптимальных статических расписаний решения этих задач взаимозависимы. [49]
Материал данной книги изложен в терминах расписаний для однопроцессорных и многопроцессорных вычислительных систем. Для расписаний использованы, в основном, детерминированные математические модели ( с заранее известными параметрами), в которых предусмотрены наборы как взаимосвязанных, так и независимых заданий или работ и соответствующие совокупности ресурсов для их исполнения. Эти модели, несмотря на их простоту, настолько содержательны, что охватывают очень широкий круг практически важных задач упорядочения, выходящих за рамки начальных формулировок. Результаты решений даны в виде эффективных оптимальных алгоритмов, эвристических алгоритмов с оценкой их эффективности и соответствующими границами, а также эффективных алгоритмов перебора и приближенных алгоритмов для построения разнообразных расписаний. Специфические вопросы применения ЭВМ не рассматриваются. [50]
Одной из наиболее простых в смысле постановки и наиболее трудных в отношении получения решения в общем виде задач упорядочения является задача Джонсона. Время выполнения работы i на машине / обозначим через t j ( il n; j т), предполагая его заранее известным. Порядок выполнения операций, составляющих работу, может быть как одним и тем же, так и различным для разных работ. Задача построения расписания состоит в указании порядка, в котором должны выполняться работы, чтобы суммарное время простоя всех машин было минимальным. [51]
Система операций описывается следующим образом. UN операций, которые необходимо выполнить. На множестве операций определяется отношение - предшествования, представляемое, например, в виде ориентированного бесконтурного графа ( С /, Е) с множеством U вершин, соответствующих операциям, и множеством Е С U x U дуг. Необходимо заметить, что транзитивная редукция не является столь уж безобидной процедурой. При построении расписаний используются различные графовые модели параллельных программ: с информационными, логическими либо информационно-логическими связями, а также графы, вершины, которых представляют операции и обработки, и обмена данными. В моделях с логическими связями ( по управлению) в силу их природы имеет место априорное упорядочение операций. Информационные связи ( по данным) позволяют выявить скрытый параллелизм программы. [52]
На вход обслуживающей системы S, содержащей М приборов, поступает множество N i. N поступает в момент времени d Q, длительность его обслуживания прибором I равна t / ti, задается в желательный срок завершения обслуживания. Обычно предполагается, что каждый прибор одновременно обслуживает но более одного требования и каждое требование одновременно обслуживается не более чем одним прибором. Прерывания в обслуживании требований в одних постановках могут допускаться, в других - запрещаться. Цель состоит в построении расписания ( календарного плана) обслуживания требований приборами, при к-ром суммарный ( или максимальный) штраф за обслуживание минимален. В общем случае для каждого требования задается определенный порядок прохождения приборов ( техноло-гич. Если технология, маршруты одинаковы для всех требований, то S - система поточного типа. [53]