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 528–539
DOI: https://doi.org/10.33048/semi.2022.19.044
(Mi semr1519)
 

Discrete mathematics and mathematical cybernetics

On complexity of two-machine routing propotionate open shop

A. V. Pyatkin, I. D. Chernykh

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
References:
Abstract: In the routing open shop problem a fleet of mobile machines has to traverse the given transportation network, to process immovable jobs located at its nodes and to return back to the initial location in the shortest time possible. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. We consider a special proportionate case of this problem, in which processing time for any job does not depend on a machine. We prove that the problem in this simplified setting is still NP-hard for the same simplest case. To that end, we introduce the new problem we call $2$-$\mathrm{Summing}$ and reduce it to the problem under consideration. We also suggest a $\frac76$-approximation algorithm for the two-machine proportionate problem with at most three nodes.
Keywords: routing open shop, proportionate open shop, complexity, approximation algorithm, standard lower bound, optima localization.
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 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 25, 2022
Bibliographic databases:
Document Type: Article
UDC: 519.854.2
MSC: 90B35
Language: English
Citation: A. V. Pyatkin, I. D. Chernykh, “On complexity of two-machine routing propotionate open shop”, Sib. Èlektron. Mat. Izv., 19:2 (2022), 528–539
Citation in format AMSBIB
\Bibitem{PyaChe22}
\by A.~V.~Pyatkin, I.~D.~Chernykh
\paper On complexity of two-machine routing propotionate open shop
\jour Sib. \`Elektron. Mat. Izv.
\yr 2022
\vol 19
\issue 2
\pages 528--539
\mathnet{http://mi.mathnet.ru/semr1519}
\crossref{https://doi.org/10.33048/semi.2022.19.044}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4478145}
Linking options:
  • https://www.mathnet.ru/eng/semr1519
  • https://www.mathnet.ru/eng/semr/v19/i2/p528
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:92
    Full-text PDF :25
    References:19
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024