Программные продукты и системы

Учитывая особенности разработки изделий в электронной промышленности, построим модель планирования работ.

Пусть требуется реализовать некий проект, по которому необходимо выполнить n работ, распределяемых по m исполнителям. Исполнители – это не только отделы (разработки, тестирования, разработки ПО), но и группы в рамках этих отделов, которые могут самостоятельно выполнять отдельные работы по проекту. Таким образом, будем считать, что каждая работа может быть выполнена одним из нескольких исполнителей.

Обозначим через wj множество работ, которые может выполнить j-й исполнитель. Также введем матрицу W={wij}iÎ1,…,n, j=1,…,m, где wij=1, если i-я работа может быть выполнена j-м исполнителем; wij=0 в противном случае.

Ясно, что при этом должно выполняться условие " jÎ1, …, n, . Пусть aj – начальная, а wj – конечная работа для j-го исполнителя (где jÎ1, …, m; aj, wjÎ1, …, n). Часто такие работы очевидны, в редких случаях их можно ввести во множество работ искусственно, присвоив нулевую длительность и нулевую потребность в ресурсах.

Необходимо учитывать и стоимость одного интервала времени работы исполнителя – sj (сюда следует отнести расходы на оплату труда сотрудников, рабочее место, амортизацию используемого оборудования и т.д.).

Исполнитель может приступить к работам по планируемому проекту только с определенного момента (например, завершив работы по предыдущему проекту). Учтем это, введя параметр . Здесь  – время начала работ j-го исполнителя; T – количество интервалов времени, на которые можно назначать выполнение различных заданий (в зависимости от требуемой точности планирования можно использовать дневные, недельные, месячные интервалы). Значением Т зададим время, отпущенное на выполнение проекта.

Следовательно, каждый исполнитель будет описываться кортежем J=, sj>, работы, производимые исполнителями, – временем ti и стоимостью ci. Получаемые зависимости легко обобщить для рассмотрения дополнительных ресурсов (таких как арендуемое оборудование или ПО, услуги сторонних организаций и т.д.). Каждую работу будем описывать кортежем I=.

На множестве работ задан нестрогий порядок: некоторые работы могут быть начаты лишь после завершения одной или нескольких предыдущих работ. Зададим его с помощью матрицы Q размером n×n элементов: Q={qik}i,kÎ1,…,n, где qik=1, если перед началом k-й работы должна быть завершена i-я работа; qik=0, если начало k-й работы не связано с результатами i-й.

Очевидно, для j-го исполнителя начальная работа aj не должна зависеть от выполнения других работ этим исполнителем, а конечная работа wj, наоборот, может быть начата только после завершения всех работ этим исполнителем. Порядок, задаваемый матрицей Q, в данном случае должен быть транзитивным, а именно: если  и , то . Иными словами, в качестве условия начала k-й работы должны быть перечислены все работы, на результат которых она полагается (а не только одна, непосредственно предшествующая), что обеспечит более гибкое планирование. Важно, что k-я и i-я работы, для которых qik=1, могут выполняться совершенно разными исполнителями.

Составим модель планирования в виде задачи целочисленного программирования. Для этого введем бинарные переменные , равные 1, если j-й исполнитель сразу после i-й работы выполнит k-ю (i, kÎ1, …, n, jÎ1, …, m), или 0 во всех остальных случаях. Также введем целочисленные переменные Hi, обозначающие время начала i-й работы (HiÎ1, …, T, jÎ1, …, m). Связь между этими переменными будет установлена в ограничениях модели. Вычислив по предлагаемой далее модели значения переменных и Hi, получим все необходимые сведения о порядке выполнения работ исполнителями и о времени их начала и окончания.

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

Итак, следует максимизировать разницу между доходами и расходами:

   (1)

с ограничениями

,                            (2)

,     (3)

                  (4)

         (5)

(6)

                               (7)

                        (8)

                        (9)

               (10)

                                                            (11)

HiÎ1, …, T.                                                           (12)

