Научный архив: статьи

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

Планирование является одним из важных процессов для проекта. К основным процессам планирования относятся определение работ, планирование ресурсов, определение продолжительности работ, разработка расписания. В статье рассматриваются проекты с независимыми работами. Целью исследования является оптимизация графика выполнения работ по периодам. Рассмотрены три частные задачи. Первая задача состоит в распределении работ по периодам таким образом, чтобы достичь максимального суммарного эффекта от их реализации с учетом ограничения затрат в каждом периоде и возможности частичного выполнения работ в данном периоде. Алгоритм решения основан на методе «Затраты - эффект». Доказана обоснованность предложенного алгоритма. Во второй задаче рассматривается распределение работ по периодам при запрете переноса части работ в другие периоды и ограничении затрат в каждом периоде. На основе метода дихотомического программирования предложен алгоритм решения задачи для двух периодов. Для количества периодов больше двух предложен приближенный алгоритм. Для случая, когда информация о невыполненных работах в ходе реализации проекта изменяется, рассмотрена задача максимизации суммарного эффекта от реализации работ проекта в текущем периоде. Причем эффект от реализации множества работ появляется после их завершения и определенный эффект появляется от частичной реализации другого множества работ. При этом получаемый эффект пропорционален части выполненного объема работ. Предложен алгоритм решения задачи, основанный на получении параметрических зависимостей суммарного эффекта для каждого множества работ от величины затрат. Доказана обоснованность алгоритма. Приведены примеры, иллюстрирующие применение предложенных алгоритмов.