This paper proposes an ant-based software system for solving flexible job-shop problem. In particular, the optimisation problem for a typical Flexible Manufacturing System (FMS), including feeding times, sequences of setup-dependent operations, jobs with different routings among workcenters (including “multi-identical” machines), has been approached by means of an original pheromone trail coding and tailored operators. The algorithm has been tested by using benchmarks found in literature and further benchmarks properly designed for FMSs. Furthermore, the method has been compared with other approaches proposed in literature.