Информационные системы и технологии УДК 004.02.021 А.С. ДОБРЫНИН, Р.С. КОЙНОВ АЛГОРИТМИЗАЦИЯ ПОСТРОЕНИЯ РАСПИСАНИЙ, УЧИТЫВАЮЩИХ ВРЕМЕННЫЕ ОГРАНИЧЕНИЯ Задачи построения расписаний (JSSP) в различных сферах человеческой деятельности имеют важнейшее теоретическое и прикладное значение. <...> Во многих из них присутствуют специфические временные ограничения, описывающие допустимые для планирования отрезки времени и периоды простоев на интервале планирования. <...> Статья описывает алгоритм распределения работ в условиях временных ограничений для задач построения производственных и учебных расписаний, а также сервисной деятельности. <...> ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ МОДЕЛИ Базовая задача построения производственных расписаний [1] для непрерывного времени формализуется как задача на графах, в которой узлы представляют собой события, дуги – отдельные процессы или работы. <...> С каждой дугой ассоциирован двухкомпонентный вес, представленный вещественным числом и временной разницей c возможностью их взаимного отождествления. <...> Этапы решения базовой задачи [1] реализованы в рамках модельно-алгоритмического комплекса (МАК) [2] и дают неплохие результаты на практике. <...> Особый интерес представляет задача, в которой необходимо учитывать ограничения, связанные с невозможностью выполнять работы в определенные отрезки времени. <...> Рассмотрим элементы математической модели для достаточно общего случая, предполагая, что на периодических интервалах времени tt структура ограничений одинакова. <...> Одним из компонентов математической модели объекта планирования, используемой для построения расписаний в ограничениях, является вектор кортежей работ W , полученный в ходе решения задачи [1], где каждая отдельная запись представляет собой параметры отдельной работы, такие, как: идентификатор работы (ID), дата начала (beginDate), дата раннего окончания (earlyEndDate), дата позднего окончания (lastEndDate), компонент временного смещения (offsetDate). w ID beginDate earlyEndDate <...>