This paper introduces a new approach for decentralized distributed scheduling in a parallel machine shop environment based on the Ant Colonies Optimization (ACO) algorithm. Distributed scheduling in parallel machine shop environment is a NP hard problem which is important to be studied from both theoretical and practical, point of view. The algorithm developed in this work extends the use of the traveling salesman problem for scheduling in one single machine, to multiple parallel machines problem. A job index-based local search method is used as a daemon action in the general ACO frame work. The result obtained through the proposed methodology is compared with that of a few priority dispatch rules and heuristics found in the literature. The proposed algorithm is found to be superior both in terms of quality and consistency of the solutions obtained. © 2005 IEEE.