Задача комбинаторной оптимизации

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

Мероприятия, составляющие проект, задаются множеством . Мероприятие представляет начало графика, а мероприятие ‑ окончание графика. Множество нефиктивных мероприятий обозначено .

Продолжительности представлены вектором в , причем ‑ это продолжительность мероприятия , а .

Отношения предшествования задаются множеством пар таких, что означает, что мероприятие предшествует мероприятию . Строится орграф предшествования «мероприятие-вершина» , в котором вершины соответствуют мероприятиям, а дуги соответствуют отношению предшествования. При этом предполагается, что орграф бесконтурный, иначе отношение предшествования было бы несовместным. Возобновимые ресурсы заданы множеством .

Наличие ресурсов представлено вектором в , причем задает наличие ресурса . Ресурс , для которого , называется унарным или дизъюнктивным ресурсом. В противном случае, если ресурс может использоваться одновременно несколькими мероприятиями, он называется кумулятивным ресурсом.

Потребности мероприятий в ресурсах заданы (n+2)×q –мерной целочисленной матрицей , причем ‑ количество ресурса , используемого в каждый период времени в течение выполнения мероприятия .

Графиком проекта называется точка в , где ‑ время начала выполнения мероприятия . ‑ время завершения мероприятия , причем . ‑ начало проекта. Здесь предполагаем, что . Решение допустимо, если оно удовлетворяет ограничениям предшествования (9.19) и ограничениям по ресурсам (9.20), записанным ниже, причем представляет множество нефиктивных мероприятий в процессе в период .

(9.19)

(9.20)

Время выполнения проекта равно ‑ времени окончания проекта.

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

Определение 9.1. ЗКППОР – это задача поиска графика без преимущества с минимальным временем выполнения , удовлетворяющего ограничениям предшествования(9.19) и ограничениям по ресурсам (9.20).