To improve the efficiency of parts supply in mixed-model assembly lines and reduce energy consumption and cost at the meantime, novel line-integrated supermarkets and mobile robots are introduced, and co-scheduling of mobile robots is considered. Combined with the characteristics of the cooperation between robots, mathematical programming formulations are given with the aim to minimize the total cost consisting of applying robots and related energy consumption. On this basis, a multiple-phases adaptive search algorithm is developed, which constructs the initial solution with a “k-means” clustering heuristics, develops appropriate destroy and repair rules with reference to that of the traditional adaptive neighborhood search, and introduces adaptive selection and perturbation strategy to improve the diversity and effectiveness. Finally, simulation and comparison with other algorithms are carried out to evaluate the proposed algorithm. The results show the superiority of the proposed algorithm for reducing the number and energy consumption of mobile robots and the good performance of the specified rules, adaptive selection and perturbation strategy.