This study addresses the optimization of ore hauling operations in surface mining by modeling the problem as a parallel machine scheduling model with different speeds and release times. A mathematical model (MIPModel) was developed, along with a set of approximate strategies that includes constructive heuristics (FIFO, SPT), a local-search heuristic (INSERT), and two tabu-search metaheuristics: one based on insertions (TSI) and another combining simultaneous insertion and swap mechanisms (TSI-S). The results showed that although the MIPModel achieved solutions closest to the optimum (with an average GAP of 1.97%), its high computational time limits its applicability to small instances. Among the approximate strategies, TSI emerged as the most efficient, achieving an average relative GAP of 9.53% with a significantly lower computational time (92.79 s), making it a viable alternative for real operational scenarios. Statistical tests confirmed significant differences between the MIPModel and the approximate strategies, supporting the effectiveness of TSI as a practical and scalable solution. As future work, enhancements to TSI are proposed to further reduce the GAP without significantly increasing computational time, as well as its adaptation to real-world cases in complex and dynamic mining environments.