PBS (Painted Body Store) scheduling problem is common in the automotive industry. Company J is a long-established automotive company and its PBS between the painting shop and the general assembly shop is special. In this PBS, company J expects to change the arrangement of car bodies' models and power types by adjusting the way the lanes are used, while minimizing the number of using return lanes and the maximum completion time. In order to optimize the 4 objectives of company J, a mathematical model is developed and a hybrid co-evolutionary genetic algorithm (CHGA) is proposed. Special neighborhood structures are designed to make the search process more directional. Finally, the effectiveness of the algorithm is tested with company J's data. For two data sets, the solution of CHGA improved by 48.66% and 25.44% on the comprehensive objective, respectively.