This paper presents a new approach to determine the number of solutions of three-variable Frobenius-related problems and to find their solutions by using order reducing methods. Here, the order of a Frobenius-related problem means the number of variables appearing in the problem. We present two types of order reduction methods that can be applied to the problem of finding all nonnegative solutions of three-variable Frobenius-related problems. The first method is used to reduce the equation of order three from a three-variable Frobenius-related problem to be a system of equations with two fixed variables. The second method reduces the equation of order three into three equations of order two, for which an algorithm is designed with an interesting open problem on solutions left as a conjecture.