We introduce a new scheduling method that reduces the time required to deploy applications by parallelizing and optimizing a schedule on multiple virtual machines (VMs) in cloud computing. Enterprise solutions typically consist of multiple servers and clients with complicated installation dependencies. If users deploy such a solution, they need to install the software sequentially in the proper installation order without violating the dependencies. Auto-deployment tools such as Chef and Puppet take a long time to install multiple applications on multiple VMs in sequential order because these tools cannot find the dependencies automatically and cannot optimize the deployment schedules. Users need to configure and schedule the deployment carefully after they understand the entire architecture of the enterprise solution. Our new automated deployment approach, Parallelized and Optimized Deployment Scheduling (PODS), can detect these application dependencies and optimize the deployment schedules based on two profiles: 1) the network connectivity between a server and clients, and 2) the time required to install applications for sequential deployment. PODS optimization can reduce the duplication timings of multiple VMs' requests to download applications from the same repository server in the parallelized deployment, which reduces network congestion of the repository server. We implemented PODS with Chef and evaluated it on a commercial public cloud environment. PODS reduced the time to deploy four VMs by 36% compared with the standard sequential deployment method.