Material handling in surface mines accounts for around 50% of the operational cost. Optimum truck dispatching plays a critical role in the reduction of this operational cost in truck and shovel surface mines. Researchers in this field have presented several mathematical models to solve the truck dispatching problem optimally. However, a critical survey of the literature has shown that three significant drawbacks exist in the available truck dispatching models. The published models underestimate the importance of the interaction between truck fleet, shovel fleet, and the processing plants. They also disregard goals set by strategic-level plans. Moreover, none of the available models account for the uncertainty associated with the input parameters. In this paper we present a new truck dispatching model that covers all of these drawbacks, using a fuzzy linear programming method. The performance of the developed model was evaluated through implementatin in an active surface mining operation. The results show a significant improvement in production and fleet utilization.