The scenario of multi-vehicles motion planning can be described as follows. Suppose that there exist a group of vehicles starting from their pre-defined initial configurations. They have to reach their own goals in minimum possible time without any collision. In this scenario, we focus on the collision-free motion planning such that the achieving time of the slowest vehicle can be minimized.