Sequence-dependent setup times arise in numerous production environments. This paper addresses an important variant of production schedule with setup time, called “single machine scheduling problem including sequence-dependent setup times”. The objective is to determine the job sequence that minimizes the maximum completion time called “makespan”. For this NP-hard problem, an Ant Colony Optimization heuristic was elaborated, implanted and tested. The experimental study shows the competitiveness of this approach. In reasonable computing time, it outperforms the algorithms in literature in terms of solution quality.