Abstract: Рассматривается задача составления расписаний в следующей постановке [1]. Имеется множество работ, которые должны быть выполнены с использованием имеющегося набора машин. Длительность pij(R) работы j зависит от используемой машины i и объема потребляемого ресурса R (задается выпуклой функцией). Общий объем ресурса ограничен, причем во время простоя машины также идет потребление ресурса (задается линейной функцией). Требуется построить допустимое расписание, при котором минимизируется длина расписания maxjCj, где Cj – момент завершения работы j. При этом могут учитываться условия предшествования и запреты на совместное выполнение [2]. Данная задача имеет приложения в производственных и компьютерных системах. В производственных системах ресурсом указанного типа выступает сырье и энергия, а в компьютерных системах – энергия и температура [1; 3]. Исследуются структурные свойства расписаний для указанной задачи, устанавливаются случаи, когда допустимого расписания не существует. Идентификация неразрешимого случая основана на поиске коней многочлена специального вида. Приводятся полиномиально разрешимые случаи, когда полиномиально вычислимая нижняя оценка и оптимальное значение целевой функции совпадают. Для решения задачи используется двухэтапный алгоритм. На первом этапе вычисляются нижняя оценка на целевую функцию и оценка длительностей работ. На втором этапе строится расписание с помощью алгоритма списочного типа при учете структурных ограничений. Предлагаются обобщения на случай, когда можно задействовать несколько машин при выполнении работы и длительность при этом уменьшается линейно Для решения задачи используется двухэтапный алгоритм. На первом этапе вычисляются нижняя оценка на целевую функцию и оценка длительностей работ. На втором этапе строится расписание с помощью алгоритма списочного типа при учете структурных ограничений. Предлагаются обобщения на случай, когда можно задействовать несколько машин при выполнении работы и длительность при этом уменьшается линейно Для решения задачи используется двухэтапный алгоритм. На первом этапе вычисляются нижняя оценка на целевую функцию и оценка длительностей работ. На втором этапе строится расписание с помощью алгоритма списочного типа при учете структурных ограничений. Предлагаются обобщения на случай, когда можно задействовать несколько машин при выполнении работы и длительность при этом уменьшается линейно.

Cite: Захарова Ю.В.
Свойства решений в задачах составления расписаний с ресурсозависимыми длительностями работ
In compilation Математическое и компьютерное моделирование : Сборник материалов XII Международной научной конференции. – Издательство Омского государственного университета им. Ф.М. Достоевского., 2025. – C.120-121. – ISBN 978-5-7779-2728-6.

Identifiers: No identifiers

Citing: Пока нет цитирований