Детерминированные задачи планирования для вычислительных систем реального времени с ограниченными ресурсами тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Овсянкин, Борис Петрович

• Овсянкин, Борис Петрович
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Овсянкин, Борис Петрович

ВВЕДЕНИЕ.

ГЛАВА I. МЕТОДЫ ПОСТРОЕНИЯ БАЗИСА ДОПУСТИМЫХ РАСПИСАНИЙ ДЛЯ ОДНОСТАДИЙНЫХ ДЕТЕРМИНИРОВАННЫХ СИСТЕМ

ОБСЛУЖИВАНИЯ.

§ I. Основные определения

§ 2. Полные системы обслуживания.

§ 3. Базис допустимых расписаний для системы обслуживания с одним прибором . 33

§ 4. Базис допустимых расписаний для системы обслуживания с несколькими параллельными приборами

ГЛАВА II. АЛГОРИТМЫ СОСТАВЛЕНИЯ РАСПИСАНИЙ НА ОСНОВЕ МЕТОДОВ ПОСТРОЕНИЯ БАЗИСА ДОПУСТИМЫХ РАСПИСАНИЙ

§ I. Активные расписания

§ 2. Верхняя оценка числа прерываний в оптимальном расписании.

§ 3. Оптимизация расписаний с директивными сроками

§ 4. Множество допустимых расписаний для системы обслуживания с несколькими параллельными приборами

ГЛАВА III. РАСЧЕТ ХАРАКТЕРИСТИК И ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

РЕАЛЬНОГО ВРЕМЕНИ.

§ I. Задачи расчёта характеристик и планирования вычислительного процесса при проектировании вычислительных систем реального времени

§ 2. Расчёт быстродействия процессора вычислительной системы реального времени

§ 3. Оценка количества ресурсов, необходимых для управления объектом в реальном времени

§ 4. Результаты вычислительного эксперимента

Введение диссертации (часть автореферата) на тему «Детерминированные задачи планирования для вычислительных систем реального времени с ограниченными ресурсами»

Потребности в высоком быстродействии и большом объёме памяти, предъявляемые к современным вычислительным системам (ВС), в настоящее время значительно опережают возможности вычислительной техники. В связи с этим задача разработки методов эффективного использования ресурсов ВС весьма актуальна.

Важное значение эта проблема имеет для ВС, применяемых для управления различными техническими объектами в реальном времени, поскольку к таким системам обычно предъявляются требования высокой надёжности при жёстких ограничениях на использование вычислительных ресурсов.

Поэтому при проектировании ВС реального времени возникает целый ряд задач, связанных с расчётом различных временных характеристик и характеристик основных ресурсов ВС, необходимых для управления объектом в реальном времени. Среди этих задач весьма важными являются расчёт необходимого быстродействия процессора, оценки потребностей в основных ресурсах ВС и построение расписаний выполнения комплекса программ, осуществляющих обработку информации и управление объектом в реальном времени.

В настоящей работе эти задачи рассматриваются главным образом для однопроцессорных ВС реального времени с учётом основных ресурсов ВС таких, как время центрального процессора (ЦП), основная память, вспомогательная память, периферийные устройства.

Вычислительные системы реального времени расчитаны на автоматический приём и обработку информации, поступающей в процессе управления различными техническими объектами, и выдачу управляющей информации непосредственно на исполнительные органы или человеку-оператору. В промышленности такие системы широко применяются с целью автоматизации процессов управления объектов с непрерывным и непрерывно-дискретным характером производства, в первую очередь, на химических, нефтеперерабатывающих, металлургических и бумагоделательных предприятиях. Весьма эффективно ВС реального времени используются для автоматизации различных энергетических объектов, автоматизации исследований, проводимых с помощью сложных экспериментальных установок, и для других целей [i].

Для ВС реального времени важнейшим параметром функционирования системы является время ответа. Как правило, все программы в таких системах должны быть обработаны с учётом временных ограничений на сроки их выполнения, зачастую довольно жёстких, чтобы обеспечить гарантированное время ответа системы. Прекращение измерения времени в этом случае эквивалентно полному отказу системы, т.к. теряется временная связь вычислительного процесса с состоянием источников внешней информации и потребителей вырабатываемых сигналов [2-4].

