Содержание к диссертации
Введение
Глава 1. Модели управления информационными проектами 17
1.1. Основные понятия управления проектами 17
1.2. Проектирование информационных систем 21
1.3. Формирование состава исполнителей проекта 28
1.4. Методы решения задач дискретной оптимизации 40
1.5. Выводы и постановка задач исследования 50
Глава 2 Модели формирования команды информационного прооека 53
2.1. Модель формирования команды информационного проекта с минимальной продолжительностью выполнения работ при заданном уровне затрат 53
2.2. Модель формирования команды информационного проекта с минимальными затратами на оплату труда при заданной продолжительности выполнения работ 62
2.3. Модель формирования команды информационного проекта в условиях неопределенности 66
2.4. Многокритериальная задача формирования команды информационного проекта 71
2.5. Многокритериальная задача формирования команды информационного проекта при лингвистических критериях 74
Глава 3. Модели управления продолжительностью информационного проекта 79
3.1. Задача совмещения выполняемых работ 79
3.2. Определение рационального совмещения работ при минимизации стоимости выполнении информационного проекта 90
3.3. Определение рационального совмещения работ при выполнении информационного проекта 93
3.4. Дискретная задача рационального совмещения работ 102
Глава 4. Практическое применение разработанных моделей 107
4.1. Краткая характеристика разрабатываемого программного продукта 107
4.2. Формирование команды проекта 110
4.3. Определение степени совмещения работ в проекте 115
Заключение 120
Литература 122
Приложение 135
- Методы решения задач дискретной оптимизации
- Модель формирования команды информационного проекта с минимальными затратами на оплату труда при заданной продолжительности выполнения работ
- Определение рационального совмещения работ при минимизации стоимости выполнении информационного проекта
- Определение степени совмещения работ в проекте
Методы решения задач дискретной оптимизации
Модели формирования команды проекта, рассмотренные в п. 1.3. показали, что все они сводятся к решению задач дискретной оптимизации.
Рассмотрим общую постановку задач дискретной оптимизации (экстремальных задач комбинаторного типа) [49]. Задано конечное множество Q допустимых решений (комбинаций). В качестве таких комбинаций могут выступать перестановки п чисел (число возможных решений п!), сочетания из п элементов то m (число решений С) последовательность из п чисел, каждый член которой может принимать одно из m значений (число возможных решений mn) и т.д. Для каждой комбинации 7CGQ определена функция ф(я) в том смысле, что есть алгоритм вычисления функции ф(л) для любого 7teQ. Требуется определить комбинацию Tto Q, ДЛЯ которой ф(я) принимает максимальное или минимальное значение. Сложность решения задач дискретной оптимизации состоит в том, что число допустимых решений экспоненциально растет с ростом размерности задачи п. Поэтому простой перебор всех решений невозможен при больших п. В то же время, эти задачи относятся, как правило, к классу NP - трудных задач, для которых доказано, что не существует методов их точного решения, отличных от перебора.
Существует несколько схем решения задач дискретной оптимизации. Ниже дается их краткое описание [31].
Определим для каждого решения ти множество Р(7с) так называемых соседних решений (окрестность решения к). При заданной процедуре получения соседних решений алгоритм локальной оптимизации работает следующим образом [21]. Берем какое-либо решение тсо Рассматриваем окрестность Р(тс0) и в этой окрестности определяем наилучшее решение щ, такое что (имеется в виду задача минимизации). Если ф(тгі) ф(тго), то рассматриваем окрестность Р(тгі), определяем наилучшее решение щ и т.д. до тех пор пока не получим решение 7гк, такое, что Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. Можно поступить по-другому, расширив окрестность. Если лк — локально-оптимальное решение, то определяем окрестность следующим образом Другими словами, Р(лк) это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если пк остается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении. Достоинством методов локальной оптимизации является простота соответствующих алгоритмов. Недостатком схемы является отсутствие оценок близости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы. Пример 1.4.1.[21] На рис. 1.4.1 приведен сетевой график проекта из 4 работ, которым соответствуют вершины сети. В нижней половине вершин указаны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1. График использования ресурсов Заметим, что работы 1 и 3 критические, а работы 2 и 4 имеют полные резервы времени равные 4. Поэтому сдвигаем начало работы 2 на 3 единицы и выполняем ее в интервале (3, 7) тремя единицами ресурсов. При этом, естественно сдвигается работа 4 на 4 единицы. График использования ресурсов после локальной оптимизации на рис. 2.2 заштрихован. Пример 1.4.2 (задача о станках). [21] Требуется обработать п деталей. Каждая деталь проходит обработку на двух станках. Продолжительность обработки детали і на первом станке равна (Х( , а на втором b{ . Имеется всего один станок первого типа и достаточное количество станков второго типа. Требуется определить очередность обработки деталей, минимизирующую продолжительность обработки всех деталей. На рис. 1.4.3 приведен сетевой график из трех деталей. В нижней половине вершин указаны времена обработки. Возьмем произвольную очередность, например, 1,2,3 (очередность обработки указана пунктиром на рис. 1.4.3, критический путь выделен двойными дугами). Продолжительность обработки Т = 23. Естественно определить соседние решения, как решения, получаемые изменением очередности работ, лежащих на критическом пути. В нашем случае окрестность состоит из одного решения (2,1,3), рис. 1.4.4. Продолжительность обработки Т = 22 уменьшилось. Для нового решения имеем два соседних (1,2,3) и (2,3,1). Из них первое мы уже рассматривали. Для второго имеем Т = 20. Это решение, как легко показать, является локально оптимальным. Более того, можно показать, что для данной Обобщением метода локальной оптимизации являются так называемые генетические алгоритмы. В этих алгоритмах окрестность определяется не для одного решения, а для пары решений (родителей) и даже для нескольких решений. Из полученной окрестности отбираются наиболее перспективные «дети» и формируются новые пары (возможно с привлечение других решений) и т.д. Например, на основе перестановок (1,2,3,4) и (3,4,2,1) можно получить окрестность, беря очередность пары соседних элементов из первой перестановки, а очередность оставшейся пары — из второй, а потом наоборот, очередность пары соседних элементов из второй перестановки, а очередность другой пары из первой.
Модель формирования команды информационного проекта с минимальными затратами на оплату труда при заданной продолжительности выполнения работ
В процессе выполнения информационных проектов особенно остро стоит вопрос соблюдения сроков завершения проекта. Это связано в основном с современными достижениями в области коммуникаций, когда распространение информации осуществляется в предельно сжатые сроки, что приводит к снижению конкурентоспособности новых продуктов, так как информация о них очень быстро становится общедоступной, лишая предприятие -производитель конкурентных преимуществ, связанных с выведением на рынок нового продукта. Такая ситуация требует от предприятия постоянно иметь на подходе принципиально новую продукцию и успеть выставить ее на рынок раньше своих конкурентов. По оценкам специалистов, полугодовая задержка проекта в сфере разработки продукции высоких технологий, как правило, ведет к потере 33 % потенциального дохода. Скорость освоения новых рыночных ниш, скорость вывода новой продукции на рынок - все это в современных условиях становится конкурентным преимуществом. В связи с этим возникает задача формирования такой команды исполнителей проекта, которая бы осуществила выполнение всех работ в заданные сроки, и при этом затраты на оплату труда были минимальны.
Рассмотри эту задачу в наиболее общем виде, считая, что предприятие имеет для реализации информационного проекта ограниченное число специалистов различной квалификации. Обозначим через я,заработную платуго специалиста, а через Ъг индивидуальную производительность. Введем двоичную переменную хп которая принимает только два значения 0 или 1. х{ = 1 в том случае если i-ый специалист принимает участие в реализации проекта и Л:, = 0 в противном случае. Тогда задача формирования команды проекта обеспечивающей выполнение проекта в заданные сроки с минимальной стоимостью будет описываться следующей целевой функцией и ограничениями: В данном случае величина Р определяется как минимально необходимая производительность труда для выполнения проекта в заданные сроки, то есть Р = —, где Q - трудоемкость выполняемого проекта, Т— строки выполнения. Таким образом, задача (2.2.1) - (2.2.2) представляет собой классическую задачу о «ранце», решение которой может быть осуществлено с помощью метода ветвей и границ [39]. Рассмотрим пример, данные по которому приведены в табл. (2.1.1). В этом случае целевая функция задачи будет иметь вид: Решая серию задач линейного программирования, приходим к решению вида То есть в качестве исполнителей выгодно выбрать специалистов третьей и четвертой квалификационных групп. В этом случае суммарная производительность будет 9,8 при величине затрат 57 тыс. р., то есть будет иметься некий, правда небольшой, запас производительности, обеспечивающий резерв, а величина затрат будет минимальна.
Для данной задачи можно сформулировать эвристическое правило, аналогичное правилу 2.1.1.
Эвристическое правило 2.2.1. Первоначально принять в качестве команды проекта весь наличный состав специалистов, вычислить общую производительность и затраты. Затем убирать из команды проекта по одному специалисту, имеющему самую низкую удельную производительность, каждый раз пересчитывая производительность и затраты, то есть вычитая из суммарной производительности производительность удаляемого специалиста, а из затрат его заработную плату. Продолжать до тех пор, пока суммарная производительность не будет равна минимально необходимой производительности труда, необходимой для выполнения проекта в заданные сроки. Полученное решение будет соответствовать минимальному уровню затрат при заданной продолжительности выполнения работ.
Из приведенных решений видно, что не всегда полученное оптимальное решение будет выгодным с точки зрения использования специалистов. Очевидно, необходимо рассмотреть постановку задачи, когда к экстремуму будет стремиться некий удельный показатель характеризующий качество работы специалистов. В качестве такого показателя удобно рассмотреть удельную производительность на единицу денежных средств, затраченных на оплату труда специалистов, работающих над проектом. В этом случае целевая функция задачи будет иметь следующий вид
Определение рационального совмещения работ при минимизации стоимости выполнении информационного проекта
Переходим к рассмотрению задачи, когда совмещение работ (i,j) приводит к росту стоимости работы j (например, увеличение времени компенсируется увеличением затрат). Обозначим через ср. (к ) в данном случае увеличение стоимости работы j, зависимости от коэффициента совмещения Kjj. Задача заключается в определении коэффициентов совмещения работ сетевого графика так чтобы проект был выполнен за время не более Т, а суммарный рост стоимости проекта был минимален. Рассмотрим сначала случай последовательной цепочки работ. Рис. 3.2.10. Если Г т, Т, то необходимо совмещение ряда работ для того, чтобы І=І продолжительность проекта была не более Т. Рассмотрим линейный случай, когда 8.(Kj) = а ,, то есть рост стоимости работы і прямопропорционален коэффициенту совмещения К;. Очевидно, что в первую очередь следует совмещать работы с минимальными a-f Пример 3.2.1.[36]. Рассмотрим сетевой график рис. 3.2.10. Пусть Т=10. 1 шаг. Минимальную величину а, имеет работа 3 (а3=5). Поэтому начинаем ее в момент t3=l, К3=1. Момент окончания работы 3 равен t3=l+4+5=10. 2 шаг. Совмещаем работу 2 с работой 1, то есть начинаем работу 2 в момент t2=3. Коэффициент совмещения равен К,2 = —, а увеличение стоимости составит Д2 =К,2 -а2 =2. Окончательно получаем, что моменты начала работ один t" = 0 работы 2 t2 = 3 и работы 3 t3 = 1. Моменты окончания работ соответственно, t, =5, t2 =t3 =10, а увеличение стоимости проекта составит AS = 5 + 2 = 7. Замечание.
В основе алгоритма лежит предположение, что в последующем работа не заканчивается раньше, чем предыдущая, то есть t; t.+1, i = l,m. В противном случае описанный алгоритм может не дать оптимального решения. Однако, данное предположение представляется вполне обоснованным, так как все работы, следующие за работой (і+1) в определенной степени зависят от работ, предшествующих работе і. Фактически мы имеем дело с зависимостями типа «финиш-финиш» (работа не может быть закончена, пока не закончена другая работа). С учетом сделанного замечания дадим обобщение алгоритма на случай произвольного сетевого графика. По сути дела задача минимизации стоимости проекта при сокращении его продолжительности за счет совмещения работ эквивалентна задаче минимизации стоимости проекта при уменьшении его продолжительности за счет уменьшения продолжительности работ [17]. Поэтому мы не будет давать подробного описания алгоритма, а ограничимся его иллюстрацией на примере. Рис. 3.2.2. сетевой график к примеру 3.2.2. 1 шаг. Полагаем, что все зависимости учитываются и определяем критические пути в сетевом графике. В нашем примере это один путь (1,4) длины Ti=17. Единственная возможность сократить продолжительность проекта заключается в совмещении работ 1 и 4. Уменьшаем момент начала работы 4 на 3 единицы. Рост затрат равен ASj = 3 5 = 15. 2 шаг.
В сети появляется еще один критический путь (1, 3, 5) рис. 3.2.3. В данном случае для уменьшения продолжительности проекта самое выгодное совмещать работу 4 с работой 1 и работу 5 с работой 3. Уменьшаем момент начала работы 4 на 2 единицы и момент начала работы 5 также на две единицы. Рост затрат составит AS2 = 2(5 + 2) = 14. З шаг. В сети появляется еще один критический путь рис. 3.2.4. Результат 3 шага. Единственная возможность уменьшения продолжительности проекта связаны с совмещением работы 4 с работой 1, работа 3 с работой 1 и работа 5 с работой 2 на две единицы. Рост затрат при этом составит График зависимости величины дополнительных затрат от продолжительности проекта приведен на рис. 3.2.5.
Определение степени совмещения работ в проекте
Обозначим коэффициент совмещения между работами (1 - 2) и (3 - 4) через Кь между работами (3 - 4) и (5 - 6) через - К2 между работами (5 - 6) и (7 - 8) Кз и между работами (7 - 8) и (9 - 10) - К4.
Из практики известно, что коэффициенты совмещения, как правило, определяются с точностью до 10 процентов, в связи с этим получим данные о величине возможного сокращения продолжительности выполнения работ за счет их совместного выполнения для различных значений коэффициента со вмещения, а также о дополнительных затратах, соответствующих такому сокращению. Соответствующие данные представлены в табл. 4.3.1. Таблица При этом значение коэффициента К3 не может превышать 0,7, так как продолжительность выполнения предыдущей работы меньше чем рассматриваемой и этому значению будет примерно соответствовать одновременное начало работ (5 - 8) и (7 - 8).
Решение начинаем с последнего шага, то есть определим коэффициент совмещения между последней и предпоследней работы (по рис. 4.3.2 это работы (7 - 8) и (9 - 10)). На этом шаге возможно максимальное сокращение продолжительности на 2, 3, 4, 5 и 6 дней. Выбираем соответствующие продолжительности с минимальными дополнительными затратами. Результаты представлены в табл. 4.3.2.
При совмещении работ (5 - 6) и (7 - 8) уменьшение продолжительности выполнения работ возможно на 2, 3, 4, 5, 6 и 7 дней. Таким образом, об щее сокращение продолжительности возможно на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 и 13. Рассмотрим возможные варианты сокращения продолжительности проекта при выполнении двух последних работ. На каждом шаге будем решать элементарную задачу оптимизации: из нескольких возможных вариантов выбираются вариант с наименьшими затратами. Данные представлены в табл. 4.3.3.
На следующем шаге рассматриваем совмещение работ (3 - 4) и (5 - 6). При этом возможно сокращение продолжительности на 1, 2, 3, 4, 5 и 6 дней. При этом общая продолжительность анализируемого комплекса работ может быть сокращена на 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 и 19 дней.
Задаваясь необходимым уровнем сокращения сроков выполнения проекта, по табл. 4.3.5 находим необходимые значения коэффициентов совмещения. Например, общую продолжительность выполнения работ по проекту необходимо сократить на 22 дня. По табл. 4.3.5 находим, что для этого необходимы дополнительные затраты в объеме 8 тыс. р. При этом степень совмещения работ (1 - 2) и (3 - 4) должна определяться коэффициентом Кх = 0,4, а степень совмещения остальных работ должна обеспечить сокращение сроков выполнения проекта на 13 дней. Для определения коэффициентов совмещения других работ используются данные табл. 4.3.4 в которой находим строку соответствующую 13 дням. Этому соответствуют коэффициенты совмещения Кг = 0,2, при этом сокращение продолжительности за счет оставшихся работ должно при этом составлять 9 дней. Используя данные табл. 4.3.3 находим комбинацию коэффициентов совмещения обеспечивающую сокращение сроков выполнения проекта на 9 дней для этого необходимо чтобы коэффициенты совмещения были равны К3 = 0,3, К4 = 0,3.
Анализируя данные табл. 4.3.5 приходим к заключению, что максимально возможное сокращение сроков выполнения проекта в данном случае возможно только на 28 дней, затраты при этом составят 18 тыс. р. Если же уменьшить продолжительность только на 18 ед., то этому будут соответствовать затраты в размере 4 тыс. р. Уменьшению продолжительности на 13, 14, 15 и 16 дней соответствуют одинаковые затраты в размере 3 ед., то есть экономически выгодно выполнить сокращение сроков на 16 дней, так как это будет соответствовать такому же объему дополнительных затрат, что и при сокращении сроков на 13 дней.
Возникает вопрос, о том, что же делать, если необходимо сократить продолжительность выполнения работ по проекту необходимо более чем на 28 дней. В этом случае необходимо увеличить число исполнителей по проекту, так как согласно приведенного расчета возможности сокращения общей продолжительности реализации проекта за счет организации совмещенного выполнения работ полностью исчерпаны.
В результате анализа особенностей информационных проектов было установлено, что процесс планирования работ по выполнению информационных проектов имеет высокую степень неопределенности, объясняемую отсутствием нормативной базы единичных норм и расценок и трудностью формализации единичного объема работы. Это приводит к появлению на этапе проектирования весьма приблизительных оценок об объемах предстоящих работ, а, следовательно, и сроках выполнения работ по проекту.
С другой стороны процесс реализации информационного проекта состоит из относительно небольшого числа типовых этапов (4 — 5 этапов) с ярко выраженным преобладанием одного этапа (технический проект составляет примерно 60 % от объемов работ по всему проекту). При этом выполнение проекта требует участия очень квалифицированных специалистов, но ограниченной номенклатуры. Состав затрат по проекту характеризуется основным преобладанием затрат на оплату труда. Причем основная часть затрат приходится на этап создания технического проекта.
Высокая степень неопределенности по проекту вынуждает держать дополнительных специалистов, способных включиться в реализацию проекта с целью компенсации накопившегося отставания от графика проведения работ, а так как основные затраты связаны с оплатой труда, то такое резервирование трудовых ресурсов высокой квалификации способствует существенному удорожанию проекта в целом.
