An optimal task allocation algorithm based on Particle swarm optimization (PSO) is proposed for cooperative timing missions that require involvement of multiple agents. The optimal solution can be utilized in the centralized operation of multi-agent system as well as a benchmark solution of the decentralized task allocation algorithm. However, the optimal solution requires significant computations because this problem is known as NP-hard. Therefore, PSO-based approach can be an alternative because it can be used to obtain a near optimal solution with reduced computational load. In this study, the conventional PSO-based algorithm is modified by adopting graph theory. Numerical simulations are carried out to demonstrate the performance of the proposed algorithm.