In this paper, we study the problem of studies the coordinated lane-changing scheduling problem in a CAV platoon, with the goal of transferring the platoon from an initial state to a target state to minimize a certain cost measurement, while heterogeneous scenarios are considered. Two approaches, i.e., an exact and an approximate approach, are proposed. For the exact approach, we formulate an integer linear programming (ILP) model to identify the global optimal solution. Multiple objective functions are defined to meet the different needs. To relieve the computational issue of the exact approach, we further propose a tree-based heuristic search (THS), an approximate algorithm framework. THS is able to obtain an acceptable solution with negligible computational effort, and has the potential to handle the scheduling problem with more precise modeling or larger platoons.  The findings indicate that ILP is practical for small- or medium-scale cases, which can generate multiple optimal solutions for different objectives; THS can solve large-scale cases in milliseconds on an ordinary personal computer, while the acquired solution is verified to be only slightly worse than the global optimum.