Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Клименко Анна Борисовна
РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛЕЙ И МЕТОДОВ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ ДЛЯ НЕОДНОРОДНЫХ СИСТЕМ ИСПОЛНИТЕЛЕЙ С ОБУЧЕНИЕМ И НАЛИЧИЕМ РЕЗЕРВА РЕСУРСОВ
Специальность 05.13.17 Теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Таганрог - 2012
Работа выполнена в Технологическом институте федерального государственного автономного образовательного учреждения высшего профессионального образования Южный федеральный университет в г. Таганроге НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук, профессор Горелова Галина Викторовна ОФИЦИАЛЬНЫЕ доктор технических наук, профессор ОППОНЕНТЫ: Карелин Владимир Петрович доктор технических наук, профессор Бутакова Мария Александровна ВЕДУЩАЯ ОРГАНИЗАЦИЯ: Южно-Российский государственный технический университет (Новочеркасский политехнический институт)
Защита диссертации состоится л28 сентября 2012 г. в 1420 на заседании диссертационного совета Д.212.208.21 при федеральном государственном образовательном учреждении высшего профессионального образования Южный федеральный университет по адресу: 347928, Таганрог, пер.
Некрасовский, 44, ауд. Д-406.
С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу: г. Ростов на Дону, ул. Пушкинская, 148.
Автореферат разослан л 12 июля 2012 г.
Ученый секретарь диссертационного совета Чернов Н.И.
Общая характеристика работы
Актуальность темы исследования.
Задача календарного планирования является одной из классических задач исследования операций. В настоящее время, однако, существуют процессы, для которых классические модели и методы календарного планирования являются недостаточными и не отражают таких значимых особенностей проектов, как: переменный характер параметров, существование зависимостей между параметрами, возможность наличия резерва ресурсов.
Одной из областей календарного планирования, где перечисленные особенности носят ярко выраженный характер, является календарное планирование проектов по производству интеллектуальных продуктов и услуг, которые производятся людьми. Здесь производительность исполнителей носит переменный характер, суммарная производительность системы исполнителей не находится в прямой зависимости от количества ресурсов, существует резерв исполнителей, которые могут быть добавлены к уже функционирующей системе. При этом, как правило, имеются ограничения на следование решаемых задач.
Следует отметить, что решение задачи календарного планирования само по себе является информационным процессом, поскольку предполагает сбор, обработку и представление информации. С другой стороны, процесс производства интеллектуальных продуктов и услуг является комплексным информационным процессом, поскольку:
- каждый исполнитель производит сбор и обработку информации, полученной от исполнителя предыдущей задачи и, в свою очередь, в процессе решения поставленной задачи является создателем новой информации, которая затем может быть передана исполнителю следующей задачи.
- немаловажную роль в производстве интеллектуальных продуктов и услуг играет процесс обучения, влияющий на скорость и качество выполнения задач.
Таким образом, календарный план проекта является моделью информационного процесса.
Проблемами исследования особенностей динамики процессов производства интеллектуальных продуктов и услуг занимаются: Б. Боэм, Р.
Мадахи, Т. К. Абдель-Хамид, С. Мадник, А. Коуберн. Полученные модели позволяют проводить оценку рисков проектов с учетом переменного характера параметров систем, но не рассчитаны на составление календарных графиков работ.
Тема календарного планирования неоднократно рассмотрена в работах:
Р.В. Конвея, В.Л. Максвелла, Л.В. Миллера, В.С. Танаева, М. Пинедо, Е.С.
Вентцель, Д.Херрмана, Э.Лина и др. Календарное планирование представляется как задача распределения ресурсов с неизменными параметрами. Обработка неопределенностей, влияющих на выполнение работ, производится путем использования концепции динамического планирования. Известные модели задач календарного планирования не позволяют учитывать переменный характер параметров и зависимости между их значениями.
Также необходимо отметить работы А.Б. Барского, разработавшего модель и метод решения задачи комплектации вычислительной системы (ВС) минимальной стоимости, которая позволяет сформировать систему исполнителей и план распределения работ между ними, при условии выполнения проекта в указанный срок. Модель задачи комплектации ВС минимальной стоимости учитывает возможность формирования системы исполнителей и существование ограничений на следование задач без учета изменений параметров системы и наличия ограничений на ресурсы.
Таким образом, можно утверждать, что область календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов является недостаточно разработанной, что определяет актуальность темы исследования.
Целью данной работы является разработка и исследование моделей и методов календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
Исходя из поставленной цели, основной научной задачей является разработка модели задачи календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности и методов ее решения при следующих исходных данных:
имеется неоднородная система исполнителей, работающих параллельно;
неоднородное множество исполнителей, которые могут быть подключены к проекту; задачи, предназначенные к исполнению с ограничением на следование;
плановое время завершения проекта и момент времени, в который происходит принятие решения о формировании состава множества исполнителей и распределении по ним не решенных задач.
Для достижения поставленной цели в диссертации решаются следующие задачи:
1. Исследование и анализ модели задачи комплектации вычислительной системы минимальной стоимости как аналога.
2. Разработка математической модели задачи календарного планирования и выбор критерия оптимизации для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
3. Разработка метода оценки минимального времени выполнения проекта для неоднородной системы исполнителей с переменной производительностью.
4. Разработка методики календарного планирования проекта для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
5. Разработка алгоритма диспетчеризации для неоднородной системы исполнителей с переменной производительностью.
6. Выполнение вычислительного эксперимента и апробация разработанных методов.
Объект исследования: система распределения работ по исполнителям для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
Предмет исследования: модели, методы и алгоритмы календарного планирования проектов.
Диссертационная работа выполнена в рамках специальности 05.13.17 - Теоретические основы информатики и соответствует ей по п.2 - Исследование информационных структур, разработка и анализ моделей информационных процессов и структур.
Методы исследования: математическое моделирование, вычислительный эксперимент, методы исследования операций.
Достоверность и обоснованность научных положений, выводов, алгоритмов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, результатами вычислительного эксперимента, актами о внедрении, выступлениями на конференциях и публикациями.
Наиболее существенные научные положения, выносимые на защиту:
1. Математическая модель задачи календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности, отличающаяся от модели задачи-аналога о комплектации ВС минимальной стоимости структурами исходных данных, налагаемыми ограничениями на переменные, наличием переменных параметров и зависимостей между их значениями, что расширяет область применения моделей задач календарного планирования.
2. Метод получения младшей G-выборки для неоднородных систем исполнителей с переменной производительностью, отличающийся от метода, описанного Барским А.Б., структурами исходных данных и введением параметра производительности с переменным значением, что позволяет получить G-выборку для графа задач, вершины которого взвешены трудоемкостями и производительностью, функционально зависящей от времени.
3. Метод оценки минимального времени выполнения проекта для неоднородной системы исполнителей с переменной производительностью, отличающийся от метода, предложенного Барским А.Б., структурами исходных данных, наличием дополнительной процедуры расчета времени завершения решения задач исполнителями и методом построения младшей G-выборки, что позволяет оценить минимальное время завершения проекта с учетом переменного характера производительности исполнителей и взвешенности информационного графа задач их трудоемкостями;
4. Алгоритм диспетчеризации для неоднородной системы исполнителей с переменной производительностью, отличающийся от алгоритма Барского А.Б.
структурами входных данных и наличием дополнительных процедур инициализации алгоритма и расчета времени завершения решения задач исполнителями, что позволяет произвести распределение задач по исполнителям с учетом переменного характера их производительности;
5. Методика календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности, позволяющая сократить расходы на проект при условии его выполнения в запланированный срок, а также выполнить прогнозирование общего бюджета проекта в точках перепланирования.
Научная новизна диссертационной работы заключается в создании модели, методов, алгоритма и методики календарного планирования проектов для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
Практическая ценность работы заключается в разработке модели, методов, алгоритма и методики, позволяющих прогнозировать общую стоимость проекта и уменьшить ее (до 25% от первоначально планируемой по результатам вычислительного эксперимента).
Апробация работы: Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на IX научнопрактической конференции преподавателей, студентов, аспирантов и молодых ученых (Таганрог, 2008), X научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых (Таганрог, 2009), IV Международной конференции Математика, ее приложения и математическое образование (Улан-Удэ, 2011), Шестой научно-практической конференции Перспективные системы и задачи управления (Таганрог, 2011), Международной научнопрактической мультиконференции Управление большими системами2011(Москва, 2011).
Внедрение результатов работы: результаты работы используются в работе OOO Inostudio Solutions и ООО Бизнес-Интеллект.
Публикации: по материалам диссертации опубликовано 19 печатных работ, в том числе 7 статей в изданиях, входящих в Перечень ведущих научных журналов и изданиях, выпускаемых в РФ, утвержденных ВАК РФ.
Структура и объем работы: рукопись диссертации состоит из введения, трех глав, заключения, библиографического списка из 1наименований, изложенных на 134 страницах машинописного текста и приложений, содержит 52 рисунка и 7 таблиц.
Во введении обоснована актуальность темы, определены цель и задачи диссертационной работы, объект и предмет исследования, указаны методы исследования, научная новизна, основные положения, выносимые на защиту, приведены сведения о научной и практической значимости результатов работы, дано краткое содержание разделов диссертации.
Первая глава посвящена исследованию и анализу проблемной области календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
Выделены наиболее значимые особенности календарного планирования, такие, как: наличие неопределенностей, влияющих на адекватность выполнения работ составленному ранее календарному плану, изменения производительности исполнителей, связанные с процессами обучения персонала и взаимным влиянием подсистем исполнителей друг на друга. В связи с недостаточностью однократно составленного календарного плана работ исследованы используемые модели динамического планирования (rescheduling). Сделаны предварительные выводы о том, что распределение задач по исполнителям в точках перепланирования может уменьшить стоимость проекта за счет коррекции календарного плана проекта и состава системы исполнителей в точках перепланирования.
Вторая глава посвящена решению основной научной задачи.
Принципиальное отличие задачи календарного планирования для неоднородных систем с обучением и наличием резерва ресурсов от классического календарного планирования заключается в том, что в силу существования резерва ресурсов возможно изменение состава системы исполнителей. Наиболее близким по смыслу аналогом является задача о комплектации вычислительной системы (ВС) минимальной стоимости, где решением задачи является состав ВС и план распределения задач между процессорами. Тем не менее, математическая модель задачи о комплектации ВС минимальной стоимости не учитывает наличия переменных параметров в описании ресурсов и наличие зависимостей между значениями параметров модели, что является обоснованием необходимости разработки математической модели задачи календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности.
Исходные данные формализованы следующим образом:
1. Информационный граф задач G, полученный путем декомпозиции главной задачи проекта на подзадачи в соответствии с одной из известных методик (например, Work breakdown structure):
, где { } { } - множество вершин графа, { } - множество предварительно оцененных трудоемкостей задач, - множество дуг, определяющих связи между задачами по информации, B={ } - отношение выполненной части задачи к общему объему задачи в момент времени (точки перепланирования). Если данная задача еще не назначалась на выполнение, то. В случае, если задача уже назначена на выполнение и решается, значение может быть равно, к примеру, 50%. Если задача выполнена, то, соответственно,. Вершины, для которых значения не рассматриваются в дальнейшем.
2. Система исполнителей M={ }, i exp n_exp learn_exp M M M M, принимающих участие в решении задач проекта:
, где exp M - множество исполнителей-экспертов, n _ exp M - множество исполнителей, для которых не окончен срок ассимиляции в проекте и которые еще не могут считаться экспертами, learn_ exp M - множество исполнителей-экспертов, выделенных для обучения неэкспертов, i - порядковый номер исполнителя, - номинальная производительность исполнителя, - оплата труда i-го исполнителя, - момент времени, в который произошло присоединение исполнителя к множеству исполнителей, работающих над проектом, - номер задачи, которая может находиться на решении у i-го исполнителя в точке перепланирования tq, - переменная, определяющая принадлежность исполнителя к одной из трех групп исполнителей в соответствии с принимаемым значением:
, где - определяет принадлежность исполнителя к группе исполнителейэкспертов;
- определяет принадлежность исполнителя к группе исполнителей-неэкспертов;
- определяет принадлежность исполнителя к группе исполнителейэкспертов, в чьи обязанности входит обучение не-экспертов.
3. Множество исполнителей ={ }, определяющее наличие резерва исполнителей, для которых существует возможность подключения к проекту.
4. Декларируемое время завершения проекта, то есть момент времени, в который проект должен быть завершен по плану.
5. Среднее время ассимиляции нового исполнителя в проекте.
6. Точка перепланирования tq.
Схематично переходы исполнителей в системе из одной группы в другую можно представить следующим образом (рис.1):
Период Резерв ассимиляции не исполнителей завершен Добавление исполнителя в Не-эксперт проект Период ассимиляции завершен Обучающий Эксперт эксперт Перемещение между подгруппами исполнителей Рисунок 1 - Схема переходов в системе исполнителей Для описания изменения производительности исполнителей с течением времени предлагается использовать функции 1 - 3.
Представим номинальную производительность не-эксперта, подключаемого к проекту, в виде формулы (1).
p, t tq 1i p2i (1 ) pnomin _ exp(t) (t tq ) p2i, tq t tq tassim (1) tassim p2i, t tq tassim где - номинальная производительность не-эксперта;
pnomin _ exp(t) - исходная производительность не-эксперта при подключении к проекту;
p 1i - приобретаемая не-экспертом производительность к концу периода p 2 i ассимиляции в проекте;
- отношение исходной производительности к приобретаемой (по результатам исследований колеблется от 0.7 до 0.8);
tq - момент времени, когда происходит перепланирование (точка перепланирования);
- период ассимиляции.
tassim i (t) Зависимость от времени количества времени, потребляемого каждым неэкспертом для собственного обучения и отнимаемое у обучающих экспертов, опишем в виде:
Li i (t) (t tq ) Li, tq t tq tassim (2) tassim 0, t tq tassim где Li - начальное значение доли времени, отнимаемого у экспертов новичком на собственное обучение (по статистике, на обучение у вновь принятых на работу исполнителей уходит до 0.3 рабочего времени).
Зависимость номинальной производительности обучающих экспертов от времени при участии в проекте исполнителей, еще не ставших экспертами, выразим формулой:
mn _ exp mn _ exp (t) (t) k k k1 k pnomilearn_ exp(0) (1 ), при 1, pnomi learn_ exp(t) (3) mlearn_ exp mlearn_ exp 0, в остальных случаях.
где pnomilearn_ exp(t) - номинальная производительность обучающего эксперта;
k (t) - доля времени, отнимаемая у экспертов k-м не-экспертом на собственное обучение;
- число не-экспертов;
mlearn_exp - число обучающих экспертов.
Для исполнителей, принадлежащих к группе экспертов, будем полагать следующее: их номинальная производительность не подвержена изменениям в связи с обучением не-экспертов.
Номинальная производительность исполнителей уменьшается с возрастанием их количества в силу накладных расходов на их коммуникацию и выражается формулами (4-6), приведенными в работах Ф. Брукса и Р. Мадахи.
0.06mexp (4) pfact (t,m) pnomexp (t) (1 );
i i 1(5) 0.06mlearn_ exp pfact (t,m) pnomlearn_ exp (t) (1 );
i i 1(6) 0.06mn _ exp pfact (t,m) pnomn _ exp (t) (1 );
i i 1 где - фактическая производительность исполнителя-эксперта;
pfactiexp(t, m) pfactilearn_ exp(t,m) - фактическая производительность обучающего эксперта;
pfactin _ exp(t,m) - фактическая производительность новичка;
- общее число исполнителей, подключенных к проекту.
m | M | Приведем условия, выполнение которых обязательно при решении задачи календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности:
1. в точке перепланирования существует ограничение на ресурсы (исполнителей), такое, что:
exp n _ exp learn_ exp M M M M Mavail ;
2. для каждого исполнителя, работающего в группе экспертов либо присоединяемого к ней, время работы в проекте должно превышать период ассимиляции в проекте:
exp mi M :tijoin tassim tq ;
3. утверждение п.2 справедливо и для исполнителей, работающих в группе обучающих экспертов:
learn_ exp mi M :tijoin tassim tq ;
4. все задачи проекта должны быть выполнены за время, не превышающее запланированное:
plan ;
max(Tij ij ) T ij 5. для всех задач, подлежащих распределению, время начала их решения не меньше значения tq:
;
j :Tij tq plan tq T 6. ;
7. любая задача не может быть начата исполнителем до того, как он завершит решение предыдущей задачи:
I, J :TkI TkJ kJ или TkJ TkI kI plan crit T T 8., т.е. задача имеет смысл только в том случае, если запланированное время окончания проекта превышает минимально возможное время выполнения всех задач с учетом ограничения на их следование.
Модель задачи календарного планирования для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности (с оптимизацией по стоимостному критерию).
Для указанных исходных данных при перечисленных ограничениях (18), а также с учетом изменения производительности исполнителей в соответствии с предложенными функциями (1-6), необходимо найти такой план распределения задач по исполнителям Tij, а также состав системы исполнителей Mexp, Mn_exp, Mlearn_exp, такие, чтобы обеспечивалось q S MIN ( (max(Tij ij )) ), i I.
(7) cl si exp learn _ exp n _ exp Tij,M,M,M ij l1 i где cl - суммарная стоимость работ на l-м временном интервале до q-й точки перепланирования;
q - номер текущей точки перепланирования;
Tij - начало решения j-й задачи i-м исполнителем;
ij - время решения j-й задачи i-м исполнителем;
si - стоимость работ, выполняемых i-м исполнителем;
Mexp - множество исполнителей-экспертов;
Mn_exp - множество исполнителей, для которых не истек срок ассимилфции в проекте;
Mlearn_exp - множество исполнителей, выделенных для обучения нового персонала.
I - множество исполнителей, доступных для работы над проектом в точке перепланирования.
Для расчета времени завершения исполнителем задачи используется формальная процедура CALC (i,M, t, j), где i - номер исполнителя, M - система исполнителей, подключенных к проекту, t - момент времени начала решения задачи, j - номер задачи. Значение, возвращаемое процедурой CALC (i,M, t, j), равно моменту времени завершения решения j-й задачи i-м исполнителем при условии начала ее решения в момент времени t. Вычисление процедуры в данной работе основано на использовании численного метода Эйлера решения дифференциальных уравнений.
В случае, когда вершины информационного графа задач G взвешены кортежами вида
X1, pfact1(t,m), pfact2(t,m) X1, pfact1(t,m) X1, pfact2(t,m) X3, pfact2(t,m) X2, pfact1(t,m) X2, pfact2(t,m) X3, pfact1(t,m) X2, pfact1(t,m), pfact2(t,m) 2 X3, pfact1(t,m), pfact2(t,m) X4, pfact1(t,m) X4, pfact2(t,m) X4, pfact1(t,M), pfact2(t,M) Рисунок 2 - преобразование графа G в граф G*.
Метод получения младшей G-выборки для неоднородной системы исполнителей с переменной производительностью.
1. Принять к рассмотрению совокупность вершин, имеющих идентичное значение j.
2. Выполнить оценку времени завершения выполнения j-й задачи i-ми исполнителями с учетом переменного характера производительности и ее зависимости от времени, выбрать минимальное значение из полученных и этим значением пометить соответствующую вершину.
3. Перейти к рассмотрению следующего подмножества вершин с идентичными значениями j (п.1).
Правила построения графа G* таковы, что при отсечении неперспективных вершин j-го яруса не происходит потери оптимального решения. Разработанный метод позволяет сократить объем вычислений для получения младшей G-выборки.
Метод оценки минимального времени выполнения проекта для неоднородного множества исполнителей с переменной производительностью.
1. [Отсечение выполненных задач]. Преобразуем информационный граф задач следующим образом: необходимо отсечь вершины и исходящие из них дуги графа G, для которых bj=100%. Получаем подграф GТ.
2. [Закрепление задач за исполнителями]. Если в подграфе GТ есть вершины, 0 bj 0, j 1,...k для которых справедливо, то считаем эти задачи закрепленными за соответствующими исполнителями из множества М, для hi j, j 1,...k которых, соответственно,. Если таких вершин нет, то предварительно ни одна из задач не закреплена ни за каким исполнителем.
3. [Построение графа G*]. Производим преобразование графа GТ в G*.
Количество вершин графа G*, порождаемых из вершины графа GТ, которая считается закрепленной за исполнителем, остается равным 1.
4. [Получение младшей G-выборки]. Получаем младшую G-выборку, используя метод получения младшей G-выборки. Если одна из вершин закреплена за исполнителем, то она входит в младшую G-выборку.
5. [Вычисление оценки времени завершения проекта]. По полученной младшей G-выборке, вершины которой уже взвешены значением времени выполнения задач, вычислить критический путь графа.
6. [Конец].
Алгоритм диспетчеризации для неоднородной системы исполнителей с переменной производительностью.
Основные переменные и их значения описаны в таблицах 1 и 2. Алгоритм разработан на основе алгоритма диспетчеризации для неоднородной ВС Барского А.Б.
Талица 1 - основные переменные алгоритма диспетчеризации для неоднородной системы исполнителей с переменной производительностью № Переменная Расшифровка 1 P Матрица следования размера n, где n - число задач для выполнения. Т.к. граф не содержит контуров, матрица следования является треугольной. При этом предварительно отсечены задачи, выполненные к моменту времени tq.
2 m Число исполнителей 3 A Таблица номеров задач, назначенных последними для выполнения для каждого исполнителя. Эти номера заносятся в позиции, закрепленные за каждым исполнителем. Если последним назначен простой исполнителя в течение некоторого времени t, в соответствующую позицию заносится 0.
4 Таблица состоит из m строк, каждая из которых соответствует одному исполнителю. В строке записывается последовательность заданий исполнителю двух видов:
выполнить задачу, бездействовать t единиц времени.
5 Текущее время занятости исполнителя. Момент окончания Ti (отсчет времени ведется от нуля) выполнения последней задачи или простоя, назначенных к данному моменту распределения i-му исполнителю.
6 B Множество исполнителей, доступных в точке перепланирования к распределению задач.
В таблице 2 представлено описание используемых в разработанном алгоритме переменных с инициализирующими значениями.
Таблица 2 - исходные данные метода диспетчеризации для неоднородной системы исполнителей с переменной производительностью.
№ Переменная Инициализирующее Пояснения значение 1 Моделируемое текущее время T T tq занятости множества исполнителей 2 Число исполнителей l 1,...m l busy 3 B Множество исполнителей, B {M \ M } доступных в точке перепланирования к распределению задач busy busy 4 Множество исполнителей, занятых M {mi} M решением задач в точке перепланирования 5 R R Исходное количество входов матрицы следования P.
6 1 Номер итерации обработки матрицы следования.
7 На первой итерации алгоритма P P P матрица следования принимается тождественной исходной с учетом отсеченных вершин.
8 A A {hj :bj 0} В множество А заносятся номера задач, находящиеся на решении в точке перепланирования на места, соответствующие занятым исполнителям. Если в точке перепланирования все исполнители свободны, то в множество B заносятся номера всех свободных исполнителей, все позиции множества А становятся равными нулю.
9 На позиции, соответствующие Tl CALC(i, M,tq, j), занятым исполнителям, заносятся busy mi M значения вычисленного времени их занятости, вычисляя Tl соответствующие посредством вычисления CALC (i,M, tq, j).
Начало Инициализация переменных Проверка состояния входов матрицы, R= Определение наличия Расчет весов задач простоев Вычисление интервалов Расчет времен занятости простоев исполнителей Составление соответствий Вычисление минимального времени занятости исполнителей Назначение задач Моделирование окончания исполнителям выполнения задач исполнителями Уточнение назначений Проверка условия занятости исполнителей Проверка распределения задач Уплотнение матрицы следования Все задачи распрелеленыы Конец Рисунок 3 - Блок-схема алгоритма диспетчеризации для неоднородной системы исполнителей с переменной производительностью.
Методика составления календарного плана работ для неоднородных систем исполнителей с обучением и наличием резерва ресурсов в условиях неопределенности с оптимизацией по стоимостному критерию Исходными данными являются:
- граф задач G;
- множество M исполнителей, подключенных к проекту до точки перепланирования;
- множество исполнителей Mavail, которые могут быть дополнительно подключены к проекту;
- директивное время завершения проекта Tplan;
- момент времени, в который происходит перепланирование tq.
В случае предварительной оценки минимального времени выполнения проекта:
M Mavail путем рассмотрения комбинаций различных 1. Для множества вариантов состава групп исполнителей получить множество младших Gвыборок {G1, G2, Е Gk} в момент времени tq. Если при взвешивании вершин графа значениями времени выполнения задач и расчете критических путей полученных G-выборок не существует ни одной G-выборки, для которой plan crit T T, задача не имеет решения.
2. В результате оценок критических путей для множества младших G-выборок {G1, G2, Е Gk} получим некоторое множество оценок минимального времени выполнения проекта C={C1, C2, Е Ck}, сохраняя при этом данные о составах групп исполнителей.
3. Для выбранных множеств комбинаций исполнителей,(в случае существования нескольких младших G-выборок соответствующих C={C1, C2, Е Ck}), таких, что plan crit T T, произведем построение расписаний выполнения работ в соответствии с алгоритмом диспетчеризации для неоднородной системы исполнителей с переменной производительностью.
4. Из построенных расписаний выбрать такое, для которого стоимость проекта будет минимальной.
Без предварительной оценки минимального времени выполнения проекта:
1. Рассчитать общую стоимость проекта, пользуясь формулой (7). При этом выполняется моделирование выполнения задач исполнителями в соответствии с описанным выше алгоритмом диспетчеризации для неоднородного множества исполнителей c переменной производительностью, и, соответственно, становится известным значение T fact.
fact plan T T 2. Проверить условие. Если результат проверки положительный, то перейти к следующему пункту. В случае отрицательного результата перейти к п.3. В ситуации, когда проект с текущим количеством исполнителей не укладывается в отведенное на его выполнение директивное время, осуществляется проверка целесообразности подключения к проекту новых исполнителей. Кроме того, необходимо произвести рассмотрение различных вариантов состава подмножеств Mn_exp, Mexp, Mlearn_exp с учетом формул (1-6), определяющих изменение производительности исполнителей в зависимости от состава подмножеств и от времени подключения к проекту. Количество подключаемых к проекту исполнителей из множества Mavail ограничено следующим образом: возможно добавление новых исполнителей, пока Mavail или пока.
pnomilearn_ exp fact plan T T 4. Если в результате действий п.3 не удалось достичь, задача не имеет решения при существующих ограничениях. Перейти к п.7.
5. В ситуации, когда с текущим количеством исполнителей время выполнения проекта укладывается в директивное время его выполнения, целесообразно уменьшить количество исполнителей, т.к. это может привести к существенному удешевлению проекта. Для этого производится рассмотрение комбинаций вариантов состава подмножеств Mn_exp, Mexp, Mlearn_exp с уменьшением количества fact plan T T исполнителей, пока.
7. Конец.
Третья глава содержит результаты вычислительного эксперимента.
Заданы: информационный граф задач (рис. 5), исходная система исполнителей M, состоящая из трех исполнителей-экспертов с производительностями 10(fp/d), 9(fp/d), 8(fp/d) и стоимостью рабочего времени 60у.е., 50 у.е., 40 у.е.
соответственно. Также имеется множество доступных для подключения к проекту исполнителей со стоимостями эксплуатации 40у.е., 30 у.е., 60 у.е и изменениями производительности в течение периода ассимиляции в проекте: от 7 до 10fp/d, от 5 до 8 fp/d, от 8 до 10fp/d соответственно. Период ассимиляции в проекте для всех потенциальных новичков равен 14 дням, при этом время, которое новичку отводится для общения с обучающими экспертами в момент подключения к проекту, равен 0,25 рабочего времени. Директивное время завершения всего проекта, т.е. решение всех задач, описанных в графе на рис. plan T (дней). Момент времени, в который происходит принятие решения о добавлении новых исполнителей к проекту совпадает с началом работы над tq 0.
проектом, т.е.
45 1 2 80 1 Рисунок 4 - Информационный граф задач проекта.
Рисунок 5 - Выделенные результаты вычислительного эксперимента со временем выполнения проекта не более 40 дней (зависимость стоимости от состава системы исполнителей).
Из графика, представленного на рис. 5 видно, что минимальное значение стоимости проекта в условиях его завершения не позднее 40 дней, достигается при следующей комбинации исполнителей: эксперт 1+обучающий эксперт 2+обучающий эксперт 3+новичок 1+новичок 2, при этом планируемая стоимость проекта равна 8559 у.е., фактическое время завершения проекта равно 38,9 дня. Таким образом, при данных исходных данных возможно уменьшение расходов до 25%, учитывая выполнение проекта в указанный срок 40 дней.
Дальнейшее сокращение времени выполнения проекта приводит к его существенному удорожанию.
Сравнение результатов применения методики календарного планирования проекта с результатами решения задачи-аналога о комплектации ВС минимальной стоимости.
Для приведенного примера рассматриваются варианты стоимости комплектации системы исполнителей (1;2) с производительностями соответственно (1;3), комплектация варианта 1 предполагает стоимости исполнителей (1; 2,2) с постоянной производительностью (1; 3,5), комплектация варианта 2 предполагает стоимости исполнителей (2;3) с производительностями (2;4). Видно, что при возможности сокращения сроков выполнения проекта более дорогая комплектация системы исполнителей с большими производительностями может дать суммарную стоимость проекта меньшую, чем комплектация минимальной стоимости.
Рисунок 7 - Граф задач, взвешенный временем выполнения работ исполнителями.
Таблица 3 - сравнение результатов вычисления стоимости проектов.
Точный Диспетчеризация Вариант 1 Вариант метод А. по А. Барскому Барского Стоимость 3 3 3,2 комплектации Стоимость 12 9 8,3 6,проекта Время 4 3 2,6 1,окончания проекта Заключение содержит основные выводы по проделанной работе.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, входящих в перечень рекомендованных ВАК:
1. Клименко А.Б., Клименко В.В. Планирование разработки программного обеспечения в условиях неопределенностей. В мире научных открытий, 2010, №3(09). Часть 3. С.72-74.
2. Клименко А.Б. К вопросу о планировании разработки программного обеспечения в условиях неопределенности. Вестник АГУ, "Экономика", вып.2(62), 2010, с.156 - 164.
3. Клименко А.Б. Оценка времени выполнения проекта для неоднородного множества независимых исполнителей с переменной производительностью. В мире научных открытий. №8(20)/2011. С.175186.
4. Клименко А.Б., Клименко В.В. К вопросу о постановке задачи планирования программных проектов. В мире научных открытий.
№1(13)/2011. С.64-5. Клименко А.Б. Оптимизация стоимости программного проекта в условиях реактивного перепланирования: формальная постановка задачи. Проблемы управления. 5.2011.с.40-45.
6. Клименко А.Б. Планирование стоимости программного проекта в условиях неопределенности: формальная постановка задачи. В мире научных открытий. №3(15).2011. с.238-247.
7. Клименко А.Б. Методика оптимизации стоимости программного проекта. В мире научных открытий. №12(24).2011. с.18-35.
Другие публикации:
8. Клименко А.Б., Клименко В.В. Проблемы обобществления знаний персонала в ракурсе гибких методологий разработки программного обеспечения. Вестник ТИУиЭ. №1(7). 2008.с. 109-19. Клименко А.Б., Клименко В.В. Анализ эффективности процесса разработки программного обеспечения в условиях изменения численности команд разработчиков. Вестник ТИУиЭ. №2(8).2008. с. 7174.
10. Клименко А.Б., Клименко В.В. Методы и средства обобществления знаний персонала для гибких методологий разработки программного обеспечения. Труды IX научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых. Том III.
2008г. Изд-во ТИУиЭ, 2008. Т.3.с.3-6.
11. Клименко А.Б., Клименко В.В. Методика оптимизации процесса разработки программного обеспечения. Вестник таганрогского института управления и экономики. №1(9)2009.Изд-во ТИУиЭ, 2009.
С.108-112. Клименко А.Б., Клименко В.В. Оптимизация процесса разработки программного обеспечения для малых/средних коллективов разработчиков. Труды X научно-практической конференции преподавателей, студентов, аспирантов и молодых ученых. Том II.
2009г. Изд-во ТИУиЭ, 2009. Т.2.с.127-131.
13. Клименко А.Б., Клименко В.В. Разработка программного обеспечения в условиях неопределенности. Вестник ТИУиЭ.№1(11). 2010. С.72-76.
14. Клименко А.Б., Клименко В.В. К вопросу о планировании разработки программного обеспечения в условиях неопределенности.
Общественные науки. 2010/2. Изд-во МИИ НАУКА МОСКВА. С.231241.
15. Клименко А.Б. К вопросу об управлении проектами в условиях неопределенности: исследование формальных постановок задачи.
Математика, ее приложения и математическое образование. Материалы IV Международной конференции. - Ч2. - Улан-Удэ: Изд-во ВСГТУ, 2011. С.40-43.
16. Клименко А.Б. Минимизация стоимости программного проекта в условиях реактивного перепланирования. Вестник ТИУиЭ.№1(11).
2011. С.72-77.
17. Клименко А.Б. К вопросу о постановке задачи планирования программных проектов. Материалы шестой научно-практической конференции Перспективные системы и задачи управления. Таганрог:
изд-во ТТИ ЮФУ, 2011.
18. Клименко А.Б. К вопросу о получении младшей G-выборки графа задач для неоднородного множества исполнителей с переменной производительностью. Труды международной научно-практической конференции Управление большими системами-2011. Том 2. Общая редакция - В.Н.Бурков, Д.А.Новиков. - М.: ИПУ РАН, 2011. С.172-176.
19. Клименко А.Б. Составление расписания для неоднородной системы исполнителей с переменной производительностью. Общественные науки. 2011/9. Изд-во МИИ НАУКА МОСКВА. С.388-394.
Технологический институт Южного федерального университета в г. Таганроге 347928, Ростовская область г. Таганрог, пер. Некрасовский 44.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям