Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задачи для самостоятельного решенияПоиск на нашем сайте 1. Построить сетевой график и определить: 1) ожидаемое время выполнения проекта; 2) вероятности завершения проекта за 33 дня и за 35 дней; 3) вероятность завершения работы E за 8 дней, вероятность завершения работы F за 12 дней. Обозначение работы Продолжительность, сутки Непосредственно предшествующая работа Минимальная Наиболее вероятная Максимальная A Нет B A C A D A E B и D F D и C G E и F 2. Построить сетевой график и определить: 1) ожидаемое время выполнения проекта; 2) вероятности завершения проекта за 60, 64 и 68 дней; 3) вероятности завершения работ: F за 12 дней, C за 9 дней, I за 8 дней, L за 10 дней. Обозначение работы Продолжительность, сутки Непосредственно предшествующая работа Минимальная Наиболее вероятная Максимальная A Нет B Нет C A и B D B E C и D F D G E и F H F I G и H J H K I и J L J M K и L N L 1.3. Линейные диаграммыПо сетевому графику, в котором дугам соответствуют работы, можно построить линейную диаграмму. Для этого указывается горизонтальная ось времени, по вертикальной оси с постоянным шагом откладываются позиции для горизонтального расположения отрезков, соответствующих работам. Длина отрезка равна длительности выполнения работы. В начальной позиции с момента времени 0 строится отрезок, отвечающий работе (0,1). В следующей вертикальной позиции с момента времени 0 строится отрезок (0,2). И так далее до последней работы с началом в нулевой момент времени. Начала и концы отрезков помечаются номерами начальных и конечных событий работ. Далее строятся отрезки, соответствующие работам с начальным номером 1. Пусть построены отрезки для работ с начальным i-м событием. Строим отрезки для работ с начальным (i+1)-м событием. Для этого находим самую правую метку с номером i+1. Соответствующий конец отрезка-работы даёт момент времени, от которого откладываются отрезки для работ с начальным (i+1)-м событием. Отрезки, строятся в порядке возрастания номера завершающего события для работы. Очевидно, что если взять проекции на ось времени всех правых концов отрезков с конкретным номером i, то максимальная из них даст Tip . Проекция самого правого конца всех отрезков даст Tкр. Минимальная проекция всех левых концов отрезков с меткой j даст Tjn . Величина сдвига отрезка (i,j) до самого левого конца отрезков с начальной меткой j определяет полный резерв времени работы (i,j). Величина сдвига отрезка (i,j) вправо без сдвига отрезков с начальным индексом j определяет свободный резерв времени работы (i,j). Линейная диаграмма сетевого графика, приведенного на рисунке 1, имеет следующий вид (рисунок 3).  4 5  3 5  2 4 2 .3  1 4  0 3  0 2  0 1  . . . . . . . . . . . . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Рис. 3.Существенным достоинством линейной диаграммы является наглядное представление работ, и возможность оценки во времени показателей, характеризующих выполнение работ. Например, количество одновременно выполняемых работ, загрузку исполнителей во времени, интенсивность потребления ресурсов в различные интервалы времени. Линейные диаграммы используются в эвристических алгоритмах при решении задач календарного планирования при ограниченных ресурсах. В этих задачах требуется найти минимальное время выполнения проекта при условии, что в каждый момент времени потребление необходимых для выполнения работ ресурсов не выходит за установленные границы. Основными методами решения таких задач являются приближенные процедуры, основанные на некоторых принятых правил или эвристиках. Рассмотрим задачу определения минимального времени выполнения проекта при условии заданных времён выполнения работ и интенсивностей потребления одного ресурса. То есть для каждой работы (i,j) задано время её выполнения tij и интенсивность потребления ресурса cij в каждый момент времени. Задана граница C потребления ресурса всеми работами, выполняемыми в каждый момент времени. Решение задачи начинается с построения сетевого графика и линейной диаграммы без учёта потребления ресурса. Затем на линейной диаграмме строятся проекции на ось времени всех начал и концов отрезков-работ. В результате получим моменты времени τ0=0, τ1, τ2, … , τk . Просматриваем последовательно интервалы времени [τi , τi+1], определяя для каждого суммарную интенсивность потребления ресурса выполняемыми в рассматриваемый интервал времени работами и проверяя полученный результат с заданной границей C. Если обнаруживается интервал времени [τi , τi+1], на котором интенсивность потребления ресурса превышает границу, необходимо некоторые работы, выполняемые в данный интервал времени, либо прервать в момент времени τi , если прерывание работы допускается, и возобновить выполнение в момент времени τi+1 , либо отсрочить начало их выполнения до момента τi+1. Выбор работ для изменения времён их выполнения осуществляется по определённой заранее эвристике. Например, «для прерывания или сдвига начала выполнения выбирается работа с наименьшей интенсивностью потребления ресурса». Если имеются работы с одинаковыми интенсивностями, то для них применяется следующая эвристика «для прерывания или сдвига начала выполнения выбирается работа с большей продолжительностью». Если и таких работ несколько, то применяют эвристику «изменению подлежит работа с большим номером начального события». Работы включаются в перечень изменяемых работ до выполнения условия не превышения границы C суммарной интенсивностью потребления ресурса оставшимися работами. Далее на линейной диаграмме производятся сдвиги выбранных отрезков-работ. Если допускается прерывание работы, то отрезок-работа разбивается на две части, первая часть от начала работы до момента времени τi , вторая часть от момента времени τi до момента завершения работы. Вторая часть отрезка сдвигается вправо на величину τi+1 - τi . Указанный сдвиг может привести к необходимости сдвига вправо отрезков-работ, начальным событием которых является завершающее событие сдвигаемой работы. Что по аналогии может вызвать сдвиги вправо некоторых отрезков-работ. Если работа не допускает прерывания, соответствующий отрезок сдвигается вправо так, чтобы его начало соответствовало моменту времени τi+1. После проведения сдвигов процедура повторяется, начиная с момента времени τi+1.Пример. Пусть для сетевого графика на рисунке 3 заданы интенсивности потребления ресурса (таблица 4), граница C=10 и прерывание работ не допускается. Таблица 4. Работа (0,1) (0,2) (0,3) (1,4) (2,3) (2,4) (3,5) (4,5) Интенсивностьпотребления ресурса 5 3 3 2 0 5 1 4 Определим эвристики: «сдвигается работа с минимальной интенсивностью потребления ресурса», «при равенстве интенсивностей сдвигается работа с меньшей продолжительностью выполнения».  4 5 3 5 2 4 2 .3 1 4 0 3 0 2 0 1 . . . . . . . . . . . . . . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Рис. 4. На первом этапе получим τ0 =0, τ1=3. Суммарная интенсивность потребления ресурса в интервале времени [0,3] равна 11, что превышает границу. В соответствии с эвристиками сдвигаем отрезок (0,2) на три единицы вправо, с последующими сдвигами отрезков (2,3), (2,4), (4,5). Получим линейную диаграмму, приведенную на рисунке 4. На втором этапе τ0=3, τ1=5. На интервале [3,5] суммарная интенсивность равна 11, что приводит к необходимости сдвига отрезка (0,2) на две единицы, опять-таки с последующими сдвигами отрезков (2,3), (2,4), (4,5). В результате получим линейную диаграмму, приведенную на рисунке 5. 4 5 3 52 42 .3 1 40 30 20 1 . . . . . . . . . . . . . . . . . . . . . . 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Рис. 5. Третий этап даёт τ0 =5, τ1=8, τ2 =10, τ3=12, τ4 =18, τ5=19, τ6 =23. В интервалах времени [τi , τi+1], i=0,…,5, суммарные интенсивности не превышают границу C. Следовательно, линейная диаграмма определяет календарный график (рис.5.) выполнения работ с Tкр =23.
|
||
|
|
Последнее изменение этой страницы: 2024-07-06; просмотров: 53; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.217.21 (0.006 с.) |
