Общая постановка задачи. Задача оптимизации графика работ при ограниченном суммарном расходе однородного ресурса формулируется следующим образом: определить сроки выполнения работ и

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

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

В качестве ограниченных ресурсов может выступать также и доступный объём инвестиционных ресурсов на инвестиционной фазе реализации проекта.

В общем виде задача формулируется следующим образом:

Найти q_ij≥0, t_ij≥0 для всех (i,j)ÎQ, обеспечивающие

(11.1),

при ограничениях

(11.2),

(11.3).

где Q - множество работ (i,j) сетевой модели рассматриваемого проекта;

t(i,j) - длительность работы (i,j);

q(i,j) - задержка начала выполнения работы (i,j);

Res - допустимая суммарная интенсивность расхода ресурса;

V_k - множество работ, одно временно выполняемых на k-м интервале времени, k=1,2 …, r;

r - число интервалов, на которые делится время выполнения проекта при условии, что в течение каждого интервала состав одновременно выполняемых работ постоянен;

a_ij, b_ij - допустимые уровни расхода ресурса на операции (i,j).

Введение задержек изменяет срок окончания операций, что должно учитываться при расчете временных параметров.

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

В зависимости от вида ограничений (11.3) возможны три модификации постановки задачи:

с фиксированными расходами ресурсов и длительностями работ. В этом случае ограничения (11.3) отсутствуют;

с расходами ресурсов, зависящими от длительности операции, но неизменными в процессе её выполнения. Здесь ограничения (11.3) сохраняет свой вид;

с расходами ресурсов, изменяющимися от длительности операции и в процессе её выполнения. При этом в ограничении (11.3) становится не только функцией длительности t_ij, но и текущего времени 0<=t<=t_ij.

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

Вторая постановка включает задачи, например, распределения оборудования по стадиям производственного цикла.

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

Процесс решения состоит из следующих этапов:

1. построение исходного графика работ;

2. получение допустимого или опорного планов;

3. улучшение опорного плана.

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

Вид постановки задачи определяет метод поиска опорного и оптимального решений и возможность формализации этого процесса.

Методы решения в основном отличаются используемыми способами регулирования суммарного расхода ресурсов.

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

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