Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports]
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find




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

Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2022, Volume 19, Issue 2, Pages 548–561
DOI: https://doi.org/10.33048/semi.2022.19.046 (Mi semr1520) 		 
Discrete mathematics and mathematical cybernetics

On the two-machine routing open shop on a tree with preemption allowed

P. M. Agzyamovaa, I. D. Chernykhb

a Novosibirsk State University, 1, Pirogova str., Novosibirsk, 630090, Russia
b Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Full-text PDF (402 kB)
References:
PDF
HTML
DOI: https://doi.org/10.33048/semi.2022.19.046
Abstract: The routing open shop problem is a natural generalization of the metric TSP and a classical open shop scheduling problem. Jobs are located at the nodes of a given transportation network, and mobile machines have to perform operations on those jobs while traveling over the edges. Machines are obligated to return to the initial location after completing all operations. The goal is to minimize the makespan. We consider the two-machine routing open shop on a tree with preemption in a general setting, where travel times are machine- and direction-dependent. For this problem we describe a wide polynomially solvable special case, for which the optimal makespan is guaranteed to coincide with the standard lower bound. To that end, we introduce a new problem setting with restricted preemption.
Keywords: shop scheduling, routing open shop, restricted preemption, individual travel times, asymmetric transportation network, polynomially solvable cases, standard lower bound.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation FWNF-2022-0019
Russian Foundation for Basic Research 20-01-00045
20-07-00458
This research was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019), and supported by the Russian Foundation for Basic Research, projects 20-01-00045 and 20-07-00458.
Received April 21, 2022, published August 26, 2022
Bibliographic databases:
Document Type: Article
UDC: 519.854.2
MSC: 90B35
Language: English
Citation: P. M. Agzyamova, I. D. Chernykh, “On the two-machine routing open shop on a tree with preemption allowed”, Sib. Èlektron. Mat. Izv., 19:2 (2022), 548–561
Citation in format AMSBIB
\Bibitem{AgzChe22}
\by P.~M.~Agzyamova, I.~D.~Chernykh
\paper On the two-machine routing open shop on a tree with preemption allowed
\jour Sib. \`Elektron. Mat. Izv.
\yr 2022
\vol 19
\issue 2
\pages 548--561
\mathnet{http://mi.mathnet.ru/semr1520}
\crossref{https://doi.org/10.33048/semi.2022.19.046}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4478147}
Linking options:
  • https://www.mathnet.ru/eng/semr1520
  • https://www.mathnet.ru/eng/semr/v19/i2/p548
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:81
    Full-text PDF :18
    References:19
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024