Dynamic voltage scaling (DVS), supported by many DVS-enabled processors, is an efficient technique for energy-efficient embedded systems. Many researchers work on DVS and have presented various DVS algorithms, some with quite good results . However, the previous algorithms either have a large time complexity or obtain results sensitive to the count of the voltage modes. Fine-grained voltage modes lead to optimal results, but coarse-grained voltage modes cause less optimal one. A new algorithm is presented, which is based on ant colony optimization, called ant colony optimization voltage and task scheduling (ACO-VTS) with a low time complexity implemented by parallelizing and its linear time approximation algo rithm. Both of them generate quite good results, saving up to 30% more energy than that of the previous ones under coarse-grained modes, and their results dont depend on the number of modes available.