What is the maximum number of instances allowed for the concerned service? If the load on the server machine is fine, you may increase the maximum number of instances. Increasing the timeout, is another option.
The performance of the ArcGIS Server depends on many other factors as well. Tune and configure services