Используемые в ВС реального времени управляющие ЭВМ обычно являются наиболее специализированными, т.к. к ЭВМ этого класса предъявляются весьма жёсткие требования по габариту, весу, потребляемой мощности и использованию внешних ресурсов. Поэтому алгоритмы и программы для ЭВМ в ВС реального времени приходится разрабатывать при весьма жёстких требованиях к оптимальности использования ресурсов управляющей ЭВМ [2].

При распределении ресурсов операционной системой зачастую возникает ситуация, когда программы, готовые к решению, не могут быть полностью обеспечены необходимыми ресурсами. В таком случае операционная система реального времени (ОСРВ) должна принимать решения относительно порядка обработки очереди для обеспечения наиболее эффективного использования ресурсов ВС и гарантированного времени ответа.

Важным видом ресурсов ВС, подлежащим распределению операционной системой, является так называемый повторно используемый ресурс, или ресурс нескладируемого типа. Ресурс этого типа обладает следующими свойствами: число единиц ресурса постоянно; каждая единица ресурса или доступна или распределена только одному процессу (разделение отсутствует) ; процесс может освободить единицу ресурса (сделать её доступной), только если он ранее получил эту единицу. Примерами ресурсов такого типа являются компоненты аппаратуры, такие, как основная память, вспомогательная память, периферийные устройства и, возможно, процессоры, а также программное обеспечение, такое, как файлы данных и таблицы [б].

В настоящее время большинство вычислительных систем реального времени имеют ОСРВ, которые дают возможность работать в режиме мультипрограммирования, позволяющем обрабатывать несколько программ одновременно. Режим мультипрограммирования обеспечивает, в частности, высокую загруженность вычислительных ресурсов и улучшает пропускную способность системы [4,5].

Одной из важных задач, с которой приходится сталкиваться при проектировании ВС реального времени, является задача оптимальной организации вычислительного процесса. Критерий эффективности вычислительного процесса для ВС реального времени должен обеспечивать гарантированное время ответа при минимальных потребляемых ресурсах ВС.

Обычно анализ вычислительного процесса, определение его числовых характеристик и проверка различных принципов планирования вычислений проводятся на имитационной модели ВС. Определение правил поведения и параметров отдельных частей имитационной модели, выбор и обоснование принципов планирования основывается на исследовании математических моделей [2-4,6-8].

Реальную ВС или её части представляют в виде стохастической или детерминированной модели массового обслуживания. Далее исследуют эту модель, используя аппарат теории расписаний, теории очередей, комбинаторного анализа, математического программирования.

Важным классом моделей планирования вычислительного процесса для ВС реального времени являются детерминированные задачи теории расписаний [2,3,6-8].

Многие задачи теории расписаний, представляющие интерес с точки зрения практики, принадлежат классу f*f & -полных задач [10,11,27,31,35-37,61,64,67]. Широко распространена гипотеза, что для решения задач этого класса не существует алгоритмов полиномиальной временной сложности [29-31].

В работах ^12,41,45] предлагаются методы решения таких задач средствами математического программирования и на основе методов ветвей и границ.

В работах [16,19,47,48,69,70] исследуются частные случаи, когда М -полная задача разрешима за полиномиальное время.

В последнее время наряду с исследованием сложности детерминированных задач теории расписаний [30,31,67,71-73] большое внимание уделяется построению эффективных приближённых алгоритмов [зз], в которых за счёт снижения точности решения уменьшается трудоёмкость.

Среди детерминированных задач теории расписаний следует выделить класс задач, которые могут быть использованы при исследовании математических моделей ВС реального времени. Это прежде всего задачи построения расписаний, не нарушающих директивных сроков обслуживания требований, для одностадийных детерминированных систем обслуживания.

Существует большое число работ, посвящённых исследованию такого рода задач [9-27,40-54].

