Модели и методы решения задач оптимизации выполнения комплекса работ с учетом ограничений по ресурсам
При формировании оптимального (рационального) варианта расписания выполнения работ с учетом ресурсов, распределенных во времени, в качестве критерия оптимальности могут быть выбраны следующие:
1. Минимизация общего времени выполнения всего комплекса работ при соблюдении ограничений на ресурсы.
2. Максимизация загрузки ресурсов.
3. Равномерность загрузки (использования) ресурсов.
4. Минимизация потребления ресурсов при соблюдении директивного срока выполнения всего комплекса работ.
5. Непрерывность использования ресурсов.
6. Минимизация отклонений от заданных сроков наступления целевых событий при соблюдении ограничений на ресурсы.
7. Минимизация дополнительных или простаивающих (пролеживающих) ресурсов при соблюдении директивного срока выполнения всего комплекса работ и др.
Решение данной задачи требует учета в каждый момент времени достаточности объемов ресурсов различных видов. В качестве таких ресурсов могут выступать трудовые ресурсы - численность сотрудников (работников) в структурных подразделениях организации (предприятия), выполняющих определенные работы; финансовые ресурсы; материальные и другие виды ресурсов.
Дадим краткую постановку задачи формирования расписания выполнения комплекса работ, заданного сетевым графиком, с учетом ограничений по ресурсам, распределенным во времени (то есть нескладируемые ресурсы).
Пусть для выполнения каждой (i-j)-й работы некоторого комплекса, представленного сетевым графиком (например, см. рисунок 8.14), требуется Pijs единиц ресурса s-го вида. Известно, что в каждый k-й момент времени (Tk) суммарный расход ресурса не может превысить некоторой заданной величины Sk (располагаемый фонд ресурса s-го вида в k-й момент времени), то есть
(8.4.18)
В рассматриваемом примере (для одноресурсной модели) располагаемый фонд ресурса (трудовые ресурсы - число специалистов) является величиной постоянной в течение всего планового периода времени, то есть
(8.4.19)
Все работы рассматриваемого комплекса выполняются непрерывно (не допускается прерывать выполнение уже начатой работы) и обладают одинаковым приоритетом, то есть на процесс выполнения работ, для которых уже выполнены предшествующие им работы (на момент времени их начала Tнач.ij и окончания Tок.ij), никаких ограничений не накладывается.
Необходимо сформировать оптимальный (рациональный) вариант расписания выполнения работ рассматриваемого комплекса (обеспечивающее минимальное время выполнения всего комплекса работ T ® min) и график загрузки (использования) ресурсов (для нашего примера соответственно рисунок 8.19 и рисунок 8.20).
 |
