We propose an efficient method for finding a Chebyshev-best soluble approximation to an insoluble system of linear equations over max-plus algebra.