Ant Colony Optimization algorithms are intrinsically distributed algorithms where independent agents are in charge of building solutions collaboratively. Stigmergy or indirect communication is the way in which each agent learns from the experience of the whole colony. In this sense, explicit communication models of ACO can be defined directly giving birth to parallel algorithms of high numerical and real time efficiency. We do so in this work, and apply the resulting algorithms to the Minimum Tardy Task Problem (MTTP), a scheduling problem that has been faced with other meta-heuristics in the past. The aim of this article is to report experimental results on the behavior of three types of parallel ACO algorithms on large instances of the mentioned problems with the goal of improving existing solutions significantly.