Формирование расписаний в задачах временного планирования

Важнейшим условием составления расписаний в проектной деятельности является учет множества временных ограничений, которые привязаны к периодическим интервалам времени проведения работ. В классических постановках задач класса JSSP (Job Shop Scheduling Problem) не уделяется должное внимание периодическим интервалам времени графиков работ большинства организаций и предприятий. Постановка и решение задачи планирования, предлагаемые нами, предполагают введение минимального отрезка времени, что позволяет гибко описывать структуру периодических временных ограничений. Рассматривается алгоритм временного сдвига, используемый для получения точного расписания в условиях периодических временных интервалов. Решение задачи подразумевает два этапа: на первом осуществляется построение непрерывного расписания (диаграмма Ганта), на втором происходит его последующая корректировка с учетом периодических временных ограничений произвольной формы. На втором этапе используется описанный алгоритм сдвига, вычислительная сложность которого зависит от минимального интервала времени и его размерности (длительности проекта). Апробация алгоритма в рамках модельно-алгоритмического комплекса на графах показывает несущественный рост сложности вычислений при значительном увеличении объема исходных данных. Таким образом, данный алгоритм имеет перспективы применения в крупных промышленных системах составления расписаний. Рассматриваемая задача планирования работ актуальна для предприятий и организаций, участвующих в разработке и внедрении проектов, поставщиков ИТ-услуг и т. д. Представленные механизмы и методики могут использоваться при разработке подсистем планирования в различных отраслях науки и техники (производство, транспорт, проектно-процессная деятельность).