75389

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Minimizing the Total Weighted Duration of Courses in a Single Machine Problem with Precedence Constraints

ISBN/ISSN: 

0005-1179

DOI: 

10.25728/arcRAS.2023.90.12.001

Наименование источника: 

  • Automation and Remote Control

Обозначение и номер тома: 

Vol. 84, No. 9

Город: 

  • Москва

Издательство: 

  • V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences

Год издания: 

2023

Страницы: 

1128–1139
Аннотация
A single machine scheduling problem with a given partial order of jobs is considered. There are subsets of jobs called courses. It is necessary to schedule jobs in such a way that the total weighted duration of all courses is minimal. We consider the case when the initial job and the final one of each course are uniquely determined. The NP-hardness of the problem under consideration is proved. We propose an algorithm for solving the problem, the complexity of which depends polynomially on the total number of jobs, but exponentially on the number of courses, which makes it possible to use it efficiently with a fixed small number of courses and an arbitrary number of jobs.

Библиографическая ссылка: 

Мусатова Е.Г., Лазарев А.А. Minimizing the Total Weighted Duration of Courses in a Single Machine Problem with Precedence Constraints // Automation and Remote Control. 2023. Vol. 84, No. 9. С. 1128–1139.