Model predictive control (MPC) is a popular controller design technique in the process industry. Recently, MPC has been extended to a class of discrete event systems that can be described by a model that is "linear" in the max-plus algebra. In this context both the perturbations-free case and for the case with noise and/or modeling errors in a bounded or stochastic setting have been considered. In each of these cases an optimization problem has to be solved on-line at each event step in order to determine the MPC input. This paper considers a method to reduce the computational complexity of this optimization problem, based on variability expansion. In particular, it is shown that the computational load is reduced if one decreases the level of "randomness" in the system. © 2007 Elsevier Ltd. All rights reserved.