\documentclass[10pt]{amsart}
\usepackage{amssymb,amsmath,amsfonts,amsbsy}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{xcolor}
\usepackage[square, comma, sort&compress, numbers]{natbib}
\usepackage{tikz}
\usepackage{srcltx}

\def\udcs{519.854.2} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{90B35} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{1}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{assumption}{Assumption}
\newtheorem{observation}{Observation}
\newcommand{\algend}{\rule{1em}{0pt}$\blacksquare$}
\newcommand {\conv}{\mbox{\rm conv}}
\newcommand {\lin}{\mbox{\rm lin}}
%\renewcommand{\appendixname}{\sc Appendix}

%\newcommand{\qed}{\rule{1em}{0pt}$\Box$}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]  %Headings in Russian
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 12, стр. 144--144 (2015) \hspace{65mm}{\rm\small УДК \udcs}} %Volume, pages in Russian,
                                                                                    %filled by Editorial board
     \newline
         {\rm\small DOI~10.17377/semi.2015.12.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\renewcommand{\figurename}{Fig.}
\renewcommand{\tablename}{Table}
\newcommand{\doi}[1]{{doi:\ #1}}
\thispagestyle{empty}

\title[Approximation algorithm for the job shop problem]{Approximate solution of the job shop problem\\ 
by means of the compact vector summation\\ 
within a bounded convex set in ${\mathbb{R}}^d$}
\author{{Sergey Sevastyanov}}%
\address{Sergey Vasilyevich Sevastyanov
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{seva@math.nsc.ru}%

\thanks{\sc Sevastyanov, S.V.,
Approximate solution of the job shop problem by means of the compact vector summation in a space with asymmetric norm}
\thanks{\copyright \ 2024 Sevastyanov S.V}
\thanks{\rm The work is supported by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014)
}
\thanks{\it Received  January, 1, 2015, published  March, 1,  2015.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract.}\ 
The first fully polynomial-time approximation algorithm for solving the Job Shop problem in its most general form with theoretically guaranteed a priori accuracy bounds was published in (Sevast'yanov, 1984). The approach used in that paper for solving the Job Shop problem, based on the method of compact vector summation in $d$-dimensional space, was further developed in (Sevast'yanov, 1986). For any fixed job shop, those algorithms provided an asymptotic optimality of the solutions, under the unlimited growth of size of the batch of jobs supplied at the problem input. Later on, two other approximation algorithms for this problem with ratio performance guarantees appeared in (Shmoys et al., 1994). The first algorithm provided (in polynomial time) a poly-logarithmic approximation in terms of two parameters: the number of machines ($m$) and the number of operations per job ($\mu$). The second algorithm guaranteed a $(2+\varepsilon)$-approximation for any fixed $\varepsilon>0$ and was polynomial-time for any fixed values of $m$ and $\mu$. Finally, in (Jansen et al., 2003), a PTAS was elaborated for the Job Shop problem, which was polynomial-time under the assumption that $m$ and $\mu$ are fixed. All three above mentioned algorithms were heavily based on the algorithm from (Sevast'yanov, 1986) and were presented as an ``improvement'' of the latter. In the present paper, a comparative analysis of the quality of four known for today theoretical algorithms for approximate solution of the Job Shop problem (namely, of the algorithms from (Sevast'yanov, 1986), (Shmoys et al., 1994), and (Jansen et al., 2003)) is carried out. It is shown that on the set of instances of practical size, the best to date by the accuracy/efficiency criteria is the algorithm from (Sevast'yanov, 1986), while the second algorithm from (Shmoys et al., 1994) and the PTAS from (Jansen et al., 2003) are not capable of obtaining a solution 10 times worse than optimal in any physically observable time even for comparatively small instances of the problem (and even with the help of the Super-Computer System of the whole Universe). The paper also presents an improved scheme of the algorithm from (Sevast'yanov, 1986), which gives a better bound on the absolute error with the same bound on the running time, which is the first positive result in this direction since 1986. Detailed schemes of all procedures used in the algorithm are given (in order to facilitate its programming). In addition, the paper shows how both algorithms from (Shmoys et al., 1994) can be transformed so that their running time becomes linear in the main problem parameter, the number of jobs $n$.

\medskip\noindent{\bf Keywords:} scheduling, job shop problem, makespan, approximation, polynomial time algorithm.
\end{quote}
}

\section{Introduction}

In the 1970s, a tight connection was discovered between multistage scheduling problems of the \emph{Flow Shop} type and geometric problems of finding an order of summation for a given finite family of vectors from $\mathbb{R}^d$ within a ball (of some norm defined in $\mathbb{R}^d$) of minimum radius\footnote{For the first time, these results were mentioned by Sevastyanov in June of 1974, in Proceedings of the 3rd All Union Conference on Problems in Theoretical Cybernetics \cite{S74}. The relationship between scheduling and vector summation problems was then independently discovered by Belov and Stolin and published in December of 1974 in \cite{BS74}.}. This connection enabled one to find efficiently approximate solutions for scheduling problems with \emph{a priori} guaranteed accuracy bounds by reducing these problems (approximately) to the corresponding vector summation problems, provided that efficient methods with theoretical performance guarantees had already been developed for the latter problems. 

Later on, a similar connection between scheduling problems and vector summation problems was found for many other multistage scheduling problems to the minimum makespan, such as: problems with several different routes of jobs through machines \cite{BBB76,BBB77,S81,S82,D89,NS93}, problems with non-fixed routes \cite{S99,S95,S96,S97,S98}, production line prob\-lems \cite{BBBD75}, flexible flow shop problem \cite{S81,S93}, a.o., which emphasized the importance of vector summation methods for scheduling theory.

As a result, a wide range of geometric problems on finding orders of vector summation within various (either fixed or optimized) domains of finite-dimensional space appeared in the scope of our interests. So, developing efficient methods for approximate solution of such problems became topical. For a more detailed acqu\-aintance with results in this area, we refer the reader to two reviews \cite{S94,S98}. Now we only note that beyond the \textbf{approximate solution} of scheduling problems, these geometric methods enable one to find \textbf{optimal solutions} for wide \textbf{polynomially solvable classes of instances} of the \emph{Open Shop} problem \cite{S95,S96,S97,S98,S99}.

By all accounts, one of the most difficult multistage scheduling problems for (not only exact, but also approximate) solution is the Job Shop problem, in which each job may have its own, individual route through machines of an arbitrarily large length. The number of operations per job is a parameter independent on the number of machines (each machine can be used multiple times in the job route). This $m$-machine $n$-job problem with the minimum makespan objective is normally denoted as $\langle J\,||\,C_{\max}\rangle$.
It can be formulated as follows.
(Here and then, $[k]$ will denote the set of integers $\{1,2,\dots,k\}$, where $[k]=\varnothing$ for $k=0$.) 

\medskip
{\bf Job Shop problem.}\ We are given a set of jobs $\{J_1,\dots,J_n\}$ that should be processed on a given set of dedicated machines $\{M_1,\dots,M_m\}$. Each job $J_j$\ ($j\in[n]$) consists of $\mu_j$ \emph{operations} $\{O_{1,j},\dots,O_{\mu_j,j}\}$ that must be processed in this order. (This means that the next operation of a job cannot start until the previous one has been completed.) Each operation $O_{\eta,j}$ should be processed on a certain machine $M(O_{\eta,j})$ within a time interval of length $p_{\eta,j}$, without interruption. The processing of different operations on the same machine should not overlap in time. Among the set of \emph{feasible schedules} (which meet the above requirements), we wish to find a schedule $S=\{s_{\eta,j}\,|\,O_{\eta,j}\in{\mathcal O}\}$ (where $s_{\eta,j}$ is the starting time of operation $O_{\eta,j}$, and ${\mathcal O}$ denotes the set of all operations) that minimizes the \emph{maximum job completion time} $C_{\max}(S)\doteq\max\{s_{\eta,j}+p_{\eta,j}\,|\,O_{\eta,j}\in{\mathcal O}\}$.

\medskip
As one can see, the above problem setting stipulates a certain route of each job through machines. As was claimed in \cite{CPW98}, such a route cannot be an arbitrary one:
``In literature of job shop scheduling, \emph{machine repetition} is usually \textbf{not allowed}, \emph{i.e.}, consecutive operations of the same job must always be assigned to different machines. We follow this convention unless stated otherwise.'' 

Apparently, accepting such a convention for the ``norm'' in the formulation of the Job Shop problem could be explained by the difficulty of solving the problem in the general case. Yet, we should note that such a restriction on the problem setting can facilitate its exact solution in very special cases only (such as the case of two machines) and is useless in more general cases. As for the approximate solution of this problem, as we will see it later, the most significant \textbf{positive results} in this direction (due to Sevastyanov \cite{S84,S86}, Shmoys, Stein and Wein \cite{SSW94}, and Jansen, Solis-Oba, and Sviridenko \cite{JSS03}) have been obtained for the Job Shop problem \textbf{in the setting presented above}, i.e., \textbf{without} the artificial constraint on job routes accepted in Chen, Potts, and Woeginger \cite{CPW98} for the ``norm''.

Moreover, the problem without such a restriction enables us to consider interes\-ting models with \emph{controllable interruptions}, in which interruptions of each operation are allowed only at certain relative time moments specified by certain (admitted) values of the volume of the already completed part of the operation. To cope with such a problem, it suffices (1) for each operation to cut down its processing time interval at given relative time moments (specifying ``allowed interruptions'' of the  operation), thereby obtaining several ``smaller operations'' to be sequentially executed \textbf{on the same machine}, and (2) to solve the resulting Job Shop problem without interruptions and \textbf{without the above restriction on machine repetiti\-on}. Such models (with controllable interruptions) generalize both the models \textbf{with preemption}, and the models \textbf{without preemption}. 

Thus, we will consider the Job Shop problem \textbf{without} the artificial constraint on machine repetition in job routes (since the latter really limits the generality of our problem) and will denote it as $\langle J\,||\,C_{\max}\rangle$. For denoting the special case of this problem with the ``bun'' on machine repetition in any job route, we suggest to use notation ``no rep''. Note also that this restriction limits not the set of feasible solutions of the problem (related to \textbf{the problem output}), but rather \textbf{the set of its inputs}, thereby determining the problem we solve: either the problem in its general form or a certain special case of it. That is why I propose to place such a definition of the problem to be solved (listing the restrictions/extensions of the set of inputs) \textbf{in the first field} of the three-field system we use, leaving the second field for recording the restrictions (or, conversely, extensions) of the set of feasible solutions of the problem. Thus, the above mentioned special case should be denoted as $\langle J, \mbox{no rep}\,||\,C_{\max}\rangle$.

The difficulty of the exact solution of the Job Shop problem is confirmed by a number of results establishing that some very special cases of it (all of which are ``no rep'') turn out to be NP-hard. For example, these are the problems $\langle J2, \mbox{no rep},\mu_j\le 3\,||\,C_{\max}\rangle$ and $\langle J3, \mbox{no rep},\mu_j\le 2\,||\,C_{\max}\rangle$ \cite{LRB77} (i.e., the problem with two machines and at most three operations per job and the problem with three machines and at most two operations per job), as well as problem $\langle J3, \mbox{no rep},n\le 3\,||\,C_{\max}\rangle$ \cite{SS95} (with three machines and at most three jobs). Meanwhile, such a special case of $\langle J3, \mbox{no rep},\mu_j\le 3\,||\,C_{\max}\rangle$ problem as $\langle F3\,||\,C_{\max}\rangle$ (when all jobs have the same route $(1,2,3)$ through machines) is strongly NP-hard~\cite{GJS76}.

As far as an approximate solution of this problem is concerned, apparently, the first efficient algorithms with theoretical performance guarantees for solving the Job Shop problem in its most general form were presented in (Sevast'yanov, 1984, 1986). The polynomial-time algorithms described in those two papers guaranteed finding schedules satisfying \emph{a priori} bounds on the \textbf{absolute error} in the form:
%
\begin{equation}\label{eq1}
C_{\max}(S)\le L_{\max}+ \varphi(m,\mu)p_{\max},
\end{equation}
%
where $L_{\max}$ is the maximum machine load (which, clearly, is a lower bound on the optimum), $\mu\doteq\max_j\mu_j$ is the maximum number of operations per job, $\varphi(m,\mu)$ is a polynomial on $m$ and $\mu$, and $p_{\max}\doteq\max_{\eta,j} p_{\eta,j}$ is the maximum processing time of an operation.\footnote{The algorithms presented in those two papers differ in the orders of their polynomials $\varphi(m,\mu)$ and in bounds on their running time.}
As one can see, the absolute error $C_{\max}(S)-L_{\max}\le\varphi(m,\mu)p_{\max}$ of the approximate solution does not depend on the number of jobs. Under the assumption that the values of parameters $m$, $\mu$, and $p_{\max}$ are bounded by constants, while the number of jobs $n$ grows without limit (and so, $p_{\max}$ becomes arbitrarily small with respect to amounts $P\doteq\sum_{\eta,j} p_{\eta,j}$ and $L_{\max}\ge P/m$), the solution found becomes \textbf{asymptotically optimal}.

It should be noted that the assumption made in \cite{S84, S86} about the limited growth of the quantities $m,\mu$, and $p_{\max}$ in parallel with the growth of the number of jobs $n$ has got a practical meaning. Assuming that the range of products manufactured in the job shop remains more or less constant over a long period of time, we can calculate the maximum values of quantities $\mu$ and $p_{\max}$ for this range of products and treat them as constants over time. The maximum possible number of machines ($m$) placed in the job shop is also limited by the size of the job shop (i.e., by a constant independent of time). As for the number of jobs $n$, this parameter obviously grows proportionally to the duration ($T$) of the \emph{planning horizon}\footnote{\emph{Planning horizon} is the time interval $[0,T]$ during which it is required/wanted/planned to perform a \textbf{specified list} of \textbf{jobs}.} of the shop activities. Under these conditions, the algorithms described in \cite{S84, S86} provide good practical solutions that become (theoretically) asymptotically optimal with unlimited growth of $T$.

Based on the algorithm from (Sevast'yanov, 1986), Shmoys et al. (1994) designed two approximation algorithms for the Job Shop problem with \textbf{ratio performance guarantees}. One of them provided a poly-log approximation in terms of \textbf{variable parameters} $m$ and $\mu$ and was purely polynomial-time. To construct an approximate schedule, they divide the entire set of jobs into ``small'' jobs (all operations of which have a length not greater than $L_{\max}/(2m\mu^3)$) and the remaining ``large'' jobs, the number of which ($n'$) does not exceed $2m^2\mu^3$. For ``small'' jobs, they use the algorithm from (Sevast'yanov, 1986) (with running time $O(m^2\mu^2n^2)$) which constructs a schedule $S_S$ with length that meets bound (\ref{eq1}), where instead of the function $\varphi(m,\mu)$ the authors of (Shmoys et al., 1994) use its upper bound $2m\mu^3$. As a result, from (\ref{eq1}) and from the upper bound on the lengths of operations of ``small'' jobs, we obtain the bound $C_{\max}(S_S)\le 2L_{\max}$. For ``large'' jobs, Shmoys et al. first transform the durations of their operations (by switching to a new time unit equal to $\delta\doteq p_{\max}/|{\mathcal O}'|$, where ${\mathcal O}'$ is the set of operations of ``large'' jobs), and then rounding them down to the nearest integer. Thus, the new durations ($p\,'_{\!\eta,j}\doteq\lfloor\frac{p_{\eta,j}|{\mathcal O}'|}{p_{\max}}\rfloor$) of operations are integers and do not exceed $|{\mathcal O}'|\le n'\mu$.
 After that, for the instance consisting of all large jobs with transformed processing times, a randomized polynomial-time algorithm is applied, which, with high probability, yields its schedule $S_2'$ of length 
%
\begin{equation}\label{eq2}
C_{\max}(S_2')\le O\left((L'_{\max}+P'_{\max})\frac{\log(n'\mu)}{\log\log(n'\mu)}\log p\,'_{\!\max}\right),
\end{equation}
%
where $p\,'_{\!\max}\doteq\max_{\{\eta,j\}} p\,'_{\!\eta,j}$ is bounded from above by $n'\mu$, while $L'_{\max}$ and $P'_{\max}\doteq\max_j \sum_{\eta\in[\mu_j]}p\,'_{\!\eta,j}$ are the maximum machine load and the maximum job length measured in the new time units. Keeping in mind that functions $x/\log x$ and $\log x$ are monotonically increasing, we may replace $p\,'_{\!\max}$ and $n'$ in (\ref{eq2}) by their upper bounds (polynomial in $m$ and $\mu$) and obtain the bound:
$$C_{\max}(S_2')\le O\left((L'_{\max}+P'_{\max})\frac{\log^2(m\mu)}{\log\log(m\mu)}\right).$$
This inequality, clearly, remains valid after returning to the original time units, because all time-dependent parameters (such as processing times $p\,'_{\!\eta,j}$, schedule length $C_{\max}(S_2')$ and amounts $L'_{\max},P'_{\max}$) are multiplied by the same number $\delta$, providing (in new terms) the inequality
%
\begin{equation}\label{eq3}
C_{\max}(S_2'')\le O\left((L''_{\max}+P''_{\max})\frac{\log^2(m\mu)}{\log\log(m\mu)}\right).
\end{equation}
%
Next, returning to the original instance of large jobs (with operation lengths $p_{\eta,j}\ge p\,''_{\!\eta,j}$) lengthens each operation by at most $\delta$ and increases the length of each path in the precedence graph of operations in schedule $S_2''$ by no more than $\delta\cdot |{\mathcal O}'|=p_{\max}$, while $L''_{\max}$ and $P''_{\max}$ in the right part of (\ref{eq3}) grow up to at most $L_{\max}$ and $P_{\max}$. As a result, the authors obtain a schedule $S_2$ for large jobs which, with high probability, meets the bound:
%
\begin{equation}\label{eq4}
C_{\max}(S_2)\le C_{\max}(S_2'')+p_{\max}\le O\left((L_{\max}+P_{\max})\frac{\log^2(m\mu)}{\log\log(m\mu)}\right).
\end{equation}
%
A subsequent derandomization of this schedule yields (in polynomial time) a deterministic schedule $S_L$ for large jobs with bound
$$C_{\max}(S_L)\le O(\log^2(m\mu)C_{\max}^*).$$

Finally, consecutively connecting schedules $S_S$ and $S_L$ for small and large jobs, they obtain schedule $S$ with the relative accuracy bound
%
\begin{equation}\label{eq4a}
C_{\max}(S)/C_{\max}^*\le O(\log^2(m\mu)).
\end{equation}
%
Since the algorithm for large jobs is polynomial-time, and the number of large jobs ($n'$) is bounded above by $2m^2\mu^3$, the overall running time of their algorithm can be estimated as $O(n^2m^2\mu^2+ P(m,\mu))$, where $P(m,\mu)$ is a polynomial of $m$ and $\mu$. 

\medskip
The \textbf{second approximation algorithm from (Shmoys et al., 1994)} provided a $(2+\varepsilon)$-approximation for any fixed $\varepsilon>0$ in polynomial ($O(n^2)$) time under assumption that parameters $m$ and $\mu$ are fixed. Again, they use the idea of dividing the whole set of jobs into two subsets of ``small'' and ``large'' jobs, yet with the ``watershed'' for lengths of operations at a different value $\frac{\varepsilon L_{\max}}{2m\mu^3}$. The application of the algorithm by (Sevast'yanov, 1986) to small jobs yields a schedule $S_S$ that meets bound (\ref{eq1}) with $\varphi(m,\mu)=2m\mu^3$ and $p_{\max}=\frac{\varepsilon L_{\max}}{2m\mu^3}$, which yields the bound $C_{\max}(S_S)\le L_{\max}+\varepsilon L_{\max}\le (1+\varepsilon)C_{\max}^*$. For ``large'' jobs (the number of which is not greater than $2m^2\mu^3/\varepsilon$, and for fixed $m,\mu$, and $\varepsilon$ is fixed), they find (\textbf{by any way}) an \textbf{optimal schedule} $S_L$ of length $C_{\max}(S_L)\le C_{\max}^*$, which yields the desired accuracy bound for the concatenation of two schedules:
%
\begin{equation}\label{eq4b}
C_{\max}(S_S\oplus S_L)\le (2+\varepsilon)C_{\max}^*.
\end{equation}

The \textbf{PTAS presented by (Jansen et al., 2003)} for the general Job Shop problem $\langle J\,||\,C_{\max}\rangle$ in the case of \textbf{any fixed $m$ and $\mu$} is a development of the above result (i.e., of the $O(n^2)$-time $(2+\varepsilon)$-approximation algorithm for problem $\langle J\,||\,C_{\max}\rangle$ with any fixed $m,\mu$, and $\varepsilon>0$). They described an $O(n)$-time $(1+\varepsilon)$-approximation algorithm for any fixed $\varepsilon\in(0,1)$ and any fixed $m$ and~$\mu$. This time, the authors divided the set of all jobs into three subsets: of ``big'', ``small'', and ``tiny'' jobs. At that, ``small'' jobs (whose total length is $\delta$-small with respect to $L_{\max}$ and $C_{\max}^*$) are scheduled separately and independently of other jobs, while for the ``big'' jobs the authors organize a full enumeration of all their ``rounded schedules'' within a time interval that obviously exceeds the length of the optimal schedule. Each chosen ``rounded schedule'' for ``big'' jobs defines time intervals of the ``second type'', for each of which a subset of machines available for processing the remaining (``tiny'') jobs is fixed and known. The target of the linear program then applied is determining suitable lengths of those time intervals and distributing the fragments of ``tiny'' jobs among those intervals. Finally, the algorithm by (Sevast'yanov, 1986) is separately applied in each ``second type'' interval to the fragments of ``tiny'' jobs distributed to it.

\medskip
As the reader could be convinced from the presented above short description of the approximation algorithms from (Shmoys et al., 1994) and (Jansen et al., 2003), all these algorithms for the Job Shop problem are heavily based on the approximation algorithm by (Sevast'yanov, 1986) and essentially use its bound (\ref{eq1}) on the absolute error of the solutions obtained. Meanwhile, no progress can be observed with respect to that absolute accuracy bound since the distant 1986. 
In the present paper, we make the first step towards a further enhancement of that basic result by improving the absolute accuracy bound guaran\-teed for the solution obtained by our algorithm. While (Shmoys et al., 1994) roughly estimated the polynomial $\varphi(m,\mu)$ (introduced in (\ref{eq1})) from above in terms of its major term as $2m\mu^3$, we now show that it can be bounded by $m\mu^2(\mu-1)$. To improve the bound, we used two new ideas. One of them is an implementation of the property of the Steinitz family of vectors defined for the original instance of the Job Shop problem to lie within a ball of an asymmetric norm (but with an internal central symmetry), which enables us to apply to these vectors a summation algorithm with a smaller bound on the radius (compared to the algorithms used in (Sevastyanov, 1984, 1986)). 

Another idea is to use a large number of additional (``dummy'') jobs with zero vector of operation durations. Yet, since an uncontrollable increase in the total number of vectors leads to an increase in the running time of the vector summation algorithm, we have to introduce an upper limit on the number of additional jobs. Thus, the resulting accuracy bound and the bound on the running time of the new algorithm are a kind of a ``deal'' between two goals: minimum error and minimum running time.

The rest of the paper is structured as follows. Section~\ref{sec2} introduces some necessary notions and notation and presents some known results used in the paper. Section~\ref{sec3} describes the new version of the algorithm for solving the Job Shop problem. At the same time (in order to avoid referring the reader to inaccessible sources and to provide a self-contained description of our algorithm), a sufficiently detailed description of the procedures dealing with families of vectors (and essentially used in our algorithm) is given in Appendices~\ref{app1} and \ref{app2}. (This can considerably help the readers interested in an experimental verification of the practical applicability of our method for solving the Job Shop problem with real size instances.) Section~\ref{sec4} presents the proof of the main result of this paper, Theorem~\ref{th2}, where the quality of the new algorithm is estimated.

In addition, Section~\ref{sec5} will demonstrate a simple technique for linearization of the complexity of both algorithms from (Shmoys et al., 1994) with respect to the number of jobs. In terms of the parameters $m,\mu,\varepsilon$, and $n$, the new bounds on their running time will be $O(\mu n+f(m,\mu))$ and $O(\mu n+g(m,\mu,\varepsilon))$, respectively, where $f(m,\mu)$ is a polynomial of $m$ and $\mu$ (which is of theoretical interest from the view point of parametric analysis of the complexity of approximate solution of the Job Shop problem), while function $g(m,\mu,\varepsilon)$ exponentially depends on the parameters $m,\mu$, and $1/\varepsilon$.
In Section~\ref{sec6}, we perform a comparative analysis of four (currently known) approximation algorithms for solving the Job Shop problem with theoretical performance guaranties subject to their applicability for solving practical instances of the problem. The analysis shows an undeniable advantage of our algorithm over other competitors. Moreover, a small instance clearly demonstrates that the second algorithm from (Shmoys et al., 1994) and the PTAS from (Jansen et al., 2003) are absolutely inoperable, neither now nor in any distant future. (We hope that the methodology of assessing the practical applicability of algorithms, presented here, can also be successfully applied for testing the practical applicability of other algorithms of solving discrete problems for which there are theoretically guaranteed bounds on their running time.) Finally, Section~\ref{sec7} contains a brief discussion of the results obtained and formulates further possible research directions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminary results}\label{sec2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The notion of a \emph{schedule} is one of the basic notions in our paper. Each schedule defined or constructed in this paper by one of our algorithms represents a certain \textbf{solution of the problem} under consideration. (Although, some schedules construc\-ted here may be infeasible.) Concerning the definition of schedule, it should be noted that there may be many ways to define this notion (depending on the complexity of the problem setting). But in our case it will be sufficient to define it as a \textbf{family of non-negative starting times of all operations}. 

\begin{definition}\label{de0}\rm
A feasible schedule for a given set of jobs is called an \emph{active schedule}, if the starting time of no operation can be decreased without either violating the feasibility of the schedule or without increasing the starting time of some other operation.
\end{definition}

It is rather evident that in scheduling problems with the minimum makespan objective (as is in our case) we can always restrict the set of the solutions (to be considered) by the set of active schedules only.

It is well known that when for a given scheduling problem, the feasibility of a schedule is determined \textbf{only by some precedence constraints} (specified by a directed network $G=(V,E)$ of type ``nodes --- tasks''), and network $G$ contains no positive-length cycles, then there is a single active schedule (which is, thereby, the optimal one), and this schedule can be found very efficiently, in $O(|V|\cdot|E|)$ time. (When $G$ contains no cycles at all, this can be done even faster, in $O(|E|)$ time.) Alternatively, when $G$ contains positive-length cycles (which can be established also in $O(|V|\cdot|E|)$ time), the given problem instance \textbf{has no feasible solutions}.

When, beyond precedence constraints, the problem under consideration has got also renewable resource constraints, the problem normally becomes NP-hard, and the set of all active schedules may have an exponential size. Such a situation takes place for the Job Shop problem (because each machine can be treated as a resource of renewable type), and that is why the problem is so hard for its optimal solution. In this paper, we overcome this obstacle by choosing (at Stage~7 of our algorithm) for each machine a certain processing order of its operations. (We thereby eliminate all resource constraints in the problem and come to the ``favorable'' situation, when there are only precedence constraints.) Our only concern in this case is to check that the precedence constraints we added (and embedded in network $G$) together with the original arcs of network $G$ do not form cycles of positive length. And this is done at Stage~7.


\medskip
In what follows, we will assume that the input jobs of the Job Shop problem are specified by a \textbf{list} (in arbitrary order), and the information about the operations of each job $J_j$ (the duration $p_{\eta,j}$ of each operation $O_{\eta,j}\in{\mathcal O}_j$ and machine $M(O_{\eta,j})$ on which it should be processed) is also specified in a list, according to the processing order of job operations. In these conditions, two simple approximation results (formulated below in Lemma \ref{le1}) are valid for the Job Shop problem.

Let ${\mathcal A}_{01}$ be the algorithm that schedules jobs sequentially, one after another (in an arbitrary order), without delay. Clearly, such a schedule $S_{01}$ can be computed in $O(|{\mathcal O}|)\le O(n\mu)$ time. 

Let ${\mathcal A}_{02}$ be another algorithm that schedules all operations level-by-level (for levels $\eta\in[\mu]$). To that end, it scans the list of jobs $\mu$ times, and at the $\eta$-th time (at \emph{Stage} $\eta\in[\mu]$), schedules all operations of the $\eta$-th level as follows. We define amounts $\bar{C}_{\eta}^i\ (\eta=0,1,\dots,\mu;\ i\in[m])$ which mean the maximum completion time over all operations of the $\eta$-th level on machine $M_i$ (where $\bar{C}_{0}^i\leftarrow 0,\ \forall\ i\in[m]$). At the beginning of Stage $\eta$ we first put $\bar{C}_{\eta}^i\leftarrow\bar{C}_{\eta-1}\doteq\max_{i\in[m]}\bar{C}_{\eta-1}^i$. Then, while considering operation $O_{\eta,j}$, we put $s_{\eta,j}\leftarrow\bar{C}_{\eta}^i$ (for machine $M_i=M(O_{\eta,j})$) and $\bar{C}_{\eta}^i\leftarrow\bar{C}_{\eta}^i+p_{\eta,j}$. Thus, the resulting schedule $S_{02}$ consists of $\mu$ \emph{layers}, and in each layer $\eta\in[\mu]$ (where all operations of the $\eta$-th level are processed), at least one machine works without idle time. The running time of this algorithm can be estimated as $O(|{\mathcal O}|+m\mu)\le O((n+m)\mu)$.

\begin{lemma}\label{le1}
Algorithm ${\mathcal A}_{01}$ finds an $m$-approximate schedule $S_{01}$ in time $O(n\mu)$.
Algorithm ${\mathcal A}_{02}$ finds a $\min\{m,\mu\}$-approximate schedule $S_{02}$ in time $O(n\mu+m\mu)$.
\end{lemma}

\begin{proof}
First, it should be observed that both schedules $S_{01}$ and $S_{02}$ meet the property: at each time moment during the makespan, at least one operation is being processed. This implies that the lengths of both schedules meet the bound: $C_{\max}(S_{x})\le P\le mL_{\max}$. Furthermore, since in each layer of schedule $S_{02}$ at least one machine is idles, the length of each layer is not greater than $L_{\max}$, which yields the bound: $C_{\max}(S_{02})\le \mu L_{\max}$. Recalling that $L_{\max}$ is the lower bound on the optimum, we get what is required in the lemma.
\end{proof}

The following theorem was proved in \cite{S91}.

\begin{theorem}[\cite{S91}]\label{th91}
Let $X=\{x_i\,|\,i\in[N]\}$ be a given family of $N$ vectors in~$\mathbb{R}^d$,\ s.t. $\sum_{x_i\in X} x_i=0$, and let $H(X)\doteq\mbox{\rm conv}\{X\}$ be its convex hull,\ $a\in\mathbb{R}^d$ be an arbitrarily chosen vector in $\mathbb{R}^d$,\ and $H_a(X)\doteq\mbox{\rm conv}\{0,a-H(X)/d\}$. Then a permutation $\pi=(\pi_1,\dots,\pi_N)$ of indices $\{1,\dots,N\}$ defining an order of summing the vectors of family $X$ can be found by algorithm ${\mathcal A}_1(d,a,N,X;\pi)$ in $O(N^2 d^{\,2})$ time, such that
\begin{equation}\label{eq5}
\sum_{i\in [k]} x_{\pi_i}\in (d-1)H(X)+H_a(X),\ \forall\ k\in[N].
\end{equation}
\end{theorem} 

(For the description of algorithm ${\mathcal A}_1$, we refer the reader to Appendix \ref{app2}.)



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Approximation algorithm ${\mathcal A}(\gamma)$ for the Job Shop problem}\label{sec3}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Algorithm ${\mathcal A}(\gamma)$ consists of a \emph{Preliminary Stage} and 7 \emph{basic stages}. The first three basic stages are destined to transform the given problem instance to a more suitable form. The other four stages are targeted to construct the desired schedule. First, we will clarify the destination of each stage. Then we start studying the operation of the algorithm stage by stage.

\medskip
At the \textbf{Preliminary Stage}, we compute the \emph{maximum processing time of an operation} ($p_{\max}\doteq\max_{\eta,j} p_{\eta,j}$),\ the total workload $L^i\doteq\sum_{O_{\eta,j}\in{\mathcal O}^i} p_{\eta,j}$\ of each machine $M_i$ (where ${\mathcal O}^i$ is the set of all operations to be processed on machine $M_i\ (i\in[m])$), and the \emph{maximum machine load} $L_{\max}\doteq\max_{i\in[m]}L^{i}$ (being, clearly, a lower bound on the optimum of the Job Shop problem).

\medskip
At \textbf{Stage 1}, a \emph{unification of job routes} through machines is performed, thereby eliminating the main obstacle of the Job Shop problem --- the differences in routes of different jobs! To that end, we make two job transformations.

(1) We equalize the number of operations of all jobs $j\in[n]$ up to the maximal one ($\mu_j\leftarrow\mu\doteq\max_j \mu_j$) by adding to each job $j\in[n]$ dummy operations of levels $\eta\in(\mu_j,\mu]$. Now, each job has got an operation of each \emph{level} $\eta\in[\mu]$.

(2) For each job $j\in[n]$, we expand the set of its operations of each level $\eta\in[\mu]$ from a single operation (to be processed on a certain machine) to $m$ operations, to be processed (independently of each other and even, maybe, simultaneously) on $m$ different machines. Thus, each such \emph{wide job} consists of $m\mu$ operations. All $m$ operations of level $\eta$ of any job $j$ have to follow all operations of the same job of smaller levels. Still, we do remember that each wide job at each level $\eta$ has \textbf{at most one real operation}. All other its operations are ``dummy'' ones, and initially receive zero processing times.

\medskip
At \textbf{Stage 2}, we \emph{equalize the workloads} $\{L^i\}$ of all machines $\{M_i\}$ by increasing the lengths of some operations (both real and dummy ones) up to at most $p_{\max}$, while keeping the values of $p_{\max}$ and $L_{\max}$ unchanged.

\medskip
At \textbf{Stage 3}, \emph{the set of $n$ wide jobs is extended by $N$ additional zero-length jobs}. All $\widetilde N\doteq n+N$ resulting jobs and their operations will then be called \emph{extended} ones.

As will be seen from bound (\ref{eq13b}) on the length of the schedule constructed by algorithm ${\mathcal A}(\gamma)$ (see page~\pageref{eq13b}), increasing the parameter $\widetilde{N}$ (present in the additive term $2(\mu-1) L_{\max}/\widetilde{N}$ in the bound on schedule length) reduces this bound. At the same time, the running time of the algorithm increases proportionally to the square of $\widetilde{N}$. Thus, the choice of a certain value of this parameter while implementing the algorithm is the result of a ``deal'' between two incomparable goals: the minimum of schedule length and the minimum of running time.

In the former version of the algorithm, when no new jobs were added to the original family of $n$ jobs (i.e., we used the minimum possible value $\widetilde{N}=n$ of this parameter), the additive term in the bound on schedule length depending on $\widetilde{N}$ was about $2\mu^2p_{\max}$. In the present paper, we set $\widetilde{N}=3n$ (tripling the number of jobs) and obtain a value of this term about $1/3$ of its maximum size. In principle, we could make this term arbitrarily close to zero by letting $\widetilde{N}$ tend to infinity. But this, clearly, would require too high cost (in terms of the running time).

The reasons for the influence of parameter $\widetilde{N}$ on the bound on schedule length may become clearer to the reader after heaving read the explanation of Stage~6 and the derivation of bound (\ref{eq13b}) in the proof of Lemma~\ref{le3}.

\medskip
At \textbf{Stage 4}, the Job Shop problem is approximately reduced to the problem of finding such an order of summing the vectors from a given family $X\in\mathbb{R}^{m\mu}$ (such that $|X|=\widetilde{N}$, and their sum is equal to zero) which satisfies inclusions (\ref{eq5}) (and exists due to Theorem~\ref{th91}). Each vector $x_j\in X$ corresponds to a certain extended job $j\in[\widetilde{N}]$, and the order (of vectors $\{x_j\}$) found at this stage is used in schedules defined at the subsequent stages of our algorithm as the order of job processing.

\medskip
At \textbf{Stage 5}, we define a preliminary (infeasible) \emph{table-based schedule} $S(\widetilde{T})$, where $\widetilde{T}$ is a $\mu\times\widetilde{N}$ table of integers. Its $j$th column corresponds to job $j\in[\widetilde{N}]$, and the order of columns is that found at Stage~4. Due to inclusions (\ref{eq5}), schedule $S(\widetilde{T})$ meets the property that for each job $j$ all its operations of the same level $\eta\in[\mu]$ are started at ``about the same time''. However, for  some $\eta$ and some job $j$, the pair of its consequent operations of levels $(\eta-1)$ and $\eta$ may violate the order of their processing prescribed in job $j$ (thereby providing an infeasible schedule). This shortcoming of schedule $S(\widetilde{T})$ will be corrected in the next stage.

\medskip
At \textbf{Stage 6}, we first observe a sharper property of schedule $S(\widetilde{T})$ (established in (\ref{eq10})):\ the completion time of an arbitrary operation $O_{\eta,k}^{\,i}(\widetilde{T})$ in this schedule ``nearly linearly'' depends on the \textbf{number $k$ of the column} in which this operation is located in table $\widetilde{T}$. More precisely, the completion time of any operation consists of three additive terms such that each incrementing of the parameter $k$ by 1 increases the first term by a \textbf{fixed amount} $L_{\max}/\widetilde{N}$, while the amounts of the other two terms are bounded from above by values \textbf{independent of} $k$. (This property of schedule will be further called a \emph{$\hat{k}$-property}.) Thus, the idea arises that in order to eliminate the infeasibility 
of schedule $S(\widetilde{T})$, table $\widetilde{T}$ should be transformed into a new table $\widehat{T}_{\gamma}$ (still maintaining the \emph{$\hat{k}$-property}), so as for each $\eta\in[\mu-1]$ each operation $\widetilde{O}_{\eta+1,j}^{\,i''}$ (i.e., an operation of the $(\eta+1)$-th level of an extended job~$j$) was localized (in the new table) \textbf{by $\gamma$ columns farther} (for a large enough~$\gamma$) than any operation $\widetilde{O}_{\eta,j}^{\,i'}$ (of the same job and of the $\eta$-th level). 

To perform this relative shift (of extended operations of level $(\eta+1)$ with respect to the same job operations of level $\eta$), we \textbf{add to the beginning of each row} $\eta\in[\mu]$ of table $\widetilde{T}$ exactly $\gamma(\eta-1)$ \textbf{extra cells} containing zeros (corresponding to dummy operations, further called \emph{S-dummy} ones). At that, the \emph{$\hat{k}$-property} remains valid due to the choice of the length of each S-dummy operation $\widehat{O}_{\eta}^{\,i}$ to be equal to the \textbf{average length} over all extended operations of machine $M_i$ and of level $\eta$.

As was said, the value of $\gamma$ should be large enough (to guarantee that the amount $\gamma L_{\max}/\widetilde{N}$ outperforms the maximum possible value of the two other terms (in total) in the right part of formula (\ref{eq10})). Ideally, it would be great if the amount $\gamma L_{\max}/\widetilde{N}$ was exactly equal to that maximum, because the increasing of $\gamma$ leads to increasing the length of schedule $S(\widehat{T}_{\gamma})$. Yet the matter is that $\gamma$ may take only \textbf{integral values}. As a consequence, the amount $\gamma L_{\max}/\widetilde{N}$ turns out to be greater than needed to guarantee the feasibility of schedule $S(\widehat{T}_{\gamma})$. In other words, we can observe here the familiar phenomenon of increasing the bound on some real-valued amount (in our case, of the $k$-independent part of terms in formula (\ref{eq10})) calculated in terms of an integral number of some fixed units (in our case, of units equal to $L_{\max}/\widetilde{N}$) by an amount comparable with the chosen unit ($L_{\max}/\widetilde{N}$). 

Yet, once we cannot avoid the above phenomenon (forced by the integral nature of the parameter $\gamma$), could we at least minimize its effect by decreasing the values of the units chosen for measuring? Trying to answer this question, we observe that it is possible to decrease our ``rounding error'' (in the bound on schedule length) by \textbf{increasing the value of the parameter} $\widetilde{N}$. This explains the \textbf{introduction of this parameter} at Stage 3 of our algorithm.

\medskip
At \textbf{Stage 7}, we construct an \emph{active schedule} $S_{\rm act}(\gamma)$ (see the definition of this notion on page \pageref{de0}) for the set of \textbf{original operations only.} To that end, we define a directed network $G(\gamma)$ specifying precedence constraints on the set of original operations (treated as nodes of the network). Since these constraints meet the order of these operations defined in the table-based schedule $S(\widehat{T}_{\gamma})$ (constructed at Stage~6 and feasible for certain values of $\gamma$), this guarantees (for the same values of $\gamma$) the existence of a feasible solution for the task scheduling problem ${\mathcal P}(\gamma)$ with precedence constraints specified by network $G(\gamma)$, and so, the existence and uniqueness of an active schedule for this problem. Moreover, we can prove that network $G(\gamma)$ is acyclic, which implies that for finding such an active schedule can be achieved by a simple algorithm in $O(|E|)$ time. Clearly, the length of the schedule found will meet the theoretical bounds derived on the length of schedule $S(\widehat{T}_{\gamma})$ (while its practical values should be, hopefully, much less). 
 
\medskip
We next proceed with a detailed description of our algorithm at stages.

\medskip\textbf{Stage 1} (unification of job routes through machines).\ 
While solving of the Flow Shop problem approximately by the compact vector summation method \cite{S75,S95}, we limited ourselves by constructing \emph{permutation schedules} only (specified by a single permutation of jobs), which made it possible to interpret the vector summation sequence found for the \emph{Compact Vector Summation problem} (the \emph{CVS-problem}) as a sequence of executing the corresponding jobs \textbf{by each machine}. At the same time, in the Job Shop problem we observe a radically different situation: instead of a unified ``job flow by machines'' (which in the Flow Shop problem is dictated by the technology of job execution on a \emph{flow line}) we observe here a family of \textbf{individual job routes by machines} (all of which may be different). And thus, it would seem that there can be no talk of any ``unified job flow''.

However, we will refute these doubts by unifying the routes of all jobs through machines in the Job Shop problem, which is the target of Stage 1. To do that, we extend the notion of a ``job'' by adding extra operations to each job. 

\begin{definition}\label{de1}\rm
Let $\mu\doteq\max_{j\in[n]}\mu_j$. We define a \emph{wide job} $\tilde{J}_j$ as a job consisting of $m\mu$ operations $\{O_{\eta,j}^{\,i}\,|\,i\in[m],\ \eta\in[\mu]\}$, where each operation $O_{\eta,j}^{\,i}$ (called a \emph{wide operation of the $\eta$-th level}) is to be processed on machine $M_i$ for $p_{\eta ,j}^{\,i}$ time units. We impose precedence constraints on the operations of job $\tilde{J}_j$:
\begin{equation}\label{eq5a}
O_{\eta,j}^{\,i'}\rightarrow O_{\eta+1,j}^{\,i''},\quad\forall\ i',i''\in[m],\ \eta\in[\mu-1],\ j\in[n].
\end{equation}
Meanwhile, no restrictions are imposed on the order of processing the operations from ${\mathcal O}_{\eta,j}\doteq \{O_{\eta,j}^{\,i}\,|\,i\in[m]\}$ (i.e., on the operations of the same level). Moreover, they can be processed \textbf{in parallel} (i.e., independently and, maybe, simultaneously, ignoring the fact of their belonging to the same wide job $\tilde{J}_j$). In this sense, the problem to be solved \textbf{extends the Job Shop problem}.
\end{definition}

The original problem instance with $n$ jobs is embedded into the model with $n$ wide jobs in an obvious way. Each real operation $O_{\eta,j}\ (\eta\in[\mu_j])$ of job $J_j$ coincides with the operation $O_{\eta,j}^{\,i}$ such that $M_i=M(O_{\eta,j})$ and has the same duration: $p_{\eta,j}^{\,i}=p_{\eta,j}$, while the durations of all other (new) operations of job $\tilde{J}_j$ are set to zero. (At Stage 2 these durations will be transformed.)

The feasibility of precedence constraints $O_{\eta,j}\rightarrow O_{\eta+1,j}$ for the original operations of job $J_j$ follows from (\ref{eq5a}). Meanwhile, it can be seen that constraints (\ref{eq5a}), while being \textbf{sufficient} for constructing a feasible schedule for each original job $J_j$, are obviously redundant. This gives hope that the \emph{a posteriori} accuracy bound computed for the solution obtained by our algorithm for each given instance of the Job Shop problem may appear to be much better than its theoretical \emph{a priori} bound. (This conclusion becomes even more obvious after analyzing our actions being performed in the subsequent stages of this algorithm.)


\medskip\textbf{Stage 2} (equalization of machine workloads).\ 
We compute the amounts $p_{\max}\doteq\max_{\{i,\eta,j\}} p_{\eta,j}^{\,i}$,\ $L_{\eta}^{\,i}\doteq\sum_{j\in[n]} p_{\eta,j}^{\,i}$, and the \emph{workload} $L^{\,i}\doteq\sum_{\eta\in[\mu]} L_{\eta}^{\,i}$ of each machine $M_i$. Since each machine now performs the same number of operations ($\mu n$), we can equalize the workloads of all machines up to the amount $L_{\max}\doteq\max_{i\in[m]}\ L^{\,i}$ by increasing arbitrarily the durations of some operations $O_{\eta,j}^{\,i}$ up to some amounts $\tilde{p}_{\eta ,j}^{\,i}\le p_{\max}$. As a result of this alignment of the machine workloads, vectors $\tilde{p}_j\doteq\{\tilde{p}_{\eta ,j}^{\,i}\,|\,i\in[m],\ \eta\in[\mu]\}\in\mathbb{R}^{m\mu}\ (j\in [n])$  of operation durations will be obtained for all wide jobs $\{\tilde{J}_j\,|\,j\in[n]\}$, with a total vector $\sum_{j\in[n]}\tilde{p}_j=\tilde{L}\doteq\{\tilde{L}_{\eta}^{\,i}\,|\,i\in[m],\ \eta\in[\mu]\}\in\mathbb{R}^{m\mu}$ such that $\tilde{L}_{\eta}^{\,i}\doteq\sum_{j\in[n]} \tilde{p}_{\eta,j}^{\,i}$ and
\begin{equation}\label{eq6}
\tilde{L}^{\,i}\doteq\sum_{\eta\in[\mu]}\tilde{L}_{\eta}^{\,i}=L_{\max},\ \forall\ i\in[m],
\end{equation}
\begin{equation}\label{eq7}
\tilde{L}_{\eta}^{\,i}\le np_{\max},\ i\in[m],\ \eta\in[\mu].
\end{equation}


\medskip\textbf{Stage 3} (extending the set of wide jobs).\ 
We extend the set of $n$ wide jobs by adding $N$ new wide jobs of zero length.
(The corresponding vectors $\tilde{p}_j$ for all new jobs are set to zero, which leaves the values of all quantities $\{\tilde{L}_{\eta}^{\,i},\ \tilde{L}^{\,i}\},\ L_{\max}$, and $p_{\max}$ unchanged.) Denote by $\widetilde{\mathcal J}$ the resulting (``extended'') set of jobs; $\widetilde{N}\doteq n+N=|\widetilde{\mathcal J}|$. All jobs from $\widetilde{\mathcal J}$ and their operations will be referred to as ``extended jobs'' and ``extended operations'', and denoted as $\tilde{J}_j$ and $\widetilde{O}_{\eta,j}^{\,i}$, respectively. (At that, the last $N$ jobs $\tilde{J}_j\in\widetilde{\mathcal J}$ have vectors $\tilde{p}_j=\textbf{0}$.) 

As will be seen later, increasing the number $\widetilde{N}$ leads to reducing the upper bound on schedule length. On the other hand, this naturally increases the running time of the vector summation procedure (used at Stage 4 of algorithm ${\mathcal A}(\gamma)$) and of the algorithm ${\mathcal A}(\gamma)$ at its subsequent stages (while constructing a feasible schedule). This, however, can be treated as a fair price for improving its accuracy bound. We could leave the final decision on the choice of the value of $\widetilde{N}$ to each particular user of our algorithm. However, we will make a definite choice of this value in this paper, in order to obtain definite bounds on the accuracy and the running time of our algorithm, formulated in Theorem \ref{th2} (page \pageref{th2}).


\medskip\textbf{Stage 4} (reducing the Job Shop problem to the vector summation problem and applying Theorem \ref{th91}).\ 
Let $d=m\mu$,\ $B\doteq[0,p_{\max}]^d$ be a $d$-dimensional cube in $\mathbb{R}^d_{+}$. Then $\sum_{j\in[\widetilde{N}]}\tilde{p}_j=\tilde{L}$ and $\tilde{p}_j\in B$ for all $j\in[\widetilde{N}]$. If to compute the \emph{average vector} $\bar p_{\rm ave}\doteq\tilde{L}/\widetilde{N}$ of family $\{\tilde{p}_j\,|\,j\in[\widetilde{N}]\}$, we can define vectors $p_j'\doteq\tilde{p}_j-\bar p_{\rm ave}$ forming a so called \emph{Steinitz family of vectors}, i.e., a vector family $X=\{p_j'\in\mathbb{R}^d\,|\,j\in[\widetilde{N}]\}$ satisfying the properties:

\medskip
\begin{center}
$\sum_{j\in[\widetilde{N}]}\ p_j'=0,$\\[1ex]
$p_j'\in B'\doteq B-\bar p_{\rm ave}.$
\end{center}
%
\medskip
This enables us to apply Theorem \ref{th91} to vector family $X$ and find a permutation $\pi^*=(\pi_1^*,\dots,\pi_{\widetilde{N}}^*)$ of indices $\{1,\dots,\widetilde{N}\}$ satisfying the inclusions:

\medskip
\begin{center}
$\sum_{j\in [k]}\ p_{\pi_j^*}'\in (d-1)H(X)+H_a(X)\subseteq (d-1)B'+B'_a,\ \forall\ k\in[\widetilde{N}],$
\end{center}
%
\medskip
where $B'_a\doteq\mbox{\rm conv}\{0,a-B'/d\}$. Since\ $-B=B-\mathbf{b}$\ for vector $\mathbf{b}\doteq(p_{\max},\dots,p_{\max})$ $\in\mathbb{R}^{d}$, we have $a-B'/d=a-B/d+\bar p_{\rm ave}/d=a+(B-\mathbf{b}+\bar p_{\rm ave})/d$. Choosing $a=(\mathbf{b}-\bar p_{\rm ave})/d$, we obtain $a-B'/d=B/d\ni 0$, implying the equality $B'_a=B/d$ and the inclusion

\medskip
\begin{center}
$\sum_{j\in [k]}\ \tilde{p}_{\pi_j^*}-k\bar p_{\rm ave}\in (d-1)(B-\bar p_{\rm ave})+B/d=\alpha(d)B - (d-1)\bar p_{\rm ave}$
\end{center}
\medskip
for $\alpha(d)\doteq d-1+1/d$. Thus, we obtain the following

\begin{corollary}\label{co1}
Algorithm ${\mathcal A}_1$ from Theorem \ref{th91} finds in $O(m^2\mu^2 \widetilde{N}^2)$ time a permutation $\pi^*=(\pi_1^*,\dots,\pi_{\widetilde{N}}^*)$ of indices $\{1,\dots,\widetilde{N}\}$ such that
\begin{equation*}%\label{eq8}
\sum_{j\in [k]} \tilde{p}_{\pi_j^*} = (k-d+1)\bar p_{\rm ave}+\alpha(d)\,\delta_k,\ \forall\ k\in[\widetilde{N}],
\end{equation*}
where $d=m\mu$, $\delta_k=\{\delta_{\eta ,k}^{\,i}\in[0,p_{\max}]\,|\,i\in[m],\ \eta\in[\mu]\}\in B$.
\end{corollary}
%
In the coordinate form, these relations look like:  
\begin{equation}\label{eq9}
\sum_{j\in [k]} \tilde{p}_{\eta,\pi_j^*}^{\,i}= \frac{k-d+1}{\widetilde{N}}\tilde{L}_{\eta}^{\,i}+\alpha(d)\,\delta_{\eta ,k}^{\,i},\ \forall\ i\in[m],\ \eta\in[\mu],\ k\in[\widetilde{N}].
\end{equation}


\medskip\textbf{Stage 5} (defining a preliminary infeasible schedule $S(\widetilde{T})$).\ 

\begin{definition}\label{de2}\rm
Let a set ${\mathcal O}'$ of $m\mu N'$ operations (including all \emph{extended operations}, defined at Stage 3, and \emph{S-dummy operations}, to be presented at Stage 6) has to be processed on $m$ machines ($\mu N'$ operations per machine). To define a \emph{table-based schedule} $S(T')$ for processing the operations from ${\mathcal O}'$, we first define a two-dimensional table $T'$ with $\mu$ \emph{rows} and $N'\ge\widetilde{N}$ \emph{columns}. Each cell \mbox{$T'(\eta,j)\ (\eta\in[\mu]$,} $j\in[N'])$ of table $T'$ contains an integer value, which is either the index $k\in [\widetilde{N}]$ of an extended job $\tilde{J}_k$, or zero (corresponding to an S-dummy operation). In both cases, row number $\eta$ specifies level $\eta$ of the operation. Each row $\eta\in[\mu]$ contains all job indices from 1 to $\widetilde{N}$, where each job index $k\in[\widetilde{N}]$ is presented exactly once. Thus, each row $\eta$ of $T'$ represents a sequence of $(N'-\widetilde{N})$ zeros and $\widetilde{N}$ pair-wise different indices from 1 to $\widetilde{N}$, and thereby, specifies an order of processing the extended operations of the $\eta$-th level \textbf{on every machine} (because for each row $\eta\in[\mu]$, these orders will be \textbf{identical} in schedule $S(T')$ for all machines $M_i,\ i\in[m]$). For each machine $M_i$, all S-dummy operations ``of the $\eta$-th level'' (if any) will have identical durations (equal to the average duration over all extended operations of the $\eta$-th level on machine $M_i$) and will not be distinguished from each other in schedule $S(T')$.

Next, we define \emph{the full sequence ${\mathcal P}(T')$ of elements} $(\eta,j)$ of table $T'$. In this sequence, the elements follow column-by-column (in the order $j=1,\dots,N'$), and for each column, in the increasing order of row indices ($\eta=1,\dots,\mu$). So, 
\begin{equation}\label{eq8}
{\mathcal P}(T'):\ (1,1),(2,1),\dots,(\mu,1),(1,2),\dots,(\mu,2),\dots,(1,N'),\dots,(\mu,N').
\end{equation}
Let ${O}_{\eta ,j}^{\,i}(T')$ denote the operation from ${\mathcal O}'$ processed by machine $M_i$ and specified by cell $T'(\eta,j)$ of table $T'$. Then the operations \textbf{on each machine} $M_i$ should be processed in schedule $S(T')$ from time zero and on, without an idle time, in the \emph{universal order} specified by sequence ${\mathcal P}(T')$:\ 
$${O}_{1,1}^{\,i}(T'),\dots,{O}_{\mu,1}^{\,i}(T'),{O}_{1,2}^{\,i}(T'),\dots,{O}_{\mu,2}^{\,i}(T'),\dots,{O}_{1,N'}^{\,i}(T'),\dots,{O}_{\mu,N'}^{\,i}(T').$$ 
\end{definition}

Denoting for each operation ${O}_{\nu ,j}^{\,i}(T')\in{\mathcal O}'$ its duration by $\hat{p}_{\nu ,j}^{\,i}(T')$, and its completion time in schedule $S(T')$ by $\hat{c}_{\nu ,j}^{\,i}(T')$, we can derive the equalities:
\begin{equation}\label{eq9a}
\hat{c}_{\eta,k}^{\,i}(T')=\sum_{\nu=1}^{\eta}\sum_{j\in[k]} \hat{p}_{\nu ,j}^{\,i}(T')+\sum_{\nu=\eta+1}^{\mu}\sum_{j\in[k-1]} \hat{p}_{\nu ,j}^{\,i}(T'),\quad \eta\in[\mu],\ k\in[N'].
\end{equation}

Now let the set $\widetilde{\mathcal O}$ of \emph{extended operations} introduced at Stage 3 be taken for the set of operations ${\mathcal O}'$. For table $T'$, we take the $\mu\times\widetilde{N}$ table $\widetilde{T}$ in which all extended operations of the $\nu$-th level ($\nu\in[\mu]$) are presented by the $\nu$-th row and are ordered according to permutation $\pi^*=(\pi_1^*,\dots,\pi_{\widetilde{N}}^*)$ of job indices found at Stage~4, while the operations of column $j$ represent the operations of the extended job $\tilde{J}_{\pi_j^*}$ on any machine $M_i$. Thus, no zeros (corresponding to S-dummy operations) are in table $\widetilde{T}$, because each cell $\widetilde{T}(\eta,j)$ of table $\widetilde{T}$ contains the value $\pi_j^*\in[\widetilde{N}]$. Then, for the table-based schedule $S(\widetilde{T})$ (see Definition \ref{de2} above), by means of (\ref{eq9a}), (\ref{eq9}), and (\ref{eq6}) (with $\tilde{L}_{\nu}^{\,i}=\sum_{j\in[\widetilde{N}]} \tilde{p}_{\nu,j}^{\,i}$), we can derive the following relations:
%
\begin{eqnarray}\label{eq10}
\quad\hat{c}_{\eta,k}^{\,i}(\widetilde{T})&=&\frac{k-d+1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i}+\frac{k-d}{\widetilde{N}}\!\!\!\sum_{\nu=\eta+1}^{\mu}\tilde{L}_{\nu}^{\,i}+ \alpha(d)\!\sum_{\nu=1}^{\mu}\delta_{\nu ,k'(k,\nu,\eta)}^{\,i}\\ &=& \frac{k-d}{\widetilde{N}}L_{\max} +\frac{1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i}+\alpha(d)\!\sum_{\nu=1}^{\mu}\delta_{\nu ,k'(k,\nu,\eta)}^{\,i} \nonumber
\end{eqnarray}
which hold for all $i\in[m],\ \eta\in[\mu],\ k\in[\widetilde{N}]$ (with $k'(k,\nu,\eta)=k$ for $\nu\le\eta$, and $k'(k,\nu,\eta)=k-1$ for $\nu>\eta$). As one can see, each schedule $S_i(\widetilde{T})$ for the operations from $\widetilde{\mathcal O}_i\doteq \{\widetilde{O}_{\eta,j}^{\,i}\,|\,\eta\in[\mu],\ j\in[\widetilde{N}]\}$ is feasible, since all operations of each extended job $\tilde{J}_{\pi_j^*}$ ($j\in[\widetilde{N}]$) on machine $M_i$ are localized in column $j$ of table $\widetilde{T}$, and so, are processed in the increasing order of their levels. Yet for the feasibility of the overall schedule $S(\widetilde{T})$, we also need fulfilling the requirements (\ref{eq5a}) for all pairs $(\widetilde{O}_{\eta,\pi_j^*}^{\,i'}, \widetilde{O}_{\eta+1,\pi_j^*}^{\,i''})$ of extended operations of job $\tilde{J}_{\pi_j^*}$ that are to be processed on \textbf{different machines}. Since operation $\widetilde{O}_{\eta,\pi_j^*}^{\,i'}$ is localized in the $j$-th column of $\widetilde{T}$, its completion time $c_{\eta,\pi_j^*}^{\,i'}$ coincides with $\hat{c}_{\eta,j}^{\,i'}(\widetilde{T})$, while the starting time $s_{\eta+1,\pi_j^*}^{\,i''}$ of operation $\widetilde{O}_{\eta+1,\pi_j^*}^{\,i''}$ coincides with $\hat{c}_{\eta,j}^{\,i''}(\widetilde{T})$. Thus, all precedence constraints (\ref{eq5a}) may be satisfied, if and only if the relations 
$$0\le s_{\eta+1,j}^{\,i''} - c_{\eta,j}^{\,i'} = \hat{c}_{\eta,j}^{\,i''}(\widetilde{T}) - \hat{c}_{\eta,j}^{\,i'}(\widetilde{T})$$
hold for all $i',i''\in[m],\ \eta\in[\mu-1],\ j\in[\widetilde{N}]$. Clearly, this is possible only in the ideal (unlikely) case, when for each $\eta\in[\mu-1]$ and $j\in[\widetilde{N}]$, all completion times $\{\hat{c}_{\eta,j}^{\,i}(\widetilde{T})\,|\,i\in[m]\}$ coincide in schedule $S(\widetilde{T})$.


\medskip\textbf{Stage 6} (defining a feasible table-based schedule $S(\widehat{T})$).\ The solution of the above problem is facilitated by the following \textbf{Observation} about the dependence of quantities $\hat{c}_{\eta,k}^{\,i}(\widetilde{T})$ on parameter $k$ according to formula (\ref{eq10}) (i.e., the dependence of the completion time of an arbitrary operation $O_{\eta,k}^{\,i}(\widetilde{T})$ in schedule $S(\widetilde{T})$ on the \textbf{number $k$ of the column} in which this operation is located in table $\widetilde{T}$): \textbf{each incrementing the parameter} $k$ by 1 is accompanied by an increase in the first term on the right-hand side of (\ref{eq10}) by a \textbf{fixed amount} $L_{\max}/\widetilde{N}$, while the other two terms are bounded from above by values \textbf{independent of} $k$. This property of schedule $S(\widetilde{T})$ (i.e., the ``almost linear'' growth of the completion time of operation $O_{\eta,k}^{\,i}(\widetilde{T})$ depending on the column number $k$) will be briefly called a \emph{$\hat{k}$-property}.

This Observation provides the following idea of defining a feasible table-based schedule: table $T'=\widetilde{T}$ should be transformed into a new table $\widehat{T}_{\gamma}$, so as for each $\eta\in[\mu-1]$ each operation $\widetilde{O}_{\eta+1,j}^{\,i''}$ (i.e., an operation of the $(\eta+1)$-th level of an extended job $\tilde{J}_j$) would be localized in the new table \textbf{by $\gamma$ columns farther} (for a large enough $\gamma$) than any operation $\widetilde{O}_{\eta,j}^{\,i'}$ (of the same job) of the $\eta$-th level. To provide this relative shifting of extended operations of the $(\eta+1)$-th level with respect to the corresponding operations of the $\eta$-th level, we \textbf{add to the beginning of each row} $\eta\in[\mu]$ of table $\widetilde{T}_{\gamma}$ exactly $\gamma(\eta-1)$ \textbf{extra cells} containing zeros. For each $i\in[m]$, they will correspond to that many \emph{shifting dummy} (or \emph{S-dummy}, for short) \emph{operations} $\{\widehat{O}_{\eta}^{\,i}\}$ of length $\hat{p}_{\eta}^{\,i}\doteq\tilde{L}_{\eta}^{\,i}/\widetilde{N}$ to be processed in  schedule $S(\widehat{T}_{\gamma})$ on machine $M_i$ (as described in Definition \ref{de2}). Furthermore, to keep the balance of the number of operations in all rows of table $\widehat{T}_{\gamma}$, we also add $\gamma(\mu-\eta)$ extra cells with zeros \textbf{to the end of each row} $\eta\in[\mu]$ (see Fig.~\ref{fig2}). Thus, each row $\eta\in[\mu]$ of table $\widehat{T}_{\gamma}$ contains $\widehat{N}(\gamma)\doteq\widetilde{N}+\gamma(\mu-1)$ cells corresponding to operations $\{{O}_{\eta,j}^{\,i}(\widehat{T}_{\gamma})\,|\,j\in[\widehat{N}(\gamma)],\ \eta\in[\mu]\}$ for any $i\in[m]$.

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=1,
TR/.style={thin}, %
NR/.style={thick}, %
GR/.style={very thick}, %
Hyp/.style={dashed}] %
\draw (0.2,7.2) node[anchor=west] {/\emph{Levels}}; %
\draw (0.2,7.6) node[anchor=west] {\emph{Rows}}; %
\draw (7.2,7.6) node[anchor=south] {\LARGE\emph{Columns}}; %
\foreach  \y in {6.5,6,5,4.5,4,3} %
\draw[NR] (2,\y) -- (12.5,\y); %
\draw[NR] (0.56,8.08) -- (2,7); %
\draw[Hyp] (6.1,7) -- (12.5,3); %
\draw[Hyp] (2,6.5) -- (8.4,2.5); %
\foreach  \x/\y/\z/\t in {2/6.5/6.1/7,2.8/6/6.9/6.5,5.2/4.5/9.3/5,6/4/10.1/4.5,8.4/2.5/12.5/3} %
\draw[fill=blue!20!white] (\x,\y) rectangle (\z,\t); %
\foreach  \x in {7.7,8.2,8.5,9,12} %
\draw[TR] (\x,7) -- (\x,2.5); %
\draw[TR] (2.5,7) -- (2.5,6.5); %
\draw[TR] (5.6,7) -- (5.6,6.5); %
\foreach  \x/\y/\z/\t in {7.7/4.5/8.2/5,8.5/4/9/4.5} %
\draw[fill=blue!40!white] (\x,\y) rectangle (\z,\t); %
\draw[->] (6.9,5.2) -- (7.95,5.2) -- (7.95,5); %
\draw[->] (9.8,5.2) -- (8.75,5.2) -- (8.75,4.5); %
\draw (7.3,5.2) node[anchor=south] {$O_{\eta,k}^{\,i'}$}; %
\draw (9.6,5.2) node[anchor=south] {$O_{\eta+1,k}^{\,i''}$}; %
\foreach  \x/\xtext in {2.25/1,4.1/\dots,5.85/\widetilde{N},6.9/\dots,7.95/j,8.8/(\!j\!+\!\gamma\!),10.5/\dots,12.1/\widehat{N}\!(\!\gamma\!)} %
\draw (\x,7.05) node[anchor=south] {{\boldmath $\xtext$}}; %
\foreach  \y/\xtext in {6.75/1,6.25/2,5.5/\vdots,4.75/\eta,4.25/\eta+1,3.5/\vdots,2.75/\mu} %
\draw (1.1,\y) node {{\boldmath $\xtext$}}; %
\draw (2.4,6.15) node[anchor=north] {$\underbrace{\rule{22pt}{0pt}}$}; %
\draw (2.4,5.85) node[anchor=north] {$\gamma$}; %
\draw (4,4.15) node[anchor=north] {$\underbrace{\rule{114pt}{0pt}}$}; %
\draw (4,3.85) node[anchor=north] {$\gamma\eta$}; %
\draw[GR] (0.3,2.5) -- (12.5,2.5); %
\draw[GR] (0.3,7) -- (12.5,7); %
\draw[GR] (2,8.08) -- (2,2.5); %
\draw[GR] (12.5,8.08) -- (12.5,2.5); %
\end{tikzpicture}
\rule{0pt}{55.8mm}
\end{center}
\caption{The construction of Table $\widehat{T}_{\gamma}$}\label{fig2}
\end{figure}

To summarize the above said about the structure of Table $\widehat{T}_{\gamma}$, we would like to highlight the following its properties.

\medskip
(a$^*$) Each cell $(\eta,j)$ of Table $\widehat{T}_{\gamma}$ corresponds either to $m$ extended operations (of the same extended job $\tilde{J}_{\pi_{\!\ell}^*}$, with $\ell\doteq j-\gamma(\eta-1)$, in case $\ell\in[\widetilde{N}]$, when we deal with an e-cell), or to $m$ S-dummy operations (related to no jobs, in case $\ell\not\in[\widetilde{N}]$).

\medskip
(b$^*$) Not every e-cell $(\eta,j)$ corresponds to \emph{original operations} (being a part of the input instance of the Job Shop problem). The necessary and sufficient conditions for such a correspondence are:\\[1ex]
\rule{2em}{0pt} (0$^*$) $\ell\doteq j-\gamma(\eta-1)\in[\widetilde{N}]$ (which means that we deal with an extended job);\\
\rule{2em}{0pt} (1$^*$) $k\doteq\widehat{T}_{\gamma}(\eta,j)\in[n]$ (which means that we deal with an original job $J_k$);\\
\rule{2em}{0pt} (2$^*$) $\eta\le\mu_k$ (means that we deal with a true level of operations of job $J_k$).

\medskip
(c$^*$) If a cell meets all above conditions, then it corresponds to the \textbf{unique original operation}, namely, $O_{\eta,j}^{\,\hat{i}(\eta,k)}(\widehat{T}_{\gamma})=O_{\eta,k}$ (the $\eta$-th level operation of job $J_k$ to be processed on machine $M_{\hat{i}(\eta,k)}\doteq M(O_{\eta,k})$).

\medskip
(d$^*$) \textbf{Every original operation} is represented in Table $\widehat{T}_{\gamma}$ \textbf{exactly once}.

\medskip
(e$^*$) For each $i\in[m]$, the sub-sequence of sequence ${\mathcal P}(\widehat{T}_{\gamma})$ composed of all cells representing the original operations of machine $M_i$ specifies the order of processing these operations in schedule $S(\widehat{T}_{\gamma})$.

\medskip
This completes the description of Table $\widehat{T}_{\gamma}$. 
As will be shown in the proof of Lemma~\ref{le2} (Sect.~\ref{sec4}), assigning to each copy of the S-dummy operation $\widehat{O}_{\eta}^{\,i}$ the same length $\hat{p}_{\eta}^{\,i}=\tilde{L}_{\eta}^{\,i}/\widetilde{N}$ preserves the $\hat{k}$-property for the table-based schedule $S(\widehat{T}_{\gamma})$, while a proper choice of the value of $\gamma$ ensures the feasibility of schedule $S(\widehat{T}_{\gamma})$.

\medskip\textbf{Stage 7} (computing the feasible active schedule $S_{\rm act}(\gamma)$).\ We define a precedence graph $G(\gamma)$ on the set ${\mathcal O}=\{O_{\eta,k}\}$ of \emph{original operations} (``\emph{o-os}'', for short) treated as nodes of the graph. The precedence on the set of operations is defined according to the order of operations of each job (provided by the input data) and to the order of operations on each machine in schedule $S(\widehat{T}_{\gamma})$. More precisely, for each o-o $O_{\eta,k}$ we specify at most two outgoing arcs: a job-based arc directed to o-o $O_{\eta+1,k}$ (if $\eta <\mu_k$) and a machine-based arc directed to the o-o $O_{\eta'\!,k'}$, directly succeeding operation $O_{\eta,k}$ on machine $M(O_{\eta,k})$ in schedule $S(\widehat{T}_{\gamma})$ (if such an o-o $O_{\eta'\!,k'}$ exists). For the weights of nodes $O_{\eta,k}\in G(\gamma)$ we take the original durations of these operations (valid before performing Stage~2).

Next, we present the most efficient algorithm for implementing this stage in $O(|{\mathcal O}|)$ time. To do this, we load all the initial information about the set ${\mathcal O}=\{O_{\eta,k}\}$ of o-os into an array $A[1..\mu; 1..n]$, so that for any job number $k\in[n]$ and any level $\eta\in[\mu_k]$ of its operation we could add and extract all necessary information on operation $O_{\eta,k}$ in $O(1)$ time. (Such a transformation of the input data can be performed in time linear in the number of o-os.) In addition to the original duration $p[\eta,k]=p_{\eta,k}$ of operation $O_{\eta,k}$ and the number $\hat{i}[\eta,k]$ of the machine executing it, the cell $A[\eta,k]$ will contain: (a) indices $(\eta'[\eta,k],k'[\eta,k])$ of the o-o $O_{\eta'[\eta,k],k'[\eta,k]}$ \emph{directly succeeding} operation $O_{\eta,k}$ on machine $M_{\hat{i}[\eta,k]}$, and (b) the number $ent[\eta,k]$ of arcs entering operation-node $O_{\eta,k}$ in graph $G(\gamma)$. Clearly, $ent[\eta,k]\le 2$ for any node $O_{\eta,k}$, where at most one of two entering arcs may be job-based (it can be obtained from the input data) and at most one may be machine-based (can be obtained from table $\widehat{T}_{\gamma}$). 

All job-based arcs are of the form $(O_{\eta,k},O_{\eta+1,k})$, and so, provide a straightforward information for graph $G(\gamma)$. In particular, these arcs contribute 1 point to parameters $ent[\eta,k]$ for each node $O_{\eta,k}$ with $\eta\in\{2,\dots,\mu_k\}$ (so that we can put at once: $ent[1,k]\leftarrow 0$ and $ent[\eta,k]\leftarrow 1$ for all $\eta\in\{2,\dots,\mu_k\},\ k\in[n]$).

Meanwhile, to get the information on the machine-based arcs, we have to scan the elements of table $\widehat{T}_{\gamma}$ according to their \emph{full sequence} ${\mathcal P}(\widehat{T}_{\gamma})$ defined in (\ref{eq8}) (i.e., column-by-column, and for each column, in the increasing order of row indices). At that, we would like to skip scanning the cells corresponding to S-dummy operations. In other words, we would like to scan \textbf{the sub-sequence} ${\mathcal P}'(\widehat{T}_{\gamma})$ of sequence ${\mathcal P}(\widehat{T}_{\gamma})$ containing only \emph{e-cells} (the cells corresponding to \emph{extended operations}). 

This can be done due to two things:

(1) to the special structure of table $\widehat{T}_{\gamma}$, where in each row $\eta\in[\mu]$ its e-cells follow as a solid segment of length $\widetilde{N}$ (further referred to as an \emph{e-segment}), and for each $\eta\in[\mu-1]$, e-segment of row $(\eta+1)$ is shifted by $\gamma$ positions to the right relative to the e-segment of row $\eta$ (see Fig.~\ref{fig2}); 

(2) to the choice of the value $\gamma=\gamma^*$ (defined in Lemma~\ref{le3}, page~\pageref{le3}).

\medskip
The following observation can be directly deduced from these two points.

\begin{observation}
(a) cells $(1,1)$ and $(\mu,\widehat{N}(\gamma))$ of table $\widehat{T}_{\gamma}$ are e-cells;\\
(b) if $(\eta,k)$ is an e-cell and $(\eta,k)\ne(\mu,\widehat{N}(\gamma))$, then at least one of three cells $(\eta+1,k),(\eta,k+1),(\eta+1,k+1)$ is an e-cell.
\end{observation}

(Here (a) follows from the construction of table $\widehat{T}_{\gamma}$, and (b) holds due to the inequality $\gamma^*\le\widetilde{N}$, where $\widetilde{N}$ is the length of each e-segment of table $\widehat{T}_{\gamma}$.)

These properties of table $\widehat{T}_{\gamma}$ enable us to design the following efficient procedure for scanning all e-cells of table $\widehat{T}_{\gamma}$ in $O(\mu\widetilde{N})$ time (receiving in parallel the missing information on graph $G(\gamma)$).

\medskip
\begin{center}
\textbf{Procedure} \emph{Scanning} (\mbox{\textbf{integer:}} $\gamma$;\ \mbox{\textbf{array of integers:}} $\pi^*[1..\widetilde{N}]$,
$\eta'[1..\mu{;}1..n], k'[1..\mu{;}1..n])$; 
\end{center}
\%\ Although the procedure is dedicated to scanning the cells of table $\widehat{T}_{\gamma}$, the latter\\
\%\ \textbf{is not presented at the input} of the procedure in an explicit form (for example,\\
\%\ as an array $\widehat{T}_{\gamma}[1..\mu {;} 1..\widehat{N}(\gamma)]$). Instead, at the INPUT, we are given an integer $\gamma$\\
\%\ and the array of integers $\pi^*[1..\widetilde{N}]$ specifying the permutation $\pi^*$ of indices $j\in[\widetilde{N}]$\\
\%\ of the extended jobs, found at Stage 4 of algorithm ${\mathcal A}(\gamma)$. These two parameters,\\
\%\ along with $\mu$, provide the complete information on table $\widehat{T}_{\gamma}$, which enables us\\
\%\ to do without a direct operation with table $\widehat{T}_{\gamma}$ when performing the procedure.\\
\%\ (We will just ``keep it in mind''.)\\
\%\ Formal parameters $\eta'[\eta{,}k], k'[\eta{,}k]$ accumulate the indices of the o-o directly suc-\\
\%\ ceeding $O_{\eta{,}k}$ on machine $M_{\hat{i}[\eta{,}k]}$. They represent the OUTPUT of the procedure.\\
\%\ In the body of procedure \emph{Scanning} it is assumed that parameters $m,n,\mu,\widehat{N}(\gamma),\mu_k$\\
\%\ $(k\in[n]),\hat{i}[\eta{,}k],p_{\eta,k}\ (k\in[n], \eta\in[\mu_k])$ are \textbf{global ones}.\\[0.5em]
%
\%\ \textbf{Local parameters:}\\
\textbf{integer:}\ $i,j,k,\eta,\eta^*,\eta^{\#},j^{\#}$;\\
\textbf{array of integers:}\ $\eta_c[1..m],\ k_c[1..m]$;\\
\%\ for each $i\in[m]$, they keep the indices $(\eta,k)$ of the last found o-o $O_{\eta,k}$ of machine\\
\%\ $M_i$ among currently scanned e-cells of table $\widehat{T}_{\gamma}$.

By $\eta^*$ and $j^{\#}$, we will denote the indices of the \emph{base row} and the \emph{current column} of table $\widehat{T}_{\gamma}$,  such that in all rows $\eta<\eta^*$ and all columns $j<j^{\#}$, all e-cells have been already scanned;\ $(\eta^{\#},j^{\#})$ will denote the e-cell being currently scanned.\\[1em]
\textbf{BEGIN}

$k_c[i]\leftarrow 0,\ \forall\ i\in[m]$;\ $(\eta',k')[\eta,k]\leftarrow (0,0),\ \forall\ k\in[n], \eta\in[\mu_k]$;

$\eta^*\leftarrow 1;\ \eta^{\#}\leftarrow 1;\ j^{\#}\leftarrow 1$;

\textbf{repeat}\ \%\ scanning the current e-cell $(\eta^{\#},j^{\#})$ of table $\widehat{T}_{\gamma}$\\
\rule{2em}{0pt} $j\leftarrow j^{\#}-\gamma(\eta^{\#}-1);\ k\leftarrow\pi_j^*$;\\ 
\rule{2em}{0pt} \textbf{if} $(k\le n)\ \&\ (\eta^{\#}\le\mu_k)$ \textbf{then begin}\ \%\ an o-o $O_{\eta^{\#},k}$ is found\\ 
\rule{3em}{0pt} $i\leftarrow\hat{i}(\eta^{\#},k)$;\ \textbf{if} $k_c[i]> 0$ \textbf{then}\\ 
\rule{4em}{0pt} $\{\eta'[\eta_c[i],k_c[i]]\leftarrow\eta^{\#};\ k'[\eta_c[i],k_c[i]]\leftarrow k;\ ent[\eta^{\#},k]\leftarrow ent[\eta^{\#},k]+1\}$;\\
\rule{3em}{0pt} $\eta_c[i]\leftarrow\eta^{\#};\ k_c[i]\leftarrow k$\\
\rule{2em}{0pt} \textbf{end};\ \%\ ``if $k\le n$''\\
\rule{2em}{0pt} \%\ Next, we search for the next e-cell in sequence ${\mathcal P}(\widehat{T}_{\gamma})$\\
\rule{2em}{0pt} \textbf{if} $(\eta^{\#}<\mu)\ \&\ (j>\gamma)$ \textbf{then} $\eta^{\#}\leftarrow\eta^{\#}+1$ \%\ $(\eta^{\#},j^{\#})$ will be the next e-cell\\
\rule{3em}{0pt} \textbf{else if} $(j^{\#}<\widehat{N}(\gamma))$ \textbf{then begin}\ \%\ The next e-cell is in the next column\\
\rule{4em}{0pt} $j^{\#}\leftarrow j^{\#}+1$;\ \textbf{if} $j^{\#}>\widetilde{N}+\gamma(\eta^{*}-1)$\qquad 
\%\ $(\eta^{*},j^{\#})$ \textbf{is not an e-cell}\\
\rule{4em}{0pt} \textbf{then} $\eta^{*}\leftarrow\eta^{*}+1$;\ \%\ The base row number should be incremented by 1\\
\rule{4em}{0pt} $\eta^{\#}\leftarrow\eta^{*}$\\
\rule{3em}{0pt} \textbf{end};\ \%\ ``else''

\textbf{until} $(\eta^{\#},j^{\#})=(\mu,\widehat{N}(\gamma))$;

\%\ Next, we deal with case $(\eta^{\#},j^{\#})=(\mu,\widehat{N}(\gamma))$

$k\leftarrow\pi_{\widetilde{N}}^*$;\ 

\textbf{if} $(k\le n)\ \&\ (\mu_k=\mu)$ \textbf{then begin}\ \%\ an o-o $O_{\mu,k}$ is found\\ 
\rule{2em}{0pt} $i\leftarrow\hat{i}(\mu,k)$;\ \textbf{if} $k_c[i]> 0$ \textbf{then}\\ 
\rule{3em}{0pt} $\{\eta'[\eta_c[i],k_c[i]]\leftarrow\mu;\ k'[\eta_c[i],k_c[i]]\leftarrow k;\ ent[\mu,k]\leftarrow ent[\mu,k]+1\}$;

\textbf{end};\ \%\ ``if $k\le n$''\\
\textbf{END}

\medskip
Now we are able to form the complete information specifying graph $G(\gamma)=(X,U)$. The set $X$ of its nodes coincides with the set $\{O_{\eta,k}\,|\,k\in[n], \eta\in[\mu_k]\}$ of o-os. The set $U$ of arcs is the union of two sets: $U=U'\cup U''$, where $U'\doteq\{((\eta,k),(\eta'[\eta{,}k],k'[\eta{,}k]))\,|\,(\eta{,}k)\in X'\}$ is the set of machine-based arcs, $U''\doteq\{((\eta{,}k),(\eta+1{,}k))\,|\,k\in[n], \eta\in[\mu_k-1]\}$ is the set of job-based arcs, and $X'\doteq\{(\eta,k)\,|\,k\in[n], \eta\in[\mu_k], k'[\eta{,}k]>0\}$ is the subset of such o-os $O_{\eta,k}\in X$ for which there are subsequent o-os processed in schedule $S(\widehat{T}_{\gamma})$ on the same machine $M_{\hat{i}[\eta{,}k]}$.

Next, after scanning (in any order) the set $U$ of arcs of graph $G(\gamma)$, we can find for each node $O_{\eta,k}\in{\mathcal O}$ the list $U_{\eta,k}$ of outgoing arcs and the number $ent[\eta,k]$ of entering arcs. This information is sufficient to start the classical algorithm that in $O(|U|)\le O(|{\mathcal O}|)\le O(\mu n)$ time computes the active schedule $S_{\rm act}(\gamma)$ which meets precedence constraints specified on the set of o-os by graph $G(\gamma)$. Thus, Stage~7 can be performed in time $O(\mu\widetilde{N})$ needed for scanning all e-cells of table $\widehat{T}_{\gamma}$. This completes the description of Stage 7 and of the whole algorithm ${\mathcal A}(\gamma)$.\algend


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Analysis of algorithm ${\mathcal A}(\gamma)$ and formulation of the main result}\label{sec4}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lemma}\label{le2}
For any $\gamma\in\mathbb{N}$, schedule $S_{\rm act}(\gamma)$ is feasible. If for some $\gamma\in\mathbb{N}$ schedule $S(\widehat{T}_{\gamma})$ is also feasible, then $C_{\max}(S_{\rm act}(\gamma))\le C_{\max}(S(\widehat{T}_{\gamma}))$.
\end{lemma}

\begin{proof}
The feasibility of schedule $S_{\rm act}(\gamma)$ consists of the feasibility of sub-schedules for each machine and each job. For \textbf{each job}, this schedule is feasible, because graph $G(\gamma)$ specifies the linear order of execution of its operations based on the input information of the Job Shop problem. At the same time, the linear order of execution of the original operations of \textbf{each machine} $M_i$ in graph $G(\gamma)$ is inherited from the linear order of execution of these operations in table-based schedule $S(\widehat{T}_{\gamma})$, which ultimately ensures the feasibility of the active schedule $S_{\rm act}(\gamma)$.

Let us prove the relation $C_{\max}(S_{\rm act}(\gamma))\le C_{\max}(S(\widehat{T}_{\gamma}))$ under the assumption that schedule $S(\widehat{T}_{\gamma})$ is feasible. As was observed above, schedule $S(\widehat{T}_{\gamma})$ meets the linear precedence constraints specified by graph $G(\gamma)$ for the set of all original operations on each machine $M_i$. Furthermore, due to the feasibility of schedule $S(\widehat{T}_{\gamma})$, it meets the linear precedence constraints imposed on the set of all operations of each original job. Thus, $S(\widehat{T}_{\gamma})$ meets all precedence constraints specified by graph $G(\gamma)$. Furthermore, schedule $S(\widehat{T}_{\gamma})$ meets all precedence constraints specified by table $\widehat{T}(\gamma^*)$ on the set of \textbf{all operations} (including extended and S-dummy ones) of each machine $M_i$. Let $\widehat{G}(\widehat{T}_{\gamma})$ be the graph with the set of nodes representing all operations of schedule $S(\widehat{T}_{\gamma})$, and with the set of arcs including all transitive closures of precedence constraints specified by table $\widehat{T}_{\gamma}$ and graph $G(\gamma)$. Then, due to the inclusion $G(\gamma)\subseteq\widehat{G}(\widehat{T}_{\gamma})$, the critical path in graph $\widehat{G}(\widehat{T}_{\gamma})$ cannot be shorter than that of graph $G(\gamma)$, which implies the relation $C_{\max}(S_{\rm act}(\gamma))\le C_{\max}(S(\widehat{T}_{\gamma}))$.
\end{proof}

\begin{lemma}\label{le3}
For any $\gamma\ge\gamma^*\doteq\left\lceil\alpha(d)\mu\widetilde{N}\frac{p_{\max}}{L_{\max}}\right\rceil+1$, schedule $S(\widehat{T}_{\gamma})$ is feasible. For any instance of the Job Shop problem with $m\ge 2$ and $\mu\ge 2$, the length of schedule $S(\widehat{T}_{\gamma^*})$ meets the bound:
\begin{equation}\label{eq11}
C_{\max}(S(\widehat{T}_{\gamma^*}))< L_{\max}+ m\mu^2(\mu-1)p_{\max}.
\end{equation}
\end{lemma}

\begin{proof}
Let us first prove that the $\hat{k}$-property holds for table $\widehat{T}_{\gamma}$ with any $\gamma\in\mathbb{N}$ and for any $i\in[m]$. More precisely, we are to prove that the equalities
\begin{equation}\label{eq12}
\quad\hat{c}_{\eta,k}^{\,i}(\widehat{T}_{\gamma})= \frac{k-d}{\widetilde{N}}L_{\max} +\frac{1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i}+\alpha(d)\!\sum_{\nu=1}^{\mu}\hat{\delta}_{\nu,k'(k,\nu,\eta)}^{\,i}(\gamma)
\end{equation}
hold for all $i\in[m],\ \eta\in[\mu],\ k\in[\widehat{N}(\gamma)]$ for some values $\hat{\delta}_{\nu,k'(k,\nu,\eta)}^{\,i}(\gamma)\in[0,p_{\max}]$. 

Indeed, as a result of adding S-dummy operations (each of length $\tilde{L}_{\nu}^{\,i}/\widetilde{N}$ for machine $M_i$) to the beginning and to the end of each row $\nu$ of table $\widetilde{T}$, formulas (\ref{eq9}) transform into the equalities
\begin{equation}\label{eq13}
\sum_{j\in [k]} \hat{p}_{\nu ,j}^{\,i}(\widehat{T}_{\gamma}) = \frac{k-d+1}{\widetilde{N}}\tilde{L}_{\nu}^{\,i}+\alpha(d)\,\hat{\delta}_{\nu,k}^{\,i}(\gamma),\ \forall\ i\in[m],\ \nu\in[\mu],\ k\in[\widehat{N}(\gamma)],
\end{equation}
with 
\begin{equation}\label{eq13a}
\hat{\delta}_{\nu,k}^{\,i}(\gamma)\doteq\left \{\begin{array}{ll}
    \delta_{\nu,k-\gamma(\nu-1)}^{\,i}, & \mbox{for $k-\gamma(\nu-1)\in[\widetilde{N}]$}\\[1ex]
    \frac{(d-1)}{\alpha\,(\!d)}\tilde{L}_{\nu}^{\,i}/\widetilde{N}, & \mbox {for $k\le\gamma(\nu-1)$ and $k>\gamma(\nu-1)+\widetilde{N}$.}
    \end {array} \right.
\end{equation}
The second case of equalities (\ref{eq13a}) follows from relations $\sum_{j\in [k]} \hat{p}_{\nu ,j}^{\,i}(\widehat{T}_{\gamma}) = k\frac{\tilde{L}_{\nu}^{\,i}}{\widetilde{N}}$ which hold for $k\le\gamma(\nu-1)$ and $k\ge\gamma(\nu-1)+\widetilde{N}$. 
Thus, in all cases, $\hat{\delta}_{\nu,k}^{\,i}(\gamma)\in[0,p_{\max}]$, because in the first case of (\ref{eq13a}) this is true for values $\delta_{\nu,j}^{\,i}\ (j\in[\widetilde{N}])$, while in the second case this follows from $(d-1)<\alpha(d)$ and $\tilde{L}_{\nu}^{\,i}\le np_{\max}\le\widetilde{N}p_{\max}$. 

Starting from (\ref{eq9a}) (with $T'=\widehat{T}_{\gamma}$) and implementing (\ref{eq13}) and (\ref{eq6}), we obtain for all $i\in[m],\ \eta\in[\mu],\ k\in[\widehat{N}(\gamma)]$:
\begin{eqnarray*}
\quad\hat{c}_{\eta,k}^{\,i}(\widehat{T}_{\gamma})&=&\frac{k-d+1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i}+\frac{k-d}{\widetilde{N}}\!\!\!\sum_{\nu=\eta+1}^{\mu}\tilde{L}_{\nu}^{\,i}+ \alpha(d)\!\sum_{\nu=1}^{\mu}\hat{\delta}_{\nu,k'(k,\nu,\eta)}^{\,i}(\gamma)\\ &=& \frac{k-d}{\widetilde{N}}L_{\max} +\frac{1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i}+\alpha(d)\!\sum_{\nu=1}^{\mu}\hat{\delta}_{\nu,k'(k,\nu,\eta)}^{\,i}(\gamma),
\end{eqnarray*}
as required in (\ref{eq12}). Now, to prove the feasibility of schedule $S(\widehat{T}_{\gamma})$ for any $\gamma\ge\gamma^*$, we should prove that all precedence constraints (\ref{eq5a}) are met. To that end, it suffices to ensure the relations $0\le s_{\eta+1,k}^{\,i''}- c_{\eta,k}^{\,i'}$ for all $i',i''\in[m],\ \eta\in[\mu-1]$,\ $k\in[\widetilde{N}]$ (i.e., for all extended jobs). As was observed at Stage 6 of the algorithm, operation $\widetilde{O}_{\eta+1,k}^{\,i''}$ coincides with operation $\widehat{O}_{\eta+1,k+\gamma\eta}^{\,i''}(\widehat{T}_{\gamma})$, and so, $s_{\eta+1,k}^{\,i''}=\hat{s}_{\eta+1,k+\gamma\eta}^{\,i''}(\widehat{T}_{\gamma})=\hat{c}_{\eta,k+\gamma\eta}^{\,i''}(\widehat{T}_{\gamma}).$
Similarly, we obtain:\ $c_{\eta,k}^{\,i'}=\hat{c}_{\eta,k+\gamma(\eta-1)}^{\,i'}(\widehat{T}_{\gamma}).$
This together with (\ref{eq12}) yields the following sufficient conditions for the feasibility of schedule $S(\widehat{T}_{\gamma})$:
\begin{eqnarray*}
0 &\le& s_{\eta+1,k}^{\,i''}- c_{\eta,k}^{\,i'}=\hat{c}_{\eta,k+\gamma\eta}^{\,i''}(\widehat{T}_{\gamma})-\hat{c}_{\eta,k+\gamma(\eta-1)}^{\,i'}(\widehat{T}_{\gamma})=\frac{\gamma}{\widetilde{N}}L_{\max} +\frac{1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i''}\\
&+& \alpha(d)\!\sum_{\nu=1}^{\mu}\hat{\delta}_{\nu,k'(k+\gamma\eta,\nu,\eta)}^{\,i''}(\gamma) -\alpha(d)\!\sum_{\nu=1}^{\mu}\hat{\delta}_{\nu,k'(k+\gamma(\eta-1),\nu,\eta)}^{\,i'}(\gamma) -\frac{1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i'}.
\end{eqnarray*}

To ensure all these inequalities, it suffices to take $\gamma$ such that
$$\frac{\gamma}{\widetilde{N}}L_{\max}\ge \alpha(d)\!\sum_{\nu=1}^{\mu}\hat{\delta}_{\nu,k'(k+\gamma(\eta-1),\nu,\eta)}^{\,i'}(\gamma)+\frac{1}{\widetilde{N}}\!\sum_{\nu=1}^{\eta}\tilde{L}_{\nu}^{\,i'}$$
holds for any $i'\in[m],\ \eta\in[\mu-1],\ k\in[\widetilde{N}]$. E.g., $S(\widehat{T}_{\gamma})$ is feasible for any
$$\gamma\ge\gamma^*\doteq\min\{\gamma\in\mathbb{N}\,|\, \gamma L_{\max}/\widetilde{N}\ge\alpha(d)\mu p_{\max}+L_{\max}/\widetilde{N}\}=
\left\lceil\alpha(d)\mu\widetilde{N}\frac{p_{\max}}{L_{\max}}\right\rceil+1.$$

Lastly, once schedule $S_i(\widehat{T}_{\gamma^*})$ (for any $i\in[m]$) has no idle time, its length is equal to $L_{\max}$ plus the total length of all S-dummy operations on machine $M_i$. Since each machine $M_i$ has $\gamma^*(\mu-1)$ S-dummy operations at each level $\eta\in[\mu]$ (each of length $\tilde{L}_{\eta}^{\,i}/\widetilde{N}$), their total length over all levels is equal to $\gamma^*(\mu-1)L_{\max}/\widetilde{N}$, and we can estimate the length of schedule $S(\widehat{T}_{\gamma^*})$ as:
\begin{eqnarray}
\rule{2em}{0pt}C_{\max}(S(\widehat{T}_{\gamma^*}))        &=& L_{\max}+ \gamma^*(\mu-1)\frac{L_{\max}}{\widetilde{N}} < L_{\max}+ \left(\alpha(d)\mu\widetilde{N}\frac{p_{\max}}{L_{\max}}+2\right)\cdot\label{eq13b}\\
\rule{2em}{0pt}\cdot(\mu-1)\frac{L_{\max}}{\widetilde{N}} &=& \left(1+\frac{2\mu-2}{\widetilde{N}}\right)L_{\max}+ \mu(\mu-1)(m\mu-1+1/m\mu)p_{\max}\nonumber 
\end{eqnarray}
Now, choosing the value $\widetilde{N}\leftarrow 3n$, we can estimate $\frac{2\mu-2}{\widetilde{N}}L_{\max}\le\frac{2(\mu-1)}{3n}\mu np_{\max}$, which yields the bound:\\
$C_{\max}(S(\widehat{T}_{\gamma^*}))\le L_{\max}+ \left(m\mu^2(\mu-1)+\left(\frac{2}{3}\mu(\mu-1)-\mu(\mu-1)+\frac{\mu-1}{m}\right)\right)p_{\max}.$

Since $m\ge 2$ and $\mu\ge 2$, the summand $\left(\frac{\mu-1}{m}-\frac{\mu(\mu-1)}{3}\right)$ in the above bound is always negative, which enables us to derive bound (\ref{eq11}). Lemma \ref{le3} is proved.
\end{proof}

\begin{lemma}\label{le4}
For any $\gamma\ge\widetilde{N}$, schedule $S(\widehat{T}_{\gamma})$ is feasible. For any instance of the Job Shop problem, schedule $S(\widehat{T}_{\widetilde{N}})$ has length $C_{\max}(S(\widehat{T}_{\widetilde{N}}))=\mu L_{\max}$.
\end{lemma}

\begin{proof}
Let $SO_i(\gamma)$ denote the sequence of operations executed on machine $M_i$ according to schedule $S(\widehat{T}_{\gamma})$. Then by construction of a table-based schedule (see its definition on page \pageref{de2}) and by the choice of $\gamma\ge\widetilde{N}$, the initial segment of $SO_i(\gamma)$ consisting of $\gamma\mu$ operations contains all $\widetilde{N}$ extended operations of the first level on that machine (and \textbf{only such} extended operations), $\gamma-\widetilde{N}$ S-dummy operations of the first level, and $\gamma$ S-dummy operations of each level from 2 to $\mu$. Thus, the total duration of this initial segment of operations on each machine $M_i$ is equal to
$$\tilde{L}_{1}^{\,i} +(\gamma-\widetilde{N})\frac{\tilde{L}_{1}^{\,i}}{\widetilde{N}}+\sum_{\eta=2}^{\mu}\frac{\gamma\tilde{L}_{\eta}^{\,i}}{\widetilde{N}}= \sum_{\eta=1}^{\mu}\frac{\gamma\tilde{L}_{\eta}^{\,i}}{\widetilde{N}}= \frac{\gamma {L}_{\max}}{\widetilde{N}}.$$
Similarly, we ensure that the next segment of $SO_i(\gamma)\ (i\in[m])$ consisting of the same ($\gamma\mu$) number of operations occupies in schedule $S(\widehat{T}_{\gamma})$ a time interval of the same length ($\gamma L_{\max}/\widetilde{N}$) and contains all $\widetilde{N}$ extended operations (of machine $M_i$) of level~2, and so on, until the $\mu$-th segment. This last segment is shorter: it contains only $\mu\widetilde{N}$ operations, with total length $L_{\max}$;\ still, it contains \textbf{all $\widetilde{N}$ extended operations} of the $\mu$-th level on that machine. Thus, all operations of the $\eta$-th level on each machine $M_i$ are concentrated in the $\eta$-th segment of the sequence of operations on that machine, while the $\eta$-th segments of all machines are synchronized in time. This provides the property that all extended operations of the $(\eta+1)$-th level are processed in this schedule after all operations of the $\eta$-th level, which provides the feasibility of schedule $S(\widehat{T}_{\gamma})$.

The length of schedule $S(\widehat{T}_{\widetilde{N}})$ coincides with the total duration of $\mu$ segments of sequence $SO_i(\gamma)$ on each machine $M_i$, while the duration of each segment (in the case of $\gamma=\widetilde{N}$) is equal to $L_{\max}$. So, we have 
$C_{\max}(S(\widehat{T}_{\widetilde{N}}))=\mu L_{\max}$.
\end{proof}



\begin{theorem}\label{th2}
Algorithm ${\mathcal A}(\gamma)$ with $\gamma=\gamma^{\#}\doteq\min\{\gamma^*,\widetilde{N}\}$ runs in time $O(m^2\mu^2n^2)$ and finds a feasible schedule $S_{\rm act}(\gamma^{\#})$ of length
\begin{equation}\label{eq17}
C_{\max}(S_{\rm act}(\gamma^{\#}))\le\min\{mL_{\max},\mu L_{\max}, L_{\max}+ m\mu^2(\mu-1)p_{\max}\}.
\end{equation}
\end{theorem}

\begin{proof}
Since in the case with either $m=1$ or $\mu=1$ the Job Shop problem can be solved to the optimum in $O(|{\mathcal O}|)$ time, we can further assume that the conditions $m\ge 2$ and $\mu\ge 2$ of Lemma \ref{le3} hold. This implies that algorithm ${\mathcal A}(\gamma^*)$ finds a feasible schedule $S(\widehat{T}_{\gamma^*})$ that meets bound (\ref{eq11}).
Next, we have relations
\begin{equation}\label{eq18}
C_{\max}(S_{\rm act}(\gamma^{\#}))\le C_{\max}(S(\widehat{T}_{\gamma^{\#}}))\le\min\{\mu L_{\max}, L_{\max}+ m\mu^2(\mu-1)p_{\max}\},
\end{equation}
where the first inequality is valid by Lemma~\ref{le2} (since schedule $S(\widehat{T}(\gamma^{\#}))$ is feasible in both cases of $\gamma^{\#}\in\{\widetilde{N},\gamma^*\}$ due to Lemmas \ref{le4} and \ref{le3}). The second inequality is valid due to the monotonic increase of the function $C_{\max}(S(\widehat{T}_{\gamma}))$ on $\gamma$ and due to Lemmas \ref{le4} and \ref{le3}. Lastly, bound $C_{\max}(S_{\rm act}(\gamma^{\#}))\le mL_{\max}$ is valid, because schedule $S_{\rm act}(\gamma^{\#})$ is feasible (by Lemma~\ref{le2}) and active. Along with (\ref{eq18}), this yields bound~(\ref{eq17}). 

To complete the proof of the theorem, it remains to justify the bound on the running time claimed above.
Clearly, Stages 1 to 3 of algorithm ${\mathcal A}(\gamma)$ can be performed in time $O(m\mu n)$. The algorithm of vector summation performed at Stage~4 for the extended set of $\widetilde{N}=3n$ jobs requires time $O(m^2\mu^2\widetilde{N}^2)\le O(m^2\mu^2n^2)$. Next, as we could see from the description of Stage 7, neither table $\widetilde{T}$, nor table $\widehat{T}(\gamma^{\#})$ defined at Stages 5 and 6 were used for constructing the active schedule $S_{\rm act}(\gamma^{\#})$, which means that Stages~5 and 6 of algorithm ${\mathcal A}(\gamma)$ are ``imaginary'' parts of it --- they contribute nothing to the running time of the algorithm. (However, the structure of the table-based schedule $S(\widehat{T}(\gamma^{\#}))$ was essentially used while deriving our upper bound on the length of schedule $S_{\rm act}(\gamma^{\#})$.) Finally, Stage 7 (of finding the active schedule $S_{\rm act}(\gamma^{\#})$) can be performed in time $O(\mu\widetilde{N})\le O(\mu n)$. Totally, this all takes time $O(m^2\mu^2n^2)$. 
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Linearization of algorithms from (Shmoys et al., 1994) with respect to the number of jobs ($n$)}\label{sec5}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Two algorithms published in (Shmoys et al., 1994) were briefly described in the Introduction (with mentioning the role that our algorithm from (Sevast'yanov, 1986) plays in both of them, see pages \pageref{eq2}--\pageref{eq4b}).

In both those algorithms, the set of all jobs ${\mathcal J}$ is first separated into two subsets (${\mathcal J}_L$ and ${\mathcal J}_S$) of so-called ``large'' and ``small'' jobs, after which \textbf{different algorithms} are applied to them, constructing two schedules independent of each other. (In particular, to construct a schedule for ``small'' jobs, our algorithm from (Sevast'yanov, 1986), based on the compact vector summation technique, was used.) The ``watershed'' between two sets of jobs is established at the input of the \emph{Algorithm of job separation} by specifying a \emph{threshold value} $p^{\#}$ of the parameter $\beta(p_j)$ (where $p_j$ is the vector of operation durations of job $J_j$, and $\beta(x)$ is the maximum component of vector~$x$): jobs with $\beta(p_j)\le p^{\#}$ fall into ${\mathcal J}_S$, the rest ones --- into ${\mathcal J}_L$. Thus, the value of $p_{\max}$ over all small jobs is not greater than the value of the ``watershed'' $p^{\#}$. 

This value is taken differently in the two algorithms: $p^{\#}=\frac{L_{\max}}{2m\mu^3}$ in the first algorithm and $p^{\#}=\frac{\varepsilon L_{\max}}{2m\mu^3}$ in the second one. As a result, the first algorithm from (Shmoys et al., 1994) provides a relative error bounded by $O(\log^2(m\mu))$, while the second algorithm yields a $(2+\varepsilon)$-approximation for any fixed $\varepsilon>0$. At that, the bounds on the running times of both algorithms ($O(n^2m^2\mu^2+ P(m,\mu))$, where $P(m,\mu)$ is a polynomial of $m$ and $\mu$, and $O(n^2)$, under assumption that parameters $m$ and $\mu$ are fixed, respectively) show that they heavily depend on the algorithm from (Sevast'yanov, 1986). We are now to show that the bounds on the running times of both these algorithms can be made linear in $n$.

Linearization of both algorithms from (Shmoys et al., 1994) in the parameter \emph{number of jobs} can be achieved (after the separation of the set of jobs into ``large'' and ``small'') by a preliminary gluing together ``small'' jobs to ``aggregated small jobs'', the number of which (due to the choice of the threshold value $p^{\#}$) is bounded from above by an amount independent of the initial number of jobs ($n$). This value is a polynomial in $m$ and $\mu$ in the case of the first algorithm from (Shmoys et al., 1994) and a polynomial in $m$, $\mu$, and $1/\varepsilon$ in the case of their second algorithm. Since the ``aggregated small jobs'' also meet the threshold value $p^{\#}$, applying to them our algorithm from (Sevast'yanov, 1986) or algorithm ${\mathcal A}(\gamma)$ from Sect. \ref{sec3}, we obtain a feasible schedule for the aggregated (and hence for the original) small jobs, which has \textbf{exactly the same upper bound on its length} as we would have obtained for small jobs without gluing them together. The only difference is that the complexity of this algorithm will no longer depend on $n$, but will be a polynomial in $m$ and $\mu$ (and of $1/\varepsilon$ in the case of the second algorithm). Thus, the dependence on parameter $n$ is preserved only for the complexity of the gluing procedure itself, which can be performed in time $O(\sum_{j\in[n]}\mu_j)\le O(\mu n)$ (i.e., in time needed to look through the input information) by means of the procedure \emph{Job\_Separation\_Gluing\_Unification} (further --- \emph{JSGU}, for short) described below.

In this procedure, three different processes are combined in a natural way within \textbf{a single loop of scanning the list of original jobs}: (1) Stage 1 of algorithm ${\mathcal A}(\gamma)$ (where the unification of job routes through machines is performed), (2) job separation (into ``large'' and ``small'' ones), and (3) the gluing the small jobs. 

Prior to the description of the procedure, we should make two remarks. First, we note that after the status of a job (being large or small) is defined, large jobs have not be subjected to processes of unification and gluing, as well as to the subsequent stages of algorithm ${\mathcal A}(\gamma)$, since other algorithms (not based on the compact vector summation) are used in (Shmoys et al., 1994) for constructing the schedules for large jobs. Thus, since the \emph{JSGU}-procedure includes the job unification, it is intended to \textbf{replace Stage 1 of algorithm} ${\mathcal A}(\gamma)$ applied to small jobs.

Second, it can be observed that the procedure of gluing the small jobs and the unification of their routes can be performed simultaneously.
Indeed, at Stage 1 we define \emph{wide jobs} ($\{\tilde{J}_j\}$), each consisting of $m\mu$ ``wide operations'' $\{O_{\eta,j}^{\,i}\,|\,i\in[m],\ \eta\in[\mu]\}$. The duration $p_{\eta,j}^{\,i}$ of each such operation is first set to zero. Then, for each job $J_j\in{\mathcal J}$, we plunge its o-os $\{O_{\eta,j}\,|\,\eta\in[\mu_j]\}$ into ``wide operations'' by setting $p_{\,\eta,j}^{\hat{i}(\!\eta,j)}\leftarrow p_{\,\eta,j}^{\hat{i}(\!\eta,j)}+p_{\,\eta,j}$, where $M_{\hat{i}(\!\eta,j)}=M(O_{\eta,j})$.
But in fact, \textbf{several original small jobs} $J_j$ (all together) could be loaded into \textbf{the same wide job} $\tilde{J}_k$ so as the total duration $\check p_{\eta,k}^{\,i}$ of their operations within each \emph{wide operation} $O_{\eta,k}^{\,i}$ would not exceed the given threshold $p^{\#}$. (This process can be viewed as a packing of vectors $\{p_j\}$ into an $(m\mu)$-dimensional bin $\tilde{J}_{\!k}$.) So, the jobs placed into the same wide job $\tilde{J}_k$ could be glued together, thereby forming an ``aggregated small'' wide job.

We next observe that the process of packing the original jobs into a \textbf{fixed wide job} $\tilde{J}_{\!k}$ can be continued until the attempt to place the next in turn vector $p_{\!j'}$ \textbf{of a small job} $J_{\!j'}$ into the current bin $\tilde{J}_{\!k}$ yields an overload of some cell of that $(m\mu)$-dimensional bin. In this case, we proceed quite simply: we treat bin $\tilde{J}_{\!k}$ as ``filled'' and add the ``aggregated small'' wide job $\tilde{J}_{\!k}$ (with a total vector $\check p_{k}\in\mathbb{R}^{m\mu}$ of operation durations) to set ${\mathcal J}_S$. After that, we start filling the next bin ($\tilde{J}_{\!k+1}$) by placing vector $p_{\!j'}$ into it. Finally, if job $J_{\!j'}$ is ``large'', we add it to set ${\mathcal J}_L$. (These jobs will not be further involved in our algorithm.)

Thus, our procedure (combining the three processes mentioned above) represents a loop of scanning the list ${\mathcal J}$ of the original jobs (in any order), where, while scanning some job $J_{\!j}\in{\mathcal J}$, we clarify two questions:

(A) Does the job fit into the current bin $\tilde{J}_{\!k}$? (Does $\check p_{\eta,k}^{\,\hat{i}(\!\eta,j)}+p_{\eta,j}\le p^{\#}$ hold for all $\eta\in[\mu_{\!j}]$?)

(B) Is it ``small'' or ``large''? (Does $p_{\eta,j}\le p^{\#}$ hold for all $\eta\in[\mu_{\!j}]$?) 

\rule{0pt}{0.8em}
Clearly, $2\mu_{\!j}$ comparisons are sufficient to answer both questions. Yet, this can be done faster: by performing at most $(\mu_j+1)$ (at best, two) comparisons. This can be done as follows (see the description of the procedure below for details).

So, while considering some job $J_{\!j}\in{\mathcal J}$, we start the loop on its operations $\{O_{\eta,j}\,|$ $\eta=1,2,\dots,\mu_j\}$. For each value of $\eta$, we first try to answer only the first question: does operation $O_{\eta,j}$ fit into the current ``aggregated wide operation'' $O_{\,\eta,k}^{\hat{i}(\!\eta,j)}$? (If it fits, then it is small.) If for all values of $\eta$ we have the positive answer to this question, we get positive answers to both questions ((A) and (B)) on job $J_{\!j}$:\ it is small and it fits into the bin. 

In case that a value $\eta=\eta^*$ is encountered such that $\check p_{\eta^*\!,k}^{\,\hat{i}(\!\eta^*\!,j)}+p_{\eta^*\!,j}> p^{\#}$ (and so, we have got the negative answer to question (A), while it still remains unclear, if job $J_{\!j}$ is small or large), we start (for values $\eta=\eta^*$ and on) getting answers to question (B): is operation $O_{\eta,j}$ small or large? (Or: does $p_{\eta,j}\le p^{\#}$ hold?) If for all $\eta$ the answers are positive, job $J_{\!j}$ is small. Otherwise, it is large. (It should be included in list ${\mathcal J}_L$ and taken out of the operation of our algorithm.)

\medskip
Procedure \emph{JSGU} (described below) uses the following \emph{global variables}:

\textbf{integer} $K$ is the number of ``aggregated small'' wide jobs;

$\check p_k\ (k\in[K])$ is an \textbf{$(m\mu)$-dimensional vector of integers}\ accumulating the resulting operation durations of the $k$-th ``aggregated small'' wide job;

${\mathcal I}_L$ and ${\mathcal I}_S(k)\ (k\in[K])$ are \textbf{sets of integers} accumulating the sets of the original indices of large jobs and of small jobs plunged into the $k$-th aggregated small wide job, respectively.\ All other information on the original jobs is also global.

\medskip
\begin{center}
\textbf{Procedure} \emph{JSGU}$(\textbf{integer:}\ n,p^{\#})$; 
\end{center}
\%\ \textbf{Formal input parameters:}\\
\%\ $n$ is the number of original jobs in ${\mathcal J}$;\\
\%\ $p^{\#}$ is the \emph{upper bound} on the maximum operation duration for ``small'' jobs\\[1em]
\%\ \textbf{Local parameters:}

\textbf{integer:}\ $i,j,k,\eta,D$;

\textbf{Boolean}:\ \textbf{unfit},\ \textbf{large};
%\textbf{set of integers:}\ ${\mathcal I}$;\ \%\ The set of indices of original jobs from ${\mathcal J}$

\medskip\textbf{Procedure} \emph{Load}(\textbf{integer:}\ $j,k$);\ \%\ load job $j$ into bin $k$

\textbf{integer:}\ $\eta$;

\textbf{begin}\\
\rule{2em}{0pt} ${\mathcal I}_S(k)\leftarrow{\mathcal I}_S(k)\cup\{j\}$;\\
\rule{2em}{0pt} \textbf{for} $\eta\leftarrow 1,\dots,\mu_j$\ \textbf{do}\ $\check p_{\eta,k}^{\,\hat{i}(\!\eta,j)}\leftarrow\check p_{\eta,k}^{\,\hat{i}(\!\eta,j)}+p_{\eta,j}$

\textbf{end}\ \%\ Procedure \emph{Load}

\medskip\textbf{BEGIN}

${\mathcal I}_L\leftarrow\varnothing;\ k\leftarrow 1;\ {\mathcal I}_S(k)\leftarrow\varnothing;\ \check p_k\leftarrow {\bf 0}$;

\textbf{for} $j\leftarrow 1,\dots,n$ \textbf{do begin}\\
%
\rule{2em}{0pt} \textbf{unfit}\ $\leftarrow$\ FALSE;\ \textbf{large}\ $\leftarrow$\ FALSE;\ $\eta\leftarrow 1$;\\
\rule{2em}{0pt} \%\ Initially we assume that job $J_{\!j}$ is small and fits into the current bin.\\
\rule{2em}{0pt} \%\ Next, we run the loop on its operations (indexed by $\eta$):\\
\rule{2em}{0pt} \textbf{repeat if} ($\check p_{\eta,k}^{\,\hat{i}(\!\eta,j)}+p_{\eta,j}\le p^{\#}$) \textbf{then} $\eta\leftarrow\eta+1$ \textbf{else} \textbf{unfit}\ $\leftarrow$\ TRUE\\
\rule{2em}{0pt} \textbf{until} $(\eta>\mu_j)\ \vee$\ \textbf{unfit};\\
\rule{2em}{0pt} \textbf{if unfit then} \textbf{repeat if} ($p_{\eta,j}\le p^{\#}$) \textbf{then} $\eta\leftarrow\eta+1$ \textbf{else} (\textbf{large}\ $\leftarrow$\ TRUE)\\
\rule{2em}{0pt} \textbf{until} $(\eta>\mu_j)\ \vee$\ \textbf{large};\\
\rule{2em}{0pt} \textbf{if not unfit}\ \%\ which means that job $J_{\!j}$ is small and fits into the current bin\\
\rule{2em}{0pt} \textbf{then}\ \emph{Load}$(j,k)$\\
\rule{3em}{0pt} \textbf{else if not large then}\ 
$\{k\leftarrow k+1;\ {\mathcal I}_S(k)\leftarrow\varnothing;\ \check p_k\leftarrow {\bf 0};\ \emph{Load}(j,k)\}$\\
\rule{4em}{0pt} \textbf{else}\ ${\mathcal I}_L\leftarrow{\mathcal I}_L\cup\{j\}$;

\textbf{end}\ \%\ for $j$

$K\leftarrow k$;

\textbf{if} $k>2$ \textbf{then begin}\\
\rule{2em}{0pt} $D\leftarrow 0$;\ \textbf{for} $i\leftarrow 1,\dots,m$ \textbf{do} \textbf{for} $\eta\leftarrow 1,\dots,\mu$ \textbf{do}
$D\leftarrow D+\check p_{\eta,1}^{\,i}+\check p_{\eta,k}^{\,i}$;\\
\rule{2em}{0pt} \textbf{if} $D\le p^{\#}$ \textbf{then} $\{\check p_1\leftarrow \check p_1+\check p_k;\ {\mathcal I}_S(1)\leftarrow {\mathcal I}_S(1)\cup {\mathcal I}_S(k);\ K\leftarrow k-1\}$\\ 
\rule{2em}{0pt} \%\ If the total length ($D$) of aggregated small jobs $\tilde{J}_1$ and $\tilde{J}_k$ does not exceed\\ 
\rule{2em}{0pt} \%\ $p^{\#}$, we combine them; if $D > p^{\#}$, we do nothing (thus retaining the value\\ 
\rule{2em}{0pt} \%\ $K=k$; in particular, $D > p^{\#}$ is guaranteed in case $k=2$).

\textbf{end}\ \%\ if $k>2$

\textbf{END};


\begin{lemma}\label{le4a}
Procedure JSGU\,$(n,p^{\#})$ runs in time $O(\mu n)$. The resulting number $K$ of aggregated small jobs and the number $n_L$ of large jobs meet the relation
\begin{equation}\label{eq14}
K/2+n_L < mL_{\max}/p^{\#}.
\end{equation}
\end{lemma}

\begin{proof}
The procedure requires a single scanning of the set of original jobs, while the information on each job $j\in[n]$ is bounded by $O(\mu_j)$. This yields the bound on the running time of the procedure. 

Let $d(x)$ denote the sum of components of vector $x$, $\langle\check p_{\ell}',K'\rangle$ and $\langle\check p_{\ell}'',K''\rangle$ denote the values of vector $\check p_{\ell}$ (of operation durations of the aggregated small wide job $\tilde{J}_{\ell}$) and of parameter $K$ (the resulting number of aggregated small wide jobs) right before and after performing the ``if $k>2$'' block, respectively. According to the \emph{JSGU}-procedure, at least one component of each vector $\check p_{\ell}'+\check p_{\ell+1}'\ (\ell\in[k-1])$ is greater than $p^{\#}$ (while other components are non-negative), which implies
\begin{equation}\label{eq15}
d(\check p_{\ell}')+d(\check p_{\ell+1}')=d(\check p_{\ell}'+\check p_{\ell+1}')>p^{\#},\ \forall\ \ell\in[k-1].
\end{equation}
After performing the block ``if $k>2$'', we have one of two cases: either (a) $K''=k$, or (b) $K''=k-1$ (when we combine the aggregated jobs $\tilde{J}_1$ and $\tilde{J}_k$, and vector $\check p_1$ receives the value $\check p_1''\doteq\check p_1'+\check p_k'$). Thus, in case (b), we have:\ 
\begin{equation}\label{eq15a}
d(\check p_1'')+d(\check p_{K''}'')=d(\check p_1'+\check p_k')+d(\check p_{k-1}')=d(\check p_1')+d(\check p_{k-1}'+\check p_k')>d(\check p_1')+p^{\#},
\end{equation}
while (\ref{eq15}) in terms of vectors $\{\check p_{\ell}''\}$ transforms into
%
\begin{equation}\label{eq15b}
d(\check p_1'')+d(\check p_{2}'')=d(\check p_1'+\check p_k'+\check p_{2}')=d(\check p_1'+\check p_{2}')+d(\check p_k') >p^{\#}+d(\check p_k');
\end{equation}
\begin{equation}\label{eq15c}
d(\check p_{\ell}'')+d(\check p_{\ell+1}'')>p^{\#},\ \ell\in\{2,\dots,k-1\}.
\end{equation}

Summing up inequalities (\ref{eq15a})--(\ref{eq15c}), we obtain:
$$2\sum_{\ell\in[K'']} d(\check p_{\ell}'') > K''p^{\#}+d(\check p_1'+\check p_k').$$
Since in case (a), we have\ $K''=K'=k$ and $\check p_{\ell}''=\check p_{\ell}',\ \forall\ \ell$, we obtain:
$$d(\check p_1'')+d(\check p_{K''}'')=d(\check p_1')+d(\check p_k')>p^{\#},\ \mbox{and, using (\ref{eq15}):}$$
$$d(\check p_{\ell}'')+d(\check p_{\ell+1}'')=d(\check p_{\ell}')+d(\check p_{\ell+1}')>p^{\#},\ \forall\ \ell\in[K''-1].$$
Similarly summing up these inequalities, we obtain the inequality:
\begin{equation}\label{eq15d}
2\sum_{\ell\in[K'']} d(\check p_{\ell}'') > K''p^{\#},
\end{equation}
which holds in both cases ((a) and (b)). Similarly, for ``large'' job, we have:
\begin{equation}\label{eq15e}
\sum_{j\in{\mathcal I}_L} d(p_j) > n_Lp^{\#}.
\end{equation}
Using these two bounds on the total durations of ``aggregated small'' and of ``large'' jobs, and recalling that their total duration is at most $mL_{\max}$, we obtain:
$$mL_{\max}\ge \sum_{\ell\in[K'']} d(\check p_{\ell})+\sum_{j\in{\mathcal I}_L} d(p_j) > \frac{K''}{2}p^{\#} + n_Lp^{\#},$$
which implies (\ref{eq14}). Lemma \ref{le4a} is proved.
\end{proof}

\begin{corollary}\label{co2}
Executing the JSGU$(n,p^{\#})$ procedure instead of Stage 1 of algorithm ${\mathcal A}(\gamma)$ applied for constructing a schedule for ``aggregated small'' jobs in the first and second algorithms from (Shmoys et al., 1994) (with values $\frac{L_{\max}}{m\mu^2(\mu-1)}$ and $\frac{\varepsilon L_{\max}}{m\mu^2(\mu-1)}$ of parameter $p^{\#}$, respectively) provides the number $n_S$ of ``small'' jobs which meets upper bounds:\ $n_S< 2m^2\mu^2(\mu-1)$\ and $n_S< 2m^2\mu^2(\mu-1)/\varepsilon$, respectively. This provides an approximate solution for the original instance of the Job Shop problem with a running time esimated as $O(\mu n+f(m,\mu))$ and $O(\mu n+g(m,\mu,\varepsilon))$, respectively, where $f(m,\mu)$ is a polynomial of $m$ and $\mu$, while function $g(m,\mu,\varepsilon)$ exponentially depends on parameters $m,\mu$, and $1/\varepsilon$.  
\end{corollary}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Comparative analysis of four theoretical approximation algorithms for the Job Shop problem}\label{sec6}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

When there are several alternative ways to solve a problem, the question of comparing these ways naturally arises. We want to find out in which cases we should give preference to one solution method and in which cases to another ones. For that purpose, it is desirable to have tools that enable one to conduct an objective analysis of the quality of methods and to compare the methods with each other.

As for ``tools'', in recent decades the methods of ``experimental analysis'' and ``experimental comparison'' of algorithms have become widespread. These methods are based on programming algorithms and on subsequent running of those programs on some \textbf{finite sets of instances} of the problem under consideration. The results of these calculations for different programs/algorithms are compared with each other, and from this (usually ambiguous) comparison a conclusion is drawn most suitable to the author of such a comparison. However, the results of this kind pertain to another science, called ``experimental mathematics'', and have no relation to the science (mathematics) to which this article is dedicated.

It seems that an objective comparison of algorithms is possible only in those cases when theoretically justified guarantees of their quality (such as accuracy bounds and bounds on their running time) have been obtained. However, such results are encountered in scheduling literature several orders rarer than those mentioned above. For example, for the Job Shop problem in its general form (i.e., for one of the most difficult-to-solve representatives of the area of \emph{multistage scheduling problems}), \textbf{only four} (as far as I know, over the more than 70-year history of this field) such polynomial-time approximation algorithms with guaranteed a priori accuracy bounds valid \textbf{for all instances of this problem} have been developed. (Either detailed or brief descriptions of these four algorithms \textbf{were given} in the previous sections and in the Introduction.)

However, even the presence of such bounds does not always provide the opportuni\-ty for comparing different algorithms with each other, since those bounds may turn out to be incomparable. This may happen for different reasons. For example, they may be formulated in different terms that are not comparable with each other. In addition, a typical situation is when different methods may have their advantages in different sub-domains of the problem definition domain, but no method dominates absolutely in the entire domain. Finally, there may be no ``absolute winner'' for that simple reason that the problem of comparison is \textbf{multi-criterion}.

In our case, when we limited ourselves to evaluating the quality of algorithms by only two criteria: the accuracy of the solutions obtained and the complexity of the algorithm, the objective of a theoretical identification of a ``winner'' among the algorithms is difficult already due to the multi-criteria nature of the compared objects. Yet, even when comparing only by one criterion (for example, by complexity), certain difficulties may arise in those cases when the bounds on the running times of candidate algorithms depend on several independent parameters (as is in the case of the Job Shop problem). Alternatively, if we are talking about accuracy bounds (even without comparing algorithms by their complexity), then, in my opinion, the bounds on absolute and relative errors have \textbf{different physical dimensions}, and for this reason \textbf{are incomparable}. Comparing such bounds is the same as trying to answer the question: ``Who jumps better: a long jumper or a high jumper?'' 

To tell the truth, it is not difficult to transform the absolute bound (\ref{eq11}) into a relative one: it suffices to divide both parts of the inequality by $L_{\max}$ and recall that $L_{\max}$ is a lower bound on the optimum. Right such a relative bound  
%
\begin{equation}\label{eq16}
\frac{C_{\max}(S)}{C_{\max}^*}\le \frac{C_{\max}(S)}{L_{\max}}\le 1+ \frac{m\mu^3 p_{\max}}{L_{\max}}
\end{equation}
%
implies the asymptotic optimality of our solutions under the condition that $n\rightarrow\infty$. 

Ok! We now have \emph{a priori} \textbf{relative accuracy bounds} for all four algorithms. At that, all of them are parametric and all of them estimate the \textbf{worst case} (for given values of the parameters in terms of which they are expressed). Let us try to compare them. And before starting this process, let us collect in one table the information we have about the four algorithms mentioned above, according to two criteria: (1) the accuracy of the solutions obtained and (2) the running time of the algorithm. We will number the algorithms in chronological order: \textbf{1} --- (Sevast'yanov, 1986), \textbf{2} --- (Shmoys et al., 1994) (1st), \textbf{3} --- (Shmoys et al., 1994) (2nd), \textbf{4} --- (Jansen et al., 2003).

\begin{table}[htb]
\begin{center}
%\parbox[t]{0.6\textwidth}{%  
\begin{tabular}{c|c|c|c|p{7em}|}  
\hline
\rule{0pt}{3ex} \textbf{Alg.} & \textbf{Accuracy bound} & \textbf{Run-time} & \textbf{Parameters} & 
\multicolumn{1}{c|}{\textbf{Applicability}}\\
\hline
\rule[-0.3ex]{0pt}{3.5ex}\textbf{1}    & (\ref{eq16}) & $O(m^2\mu^2n^2)$ & Any $m,\mu,n$ & 
\multicolumn{1}{c|}{Yes} \\    
\hline
\rule[-1.5ex]{0pt}{4.5ex}\textbf{2}    & $\frac{C_{\max}(S)}{{\mathit OPT}}\le O(\log^2(m\mu))$ & $O(m^2\mu^2n^2)$ & Any $m,\mu,n$ & 
\multicolumn{1}{c|}{Bad accuracy} \\    
\hline
\rule[-1.5ex]{0pt}{4.5ex}\textbf{3}    & $\frac{C_{\max}(S)}{{\mathit OPT}}\le 2+\varepsilon$ & $O(n^2)$ & Fixed $m,\mu,\varepsilon$ & 
\multicolumn{1}{c|}{No} \\    
\hline
\rule[-1.5ex]{0pt}{4.5ex}\textbf{4}    & $\frac{C_{\max}(S)}{{\mathit OPT}}\le 1+\varepsilon$ & $O(n)$ & Fixed $m,\mu,\varepsilon$ & 
\multicolumn{1}{c|}{No} \\    
\hline
\multicolumn{5}{c}{\rule{0pt}{2ex}}
\end{tabular}  
\caption{Comparison of the four algorithms}\label{ta1}
\end{center}
\end{table}

Can we start comparing these four algorithms now?

No, they still remain \textbf{incomparable in accuracy} (except for the two algorithms heaving bounds depending only on $\varepsilon$; they \textbf{can be compared}), since they depend on different sets of parameters. Namely, bound (\ref{eq4a}) depends on parameters $m$ and $\mu$, bound (\ref{eq4b}) by (Shmoys et al., 1994) and bound $(1+\varepsilon)$ for each algorithm ${\mathcal A}_{\varepsilon}$ by (Jansen et al., 2003) depend on $\varepsilon$, while our bound (\ref{eq16}) depends on two extra parameters: $p_{\max}$ and $L_{\max}$, and does not depend on $\varepsilon$. However, these differences are easily leveled off by Shmoys et al.: they just put $p_{\max}=L_{\max}$ in our bound (\ref{eq16}), which is a gross distortion of the bound. Of course, for some (very rare) instances (with small values of parameters $m,\mu$ and $n$) these parameters can take close values. But such an event is practically improbable for instances of practical size. For the \textbf{overwhelming majority} of practically significant instances, our accuracy bound (due to its asymptotic optimality) outperforms bound (\ref{eq4b}) (not mentioning (\ref{eq4a})).

However (Shmoys et al., 1994), having performed the above transformation of my accuracy bound (i.e., having equated $p_{\max}$ to $L_{\max}$), came to a completely different conclusion: ``It is interesting to note that Sevast’yanov’s algorithm for the job shop problem can be viewed as a $(1+m\mu^3)$-approximation algorithm''. This ``interesting observation'' and a comparison of the accuracy bound obtained in this way with their own (obviously better!) bounds on the relative error enabled the authors to make an irrefutable conclusion that their algorithms are ``better than previously known ones'' (which is reflected in the title of their article: ``Improved Approximation Algorithms...'')\footnote{In a similar way, i.e., ignoring other conditions and parameters of comparison and taking into account only the parameters chosen by themselves, they could conclude that ``The long jumper jumps better!''.}. It had not come to their mind that I would never publish an algorithm with that terrible relative accuracy bound, just because the simplest algorithm ${\mathcal A}_{02}$ constructs a $\min\{m,\mu\}$-approximate schedule in $O(n\mu+m\mu)$ time (see Lemma \ref{le1} on page \pageref{le1}).

As for the evaluation and comparison of algorithms by the second criterion (the running time), Shmoys et al. (1994) admit that their algorithms are inefficient, but they assign the responsibility for that inefficiency on my algorithm:
``While all of the algorithms that we give are polynomial-time, they are all rather inefficient. Most rely on the algorithms of Sevast'yanov.'' However, I would look at this differently.

Of course, the authors of (Shmoys et al., 1994) are right that the complexity of their algorithms depends significantly on the complexity of our algorithm, for the simple reason that our algorithm is the \textbf{most significant part of their algorithms}, applied to \textbf{the majority of jobs} in the original problem instance (to so-called \emph{small jobs}). For this reason, the bound on the running time of their \textbf{first algorithm} coincides with that of ours. Which, however, is not a ``death sentence'' for it, since the bound $O(m^2\mu^2n^2)$ \textbf{is completely polynomial in all parameters} of the problem, and is only quadratic in the main parameter, the number of jobs $n$, whereas the values of the other two parameters, $m$ and $\mu$, are usually relatively small, and, while solving the problem for a fixed shop, they ``hit into'' their natural upper limits, when the planning horizon is expanded. Taking into account the possibility of linearization of the complexity of this algorithm in $n$, demonstrated in Section \ref{sec5}, and also due to the high speed of modern Supercomputers (\emph{SC}, for short), such complexity of the algorithm does not seem to be an insurmountable obstacle for its application to instances of practical size. However, this does not make this algorithm competitive with ours, since in accuracy it remains catastrophically worse than our (asymptotically optimal) algorithm \textbf{on the majority of instances of practically significant size}.

As for the second, $(2+\varepsilon)$-approximation algorithm from (Shmoys et al., 1994) (the complexity of which, after linearization, can be represented as $O(\mu n)+\psi(m,\mu,\varepsilon)$, where $\psi(m,\mu,\varepsilon)$ is an exponent of $m,\mu$, and $1/\varepsilon$), its main complexity (and the fundamental inapplicability of the algorithm for solving practical problems) lies not in our algorithm, but \textbf{is hidden in the ``constants''} that estimate the complexity of the \textbf{second half of the algorithm}. And as will be shown below, neither the linearization by $n$ of the running time of the first half of this algorithm, nor any technical progress in the design of supercomputers can correct this situation.


To convince the reader in the practical inapplicability of this algorithm, we will suggest to it to find a $(2+\varepsilon)$-approximate solution for a definitely small-size instance with $m=10$ machines in the shop and with $\mu=10$ operations per job (all of which are to be processed on 10 \textbf{different machines})\footnote{This special case of the Job Shop problem is called an \emph{acyclic job shop problem}, in which each job has exactly one operation on each machine, and each machine $M_i$ processes $n$ jobs according to some permutation $\pi^i=(\pi^i_1,\dots,\pi^i_n)$.}. At that, we will take the number of jobs $n\approx 10000$, which clearly does not exceed its average value for practically significant instances. We will neither overstrain their algorithm by proposing to find solutions arbitrarily close to 2-approximate ones, but take instead $\varepsilon=8$ (thus letting the algorithm find just a 10-approximate solution for our small instance).

Finally, we will allow the authors to use our new accuracy bound (\ref{eq11}) (which should help reduce the running time of their algorithm). We will also make five further agreements.

\textbf{A.} That our instance is being solved in a \emph{System} of parallel Supercomputers, each SC having the maximal known for today capacity of $2\cdot 10^{18}$ flops.

\textbf{B.} That there are 10 billion such SCs in our System on the Globe, i.e., about one ``personal Supercomputer'' for every inhabitant of the Earth\footnote{By the way, ONE such modern SC occupies an area greater than 1000 $m^2$, which results in total more than 10.000.000 $km^2$, --- more than the area of China.}.

\textbf{C.} That in each of 10 trillion galaxies (in the visible part of the Universe) there are 100 billion stars, and each star has 10 planets, on each of which we have placed an SC-system similar to that of the Earth. Totally, $10^{25}$ Globe SC-systems, forming the \emph{Supercomputer System of the Universe} (\emph{SSU}, for short).

\textbf{D.} That we have the opportunity to parallelize our problem, equally dividing the load between all computers of the SSU, and that each SC can work as long and continuously as desired.

\textbf{E.} That we measure the working time of our SSU in time units ``\emph{AU}'' (\emph{Age of the Universe}). We took the value of this amount to be \textbf{15} billion years.

\medskip
After that much strong assumptions (and suggestions on our part), the reader should have absolutely no doubts about the ``success of the enterprise''. However, the results of the forthcoming analysis may be very discouraging to those potential users of this algorithm who were attracted by its theoretical performance guarantees in accuracy and complexity given in (Shmoys et al., 1994).

To begin with, let us estimate the total capacity of our SSU, as well as how many flops (floating point operations) it can perform per the new unit of time, 1AU.

Taking into account the above characteristics of the System, its total capacity is $2\cdot 10^{18}\cdot 10^{10}\cdot 10^{25}=2\cdot 10^{53}$ flops. Accepting the agreement that the Earth year consists of 365.25 days, we obtain the relation: 1AU $=1.5 \cdot 10^{10}\cdot 365.25\cdot 24\cdot 3600\approx 4.73\cdot 10^{17}$ seconds. Multiplying this by the capacity of SSU, we obtain an upper bound on the capacity of SSU per 1AU: $10^{71}$ flopAU.

Now let us estimate the complexity of an approximate solution to our problem instance by the second algorithm from (Shmoys et al., 1994). The user of this algorithm will have to find an optimal schedule for the set of so called \emph{large jobs}, the number of which can be estimated from above by $n'=m^2\mu^2(\mu-1)/\varepsilon=11250$. If we solve this sub-problem by a simple enumeration of all combinations of permutations $\{\pi^i\,|\,i\in[m]\}$ (I remind that this sub-problem must be solved \textbf{exactly}, so as to guarantee the relative error of 10 for the resulting solution), then this will require enumerating $(n')!^m\approx (11250/\mathbf{e})^{112500}\cdot (2\boldsymbol{\pi}\cdot 11250)^5 \approx 10^{112500\cdot\log_{10} 4138.644}\cdot 10^{5\log_{10} 70 650} \approx 10^{406 921}$ variants of combinations of job permutations. For each variant of this schedule, graph $G$ of precedence constraints specifying the precedence of operations by jobs and by machines, contains $mn'=112500$ nodes and about $2mn'=225000$ arcs. It should be checked for the absence of directed cycles, and if there are no cycles, the length of the critical path in graph $G$ should be computed. Using for these purposes the algorithm with running time $O(mn')$ (linear in the number of arcs of the graph), we have to multiply the above amount by at least the number $225000\approx 10^{5.35}$ of arcs in $G$, which results in $10^{406 926}$ elementary actions to be performed. Thus, to perform these calculations on our CSU (the \textbf{Super-Computer System of the Univers}) and find a solution (to a given small instance) that would be no more than \textbf{10 times worse the optimum}, they would need time equal to $10^{406 855}$ \textbf{Ages of the Universe}.

\medskip
As for the question of the practical feasibility of algorithms ${\mathcal A}_{\varepsilon}$ from the PTAS designed by Jansen et al. (2003), preliminary estimation shows that the situation for these algorithms is even more deplorable starting from rather small values ??of parameters $m$ and $\mu$. (At that, the scheme works only with values $\varepsilon<1$.)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}\label{sec7}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this paper, we present a new version of the algorithm for solving the Job Shop problem based on the compact vector summation algorithm.
As shown in the paper, the new algorithm guarantees an improved a priori bound on the absolute error of the solutions obtained, while the bound on the running time remains the same. In addition, in Section~\ref{sec6} we perform a comparative analysis of quality of four currently known theoretical algorithms of approximate solution of this problem with a priori performance guarantees. Undoubtedly, the algorithms presented in (Shmoys et al., 1994) and (Jansen et al., 2003) have significant theoretical value from the view point of \textbf{parametric analysis of the complexity of approximate solution} of the Job Shop problem. However, in Section~\ref{sec6} we pursued a different goal: to perform a comparative analysis of the \textbf{practical suitability} of these algorithms for solving real-size instances of the Job Shop problem.
The results of this analysis and of the comparison of the four algorithms are the following conclusions (the first two relate to accuracy, the rest ones --- to the complexity of the algorithms).

(1) According to the theoretical accuracy bounds derived for these algorithms, \textbf{none of them dominates} the others \textbf{in the entire range of instances} of this problem (in terms of accuracy of the solutions obtained).

(2) For the overwhelming majority of instances having practically significant sizes, our algorithm with bound (\ref{eq16}) (ensuring \textbf{asymptotic optimality} of the solutions obtained with an increase in the planning horizon) has an advantage in accuracy over the algorithms from (Shmoys et al., 1994).

(3) Our algorithm has a moderate, polynomial in all main parameters, bound on the running time $O(m^2\mu^2n^2)$, which is just quadratic in the main parameter of the problem, the number of jobs $n$. At that, the other two parameters, $m$ and $\mu$, have natural upper bounds independent of length of the planning horizon ($T$), and thus, in the conditions of solving a practical problem \textbf{for a fixed shop}, with an increase in $T$ they can be treated as amounts ??limited by constants, which justifies the \textbf{practical feasibility} of our algorithm on \textbf{real size problem instances} on modern computers.

(4) The first of the two algorithms from (Shmoys et al., 1994) in its original version has no advantage in complexity over our algorithm, but after its modification (linearization in $n$, performed in Section~\ref{sec5}) it gains some advantage in the running time for large values of $n$. At that, as $n$ increases, it becomes \textbf{much worse than our algorithm} in accuracy (due to the fact that its accuracy bound, depending on $m$ and $\mu$, remains stable, while the relative error of our algorithm tends to zero). 

(5) The second algorithm from (Shmoys et al., 1994), supposedly guaranteeing $(2+\varepsilon)$-approximation in polynomial time (for any fixed values of parameters $m$, $\mu$, and $\varepsilon$), is \textbf{practically inoperative} on the overwhelming majority of instances (starting with instances of small size), since even \textbf{after its linearization} in $n$ it is not capable of obtaining even 10-approximate solutions for small enough instances \textbf{in any physically observable time}. Thus, \textbf{its comparison with our algorithm makes no sense} on the majority of real-size instances.

The situation with the practical applicability of any algorithm ${\mathcal A}_{\varepsilon}$ from the PTAS presented in (Jansen et al., 2003) (according to our preliminary estimation) seems even more hopeless. Moreover, as our calculations performed in Section~\ref{sec6} convincingly demonstrate, this deplorable situation with the last two algorithms can be corrected by no future progress in the development of Supercomputers.

\medskip
The calculations made in Section \ref{sec6} raise up some further interesting questions: 

--- What are the huge Super-Computers needed for, if, even with the help of algorithms with ``improved'' performance guarantees, the Super-Computer Army of the whole Universe for the whole Eternity is not capable of finding a rough approximate solution for a small instance of an ordinary (just strongly NP-hard) discrete optimization problem?
 
--- What are the ingenious algorithms with theoretically justified ``excellent perfor\-mance guarantees'' (high accuracy and ``polynomial-time'' complexity) needed for, if, even with the power of the Super-Computer System of the Universe and for the whole Age of the Universe they are unable to find a rough approximate solution for a small problem instance? 

The answer to the first question, apparently, is that Super-Computers are dedica\-ted to solving some other-type enumeration problems (consisting in processing a large amount of information in a minimum time and allowing maximum parallelization of this process). And even when they are used for solving such problems as the Job Shop problem, they should run programs for the algorithms having more definite performance guarantees (without hiding their inaccuracy into forms like ``$O(\cdot)$'' and hiding their running time into ``constants'' with indefinite values). When any new algorithms appear that position themselves as an ``improvement of all previous ones'', a not bad idea is to test their practical applicability in terms of the time unit ``AU'' (as demonstrated in Section \ref{sec6}). And in case that 1AU appears to be insufficient to find a solution by the new method, this clearly indicates that one should not rush into programming such an algorithm.

The answer to the second question is ambiguous and requires a detailed analysis of each algorithm under consideration. It is only clear that the mere existence of ``excellent theoretical performance guarantees'' for an algorithm does not guarantee equally excellent practical behavior of this algorithm in solving real-size problems (as shown by the above analysis of the algorithms from (Shmoys et al., 1994) and (Jansen et al., 2003)). It is obvious that all three algorithms were not originally intended for solving practical instances of the Job Shop problem. They have purely \textbf{theoretical significance} and contribute to the \textbf{theoretical analysis of the parametric complexity of an approximate solution} of this problem.

Thus, our algorithm remains today \textbf{the only workable algorithm} for an approximate solution to the Job Shop problem with \textbf{theoretically justified a priori bounds} of their quality, enabling one for \textbf{practically significant instances} of this problem to find solutions with acceptable accuracy and in a realistic time.

As for the approach we have developed for an approximate solution of the Job Shop problem (first proposed in (Sevastyanov, 1984, 1986) and improved in this paper), its potential, as we see it, is far from being exhausted and lies in two possible directions. First, we are not sure that this paper presents the most perfect method for reducing the original problem to a compact vector summation problem. \textbf{Reducing the degree of dependence of the solution error on parameters} $m$ and $\mu$ is, in our opinion, a relevant and quite achievable goal. Second, the unimprovability of the (presented here) accuracy bound of the vector summation algorithm \textbf{had not been proved} either, which gives hope for a possibility of its further improvement.


\bigskip
\begin{thebibliography}{99} %***

\bibitem{BBB76} %***
Babuskin, A.I. Basta, A.L., and Belov, I.S. \emph{The scheduling a three-machine job shop problem}, Avtomat. i Telemeh., No. 7 (1976), 154--158 (in Russian).

\bibitem{BBB77} %***
Babushkin, A.I., Bashta, A.A., and Belov, I.S. \emph{Scheduling for problems of counterroutes}, Cybern. Syst. Anal. \textbf{13} (1977), 611--617;\\ \doi{10.1007/BF01069562}

\bibitem{BBBD75} %***
Babuskin, A.I., Basta, A.L., Belov, I.S., and Dushin, B.I. \emph{Minimizing of the production line cycle}, Avtomat. i Telemeh., No. 6 (1975), 161--167 (in Russian).

\bibitem{BS74} %***
Belov, I.S. and Stolin, Ja.N. \emph{An Algorithm for the Single-Route Scheduling Problem}, in: Mathematical Economics and Functional Analysis, ``Nauka'', Moscou (1974), 248--257 (in Russian).

\bibitem{CPW98} %***
Chen, B., Potts, C.N., and Woeginger, G.J. \emph{A review of machine scheduling: complexity, algorithms and approximability}, in: Handbook of Combinatorial Optimization, Boston: Kluwer Acad. Publ., \textbf{3} (1998), 21--169;\\ \doi{10.1007/978-1-4613-0303-9\_25} 

\bibitem{D89} %***
Dushin, B.I. \emph{Algorithm for the $p$-route Johnson problem}, Kibernetika, 2 (1989), 119--122 (in Russian).

\bibitem{GJS76} %***
Garey, M.R., Johnson, D.S., and Sethi, R. \emph{The Complexity of Flowshop and Jobshop Scheduling}, Math. Oper. Res. {\bf 1} (1976), 117--129;\\ \doi{10.1287/moor.1.2.117}

\bibitem{JSS03} %***
Klaus Jansen, Roberto Solis-Oba, and Maxim Sviridenko (2003) Makespan Minimization in Job Shops: A Linear Time Approximation Scheme, 
SIAM J. Discret. Math., 16(2), 288--300. \doi{10.1137/S0895480199363908}

\bibitem{S99} %***
  A.~Kononov, S.~Sevastianov, and I.~Tchernykh,
  When difference in machine loads leads to efficient scheduling in open shops,
  Annals of Operations Research, 92 (1999), 211-239.
DOI:10.1023/A:1018986731638

\bibitem{LRB77} %***
Lenstra, J.K., Rinnooy Kan, A.H.G., and Brucker, P. \emph{Complexity of machine scheduling problems}, Annals of Oper. Res. \textbf{1} (1977), 343--362;\\ \doi{10.1016/S0167-5060(08)70743-X}

\bibitem{NS93} %***
Neumytov, Ju.D., and Sevastyanov, S.V. \emph{Approximation algorithm with a tight accuracy bound for the three-machine counter-routes problem}, Upravlyaemye Sistemy {\bf 31} (1993), 53--65 (in Russian).

\bibitem{S74} %***
Sevastyanov, S.V. \emph{Asymptotical Approach to Some Scheduling Problems}, in: Third All-Union Conf. Problems of Theoretical Cybernetics. Thes. Dokl., Novosibirsk (June, 1974), 67--69 (in Russian).

\bibitem{S75} %***
S.V. Sevastyanov, \emph{Asymptotical Approach to Some Scheduling Problems}, Upravlyaemye Sistemy {\bf 14} (1975), 40--51 (in Russian).

\bibitem{S80a} %***
  S.V. Sevastyanov (1980) Approximate Solution to a Calendar-Planning Problem,
  {\em Upravlyaemye Sistemy} {\bf 20}, 49—63 (in Russian)

\bibitem{S81} %***
Sevastyanov, S.V. \emph{Some generalizations of the Johnson problem}, Upravlyaemye Sistemy {\bf 21} (1981), 45--61 (in Russian).

\bibitem{S82} %***
Sevastyanov, S.V. \emph{Algorithms with performance guarantees for the Johnson and the Akers-Friedman problems in the case of three machines}, Upravlyaemye Sistemy {\bf 22} (1982), 51--57 (in Russian).

\bibitem{S84} %***
  S.V. Sevast'yanov, Efficient construction of schedules close to optimal for the cases of arbitrary and alternative routes of parts,
  Soviet Math. Dokl., {\bf 29} (1984), 447--450; Zbl 0586.90051

\bibitem{S86} %***
Sevast'yanov, S.V. \emph{Bounding algorithm for the routing problem with arbitrary paths and alternative servers}, Cybern. Syst. Anal. \textbf{22} (1986), 773--781;\\ \doi{10.1007/BF01068694}\\ (Translated from ``Kibernetika'', November-December, No.6, (1986), 74--79.) 

\bibitem{S91} %***
Sevastyanov, S.V., \emph{On the Compact Vector Summation}, Diskretnaya Matematika, \textbf{3}(3) (1991), 66--72. (in Russian)

\bibitem{S93} %***
Sevastyanov, S.V. \emph{Construction of an approximate schedule for a flow-type system}, Upravlyaemye Sistemy, \textbf{31} (1993), 66--71 (in Russian).

\bibitem{S94} %***
Sevast'janov, S.V. \emph{On Some Geometric Methods in Scheduling Theory: a survey}, Discrete Appl. Math. \textbf{55}(1) (1994), 59--82;\\
\doi{10.1016/0166-218X(94)90036-1}

\bibitem{S95} %***
Sevast'janov, S.V. \emph{Vector summation in Banach space and polynomial algorithms for flow shops and open shops}, Mathematics of Operations Research, \textbf{20}(1) (1995), 90--103;\ \doi{10.1287/moor.20.1.90}

\bibitem{S96} %***
Sevast'yanov, S.V. \emph{Efficient scheduling in open shops}, in: A.D.~Korshunov (ed.), Discrete Analysis and Oper. Res., Kluwer, Dordrecht, 1996, 235--255;\\ \doi{10.1007/978-94-009-1606-7\_17}

\bibitem{S97} %***
Sevast'yanov, S.V. \emph{Nonstrict vector summation in the plane and its application to scheduling problems}, in: A.D.~Korshunov (ed.), Operations Research and Discrete Analysis, Kluwer, Dordrecht, 1997, 241--272;\\ \doi{10.1007/978-94-011-5678-3\_19}

\bibitem{S98} %***
Sevastianov, S., \emph{Nonstrict vector summation in multi-operation scheduling}, Annals of Operations Research, \textbf{83} (1998), 179--211;\\ \doi{10.1023/A:1018908013582}

\bibitem{SSW94} %***
D.B. Shmoys, C. Stein and J. Wein, \emph{Improved Approximation Algorithms for Shop Scheduling Problems}, SIAM Journal on Computing {\bf 23} (1994), 617--632;\\ \doi{10.1137/S009753979222676X}

\bibitem{SS95} %***
Sotskov, Y.N., and Shakhlevich, N.V. \emph{NP-hardness of shop-scheduling problems with three jobs}, Discrete Applied Math. 59 (1995), 237--266;\\ \doi{10.1016/0166-218X(95)80004-N}
\end{thebibliography}


\renewcommand{\appendixname}{\sc Appendix}
\appendix
\section{Searching for a base of a given family of vectors}\label{app1}

Next, $\lin(Y)$ will denote the linear hull of a set $Y\subseteq\mathbb{R}^{d}$.

\begin {definition}\rm
A set of vectors $X_{B}\subseteq\mathbb{R}^{d}$ is called a {\em base of a family of vectors} $X\subset\mathbb{R}^{d}$, if $X_{B}$ is linearly independent and $X_{B}\subseteq X\subseteq\lin (X_{B})$.
\end {definition}

The following lemma was proved in \cite{S80a}.

\begin {lemma}[\cite{S80a}]\label{le5}
Let a family of vectors
$X=\{x_{1},\dots,x_{n}\}\subset\mathbb{R}^{d}$ and a family of numbers $\Lambda=\{\lambda_{j}\in[0,1]\,|\,j\in[n]\}$ be given.
Then there exists an algorithm that in $O(nd^{2})$ time finds a base $X_{B}$ of family $X$ and
a family of numbers $\Lambda'=\{\lambda_{j}'\in[0,1]\,|\,j\in[n]\}$ such that
$$\left(\sum_{j\in[n]}\lambda_{j}'x_j = \sum_{j\in[n]}\lambda_{j}x_j\doteq x\right)\ \&\ 
\left(\{x_j\,|\,\lambda_j'\in(0,1)\}\subseteq X_{B}\right).$$
\end {lemma}

It is easy to verify the existence of the desired base of the family of vectors $X$ and of the family of numbers $\{\lambda_{j}'\}$. Indeed, if the family of vectors $\{x_{j}\,|\,\lambda_{j}\in(0,1)\}$ is linearly dependent, then we can find this dependence and, using it, change the coefficients $\{\lambda_{j}\in(0,1)\}$ while preserving the sum $\sum \lambda_{j}x_{j}$ so that at least one of the coefficients turns to $0$ or $1$. Repeating this procedure no more than $n$ times, we arrive at a linearly independent family of vectors $\{x_{j}\,|\,\lambda_{j}\in(0,1)\}$, which is obviously contained in some base of family $X$. If (in the case of $|X|>d$) we first consider subfamilies of vectors $X'\subseteq X$ of cardinality $|X'|=d+1$, and use the usual Gauss method to find (in $O(d^3)$ time) the coefficients of the linear dependence of vectors in each such subfamily, then we can obtain the desired base and the family of numbers $\{\lambda_{j}'\}$ in time $O(nd^3)$. The procedure below yields the desired result in $O(nd^2)$ time.

The procedure executes a loop on $t=1,\dots,n$. At the end of each iteration $t$ of this loop, we know coefficients $\{\lambda_{j}'\in[0,1]\,|\,j\in[n]\}$ and a partition of the index set $[n]$ into three subsets: $[n]= J_{Z}\cup J_{W}\cup J_{R}$ such that:
$$\sum_{j\in[n]}\lambda_{j}'\,x_{\!j} = x;\ \lambda_{j}'=\lambda_{j},\ \forall\ j\in J_{R}=\{t+1,\dots,n\};\ \lambda_{j}'\in\{0,1\},\ \forall\ j\in J_{Z};$$
$$X_{B}=\{x_{j}\,|\,j\in J_{W}\}\ \mbox{is a base of the subfamily}\ \{x_{j}\,|\,j\in[t]=J_{W}\cup J_{Z}\}.$$

Thus, initially all coefficients $\lambda_{j}'$ coincide with $\lambda_{j}$. At subsequent iterations $t$, the set of indices $\{j\in J_{R}\}$ corresponds to those coefficients $\lambda_{j}'$ that {\em have not yet been transformed}, and the set $J_{Z}$ corresponds to those ones that {\em will not be further transformed} (they are integers). The coefficients $\{\lambda_{j}\,|\,j\in J_{W}\}$ are ``in progress''.

The base $X_{B}$ changes dynamically during the iterations of the loop over $t$: new vectors are added to it, while some vectors (that were previously included) leave it. (In the latter case, their indices move from set $J_{W}$ to set $J_{Z}$.) The current list of the base is determined by the set $J_{W}=\{j'\!(1),j'\!(2),\dots,j'\!(s)\}$ of indices of the vectors included in it. It should be noted that those indices of the base vectors will not necessarily be listed in ascending order, since the \emph{place of each new vector in the base} is dynamically determined during the algorithm. In this case, the place in the base that a vector receives when it enters the base is \textbf{permanent} until the moment of its leaving the base or until the end of the algorithm. This place corresponds to the column number of matrix $C$ of the transition from base $X_{\!B}=\{x_{\!j'\!(1)},\dots,x_{\!j'\!(s)}\}$ to basis $B$ (to be defined below).

Thus, at each iteration $t$, beyond the sets $J_{Z},J_{W},J_{R}$, we adjust the following:\\
--- basis $B=\{b_1,\dots,b_s\}$ of space $\lin\{x_1,\dots,x_t\}$ and the first $s=|J_{W}|$ components of the formed permutation $\pi=(\pi_1,\dots,\pi_d)$ of coordinates of space $\mathbb{R}^{d}$, so that\
$b_{k}(\pi_{i})= 0,\ \forall\ i\in[k-1];\ b_{k}(\pi_{k})\ne 0,\ \forall\ k\in[s]$. Namely, both basis $B$ and permutation $\pi$ may be incremented by a new, $(s+1)$-th element, while $s$ previously defined elements remain unchanged;\\
--- matrix $C=(c_{k,i})_{k,i\in[\!s]}$ of the transition from base $X_{\!B}=\{x_{\!j'\!(1)},\dots,x_{\!j'\!(\!s)}\}$ to basis $B$:
\begin{equation}\label{eq19}
b_{k}=\sum_{i\in[\!s]} c_{k,i}\,x_{\!j'\!(i)},\ k\in[s];
\end{equation}
--- function $j'(i)$, specifying the position of each vector $x_j\in X_{\!B}$ in the base and in matrix $(c_{k,i})$ (the $i$-th column of this matrix corresponds to vector $x_{\!j'\!(i)}$). 

When adding a new vector $x_t$ to consideration at iteration $t$, the following three cases are possible.

(1) Vectors $X_{B}\cup\{x_t\}$ are linearly independent. In this case, vector $x_t$ is added to basis $X_{B}$ and placed in it at the $(s+1)$-th position, where $s=|X_{B}|$. In addition, basis $B$ and permutation $\pi$ are supplemented with $(s+1)$-th elements; matrix $C$ is incremented by one more column and one row.

(2) Vectors $X_{B}\cup\{x_t\}$ are linearly dependent; vector $x_t$ does not get into the base. After recalculating the coefficients $\{\lambda_{j}'\}$, index $t$ of vector $x_t$ is transferred from $J_{W}$ to $J_{Z}$. The base, the basis, matrix $C$, and permutation $\pi$ remain unchanged.

(3) Vectors $X_{B}\cup\{x_t\}$ are linearly dependent; one of vectors of the base ($x_{\!j'\!(i^*)}$) is removed from it, and vector $x_t$ is inserted into the base \textbf{at the vacated position} $i^*$. (In matrix $C$ it will correspond to the recalculated $i^*$-th column.) Matrix $C$ and function $j'(i)$ are recalculated; basis $B$ and permutation $\pi$ remain unchanged.

\medskip
\begin{center}
\textbf{Procedure}~\emph{Search\_for\!\_\!a\_\!Base}(\mbox{\textbf{integer}}\!:\ $n{,}s{;}$\\ 
\textbf{family of integers:}\ $\{j_B[i]\,|\,i\in[d]\}$; \textbf{family of vectors in}\ $\mathbb{R}^d\!:\ X\!=\!\{x_t\,|\,t\in[n]\}$;\\ 
\textbf{family of reals:}\ $\Lambda=\{\lambda_{j}\in[0,1]\,|\,j\in[n]\},\Lambda'=\{\lambda_{j}'\in[0,1]\,|\,j\in[n]\})$;
\end{center}
\%\ The OUTPUT parameter $\{j_B[i]\,|\,i\in[s]\}$ is the set of indices of the vectors\\
\%\ $x_t\in X$ forming the base $X_B$ of $X$ that we are looking for\\
\%\ \textbf{Local parameters:}\\
\rule{1em}{0pt} \textbf{integer:}\ $t,k,j,i,i^*$;\ \textbf{real:}\ $\varepsilon,\varepsilon^*$;\ \textbf{vector in}\ $\mathbb{R}^d:$\ $b$;\\
\rule{1em}{0pt} \textbf{family of integers:}\ $J_{R},J_{Z},J_{W},J_{W}',\{\pi_k\,|\,k\in[d]\}$;\\ 
\rule{1em}{0pt} \textbf{family of reals:}\ $\{\mu_k\,|\,k\in[n]\};\ \{\mu_k'\,|\,k\in[n]\};\ \{c_{k,i}\,|\,k,i\in[d]\}$;\\
\rule{1em}{0pt} \textbf{family of vectors in}\ $\mathbb{R}^d\!:\ B\!=\!\{b_k\,|\,k\in[d]\}$;\\ 
%
\noindent\textbf{BEGIN}

$J_{R}\leftarrow[n];\ J_{Z}\leftarrow\varnothing;\ J_{W}\leftarrow\varnothing;\ \lambda_{j}'\leftarrow\lambda_{j},\ \forall\ j\in[n];\ s\leftarrow 0;$

\textbf{for}\ $t\leftarrow 1,\dots,n$\ \textbf{do begin}\\
\rule{2em}{0pt} $J_{R}\leftarrow J_{R}\setminus\{t\}$;\ \textbf{if}\ $x_{t}=0$\ \textbf{then}
      $\{\lambda_{t}'\leftarrow 0;\ J_{Z}:=J_{Z}\cup\{t\}\}$\\
\rule{2em}{0pt} \textbf{else begin}\\
\rule{3em}{0pt} $J_{W}\leftarrow J_{W}\cup\{t\};\ j_B[s+1]\leftarrow t;\ b\leftarrow x_t$;\\
\rule{3em}{0pt} \textbf{for}\ $k\leftarrow 1,\dots,s$\ \textbf{do}\
 $\{\mu_k\leftarrow b(\pi_k)/b_k(\pi_k);\ b\leftarrow b-\mu_k b_k\}$;\\
\rule{2em}{0pt} \%\ We have obtained vector $b=x_{t}-\sum_{k\in[\!s]} \mu_k b_k$ such that $b(\pi_i)=0\ (i\in[s])$. 
\rule{2em}{0pt} \%\ Substituting the values of $\{b_k\}$ from (\ref{eq19}) to this expression, we obtain\\
\rule{2em}{0pt} \%\ $b=-\sum_{i\in[\!s+1]} \mu_{\!j_{\!B}[i]}' x_{\!j_{\!B}[i]}$, where the coefficients $\{\mu_{\!j_{\!B}[i]}'\}$ are defined as:\\
\rule{3em}{0pt} $\mu_{\!j_{\!B}[i]}'\leftarrow \sum_{k\in[\!s]}\mu_{k}\cdot c_{k,i},\ i\in[s];\ \mu_{\!j_{\!B}[s+1]}'\leftarrow -1$;\\
\%\ As proved in \cite{S80a}, $x_{j_{\!B}[s+1]}$ linearly depends on vectors $\{x_{j_{\!B}[1]},\dots,x_{j_{\!B}[\!s]}\}$, if and\\
\%\ only if $b=0$. We next check, if $b(\pi_i)=0$\ holds for all $i\in[d]\setminus\{\pi_{i}\,|\,i\in[s]\}$.\\
\rule{3em}{0pt} \textbf{if} $b\ne 0$ \textbf{then begin}\\
\rule{4em}{0pt} \mbox{find a coordinate} $i^*\in[d]\setminus\{\pi_{i}\,|\,i\in[s]\}$ \mbox{such that} $b(i^*)\ne 0$;\\ 
\rule{4em}{0pt} $\pi_{s+1}\leftarrow i^*;\ b_{s+1}\leftarrow b$;\\
\rule{3em}{0pt} \%\ We next complement matrix $(c_{i,j})$ by defining the coefficients from the\\
\rule{3em}{0pt} \%\ $(s+1)$-th row and the $(s+1)$-th column as:\\
\rule{4em}{0pt} $c_{s+1,i}\leftarrow -\mu_{\!j_{\!B}[i]}',\ i\in[s+1]$;\\
\rule{4em}{0pt} $c_{k,s+1}\leftarrow 0,\ k\in[s];\ s\leftarrow s+1$;\\
\rule{3em}{0pt} \textbf{end}\ \% ``if $b\ne 0$''\\
\rule{3em}{0pt} \textbf{else begin}\ \% the case when vectors $\{x_{\!j_{\!B}[1]},\dots,x_{\!j_{\!B}[s+1]}\}$ are linearly dependent,\\
\rule{8em}{0pt} \%\ since $\sum_{i\in[\!s+1]}\mu_{\!j_{\!B}[i]}' x_{\!j_{\!B}[i]}=0$, while $\mu_{\!j_{\!B}[s+1]}'=-1$.\\
\rule{4em}{0pt} Define the set $J_{W}'\doteq\{j\in J_{W}\,|\,\mu_{\!j_{\!B}[i]}'\ne 0\}$;\\
\rule{4em}{0pt} find $\varepsilon^*=\max\{\varepsilon\,|\,\lambda_{j}'+\varepsilon\mu_{\!j}'\in [0,1],\ \forall\ j\in J_{W}'\}$;\\ 
\rule{4em}{0pt} redefine the coefficients $\{\lambda_{j}'\,|\,j\in J_{W}'\}$ as: 
$\lambda_{j}'\leftarrow\lambda_{j}'+\varepsilon^*\mu_{\!j}',\ j\in J_{W}'$;\\
\rule{3em}{0pt} \%\ At that, the sum $\sum_{j\in[n]}\lambda_{j}'x_{\!j}$ does not change and at least one of the\\
\rule{3em}{0pt} \%\ coefficients $\{\lambda_{j}'\,|\,j\in J_{W}'\}$ takes a value from $\{0,1\}$.\\
\rule{4em}{0pt} Find $i^*\in[s+1]$ such that $(\lambda_{\!j_{\!B}[i^*]}'\in\{0,1\})\ \& (j_{\!B}[i^*]\in J_{W}')$;\\
\rule{4em}{0pt} $J_{W}\leftarrow J_{W}\setminus\{j_{B}[i^*]\};\ J_{Z}\leftarrow J_{Z}\cup\{j_{B}[i^*]\}$;\\
\rule{3em}{0pt} \%\ In case that $j_{B}[i^*]=j_{B}[s+1]=t$, there is nothing to do next, because
\rule{3em}{0pt} \%\ both the base and the basis \textbf{remain unchanged}. Otherwise, we replace 
\rule{3em}{0pt} \%\ vector $x_{\!j_{\!B}[i^*]}$ of base $X_{\!B}$ by vector $x_{t}$ and recalculate the coefficients $(c_{k,i})$
\rule{3em}{0pt} \%\ of the transition from the base to basis $B$ (which remains unchanged)
\rule{3em}{0pt} \%\ according to formula (\ref{eq19}). (We note here that $J_{W}''\doteq J_{W}'\setminus\{t\}\ne\varnothing$, since\\
\rule{3em}{0pt} \%\ $x_t=\sum_{j\in J_{W}''} \mu_{\!j}' x_j\ne 0$.) So,\\
\rule{4em}{0pt} \textbf{if} $i^*\le s$ \textbf{then begin}\\
\rule{5em}{0pt} $c_{k,i^{*}}\leftarrow c_{k,i^{*}}/\mu_{\!j_{\!B}[i^*]}'$;\ $c_{k,i}\leftarrow c_{k,i}-c_{k,i^{*}}\mu_{\!j_{\!B}[i]}',\ i\in[s]\setminus\{i^*\},\ k\in[s]$;\\
\rule{5em}{0pt} $j_{B}[i^*]\leftarrow t$;\\
\rule{4em}{0pt} \textbf{end};\ \%\ ``if''\\
\rule{3em}{0pt} \textbf{end};\ \%\ ``else''

\textbf{end};\ \%\ ``for $t$''\\
\textbf{END};\ \%\ of Procedure \emph{Search\_for\!\_\!a\_\!Base}



\section{Vector summation algorithm ${\mathcal A}_1$ from Theorem \ref{th91}}\label{app2}

\begin{definition}\label{de3}\rm
Let $B$ be a convex set in $\mathbb{R}^d,\ I$ be a finite set such that $k\doteq|I|\ge d$,\ 
$a\in\mathbb{R}^d,\ B_a\doteq\mbox{\rm conv}\{0,a-B/d\}$. A family of vectors $\{x_{i}\,|\,i\in I\}\subset B$ is called a {\em $B_{a}$-balanced system of vectors} (\emph{$B_{a}$-BSV}, for short), if there is a family of numbers $\{\lambda_{i}\in\mathbb{R}\,|\,i\in I\}$ satisfying the conditions:
\begin {equation}\label{23.10}
 \lambda_{i}\in [0,1],\, i\in I,
\end {equation}
\begin {equation}\label {23.11}
 \sum_{i\in I}\lambda_{i} =k-(d-1),
\end {equation}
\begin {equation}\label {23.12}
 \sum_{i\in I}\lambda_{i}x_{i}\in B_{a}.
\end{equation}
\end{definition}

The construction of the desired sequence $\pi^*$ of summing the vectors of family $X=\{x_i\,|\,i\in[N]\}\subset\mathbb{R}^d$ by algorithm ${\mathcal A}_1$ is based on the cyclic usage of the procedure \emph{Next\_BSV} (described below), which, heaving at its input a $B_{a}$-balanced system of vectors $U=\{x_i\,|\,i\in I\}\subset\mathbb{R}^d$ (defined for a subset $I\subseteq[N]$, s.t. $|I|\ge d+1$), finds an index $i^*\in I$ such that the family $U\setminus\{x_{i^*}\}$ is a $B_{a}$-BSV again.

The correctness of this procedure was justified in

\begin{lemma}[\cite{S91}]
Let $B$ be a convex set in $\mathbb{R}^d,\ a\in\mathbb{R}^d,\ \{x_{i}\in B\,|\,i\in I\}$ be a $B_{a}$-BSV with $|I|\doteq k\ge d+1$, for which the corresponding family of numbers $\{\lambda_{i}\,|\,i\in I\}$ satisfying the conditions (\ref{23.10})--(\ref{23.12}) is known. Then there exists an index $i^*\in I$ such that the system of vectors $U'=\{x_{i}\,|\,i\in I\setminus\{i^*\}\}$ is $B_{a}$-BSV again; index $i^*$ and the numbers $\{\lambda_{i}'\}$ corresponding to vectors from $U'$ can be found in $O(k d^{\,2})$ time.
\end{lemma}

\begin{center}
\textbf{Procedure} \emph{Next\_BSV}(\mbox{\textbf{integer:}}\ $i^*,k$;\ \mbox{\textbf{finite set of integers:}}\ $I$;\ \ \%\ $|I|=k$\\
\mbox{\textbf{family of vectors in $\mathbb{R}^d$:}}\ $U=\{x_{i}\,|\,i\in I\}$;\ \mbox{\textbf{family of reals:}}\ $\Lambda=\{\lambda_{i}\,|\,i\in I\})$;
\end{center}
\%\ The input family of vectors $U$ is a $B_{a}$-BSV with given coefficients $\{\lambda_{i}\,|\,i\in I\}$.\\
\%\ The set $I$ (with the output value $I\leftarrow I\setminus\{i^*\}$), numbers $i^*$ and $k$, and the\\ 
\%\ transformed families $U$ and $\Lambda$ are also \textbf{output parameters} of the procedure.\\[1ex]
\%\ \textbf{Local parameters:}\\
\rule{1em}{0pt} \textbf{integer:}\ $i,i_0$;\\
\rule{1em}{0pt} \textbf{real:}\ $\varepsilon, r$;\\
\rule{1em}{0pt} \textbf{a finite set of integers:}\ $I_1,I_W,I_W^-,I_W'';$\\
\rule{1em}{0pt} \textbf{a family of reals with indices $\{i\in I\}$:}\ $\{\lambda_{i}'\}, \{\lambda_{i}''\}, \{\mu_{i}\}, \{\mu_{i}'\}, \{\mu_{i}''\}, \{\eta_{i}\};$\\
\rule{1em}{0pt} \textbf{family of vectors in} $\mathbb{R}^{d+1}$:\ $\bar U=\{\bar x_{i}\,|\,i\in I\};\ \bar U'=\{\bar x_{i}\,|\,i\in I_W\}$;\\ 
\rule{1em}{0pt} \textbf{vector in} $\mathbb{R}^{d}$:\ $c,b$;\\ 
\rule{1em}{0pt} \textbf{vector in} $\mathbb{R}^{d+1}$:\ $\bar c, \bar a$;\\ 
%
\noindent\textbf{BEGIN}

Put $\lambda_{i}'\leftarrow (k-d)\lambda_{i}/(k-d+1),\ \forall\ i\in I$. Then we have:
\begin {equation}\label {23.13}
 \lambda_{i}'\in [0,1],\ i\in I,
\end {equation}
\begin {equation}\label {23.14}
 \sum_{i\in I} \lambda_{i}'=k-d,
\end {equation}
\begin {equation}\label {23.15}
 \sum_{i\in I} \lambda_{i}'x_{i}\in B_{a}.
\end {equation}
To obtain the desired result (a $B_{a}$-BSV with the number of vectors less by one), it remains to transform the coefficients $\{\lambda_{i}'\}$ while preserving the properties (\ref{23.13})--(\ref{23.15}) so that one of the coefficients ($\lambda_{i^*}'$) becomes zero (which would mean that the family of vectors $U'=\{x_{i}\,|\,i\in I\setminus\{i^*\}\}$ becomes a $B_{a}$-BSV). The desired transformation will require at most four ``Steps'' described below.

\medskip {\bf Step 1.}
Let us define a family of vectors $\bar U=\{\bar{x}_{i}\doteq(x_{i},1)\,|\,i\in I\}\subset\mathbb{R}^{d+1}$, and then transform the coefficients $\{\lambda_{i}'\}$ while preserving the condition (\ref{23.13}) and the sum $\sum_{i\in I}\lambda_{i}'\bar{x}_{i}$ so that the subfamily of vectors $\bar U'\doteq\{\bar{x}_{i}\in\bar U\,|\,\lambda_{i}'\in(0,1)\}$ is contained in some base $\bar U^*$ of family $\bar U$. By Lemma \ref{le5}, the desired coefficients $\{\lambda_{i}'\}$ and the base $\bar U^*\subseteq\bar U$ can be found (by means of the procedure \emph{Search\_for\!\_\!a\_\!Base} described in Application \ref{app1}) in $O(|I|d^{\,2})$ time.
If among the coefficients $\{\lambda_{i}'\}$ there is a coefficient $\lambda_{i^*}'=0$, then the family of vectors $\{x_{i}\}_{i\ne i^*}$ is the desired $B_{a}$-BSV with coefficients $\{\lambda_{i}\leftarrow\lambda_{i}'\}_{i\ne i^*}$. Next we assume that
\begin{equation}\label{23.16}
 \lambda_{i}'>0,\ \forall\ i\in I.
\end{equation}

Let $I_W\doteq\{i\in I\,|\,\lambda_i'\in(0,1)\},\ I_1\doteq\{i\in I\,|\,\lambda_{i}'=1\}$. Then using (\ref{23.14}) and (\ref{23.16}), we obtain
$$k-d=\sum_{i\in I}\lambda_{i}'=\sum_{i\in I_1}\lambda_{i}'+\sum_{i\in I_W}\lambda_{i}'=|I_1|+\sum_{i\in I_W}\lambda_{i}'=k-|I_W|+\sum_{i\in I_W}\lambda_{i}',$$
implying $d+\sum_{i\in I_W}\lambda_{i}'=|I_W|\le|\bar U^*|\le d+1$. 
Thus, $\sum_{i\in I_W}\lambda_{i}'$ must be an integer not greater than 1. It cannot be 0 (since $|I_W|\ge d$), so, we obtain: 
$$\sum_{i\in I_W}\lambda_{i}'=1,\ |I_W|=d+1,\ \bar U'\ \mbox{is a basis of}\ \mathbb{R}^{d+1}.$$

Let us transform the coefficients $\{\lambda_{i}'\,|\,i\in I_W\}$ while preserving the properties (\ref{23.13})--(\ref{23.15}) so that one of the coefficients becomes zero. To that end, we denote:
\begin{equation}\label{23.16a}
c\doteq -\sum_{i\in I_1} x_{i},\ \bar{c}\doteq(c,1)\in \mathbb{R}^{d+1},\ b\doteq\sum_{i\in I} \lambda_{i}'x_{i}\in B_{a}.
\end{equation}

{\bf Step 2.}
Let us find the unique representation $\bar {c}=\sum_{i\in I_W} \mu_{i}\bar{x}_{i}$. The coefficients $\{\mu_{i}\}$ can be found, for example, by the Gauss method in $O(d^{\,3}\!)\le O(kd^{\,2})$ time. If
\begin{equation}\label{23.17}
 I_W^-\doteq\{i\in I_W\,|\,\mu_{i}\le 0\}\ne\varnothing,
\end{equation}
we define $\varepsilon\doteq\max_{i\in I_W^-}\{-\mu_{i}/(\lambda_{i}'-\mu_{i})\}$. Clearly, $\varepsilon \in [0,1)$,
$$\lambda_{i}''\doteq(1-\varepsilon)\mu_{i}+\varepsilon\lambda_{i}'=\mu_{i}+\varepsilon(\lambda_{i}'-\mu_{i})\ge 0,\ \forall\ i\in I_W,$$
and there is an $i^*\!\in I_W^-$ such that $\lambda_{i^*}''=0$. It follows from $\sum_{i\in I_W}\!\mu_{i}=1,\,\!\sum_{i\in I_W}\!\!\lambda_{i}'\!=1$ that $\sum_{i\in I_W}\lambda_{i}''=1$. Put $\lambda_{i}''\leftarrow 1,\ \forall\ i\in I_1$. 
Then $\sum_{i\in I}\lambda_{i}''= |I_1|+\sum_{i\in I_W}\lambda_{i}''=k-|I_W|+1=k-(d+1)+1=k-d$. Furthermore, due to (\ref{23.16a}) and $\varepsilon \in [0,1)$,
\begin{eqnarray*}
 \sum_{i\in I}\lambda_{i}''x_{i}&=&
 \sum_{i\in I_1} x_{i}+\sum_{i\in I_W} \lambda_{i}''x_{i}=-c+\sum_{i\in I_W} [(1-\varepsilon)\mu_{i}+\varepsilon\lambda_{i}']x_{i}=\\[1em]
 &=& -c+(1-\varepsilon)c+\varepsilon(c+b)= \varepsilon b\in B_{a}.
\end{eqnarray*}
Thus, the family of vectors $U=\{x_{i}\,|\,i\in I'\}$ (specified for the set of indices $I'\doteq I\setminus\{i^*\}$) is a $B_{a}$-BSV with coefficients $\{\lambda_{i}\leftarrow\lambda_{i}''\,|\,i\in I'\}$. 

Let (\ref{23.17}) not hold, which means, $\mu_{i}\in (0,1),\ \forall\ i\in I_W$.

\medskip {\bf Step 3.}
Find the unique representation of vector $\bar{a}=(da,1)\in \mathbb{R}^{d+1}$ in the form:\\ 
$\bar{a}=\sum_{i\in I_W}\eta_{i}\bar{x}_{i}$. Since $\sum_{i\in I_W} (d\mu_{i}+\eta_{i})=d+1$, there exists $i_{0}\in I_W$ such that $d\mu_{i_{0}}+\eta_{i_{0}}\le 1$. Since $\mu_{i_{0}}>0$, the inequality $\eta_{i_{0}}<1$ holds, and we can define
\begin{equation}\label{23.18}
 r\doteq\frac{\mu_{i_{0}}}{1-\eta_{i_{0}}}\le\frac{1}{d}.
\end{equation}

As shown in \cite{S91}, vector $c-rx_{i_{0}}$ can be presented as
\begin{equation}\label{23.19}
c-rx_{i_{0}}=\sum_{i\in I_W}\mu_{i}'x_{i} - dar
\end{equation}
with coefficients
$\mu_{i}'\doteq \mu_{i}+\mu_{i_{0}}\eta_{i}/(1-\eta_{i_{0}}),\ i\in I_W'\doteq I_W\setminus\{i_0\};\ \mu_{i_{0}}'\doteq 0$. Thus, 
$$\sum_{i\in I_W}\mu_{i}'=\sum_{i\in I_W'}\mu_{i}'=\sum_{i\in I_W'}\mu_{i}+\frac{\mu_{i_{0}}}{(1-\eta_{i_{0}})}\sum_{i\in I_W'}\eta_{i}=\sum_{i\in I_W'}\mu_{i}+\mu_{i_{0}}=\sum_{i\in I_W}\mu_{i}=1,$$
so, putting $\mu_{i}'=1\ (i\in I_1)$, we obtain $\sum_{i\in I}\mu_{i}'=k-(d+1)+1=k-d$.
Using (\ref{23.19}) and (\ref{23.18}), we also get
$$\sum _{i\in I}\mu_{i}'x_{i}=\sum _{i\in I_1}\mu_{i}'x_{i}+\sum_{i\in I_W}\mu_{i}'x_{i}= -c+c-rx_{i_{0}}+dar= dr\left(a-\frac{1}{d}x_{i_{0}}\right)\in B_{a}$$
(since $a-\frac{1}{d}x_{i_{0}}\in a-\frac{1}{d}B\subseteq B_{a}$ and $dr\le 1$). Thus, if $\mu_{i}'\ge 0,\ \forall\ i\in I_W$, 
we put $I'\doteq I\setminus\{i_0\},\ \lambda_{i}\leftarrow\mu_{i}'\ (i\in I'),\ i^*\leftarrow i_0$, and 
the family of vectors $U=\{x_{i}\,|\,i\in I'\}$ becomes a $B_{a}$-BSV with coefficients $\{\lambda_{i}\,|\,i\in I'\}$.

We next suppose that $I_W''\doteq\{i\in I_W\,|\,\mu_{i}'<0\}\ne\varnothing$. 

\medskip {\bf Step 4.}
Define $\varepsilon\doteq\max_{i\in I_W''}\{-\mu_{i}'/(\mu_{i}-\mu_{i}')\}$. Then $\varepsilon \in (0,1)$ (because all $\mu_i>0$). So, we get $\mu_{i}''\doteq (1-\varepsilon)\mu_{i}'+\varepsilon\mu_{i}=\mu_{i}'+\varepsilon(\mu_{i}-\mu_{i}')\ge 0,\ \forall\ i\in I_W,$
\begin{eqnarray*}
 &\exists\ i^*\in I_W'':\ \mu_{i^*}''=0,\\
 &\sum_{i\in I_W}\mu_{i}''=1.
\end{eqnarray*}

Putting $\mu_{i}''=1\ (i\in I_1)$, we have $\sum_{i\in I}\mu_{i}''=k-d$. Then, using (\ref{23.19}), the definition of $\{\mu_i\}$ (see Step 2), and (\ref{23.16a}), we obtain:
\begin{eqnarray*}
 &\sum_{i\in I}\mu_{i}''x_{i}= \sum_{i\in I_1}x_{i}+ \sum_{i\in I_W}\mu_{i}''x_{i}= -c+\sum_{i\in I_W}
 [(1-\varepsilon)\mu_{i}'+\varepsilon\mu_{i}]x_{i}=\\
 &= -c+(1-\varepsilon)(c-rx_{i_{0}}+dar)+\varepsilon c= (1-\varepsilon)dr\left(a-\frac{1}{d}x_{i_{0}}\right)\in B_{a}.
\end{eqnarray*}
Thus, the family of vectors $U\doteq\{x_{i}\,|\,i\in I'\}$ (for $I'\doteq I\setminus\{i^*\}$) is a $B_{a}$-BSV with coefficients $\{\lambda_{i}\leftarrow\mu_{i}''\,|\,i\in I'\}$.\\[1ex]
Put $I\leftarrow I'$.\\
%
\noindent\textbf{END};\ \%\ of Procedure \emph{Next\_BSV}

\bigskip 
\begin{center}
\textbf{Algorithm ${\mathcal A}_1(d,a,N,X;\pi)$}\\
\textbf{(of finding the order $\pi$ of a ``compact summation'' of the family of vectors $X=\{x_i\,|\,i\in[N]\}\subset\mathbb{R}^d,\ \sum_{x_i\in X} x_i=0$)}
\end{center}
%
\%\ \textbf{Notation} (see Theorem \ref{th91}, page \pageref{th91}, and Definition \ref{de3}, page \pageref{de3}):\\
\%\ $B\doteq\mbox{\rm conv}\{X\};\ a\in\mathbb{R}^d;\ B_a\doteq\mbox{\rm conv}\{0,a-B/d\}$\\
\%\ To obtain the desired permutation $\pi$ of indices $k\in[N]$, we find a sequence of\\
\%\ sets $I_k\subseteq[N]\ (k=1,\dots,N)$ such that
\begin{equation}\label{23.20}
I_1\subset I_2\subset\dots\subset I_N=[N];\quad |I_k|=k,\ \forall\ k\in[N];
\end{equation}
\begin{equation}\label{23.21}
\sum_{i\in I_k} x_{i}\in(d-1)B+B_a,\ \forall\ k\in[N].
\end{equation}
\%\ To that end, we first observe that \textbf{if} a family of vectors $X(I)\doteq\{x_i\,|\,i\in I\}\subset\mathbb{R}^d$\\
\%\ (for $|I|\ge d$) is a $B_{a}$-BSV with coefficients $\{\lambda_{i}\,|\,i\in I\}$, \textbf{then} we have:
\begin{equation*}
 \sum_{i\in I} x_{i}=\sum_{i\in I} (1-\lambda_{i}) x_{i}+\sum_{i\in I}\lambda_{i}x_{i}\in\sum_{i\in I}(1-\lambda_{i})B+B_a=(d-1)B+B_a,
\end{equation*}
\%\ which means that $X(I)$ meets (\ref{23.21}). Also observe that $X(I_N)$ is a $B_a$-BSV with\\
\%\ coefficients $\{\lambda_i=(N-(d-1))/N\,|\,i\in I_N\}$, since $\lambda_{i}\in[0,1],\ \sum\lambda_i=N-(d-1)$,\\
\%\ $\sum\lambda_{i}x_{i}=0\in B_a$. Applying these two facts and Procedure \emph{Next\_BSV}, we can\\
\%\ find subsets $I_d,\dots,I_{N-1}$ which are $B_{a}$-BSV (and thus, meet (\ref{23.21})) and can define\\
\%\ the items $\pi_k\in I_k\setminus I_{k-1}\ (k=d+1,\dots,N)$ of permutation $\pi$, respectively. Finally,\\
\%\ defining the subsets $\{I_k\,|\,k<d\}$ satisfying (\ref{23.20}) arbitrarily, we obtain for them:
$$\frac{1}{d-1}\sum_{i\in I_k} x_i=\frac{k}{d-1}\sum_{i\in I_k}\frac 1k x_i\doteq\frac{k}{d-1}x'\in B,$$
\%\ since $x'\doteq\sum_{i\in I_k}\frac 1k x_i\in B$,\ $\frac{k}{d-1}\le 1$,\ and $\mathbf{0}\in B$. Thus,
$$\sum_{i\in I_k} x_i\in (d-1)B\subseteq(d-1)B+B_a$$
\%\ (since $\mathbf{0}\in B_a$), providing (\ref{23.21}) again.\\
\%\ This yields the following simple scheme for Algorithm ${\mathcal A}_1$.\\[1ex]
%
\%\ \textbf{Local parameters:}\\
\rule{1em}{0pt} \textbf{integer:}\ $k,i^*$;\\[1ex]
\noindent\textbf{BEGIN}\\
\rule{1em}{0pt} $I\leftarrow [N];\ \lambda_i\leftarrow(N-(d-1))/N,\ \forall\ i\in I$;\\
\rule{1em}{0pt} \textbf{for} $k\leftarrow N$\ \textbf{step} $-1$ \textbf{down to} $d+1$ \textbf{do}\\
\rule{2em}{0pt} $\{$\emph{Next\_BSV}($i^*;\ I;\ U=\{x_{i}\in X\,|\,i\in I\};\ \Lambda=\{\lambda_{i}\,|\,i\in I\});\ \pi_k\leftarrow i^*\}$;\\
\rule{1em}{0pt} \textbf{for} $k\leftarrow 1,\dots,d$\ \textbf{do}\ 
$\{$Find $i^*\in I;\ \pi_k\leftarrow i^*;\ I\leftarrow I\setminus \{i^*\}\}$\\
\noindent\textbf{END.}

\end{document}

