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


Sib. Èlektron. Mat. Izv., 2019, Volume 16, Pages 406–426 (Mi semr1065)  

Computational mathematics

Some positive news on the proportionate open shop problem

Sergey Sevastyanov

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia

Abstract: The special case of the open shop problem in which every job has equal length operations on all machines is known as a proportionate open shop problem. The problem is NP-hard in the case of three machines, which makes topical such traditional research directions as designing efficient heuristics and searching for efficiently solvable cases. In this paper we found several new efficiently solvable cases (wider than known) and designed linear-time heuristics with good performance guarantees (better than those known from the literature). Besides, we computed the exact values of the power of preemption for the three-machine problem, being considered as a function of a parameter $\gamma$ (the ratio of two standard lower bounds on the optimum: the machine load and the maximum job length). We also found out that the worst-case power of preemption for the $m$-machine problem asymptotically converges to 1, as $m$ tends to infinity. Finally, we established the exact complexity status of the three-machine problem by presenting a pseudo-polynomial algorithm for its solution.

Keywords: open shop, proportionate, scheduling, makespan minimization, power of preemption, polynomial time heuristic, dynamic programming.

Funding Agency Grant Number
Russian Foundation for Basic Research 17-07-00513_а
Siberian Branch of Russian Academy of Sciences 0314-2019-0014
The work is supported by the Russian Foundation for Basic Research (grant 17-07-00513) and by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014).


DOI: https://doi.org/10.33048/semi.2019.16.023

Full text: PDF file (642 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.854.2
MSC: 90B35
Received December 21, 2018, published March 29, 2019
Language:

Citation: Sergey Sevastyanov, “Some positive news on the proportionate open shop problem”, Sib. Èlektron. Mat. Izv., 16 (2019), 406–426

Citation in format AMSBIB
\Bibitem{Sev19}
\by Sergey~Sevastyanov
\paper Some positive news on the proportionate open shop problem
\jour Sib. \`Elektron. Mat. Izv.
\yr 2019
\vol 16
\pages 406--426
\mathnet{http://mi.mathnet.ru/semr1065}
\crossref{https://doi.org/10.33048/semi.2019.16.023}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000462734100001}


Linking options:
  • http://mi.mathnet.ru/eng/semr1065
  • http://mi.mathnet.ru/eng/semr/v16/p406

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:59
    Full text:13
    References:14

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019