Virtualization technology can readily change the placement of an execution environment, such as a virtual machine (VM), in accordance with the current statuses. To effectively manage system resources in the virtualized infrastructure, the elasticity of a virtualized infrastructure has attracted significant attention for determining on which server VM should be deployed. However, there has been little attention to how long it takes to relocate VMs and in what order VMs migrate. It is difficult to determine the migration order of VMs in consideration of the residual resources of the destination server and network topology. In this paper, we propose two methods for scheduling the parallel migration of multiple VMs to reduce the impact on performance degradation due to VM migrations. We first formulate an integer linear programming (ILP) model to determine the VM migration order. To solve the problem in an acceptable time for large infrastructures, we also design a heuristic method based on dependencies between VM migrations and network bandwidth. Simulation results demonstrate that the heuristic-based method obtained the solutions in a few seconds for the settings with small differences with the optimal solutions obtained from the ILP-based method.