Avtomatika i Telemekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Avtomatika i Telemekhanika, 2023, Issue 9, Pages 153–168
DOI: https://doi.org/10.31857/S000523102309009X (Mi at16208) 		 
Optimization, System Analysis, and Operations Research

Minimizing the total weighted duration of courses in a single machine problem with precedence constraints

E. G. Musatova, A. A. Lazarev

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
Full-text PDF (387 kB) First page
References:
PDF
HTML
DOI: https://doi.org/10.31857/S000523102309009X
Abstract: 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.
Keywords: scheduling theory, single machine problem, NP-hard problems, downtime of resources minimization.
Presented by the member of Editorial Board: P. Yu. Chebotarev

Received: 08.02.2023
Revised: 20.06.2023
Accepted: 20.07.2023
English version:
Automation and Remote Control, 2023, Volume 84, Issue 9, Pages 1005–1015
DOI: https://doi.org/10.1134/S0005117923090102
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: E. G. Musatova, A. A. Lazarev, “Minimizing the total weighted duration of courses in a single machine problem with precedence constraints”, Avtomat. i Telemekh., 2023, no. 9, 153–168; Autom. Remote Control, 84:9 (2023), 1005–1015
Citation in format AMSBIB
\Bibitem{MusLaz23}
\by E.~G.~Musatova, A.~A.~Lazarev
\paper Minimizing the total weighted duration of courses in a single machine problem with precedence constraints
\jour Avtomat. i Telemekh.
\yr 2023
\issue 9
\pages 153--168
\mathnet{http://mi.mathnet.ru/at16208}
\crossref{https://doi.org/10.31857/S000523102309009X}
\edn{https://elibrary.ru/JUNOUZ}
\transl
\jour Autom. Remote Control
\yr 2023
\vol 84
\issue 9
\pages 1005--1015
\crossref{https://doi.org/10.1134/S0005117923090102}
Linking options:
  • https://www.mathnet.ru/eng/at16208
  • https://www.mathnet.ru/eng/at/y2023/i9/p153
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Avtomatika i Telemekhanika
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025