No label defined (Q3675864)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3896632
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3896632

      Statements

      1982
      0 references
      Johnson scheduling problem
      0 references
      0 references
      The Johnson scheduling problem is a special case of the more general Akers-Fridman (Akers-Friedmann) problem: for given \(m\) machines and \(n\) details the matrix \(a_j\) of processing durations of the \(j\)-th detail on the \(i\)-th machine is known; also the technological sequence of processing \((s_ j(1), s_ j(2),\ldots,s_ j(m))\) for the detail \(j\) is given; what is the minimal duration \(T(P)\) of a schedule \(P\) of all details processing? And which schedule \(P\) realizes this minimal duration? Let \(m=3\), \(a=\max a_{ij}\) over \(i\) and \(j\), \(A=\max \sum^{n}_{j=1}a_{ij}\) over \(i=1,\ldots,m\). Then the results of the paper can be presented as follows: \bigskip \begin{tabular}{lllll} \hline Problem &Best known case &&Author's estimations\\ &\(T(P)\leq\) &Algorithmic &\(T(P)\leq\) &Algorithmic\\ &&complexity&&complexity\\ \hline Johnson &\(O(n^2)\) &\(A+4a\) &\(O(n\,\log\,n)\) &\(A+3a\)\\ Ackers-not Friedmann &mentioned &\(A+3(3\sqrt2+2)a\) &\(O(n^2)\) &\(A+6a\) \\ \hline \end{tabular} \bigskip The first estimation is proved not to be improvable.
      0 references

      Identifiers