Open AccessPROJECT SCHEDULING PROBLEM WITH UNIT PROCESSING TIME OF JOBS
Author(s) -
N. V. Gerasimenko,
V. V. Servah
Publication year - 2021
Publication title -
dinamika sistem, mehanizmov i mašin
Language(s) - Russian
Resource type - Journals
ISSN - 2310-9793
DOI - 10.25206/2310-9793-9-4-15-17
Subject(s) - scheduling (production processes) , computer science , unit (ring theory) , operations research , mathematical optimization , mathematics , mathematics education
В работе рассматриваются вопросы вычислительной сложности задачи календарного планирования с ограниченными ресурсами. Описаны максимально полиномиально разрешимые и минимально NP-трудные случаи. Граничной задачей, вычислительная сложность которой неизвестна, является задача с единичными длительностями выполнения работ при единичном потреблении ресурсов и фиксированным уровнем возобновимого ресурса. Получены новые полиномиально разрешимые подслучаи этой задачи, связанные с шириной частичного порядка выполнения работ и максимально возможной длиной цепи в графе.