Разновидности задачи сетевого планирования, некоторые методы их решения и алгоритмические оценки

Abstract

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