Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 10/2018(9))

- сетевое планирование или построение расписания для проекта, Project scheduling (PS); - календарное планирование или построение расписания для приборов, Machine scheduling (MS); - составление временных таблиц (Time Tabling); - доставка товаров в магазины (Shop-Floor Scheduling); - составление расписаний движения транспортных средств (Transport Scheduling); - циклические расписания для транспортных средств (Vehicle Routing) Остановимся на двух основных классах задач: построение расписания для проекта и построение расписания для приборов. В задаче построения расписания для проекта (Resource-Constrained Project Scheduling Problem, RCPSP - построения расписания выполнения работ проекта с учетом отношений предшествования и ограничения на ресурсы) под проектом понимают совокупность взаимосвязанных действий, направленных на достижение конкретных целей. В задаче RCPSP необходимо построить оптимальное расписание проекта (выполнения работ проекта) с учетом сетевого графика (отношений предшествования между работами) и с учетом необходимых/доступных ресурсов, при котором будет оптимизирована некоторая целевая функция [29]. В задачах построения расписания для приборов (в задачах календарного планирования) выделяются несколько подтипов задач: задачи для одного прибора, задачи для параллельных приборов, задачи цеха (Shop Scheduling), Job- shop, Flow-shop, Open-shop. Отличие задач построения расписания для проекта и расписания для приборов заключается в том, что при построении расписания для проекта подразумевается одновременное участие нескольких исполнителей. Календарное планирование - это процесс составления и корректировки расписания, в котором работы, выполняемые различными исполнителями, связываются между собой во времени и с возможностями их обеспечения различными видами материально-технических и трудовых ресурсов. При календарном планировании обязательно должно учитываться соблюдение заданных ограничений (продолжительность работ, лимиты ресурсов) и оптимальное распределение ресурсов. В теории расписаний для решения перечисленных выше задач используюся следующие методы: эвристические алгоритмы, метаэвристические методы, метод динамического программирования, графический метод, метод ветвей и границ. Эвристические алгоритмы - алгоритмы, основанные на правдоподобных, но не обоснованных математически предположениях о свойствах оптимального решения задачи. Фактически в эвристическом алгоритме учитывается одно или несколько свойств оптимального решения, на основе которых производится сокращение перебора возможных решений. Метаэвристические методы. Примерами таких метаэвристических методов являются генетический алгоритм и метод муравьиных колоний [30, 31]. Метод динамического программирования получил большое распространение при решении некоторых задач дискретной оптимизации [29]. 30