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.8177245855331421
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