Let $a\oplus b=\max(a,b)$ and $a\otimes b=a+b$ for $a,b\in\overline{\mathbb{R}}:=\mathbb{R}\cup\{-\infty\}$. By max-algebra we understand the analogue of linear algebra developed for the pair of operations $(\oplus,\otimes)$, extended to matrices and vectors. The symbol $A^{k}$ stands for the $k$th max-algebraic power of a square matrix $A$. Let us denote by $\varepsilon$ the max-algebraic “zero” vector, all the components of which are $-\infty$. The max-algebraic eigenvalue-eigenvector problem is the following: Given $A\in\overline{\mathbb{R}}^{n\times n}$, find all $\lambda\in\overline{\mathbb{R}}$ and $x\in\overline{\mathbb{R}}^{n}$, $x\neq\varepsilon$, such that $A\otimes x=\lambda\otimes x$. Certain problems of scheduling lead to the following question: Given $A\in\overline{\mathbb{R}}^{n\times n}$, is there a $k$ such that $A^{k}\otimes x$ is a max-algebraic eigenvector of $A$? If the answer is affirmative for every $x\neq\varepsilon$, then $A$ is called robust. First, we give a complete account of the reducible max-algebraic spectral theory, and then we apply it to characterize robust matrices.