Model reduction for a class of input-quantized systems in the max-plus algebra

摘要

We present a systematic method for model reduction of a class of input-quantized systems in the max-plus algebra. We consider a generalization of the flow shop with finite intermediate storage. These systems are useful in modeling chemical processes and manufacturing systems, including pharmaceutical manufacturing, construction, propellant manufacturing and assembly lines. The makespan minimization problem we consider is NP-complete. Our method of model reduction reduces the number of states that a system can reach, thus reducing the search space for the optimization problem. This allows us to construct a smaller NP-complete problem to approximate the solution to the larger problem. We show that the error of the approximation is bounded and that as the approximated system approaches the true system, that the error of the approximation goes to zero.