Ограничение (2) гарантирует, что затраты на получаемый план будут меньше дохода. Ограничения (3)–(6) обеспечивают связность потока работ для каждого исполнителя. Ограничения (3) требуют, чтобы после каждой работы, кроме последней, у исполнителя имелась только одна работа. Ограничения (4) и (5) обеспечивают отсутствие работ после последней и перед первой работами; (6) устанавливает, что каждая работа должна иметь исполнителя (кроме начальных работ, так как этот случай уже покрыт ограничением (4)).

Ограничение (7) устанавливает, что первая работа j-го исполнителя начинается не раньше, чем он освободится; (8) требует завершения работы не позже установленного срока.

По ограничению (9) следующая работа должна начаться не ранее, чем закончится предыдущая. Это неравенство представляет собой реализацию отношения следовательно: если , оно превращается в Hk³Hi+ti, а при  выполняется автоматически.

Ограничение (10) гарантирует выполнение любой работы только после завершения всех работ, от результатов которых она зависит.

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

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

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

Пусть после разработки изделия будет также подготовлено Nb блоков. Создание b-го блока (bÎ1, …, Nb) имеет стоимость rb (при затруднениях в определении стоимости можно использовать трудоемкость в человеко-часах на создание этого модуля как отдельного проекта).

Предположим, что в будущем планируется работа по ряду дополнительных проектов, которые могут использовать наработанные в данном проекте библиотечные блоки. Просматривается NV проектов. Доход от реализации v-го проекта (vÎ1, …, NV) примерно оценивается величиной Sv, себестоимость – Rv, а вероятность получения заказа на его реализацию – числом pv (pvÎ[0, 1], оценку может проводить ЛПР самостоятельно или на основе экспертной оценки).

Использование в будущем v-м проектом библиотечных элементов, разработанных в рамках реализуемого в данный момент проекта, обозначим вектором , , где uvb=1, если v-й проект использует b-й библиотечный элемент, uvb=0 в противном случае (bÎ1, …, Nb).

Итак, возможный проект описывается кортежем V=>.

Будем считать получение заказа на v-й проект не зависящим от получения заказа на любой из остальных Nv–1 проектов.

Оценим прибыль от реализации проекта. Создание b-го библиотечного блока, используемого в v-м проекте, позволит уменьшить его себестоимость на величину rb/Rv. Сокращение себестоимости можно оценивать как пропорциональный вклад в прибыль предприятия размером (Sv–Rv)/Rv´rb. Общую полезность всех библиотечных блоков для v-го проекта можно вычислить формулой  или в векторной форме: , где ;  – скалярное произведение векторов. Возможна также оценка полезности, идущая не от вклада в доход, а от уменьшения расходов, в этом случае коэффициент (Sv–Rv)/Rv следует убрать.

Кроме того, необходимо учесть неопределенность получения заказов. Используем для этого математическое ожидание получаемой суммы. По условию, с вероятностью pv будет получен доход Sv или с вероятностью 1–pv доход 0, следовательно, математическое ожидание получаемой суммы можно рассчитать по формуле . Учитывая принятую выше независимость проектов, перепишем целевую функцию (1) в виде

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

Итак, получена задача целочисленного программирования с линейной целевой функцией и нелинейными ограничениями (нелинейным является только ограничение (9)). Обзор методов решения таких задач можно найти в [1, 2]. Разрабатываются современные алгоритмы, использующие возможности многопроцессорных систем [3], в том числе высокоскоростные векторные вычислители, устанавливаемые на видеокартах.

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

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

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

Литература

1. Laurence A. Wolsey and George L. Nemhauser, Integer and Combinatorial Optimization. Wiley-Interscience, 1 edition, November, 1999.

2. Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т.; [пер. с англ.].  М.: Мир, 1991. 360 с.

3. Hirayama K., Yokoo M. The distributed breakout algorithms // Artificial Intelligence, 2005, Vol. 161, pp. 89–115.