В системах этого типа множество требований S -{-f,JV J обслуживается М 4 параллельными приборами, которые обычно считаются идентичными [17,18,27,32,43,46,50-56], но могут быть и различными [16,49].

Требование ie S поступает в очередь на обслуживание в момент времени , и длительность его обслуживания равна ii . Обычно предполагается также заданным директивный срок J. обслуживания требования, т.е. момент времени, к которому обслуживание этого требования должно быть завершено.

На множестве требований может быть задано отношение частичного порядка, которое определяет возможную последовательность обслуживания требований. В самом общем случае последовательность обслуживания требований определяется направленным ациклическим графом [14,15,28,48,54,56], в других случаях эта последовательность задается параллельно-последовательной сетью, совокупностью деревьев или деревом [22,55,57, 58].

Обычно рассматривают две дисциплины обслуживания требований: обслуживание с прерываниями [13-18,20,21,23,24,26,32, 41-43,46,49,52,53] и без прерываний [12,14-16,19,22,27,28,

44,45,47-48,50,51,55-58]. При обслуживании требований с прерываниями обычно предполагается, что каждое требование одновременно может обслуживаться лишь одним прибором, причём на прерывания не расходуется дополнительное время.

В некоторых работах допускается возможность обслуживания требования одновременно несколькими приборами [16-18].

Качество расписания обычно оценивается значением некоторой функции, аргументами которой являются моменты завершения обслуживания требований. Значение функции в этом случае представляет собой штраф за обслуживание требований, а расписание, которому соответствует наименьшее значение функции, называется оптимальным.

Обычно рассматриваются критерии качества расписания, при которых минимизируются следующие величины [9-11,15,18,22, 24-27,40,46-48,50-51,55-58]:

- общее время обслуживания требований;

- сумма (или среднее значение) моментов окончания обслуживания требований;

- взвешенная сумма моментов окончания обслуживания требований;

- взвешенная сумма величин, экспоненциально зависящих от моментов окончания обслуживания требований;

- сумма запаздываний в обслуживании требований;

- взвешенная сумма запаздываний;

- число запаздывающих требований;

- взвешенное число запаздывающих требований.

Как отмечалось выше, при исследовании математических моделей ВС реального времени особый интерес представляет задача построения расписаний, не нарушающих директивных сроков.

Эта задача для системы обслуживания с одним прибором рассматривается в работах [9-16,20-22,24-27,40,41,44-48,51, 53,54].

При обслуживании требований с прерываниями известны различные необходимые и достаточные условия существования допустимых (не нарушающих директивных сроков и ограничения предшествования требований') расписаний [14-16,20,21,26,46,53] и различные алгоритмы построения допустимых расписаний [9-II, 14-16,20,21,23,24,26,41,46].

В работах [20,24,46] получена верхняя оценка числа прерываний обслуживания требований по оптимальному расписанию, в предположении, что критерий оптимальности - минимальное число прерываний обслуживания требований. В этих работах предлагаются алгоритмы построения допустимого расписания, при котором прерывания обслуживания требований имеют место не чаще, чем в моменты поступления требований в систему.

В случае, когда прерывания обслуживания требований запрещены, задача построения допустимого расписания является /V -полной в сильном смысле [31,72,73].

В работах [12,41,45] предлагаются точные решения задачи построения допустимого расписания без прерываний обслуживания требований средствами математического программирования и методом ветвей и границ. Исследованию частных случаев, когда задача разрешима за полиномиальное время, посвящены работы [16,19,47,48,69,70]. В работе [44] определяются характеристики множества всех допустимых расписаний.

Задача построения допустимых расписаний для системы обслуживания с несколькими параллельными приборами рассматривается в работах [9-11,15,20-21,23,25,27,40,42,43,46,49-54].

В случае, когда разрешены прерывания обслуживания требований и не задано ограничение предшествования требований, известны необходимые и достаточные условия существования допустимых расписании [20,21,46].

В работах [20,2l] задача построения допустимого расписания решается сведением к задаче нахождения максимального потока в транспортной сети, а в [б8] - средствами математического программирования.

В работе [4б] приводится алгоритм построения некоторого подмножества допустимых расписаний в случае, когда требования в систему поступают одновременно и не задано ограничение предшествования требований.

В работах [59,60] рассматривается модель ВС реального времени, представляющая собой систему обслуживания, в которую периодически поступают потоки требований.

Однако вышеперечисленные модели учитывают лишь основной ресурс ВС - время центрального процессора.

В работах [15,34,62-66] рассматриваются более сложные модели, в которых учитываются различные факторы, влияющие на функционирование ЦП.

В работах [15,34] предлагается модель однопроцессорной ВС реального времени, которая учитывает влияние системы ввода/вывода на работу ЦП.

В работах [62-66^ предлагаются алгоритмы планирования, которые учитывают распределение основных ресурсов ВС. Однако в [62,64,66] предполагается, что времена обслуживания всех требований одинаковы, в [бб] предполагается, что требования в систему поступают одновременно и отсутствует ограничение предшествования требований, а в [бЗ] предлагается лишь метод оценки гарантированного времени ответа системы.

В настоящей работе исследуется математическая модель ВС реального времени, которая учитывает основные ресурсы, подлежащие распределению, такие, как время ЦП, основная память, вспомогательная память и периферийные устройства.

Модель представляет собой одностадийную детерминированную систему обслуживания, состоящую из М А параллельных идентичных приборов. На обслуживание поступает конечный поток jVj требований, каждое из которых может обслуживаться на любом приборе, причём одно и то же требование не может обслуживаться одновременно на нескольких приборах, и в любой момент времени каждый прибор обслуживает не более одного требования.

Требование I е S поступает в очередь на обслуживание в момент времени iL >, 0 , требует для обслуживания ii > О единиц времени и должно быть обслужено к моменту времени , называемому директивным сроком.

На множестве требований задано отношение частичного порядка, определяющее возможную последовательность обслуживания требований. Предполагается, что разрешены прерывания обслуживания требований, причём на прерывания не расходуется дополнительное время.

Имеется п, видов ресурсов , <&*.) нескладируемого типа, причём количество ресурсов каждого вида конечно.

Для каждого требования .t е S задан вектор потребляемых ресурсов х" - г».,•• •, ^и. ) • Начинать обслуживание требования се S можно только после того, как выделенн все необходимые ресурсы, а после окончания обслуживания этого требования все выделенные ранее ресурсы освобождаются и могут быть повторно использованы.

Задачи расчёта временных характеристик и оценки необходимого количества ресурсов ВС реального времени сводятся к задаче построения допустимых (относительно директивных сроков, ограничения предшествования требований и ограничения на ресурсы) расписаний для вышеописанной системы обслуживания.

Последняя задача является hf ffi -полной в сильном смысле в случае, когда времена обслуживания всех требований равны единице, на множестве требований задано отношение частичного порядка и число приборов М > -i [3l] .

Основной целью данной работы является исследование свойств вышеописанной математической модели ВС реального времени, исследование случаев, когда задача построения допустимых расписаний разрешима за полиномиальное время и конструирование эффективных алгоритмов построения расписаний работы моделей такого типа.

В первой главе диссертационной работы вводится понятие базиса допустимых расписаний, и предлагаются методы построения базиса допустимых расписаний для одностадийных детерминированных систем обслуживания с одним или несколькими параллельными идентичными приборами.

Показывается, что можно ограничиться рассмотрением только полных систем обслуживания, в которых в любой момент времени каждый из приборов занят обслуживанием некоторого требования, т.е. недопустимы простои приборов.

В случае, когда отсутствуют ограничения на повторно используемые ресурсы, даётся описание методов построения базиса допустимых расписаний для системы обслуживания с одним прибором и несколькими параллельными идентичными приборами при одновременном поступлении требований в систему.

Предлагается способ построения любого допустимого расписания, основанный на использовании методов построения базиса допустимых расписаний, и описывается множество всех допустимых расписаний в вышеуказанных случаях.

Приводятся оценки временной сложности разработанных алгоритмов.

Вторая глава посвящена конструированию различных алгоритмов построения допустимых расписаний для одностадийных детерминированных систем обслуживания при отсутствии ограничений на повторно используемые ресурсы. При этом существенно используются методы построения базиса допустимых расписаний, разработанные в первой главе.

Описывается множество активных расписаний, обладающих тем свойством, что при каждом назначении требования обслуживаются максимальное возможное время, но не больше, чем до момента поступления в систему некоторого требования.

Показывается, что при построении допустимых расписаний для системы обслуживания с одним прибором и ограниченными ресурсами можно рассматривать только активные расписания. Получены верхние оценки числа прерываний обслуживания требований по любому активному расписанию для системы обслуживания с одним прибором и несколькими приборами при одновременном поступлении требований в систему.

Для системы обслуживания с одним прибором получена верхняя оценка числа прерываний обслуживания требований по оптимальному расписанию, в предположении, что критерий оптимальности - минимальное число прерываний обслуживания требований.

Далее предлагается эффективный алгоритм приоритетного планирования для системы обслуживания с одним прибором и несколькими параллельными приборами при одновременном поступлении требований в систему.

Описывается алгоритм метода ветвей и границ построения активного расписания с минимальным числом прерываний обслуживания требований для системы обслуживания с одним прибором.

В конце главы описывается множество всех допустимых расписаний для системы обслуживания с несколькими параллельными приборами при отсутствии ограничения предшествования требований.

В третьей главе алгоритмы построения базиса допустимых расписаний и активных расписаний применяются для решения задач расчёта характеристик и планирования вычислительного 'Процесса при проектировании ВС реального времени.

Предлагается метод определения необходимого быстродействия процессора ВС реального времени. Основу метода составляет алгоритм построения активного расписания для системы обслуживания с одним прибором и ограниченными ресурсами. Этот алгоритм использует метод построения базиса допустимых расписаний, позволяющий существенно совратить перебор вариантов.

Далее описывается метод оценки количества ресурсов ВС, необходимых для управления объектом в реальном времени. Основу этого метода составляет алгоритм построения активного расписания, при котором прерывания обслуживания требований имеют место не чаще, чем в моменты поступления в систему требований, имеющих вложенные директивные интервалы.

В заключении главы приводятся результаты вычислительных экспериментов, которые показали достаточно высокую скорость сходимости алгоритмов построения активных расписаний для систем обслуживания с числом требований около 100.

Результаты вычислительных экспериментов подтвердили, что разработанные в данной работе алгоритмы могут быть использованы при проектировании ВС реального времени для расчёта временных характеристик и характеристик ресурсов ВС.

В данной работе в основном используется терминология, принятая в теории расписаний [9].

Основные результаты диссертационной работы опубликованы в [75-79].

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Овсянкин, Борис Петрович

Выводы.

1. Алгоритм А позволяет построить активное расписание достаточно высокого качества, которое отличается от оптимального примерно на 12%.

2. Алгоритм В построения оптимального активного расписания имеет достаточно высокую скорость сходимости для задач с числом требований порядка 100. За приемлемое время он находит оптимальное решение примерно в 93% случаев, а в 3% случаев находит приближённое решение.

3. Алгоритм С построения активного расписания для систем обслуживания с ограниченными ресурсами работает достаточно быстро для задач с числом требований около 100. За приемлемое время решение было получено в 97% случаев.

4. Разработанные в данной работе алгоритмы построения активных расписаний для одностадийных детерминированных систем обслуживания могут быть использованы при проектировании ВС реального времени для расчёта временных характеристик и характеристик ресурсов ВС.

ЗАКЛЮЧЕНИЕ

Требование надёжности, предъявляемое к современным ВС реального времени, приводит к тому, что ещё на этапе проектирования таких систем полезно иметь различные временные оценки ВС и оценки ресурсов, необходимых для управления объектом в реальном времени.

В настоящей работе исследована математическая модель ВС реального времени, которая учитывает основные ресурсы ВС такие, как время ЦП, основная память, вспомогательная память, периферийные устройства, а также программное обеспечение, например, файлы данных и таблицы. Вышеописанные задачи оценки характеристик проектируемой ВС реального времени были сведены к задаче построения допустимых расписаний работы такой модели.

Поскольку последняя задача оказалась N9 -полной в сильном смысле, то основное внимание в диссертационной работе уделялось исследованию свойств модели для различных классов подзадач. Эти свойства были использованы для конструирования алгоритма построения допустимого расписания работы модели и методов оценки характеристик модели ВС реального времени в общем случае.

Основу принятого в диссертационной работе подхода составляют эффективные методы построения базиса допустимых расписаний, которые позволяют построить любое допустимое расписание и описать множество всех допустимых расписаний работы модели в случае, когда отсутствуют ограничения на ресурсы. На основе исследования свойств базиса допустимых расписаний было описано некоторое множество активных расписаний, т.е. расписаний, допускающих прерывания обслуживания требований лишь в определённые моменты времени. Результаты, полученные при исследовании свойств активных расписаний, были применены для решения задач расчёта временных характеристик и характеристик ресурсов проектируемой ВС реального времени.

Вычислительные эксперименты показали достаточно высокую скорость сходимости разработанных алгоритмов, и следует ожидать, что описанные в данной работе методы расчёта характеристик и планирования вычислительного процесса могут найти применение при проектировании ВС реального времени.

- но

Список литературы диссертационного исследования кандидат физико-математических наук Овсянкин, Борис Петрович, 1984 год

1. Грубов В.И., Кирдан B.C. Справочник по ЭВМ и аналоговым устройствам. Киев: Наукова Думка, 1977.

2. Липаев В.В., Колин К.К., Серебровский Л.А. Отладка систем управляющих алгоритмов ЦВМ реального времени. М.: Сов. радио, 1974.

3. Липаев В.В., Яшков С.Ф. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975.

4. Мартин Дж. Программирование для вычислительных систем реального времени. М.: Наука, 1975.

5. Шоу А. Логическое проектирование операционных систем. М.: Мир, 1981.

6. Головкин Б.А. Расчёт характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 19®.

7. Липаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979.

8. Авен О.И., Коган Я.А. Управление вычислительным процессом в ЭВМ. М.: Энергия, 1978.

9. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.

10. Танаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы обслуживания. М.: Наука, 1984.

11. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.

12. Беззубов Ю.И. Оптимизация вычислительного процесса в ЦВМ при детерминированном потоке заявок.- Изв.АН СССР. Техн. кибернетика, 1975, W 3.

13. Беззубов Ю.И. Оптимальный план вычислительного процесса в управляющей ЭВМ.- Изв. АН СССР. Техн. кибернетика, 1978, № 4.

14. Буланже Д.Ю. Оптимальная коррекция директивных интервалов для задачи одного прибора. Препринт. М.: ВЦ АН СССР, 1983.

15. Буланже Д.Ю., Сашков Б.Г. Алгоритмы управления вычислительными системами жёсткого реального времени.- Изв. АН СССР. Техн. кибернетика, 1982, Р 6.v 16. Визинг В.Г. О расписаниях, соблюдающих директивные сроки выполнения работ.- Кибернетика, 1981, Р I.

16. Визинг В.Г. Оптимальный подбор интенсивностей выполнения работ при выпуклой функции штрафов за интенсивность.- Кибернетика, 1982, Р 3.

17. Визинг В.Г. Минимизация максимального запаздывания в системах обслуживания с прерыванием.- ЖВМ и МФ, 1982, Р 3.

18. Визинг В.Г., Клипкер И.А. Полиномиальный алгоритм решения задачи Гэри-Джонсона о составлении расписания.- Сообщения АН ГССР, 1981, Р I.

19. Гордон B.C. Детерминированные одностадийные системы обслуживания с прерываниями.- В сб.: Вычислит, техн. в машиностроении. Шнек: Ин-т техн. кибернетики АН БССР, июнь, 1973.

20. Гордон B.C., Танаев B.C. Детерминированные системы обслуживания с одним прибором, древовидным упорядочением требований и экспоненциальными функциями штрафа.- В сб.: Вычисл. техн. в машиностр. Минск: Ин-т техн. кибернетики АН БССР, 1973.

21. Гордон B.C. Об оптимальных расписаниях с прерываниями процесса обслуживания.- Изв. АН БССР. Сер. физ. мат. наук, 1974, № 5.

22. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной оптимизации.» Изв. АН СССР. Техн. кибернетика, 1982, № 6.

23. Копылов Г.Н. Точное решение задачи одного станка.- Вестн. Ярославского ун-та, 1975, вып. 9.

24. Левин М.Ш. Детерминированные задачи планирования при идентичных процессорах и одновременном поступлении заявок.-Изв. АН СССР. Техн. кибернетика, 1982, № 4.

25. Лившиц З.М. Минимизация максимального штрафа в задаче одного станка.- В сб.: Труды I зимней школы по математическому программированию. М.: ЦЗМИ АН СССР, 1969, вып. 3.

26. Карп P.M. Сводимость комбинаторных проблем. Кибернетический сборник. Новая серия. М.: Мир, 1975, вып. 12.

27. Ахо А., Хопкрофт Дк., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

28. Гэри М., Дконсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.

29. Буланже Д.Ю. Задача построения расписаний для вычислительных систем реального времени. Автореферат дис. на соискание уч. ст. канд. физ.-мат. наук. М.: ВЦ АН СССР, 1983.

30. Мищенко А.В., Сушков Б.Г. Минимизация времени выполнения работ, представленных сетевой моделью, при нефиксированных параметрах сети. Препринт. М.: ВЦ АН СССР, 1980.

31. Раевич С.К. Применение метода ветвей и границ для решения одной задачи распределения ресурсов.- В сб.: Математические методы решения экономических задач. М.: Наука, 1969, № I.

32. Кнут Д. Искусство программирования для ЭВМ. М.: Мир, 1978, т. 3.40. Со^м/ъю Coryvi^odjui амЛtfUoty. 'Yleu?- ^oiJL '. у. qwvcL 49 7-6.41. (ВюМу Жги^ W., 9. MJmA^ uil

33. SI AM £ CcyyAjwt., -1973, t* 8 ,44. b^JX^ (FuJUeJ. IWta £ CUA^

34. Цщ Mi fajJUL МфхЯМ*М> feb К to QASUUJUL ovut ом, Си /V<We vwx&fa**. Ор&ь. iRjLb4380.1. УЗ.45. е^сЖ -У., o?w С., QujUM £

35. O^y^Oifxiuo^. Ui. (fk*., 438Л, 19-.^, A/-/.

36. Hot-ku UX(L. Awwul МЛ^ЛК, ^oiuuLu^Lv^ (xJLjjMrbifJwiA, — Tbx^ (IW &><}. QoasuL., v.Z-1, N1.47. 'УьсиМ^ ^oXuu 'YYLivbLvvOJbiwj -Щц ОЛгШЯ^Л cLfbiouLjo^

37. СоЛлл^У^^олл IjUMJO) OU COYK.WMJVI cLlul cUA.48. {jajjz&jb 2. Oja^wta^7 o^ Ct Suv^A v^axAivui /yxl^xJi ~bo рЪъсяоЬLwxe, ситд^дллллЛ.- 'Yfb^wxQ.-m3 , ^ <9, A/5".

38. AoJh M, /4. -^OJ^VvU^OlSuC AC^JuJLm^Im/^ UJ-bUb Лил, JLoJjl^ — Ор*/ъ. 4919 , -ЛП, л/s.53.oc. l-U. M.54.1. Ovu

39. M^yJbcLuJllM^ uuxjjl 'XJzJt&<*J&, (Vvui.oisUXcLtl^M, ^^^V^U-VtLi/tC <x/wol /JjoJ^ojJ:oc. ПХТ0 CUas. AULf ОСaujI (Rj^. sUo^.

40. Ни. Т. C. ^«owi^i скллА, сиьМлмМ!^ Jfar\j(JU!sLWO>. ор^ъ. (RJU ., 96 У, 9.

41. U/fv^H. е.-У., УодХьил, ft./. MJh^-hum pгьотъсъ VjJjbvvL . - (Xcfc i^c^ywJjuoc^ л49 W, A/-/.

42. H out LOr CL . АМ^Л. jo£ slZpUJLVVciu^ ипДp^vu^^i. SI/\M QLrfl.mdA., 4ЭП,1*1Ъ,Ы1.

43. A^^U-^VUC'tH^ UjiJJl ^/UlA&ctsiMJLC,- rruUi.,

44. U/t <Ъ -ftasocL tCwuL ^ЯЯПХУ^упЛ^и^

45. Gtf Hul ACM, тз, Hhto, A/-/.во. ЪЬМ Л. ^C., С. On. ^JJmA^pto^&vn. (h*. , -/ЗУЯ, А/У61.

46. UKaJL OvueL etuJL, <&VL ^xy^- ОлмхЬjod Ojt^ 4ЭИ, гл A/3.62. Ъяи^оХ fy *K .-ZjyA/JL ~(лмля 'to-iJ&bимА&п, UAAjjL 'хялтл,VL 'XSUJ^UJjlv^ . Cxyu^.§<XAjoMl vfaocM^v^, W8. Wg.

47. I^IMJIOUUU^L ^МЛЛАЖЬА XH^ovujl (ела. «лг X^ot

48. ХЛаЛ,- tivKJl ^VlfbiruyvbW&vcl,. J E EE TxAMA. ^o^tuyo^dl4980, O: A/Y.64. a. a. Ck-We. oov^f&Jy ^еШ^ CLIJJ^AJJ&L ииьоилллл bo vvii.vU^w^na, s&L cei^ i^O/UM,. Фюсе^. <£d£.7 ЛП0, г* -fO,65. /^Lo^i^V^JkL (R>. iL "fcju^ ^4JLQ,YvJZ0biLj Лил- Ль

49. A^j^vwdjbJijtb. CyJ^YjJuuL , 4384, ДЛ, /V^.66. 6JloJxsiMywb, Ло^лЛм^ г^оилхс- Ореъ. fit*., -#98-/, ЛИ.67. (М^елд^ у. , ^xvX. %., а. Н.-У.

50. Ли/j^d to ъщьшься, ccmJjxjuL\aJj> :

51. М^АмЛыл. luaJJLа, Ь\slwAJL\\AJL .m, V.16, N1 '1. CL.H.y, fiwJU ^

52. CcyvtVWbCу»)t$JuLu£L\fiJj рЪоЖ&ЩЛ. &1ЛЛЛ, .1. Ьл^шкс OYUXl., Ш?, v.'/.и^чллАлл, f/чР" COYVI^^A- AZXAAM^Mj^, jO^bo^dh^. lov^vJjUt (wi /3^,14 xki,., WS", <*-/0.

53. Дорофеева М.П., Овсянкин Б.П., Шпенёв В.М. Управление обработкой данных в АСУ ТП,- В сб.: Проблемы разработки автоматизированных систем управления в нефтяной и газовой промышленности. Киев: Ин-т автоматики им. ХХУ съезда КПСС, 1982.

54. Брушлинская Н.Н., Дорофеева М.П., Овсянкин Б.П., Шпенёв

55. В.М. Об одной задаче организации обработки данных на ЭВМ.- ЖВМ и Щ, 1983, № 3.

56. Овсянкин Б.П. Об одной задаче организации обработки данных в многопроцессорных вычислительных системах.- ЯШМ и т, 1983, № 5.

57. Дорофеева М.П., Овсянкин Б.П., Смирнов А.В. О многопроцессорных расписаниях, соблюдающих директивные сроки.-Докл.' АН Арм. ССР, 1984.