|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Minimizing the Total Weighted Duration of Courses in a Single Machine Problem with Precedence Constraintsстатья
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 1 мая 2024 г.
- Авторы: Musatova E.G., Lazarev A.A.
- Журнал: Automation and Remote Control
- Том: 84
- Номер: 9
- Год издания: 2023
- Издательство: Pleiades Publishing, Ltd
- Местоположение издательства: Road Town, United Kingdom
- Первая страница: Page
- Последняя страница: 1128–1139
- DOI: 10.25728/ARCRAS.2023.90.12.001
- Аннотация: 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.
- Добавил в систему: Лазарев Александр Алексеевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | 72394-75389.pdf | 354,6 КБ | 19 декабря 2023 [Lazarev] |