Many real-life systems in production and transportation logistics are complex, large-scale, and stochastic in nature. As a consequence, simheuristic approaches – which integrate simulation inside a metaheuristic framework – are becoming increasingly popular in the optimization and simulation communities. In a simheuristic algorithm, time-consuming simulation runs are required in order to: (i) obtain accurate results on the stochastic performance of solutions generated by the metaheuristic; and (ii) provide feedback that can be useful to better guide the metaheuristic search. If the underlying system is complex, discrete-event simulation might be needed, and then the simulation component could easily overrun the computational time of the metaheuristic component. Thus, for each new solution generated by the metaheuristic, several related questions arise: (i) should the simulation component be applied to that solution? – i.e., is that solution ‘promising’ enough to invest additional computational time on retrieving information about its performance in a stochastic environment?; and (ii) if so, how many simulation runs are needed in order to obtain useful information (i.e., statistics with a minimum level of accuracy)? This paper discusses these issues and proposes several concepts that allow to improve the efficiency (in terms of computational time) of simheuristic algorithms. A case study, based on a typical manufacturing system, is introduced. In order to illustrate and test different speeding-up techniques, the system is optimized by using a simheuristic that integrates a genetic algorithm with discrete-event simulation.