Рисунок 8.19 - Расписание выполнения комплекса работ
Рисунок 8.20 - График загрузки (использования) ресурсов
Потребность в ресурсах для выполнения работ рассматриваемого комплекса и ежедневно располагаемый фонд ресурса представлены в таблице 8.7.
Возможна постановка обратной задачи.
Пусть для выполнения каждой (i-j)-й работы некоторого комплекса, представленного сетевым графиком, требуется Pijs единиц ресурса s-го вида. Весь комплекс работ необходимо завершить к моменту времени T.
Необходимо сформировать оптимальный (рациональный) вариант расписания выполнения работ рассматриваемого комплекса и график загрузки ресурсов, обеспечивающие минимальный объем ресурсов, требуемый для выполнения всего комплекса работ в установленный срок. Для одноресурсной модели критерий оптимальности можно математически выразить следующим образаом:
(8.4.20)
Для одноресурсной модели может быть использован также и другой критерий - обеспечение наиболее равномерного потребления ресурсов в течение всего планового периода. Хотя критерий равномерности необязателен, например, в строительстве используется параболическая загрузка ресурсов. Таким образом, в общем случае потребление ресурсов в течение планового периода может быть задано некоторой функцией от времени и необходимо обеспечить минимальное суммарное отклонение от заданной функции использования ресурсов во времени.
Необходимо отметить, что приведенные постановки задач распределения ресурсов можно усложнять в зависимости от реальной ситуации и целей планирования. Например, разрешая прерывать выполнение уже начатой работы или устанавливая приоритетность работ, в том числе обусловленную использованием дефицитного вида ресурса. Очевидно, что для многоресурсных моделей постановка и поиск решения задачи значительно усложняются по сравнению с одноресурсными.
Фрагмент экономико-математической модели для рассматриваемой прямой постановки задачи представлен ниже:
(8.4.21)
Рассматриваемая задача является многовариантной оптимизационной. Оптимальное решение можно найти путем полного перебора всех вариантов или используя специальные точные экономико-математические методы (математического программирования), но для реальных производственных условий, а следовательно, задач реальной размерности эти методы, даже при использовании современной вычислительной техники, малопригодны.
Отметим, что в ряде частных случаев удается свести рассматриваемую задачу к виду, достаточно простому для ее решения, методами линейного программирования, а поскольку в настоящее время создан весьма мощный аппарат линейного программирования, то на современной вычислительной технике решение таких задач (большой и сверхбольшой размерности) не составляет особого труда.
Для решения поставленной задачи чаще всего используются эвристические методы, в частности, методы, основанные на выборе и реализации эвристических правил (правил предпочтения).
В общем случае нет универсальных эвристических правил, пригодных для решения всех задач рассматриваемого класса для различных критериев оптимальности и ограничительных условий, учитывающих все многообразие (различие) производственных условий. В каждой конкретной задаче для получения рационального расписания выполнения работ некоторого комплекса в соответствии с выбранными критерием оптимальности и ограничительными условиями может быть использовано одно или несколько (совокупность) эвристических правил.
Совокупность эвристических правил формируется для того, чтобы в любой момент времени (при наличии минимально необходимого - достаточного количества ресурсов) можно было выбрать хотя бы одну работу из множества работ {Ak}, ожидающих выполнения в k-й момент времени, и выбор был однозначным. Поэтому, как правило, последним в совокупности правил предпочтения используется выбор по минимальному коду работы.
Обычно все эвристические правила делят на две группы:
правила, зависящие лишь от работ, участвующих в конфликтной ситуации (работы, которые могут быть назначены для выполнения в данный момент времени);
правила, зависящие не только от работ, участвующих в конфликтной ситуации, но и от работ, которые должны быть выполнены в дальнейшем.
Можно предложить некоторые из наиболее употребительных правил предпочтения (выбора, назначения) работ (i-j).
1. Правило наиболее трудоемкой работы 
:
(8.4.22)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается (i-j)-я работа, которая имеет максимальную трудоемкость и для выполнения которой требуются ресурсы (Pijsk) в объеме не более оставшегося (Sост.k) в рассматриваемый момент времени после включения других работ.
2. Правило наименее трудоемкой работы:
(8.4.23)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается та, которая имеет минимальную трудоемкость.
3. Правило наибольшей суммарной загрузки ресурса:
(8.4.24)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается такая совокупность работ {By}, которая максимально дозагружает свободный ресурс Sk в k-й момент времени Tk.
4. Правило наибольшей потребности в ресурсе:
(8.4.25)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается та, для выполнения которой требуется максимальное количество ресурса.
5. Правило наименьшей потребности в ресурсе:
(8.4.26)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается та, для выполнения которой требуется минимальное количество ресурса.
6. Правила минимального резерва времени:
6.1. 
(8.4.27)
6.2. 
(8.4.28)
6.3. 
(8.4.29)
В соответствии с этими правилами из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается та, которая обладает минимальным резервом времени соответственно или полным (общим), или частным первого вида, или частным второго вида.
7. Правило критической работы:
(8.4.30)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается работа критического пути.
8. Правило минимального кода работы:
(8.4.31)
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени, выбирается та, которая имеет минимальный код работы.
9. Правило наибольшего доступа.
В соответствии с этим правилом из множества работ {Ak}, ожидающих выполнения в k-й момент времени (Tk), выбирается та, завершение выполнения которой в момент времени Tk+Tij дает возможность приступить к выполнению наибольшего числа работ непосредственно следующих за данной (или всех работ, следующих за данной).
10. Правило случайного назначения работ.
11. Рандомизированные (комбинированные) правила предпочтения и другие правила.
В рассматриваемом примере (см. таблицу 8.7, таблицу 8.8) для формирования оптимального (рационального) варианта расписания выполнения комплекса работ, заданного сетевым графиком (см. рисунок 8.14), с учетом ограничений по ресурсам, распределенным во времени (то есть нескладируемые ресурсы), выбрана следующая совокупность эвристических правил предпочтения:
1. Правило наибольшего доступа.
2. Правило критической работы.
3. Правило наиболее трудоемкой работы.
4. Правило минимального кода работы.
Расписание выполнения комплекса работ и график загрузки ресурсов, построенные с использованием данной совокупности эвристических правил предпочтения для рассматриваемого примера, представлены соответственно на рисунке 8.19 и рисунке 8.20.
Для рассматриваемого примера получено оптимальное решение (24 дня), так как общее время выполнения комплекса работ лишь на 3 дня больше длины критического пути, а в эти 3 дня выполняется работа “1-4” (работа “Б”), которая не может быть запараллелена (выполняться одновременно) с работами критического пути ввиду ограничения по ресурсам:
(8.4.32)
Поскольку при использовании различных совокупностей (наборов) правил или отдельных правил предпочтения получаются неравнозначные с точки зрения выбранного критерия расписания выполнения комплекса работ и графики загрузки ресурсов, то применительно к конкретным производственным условиям необходимо оценить эффективность тех или иных правил предпочтения, то есть выяснить близость полученных расписаний и графиков к оптимальному варианту.
При оценке эффективности правил предпочтения можно воспользоваться, например, следующими методами:
1. Решение тестовых задач. В качестве тестовых выбираются задачи, достаточно близкие к данным производственным условиям и решенные каким-либо точным методом.
Недостатком этого метода является то, что задачи, решаемые точными методами, имеют небольшую размерность, и количество этих задач невелико. Поэтому выбор правил предпочтения может оказаться недостаточно обоснованным.
2. Метод сравнения экспериментов. Он основан на моделировании конкретных производственных условий и позволяет определить в соответствии с выбранным критерием наилучшее правило или совокупность правил предпочтения (имитационный метод).