Построение - расписание
Cтраница 3
Предметом последних двух глав служат математические вопросы, возникающие при организации шахматных состязаний - от вычисления так называемых коэффициентов Эло, характеризующих индивидуальную силу шахматиста в данный момент, до построения рациональных расписаний. [31]
Также предположим, что продолжительность выполнения каждой работы на машине известна, и обозначим ее через ti, i N. Задача построения расписания выполнения множества работ одной машиной состоит в том, чтобы определить такой порядок выполнения работ, при котором некоторый заданный критерий эффективности будет принимать оптимальное значение. [32]
Тогда задача построения расписания, которому соответствует наименьшее значение функционала (9.1), сводится к следующей задаче транспортного типа. [33]
Доказательство достаточности (4.9) и (4.10) дает возможность использовать алгоритм построения расписания, если исходные данные совместны. Воспользовавшись приведенным алгоритмом, задачу построения расписания для простейшего случая задания условий легко решить. [34]
Следует отметить, что построение допустимого расписания или даже выяснение того факта, существует ли оно вообще, является зачастую далеко не тривиальной задачей. Вместе с тем во многих ситуациях построение допустимых расписаний не вызывает сколь-нибудь серьезных затруднений, и речь идет о выборе среди них наилучшего в том пли ином смысле расписания. [35]
Из теоремы 2.7 следует, что всякий раз, когда мы можем построить оптимальное расписание без прерываний для системы, состоящей из заданий с одинаковыми временами выполнения, мы можем построить расписание с прерываниями для системы заданий с произвольными временами выполнения, которое будет сколь угодно близким к оптимальному. Немногие случаи, для которых известны алгоритмы построения расписаний без прерываний, рассмотрены в § § 2.2, 2.3, а именно деревья при произвольном числе процессоров и произвольные частичные упорядочения при двух процессорах. [36]
Во второй и третьей главах рассмотрены основные алгоритмы составления расписаний, обеспечивающих минимизацию времени завершения комплекса работ и минимизацию среднего времени завершения работ соответственно для случаев различного числа тех или иных процессоров, различных видов заданий, их исходного упорядочения и условий исполнения. Четвертая глава посвящена вычислительной сложности решения задач упорядочения при построении расписаний. В пятой главе рассмотрены верхние оценки длин расписаний, а в шестой-точные и приближенные алгоритмы ветвей и границ для составления расписаний и результаты вычислительных экспериментов, а также осуществлено сравнение с алгоритмами динамического программирования. [37]
Состыковав расписания для интервалов Jk ( / c l, m), получим расписание s такое, что T ( s) T ( SO. Поскольку оценка временной сложности алгоритма упаковкп равна 0 ( п), то для построения расписания s по заданному расписанию sa требуется выполнить не более 0 ( пг) операций. [38]
 |
Информационно-техническая структура системы при работе в закрытом цикле. [39] |
При этом учитываются приоритет заявок и характеристики автомобилей. Разработаны и внедрены эффективные методы планирования внутризаводских автомобильных перевозок по маятниковым маршрутам и методы построения расписания движения транспорта по радиально-кольцевым маршрутам, обеспечивающие максимальное использование грузоподъемности транспортных средств при развозе продукции одного цеха в ряд других цехов. Некоторые алгоритмы оптимизируют маршруты перевозок по минимуму пробега автомобилей. [40]
В задаче построения расписания минимальной длины на известной вычислительной системе для заданного комплекса информационно и логически связанных задач уже можно рассматривать и статические, и динамические планы решения задач. Задачи планирования и назначения связаны между собой, и часто их разделение носит вынужденный характер либо объясняется принципами построения расписания. Это разделение может иметь место при составлении динамических списочных расписаний, в то время как при построении оптимальных статических расписаний решения этих задач взаимозависимы. [41]
Очевидно, что при этом расписание, минимизирующее потери, дает нулевое значение функционала, а все прочие - равное бесконечности. Если при конкретных значениях исходных данных минимум (4.8) имеет значение, будем говорить, что не обеспечивается возможность построения расписания, укладывающегося в предельные сроки. В этом случае будем говорить также, что исходные данные несовместимы. [42]
В предыдущем параграфе было установлено, что стратегия первым идет самый высокий уровень является оптимальной для лесов. Поскольку деревья являются частным случаем орграфов, следует ожидать, что и для произвольных орграфов уровни играют определенную роль при построении расписаний. Было бы хорошо, если бы мы смогли снова расставить приоритеты по уровням, после чего пришлось бы только заботиться о порядке, в котором должны выполняться задания одного уровня. [43]
Для всех единичных интервалов, предшествующих t, задание Tt, по утверждению леммы, не готово к выполнению. Следовательно, даже если до него и доходит просмотр списка, оно не может быть назначено на выполнение. В процессе построения расписания Si Tt может быть достигнуто в следующие после t интервалы, если имеется свободный процессор и нет других заданий, подлежащих назначению. [44]
Педагогически как на дневных, так и на вечерних отделениях / опраддывают себя одночасовые лекции, что подтверждается опытом заботы Ростовского университета. Но чтобы этот час учебной работы создал хорошую основу для самостоятельной работы студентов, лекция должна быть особенно тщательно подготовлена. Одночасовые лекции помогают построению расписания с эффективным использованием первых трех часов занятий. [45]
Страницы: 1 2 3 4