scientific article; zbMATH DE number 3896632
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.
- The flow shop problem with no-idle constraints: a review and approximation
- On some geometric methods in scheduling theory: A survey
- Vector summation within minimal angle
- The simple F2//C with forbidden tasks in first or last position: a problem more complex that it seems
- Performance guarantees for flowshop heuristics to minimize makespan
- Ordering of jobs with three different processing times in the \(Mxn\) Bellman-Johnson problem
- scientific article; zbMATH DE number 3871006 (Why is no real title available?)
- scientific article; zbMATH DE number 4128650 (Why is no real title available?)
- scientific article; zbMATH DE number 1091396 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3675864)